Wayfair Whiteboard Coding Practice 1
AnneOnymous
542
JavaEasyInterview

🚀 This is a common Wayfair coding interview question that requires handling large integer addition using strings.
💡 The problem requires handling commas, carry propagation, and edge cases like invalid characters.

LeetCode Post: Add Two Large String Numbers

🔹 Original Problem Statement (LeetCode #415 - Add Strings)

📌 Problem Description

Given two non-negative integers, num1 and num2 represented as strings, return the sum of num1 and num2 as a string.

You must not use any built-in library for handling large integers (such as BigInteger) and must not convert the inputs to integers directly.

🔹 Example 1

Input: num1 = "11", num2 = "123"
Output: "134"

🔹 Example 2

Input: num1 = "456", num2 = "77"
Output: "533"

🔹 Example 3

Input: num1 = "0", num2 = "0"
Output: "0"

🔹 Constraints

  • 1 <= num1.length, num2.length <= 10^4
  • num1 and num2 contain only digits (0-9).
  • num1 and num2 do not contain any leading zeros except for "0" itself.

🔹 Follow-Up Questions

These additional requirements extend the problem to real-world use cases.

1️⃣ Handle input with commas

🔹 Additional Requirement

  • Modify the function so that the input can contain commas as thousands separators.
  • Example: 
    Input: num1 = "1,234", num2 = "2,345"
Output: "3,579"
  • Solution: Ignore commas when processing digits.

2️⃣ Format the output with commas

🔹 Additional Requirement

  • Modify the function so that the output includes commas in the correct format.
  • Example: 
    Input: num1 = "1000", num2 = "2000"
Output: "3,000"
  • Solution: Insert commas after every three digits.

3️⃣ Use this method to compute Fibonacci numbers

🔹 Additional Requirement

  • Use addStrings() to compute the Fibonacci sequence for large numbers.
  • Example: 
    Input: fibonacci(10)
Output: "55"

Input: fibonacci(20)
Output: "6,765"
  • Solution: Implement Fibonacci using addStrings() to avoid integer overflow.

4️⃣ Handle special characters by throwing exceptions

🔹 Additional Requirement

  • Modify the function to throw an exception if the input contains invalid characters.
  • Example: 
    Input: num1 = "1,23@", num2 = "456"
Output: Exception: "Invalid character in input: @"
  • Solution: Detect non-digit characters and throw an IllegalArgumentException.

🚀 Optimized Solution (Handles All Follow-Ups)


/*
✅ Problem: Add Two Large String Numbers
🚀 This is a standard Wayfair coding question!

🔹 What’s Required?
Implement string-based addition (like adding two big integers stored as strings).
Handle carry, different lengths, and edge cases.

🔹 Follow-Up Questions:
1️⃣ Handle input with commas (e.g., "1,234" + "2,345" → "3,579")
2️⃣ Output should also have commas (e.g., "3579" → "3,579")
3️⃣ Use this string addition method to compute Fibonacci(n)
4️⃣ Handle special characters like @,&,$ by throwing exceptions
*/

import java.util.*;

class Solution {
    public static String addStrings(String num1, String num2) {
        int i = num1.length() - 1, j = num2.length() - 1, carry = 0, commacount = 0;
        StringBuilder res = new StringBuilder();

        while (i >= 0 || j >= 0 || carry > 0) {  
            int n1 = 0, n2 = 0;

            // ✅ Ignore commas while processing digits
            while (i >= 0 && num1.charAt(i) == ',') i--;
            while (j >= 0 && num2.charAt(j) == ',') j--;

            if (i >= 0) { 
                char c1 = num1.charAt(i);  
                if (!Character.isDigit(c1)) throw new IllegalArgumentException("Invalid character in input: " + c1);
                n1 = c1 - '0';
                i--;
            }

            if (j >= 0) { 
                char c2 = num2.charAt(j);
                if (!Character.isDigit(c2)) throw new IllegalArgumentException("Invalid character in input: " + c2);
                n2 = c2 - '0';
                j--;
            }

            int sum = n1 + n2 + carry;
            carry = sum / 10;
            res.append(sum % 10);
            commacount++;

            if (commacount % 3 == 0 && (i >= 0 || j >= 0 || carry > 0)) {  
                res.append(',');
            }
        }

        return res.reverse().toString();
    }

    public static String fibonacci(int n) {  
        if (n == 0) return "0";
        if (n == 1) return "1";

        String a = "0", b = "1";
        for (int i = 2; i <= n; i++) {
            String temp = addStrings(a, b);
            a = b;
            b = temp;
        }
        return b;
    }

    public static void main(String[] args) {
        try {
            System.out.println(addStrings("1,234", "1,111"));  // ✅ Expected: "2,345"
            System.out.println(addStrings("1,234", "111"));    // ✅ Expected: "1,345"
            System.out.println(addStrings("9,999", "1"));      // ✅ Expected: "10,000"
            System.out.println(addStrings("123", "456"));      // ✅ Expected: "579"
            System.out.println(addStrings("99", "1"));         // ✅ Expected: "100"

            // ❌ Invalid input cases (should throw exceptions)
            System.out.println(addStrings("12@3", "456"));     // ❌ Should throw an exception
            System.out.println(addStrings("1,23$", "789"));    // ❌ Should throw an exception

        } catch (IllegalArgumentException e) {
            System.out.println("Exception: " + e.getMessage());
        }

        System.out.println("\nFibonacci Tests:");
        System.out.println(fibonacci(10));  // ✅ Expected: "55"
        System.out.println(fibonacci(20));  // ✅ Expected: "6,765"
        System.out.println(fibonacci(50));  // ✅ Large Fibonacci number
    }
}

🔹 Complexity Analysis (Concise & Clear)

1️⃣ Addition Function (addStrings)

  • Time Complexity: ( O(\max(N, M)) )
    • Each digit is processed once, including carry handling and comma formatting.
  • Space Complexity: ( O(N + M) )
    • Uses a StringBuilder to store the result, and reversing takes linear space.

2️⃣ Fibonacci Function (fibonacci(n))

  • Time Complexity: ( O(n . d) ), where d is the number of digits in F(n).

    • F(n) has approximately ( O(n) ) digits (since Fibonacci grows exponentially).
    • Each Fibonacci addition takes ( O(d) ), leading to ( O(n \cdot d) ).

  • Space Complexity: ( O(d) )

    • Only two Fibonacci numbers are stored at a time.

✅ Final Complexity Summary:

FunctionTime ComplexitySpace Complexity
addStrings(num1, num2)( O(\max(N, M)) )( O(N + M) )
fibonacci(n)( O(n . d) )( O(d) )
Comments (0)