Leetcode Grind: How to Ace the Interview [+Interview Simulation]

➡️ Interviewer: Hi, could you please walk me through your solution to LeetCode problem 67 - Add Binary in Java?

👨‍🦰 Sideon: Sure, the problem is to add two binary strings and return the sum as a binary string.

➡️ Interviewer: Alright. What is your approach to solving this problem?

👨‍🦰 Sideon: I convert the two binary strings to decimal numbers, add them, and then convert the result back to a binary string.

➡️ Interviewer: I see. How do you convert a binary string to a decimal number?

👨‍🦰 Sideon: I iterate through the binary string from right to left and multiply each digit by 2 raised to the power of its position. Then, I add up all the resulting products.

➡️ Interviewer: Okay, and how do you convert a decimal number to a binary string?

👨‍🦰 Sideon: I repeatedly divide the decimal number by 2 and append the remainder to a string. Then, I reverse the string to get the binary representation.

➡️ Interviewer: That sounds reasonable. Have you considered any edge cases?

👨‍🦰 Sideon: Yes, I have considered a few edge cases. One is when one of the input strings is empty. In that case, I simply return the other input string. Another edge case is when the sum of the two decimal numbers is 0. In that case, I return "0".

➡️ Interviewer: Great. Is there any way to optimize your solution?

👨‍🦰 Sideon: Yes, one optimization we can do is to convert the input strings to char arrays and iterate through them simultaneously. This way, we can avoid converting the binary strings to decimal numbers and back.

➡️ Interviewer: That's a good optimization. Can you show me the optimized code?

public String addBinary(String a, String b) {
    char[] aArray = a.toCharArray();
    char[] bArray = b.toCharArray();
    int carry = 0;
    StringBuilder result = new StringBuilder();
    int i = aArray.length - 1, j = bArray.length - 1;

    while (i >= 0 || j >= 0 || carry > 0) {
        int sum = carry;

        if (i >= 0) {
            sum += aArray[i--] - '0';
        }

        if (j >= 0) {
            sum += bArray[j--] - '0';
        }

        result.append(sum % 2);
        carry = sum / 2;
    }

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

➡️ Interviewer: Does the above code follow all the coding principles and standards, is the implementation correct, with all test and edge cases covered?

👨‍🦰Sideon: (As a conclusion, summarize and think aloud for the final take) In terms of edge cases, the code handles the case where one of the input strings is empty by returning the other input string, and the case where the sum of the two decimal numbers is 0 by returning "0". However, it does not handle the case where the input strings are not valid binary strings (i.e. they contain characters other than '0' and '1'). If the input strings are not valid, the code would throw a NumberFormatException when trying to subtract '0' from a non-digit character.

To handle this edge case, we can add an initial check to ensure that both input strings are valid binary strings using a regular expression pattern. We can also add a check to ensure that the resulting binary string does not have leading zeros. This can be accomplished by checking if the last character in the StringBuilder result is '0' and removing it if it is.

➡️ Interviewer: Overall, your solution is well-optimized and correctly handles most edge cases. However, I suggest you add checks to handle non-binary input strings and remove leading zeros from the resulting binary string. Great job, and thank you for sharing your solution!

Keep an eye out for similar Leetcode Interview Simulations on various problems, Though we kicked off with an easy one today, always check the comments.

67. Add Binary