Simplicity: An overlooked interviewing skill

OK, you've studied data structures and algorithms. You've practiced problem solving on a computer and on a whiteboard. You've done mock interviews with a friend, or maybe through platforms like interviewing.io or Pramp.

What's left?

Simplicity

Every year, I interview dozens of candidates for software engineering positions. Most of the interviews I end up doing are for software engineer internships or new grad positions, but I also end up in interviews for front and back end positions at all levels up to Senior Software Engineer. Despite the varying roles and levels, a good portion of candidates come unprepared in the same exact areas.

You've heard most of the common ones before:

• Lack of knowledge in areas mentioned in the job description

• (Worse) lack of knowledge in areas claimed on the candidate's resume

• Arrogance

• Poor communication

These things all come up all the time when you read about interviewing.

But there's one skill that almost always gets overlooked: simplicity.

Simplicity is always an attribute of a good candidate's solution. If you think about this in the crudest terms, it makes complete sense. One loop is better than nested loops. A solution with well-named, sensible helper methods is better than a God method. Something that I, your interviewer, can understand easily is something you, the interviewee, should be striving for, and which you can better explain.

I frequently see candidates struggle with overcomplicated solutions. Often, I chime in with simplifications. "What if you ignore this part of the problem for now?" I say. "Why don't you solve the majority of cases first, before focusing on edge cases?"

But, quite often, candidates are stuck on solutions which obscure and hide what a simpler approach might offer.

Let me run through a couple of concrete examples to help this make sense.

Example 1: FizzBuzz

Let's take the famous FizzBuzz question as an example.

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

I don't ask this question, but if I did, I would literally expect a candidate to translate it more or less phrase-by-phrase into code. The point of a question like this is just to check simple coding fundamentals. So, for example:

Write a program that prints numbers from 1 to 100

for(int i = 1; i <= 100; i++) {
    System.out.println(i);
}

But for multiples of three print “Fizz” instead of the number

for(int i = 1; i <= 100; i++) {
    if(i % 3 == 0) {
        System.out.print("Fizz");
    } else {
        System.out.println(i);
    }
}

and for the multiples of five print “Buzz”

for(int i = 1; i <= 100; i++) {
    if(i % 3 == 0) {
        System.out.println("Fizz");
    } else if(i % 5 == 0) {
        System.out.println("Buzz");
    } else {
        System.out.println(i);
    }
}

For numbers which are multiples of both three and five print “FizzBuzz”

This is the only (not very) tricky part to fit onto the solution we have so far. We know that only one branch of an if/else will execute. Yet this asks us to consider a case that has already come up twice in the solution above. We decide to make the check for "multiple of both three and five" first:

for(int i = 1; i <= 100; i++) {
    if(i % 3 == 0 && i % 5 == 0) {
        System.out.println("FizzBuzz");
    } else if(i % 3 == 0) {
        System.out.println("Fizz");
    } else if(i % 5 == 0) {
        System.out.println("Buzz");
    } else {
        System.out.println(i);
    }
}

Another approach is to move away from a single if/else, to allow Fizz and Buzz to be checked and printed separately, with the result that the output becomes "FizzBuzz" for those cases where the output is divisible by 3 and 5 at the same time.

for(int i = 1; i <= 100; i++) {
    if(i % 3 == 0) {
        System.out.print("Fizz");
    } 

    if(i % 5 == 0) {
        System.out.print("Buzz");
    }

    if(i % 3 != 0 && i % 5 != 0) {
        System.out.print(i);
    }
    System.out.println();
}

I would argue that this solution is actually more complex. The interplay between these conditionals is something we have to think about now, because more than one of them might execute in a given iteration of the loop. And you need to print the line break at the end separately.

So the first solution, which is just the natural result of translating each phrase into code, is actually just fine like it is. No need to overthink it.

The only thing I can come up with that's better is:

for(int i = 1; i <= 100; i++) {
    if(isMultipleOf(i, 3) && isMultipleOf(i, 5)) {
        System.out.println("FizzBuzz");
    } else if(isMultipleOf(i, 3)) {
        System.out.println("Fizz");
    } else if(isMultipleOf(i, 5)) {
        System.out.println("Buzz");
    } else {
        System.out.println(i);
    }
}

With the isMultipleOf method:

private boolean isMultipleOf(int x, int y) {
    return x % y == 0;
}

Most people think in English or whatever language they speak rather than in modulus operators, so writing a quick isMultipleOf method makes this more readable.

Yet, when the popularity of FizzBuzz hit its peak, simplicity and readability weren't actually the result of the conversation. Instead, it led to very annoying things like this obfuscated FizzBuzz CodeGolf and the funny, but still annoying enterprise Java FizzBuzz.

Reginald Braithwaite actually became so annoyed by the overanalysis of FizzBuzz that he authored the classic post, Don't Overthink FizzBuzz, which says, in part:

If you are conducting an interview and you receive a cryptic answer, or an impossibly concise one-liner, or perhaps something like the above that is redolent of Higher Order Functions, do you embrace the candidate as a genius? Or perhaps avoid them as someone who cannot write clear, maintainable code?

Wise words.

Example #2: TwoSum

TwoSum is a famous problem that I first heard about when my brother-in-law was asked the question for an interview at Tableau at least six years ago.

Here is one phrasing of the problem:

You are given an array of n integers and a number k. Determine whether there is a pair of elements in the array that sums to exactly k. For example, given the array [1, 3, 7] and k = 8, the answer is “yes,” but given k = 6 the answer is “no.”

It's very simple to write a "brute force" solution as follows:

• Iterate the array one-by-one. Store the current number in a variable.

• Iterate the array again, looking for a number that, when summed with the "current number" of the outer iteration, results in the expected sum. If it does, return true.

• Return false

This solution looks like this in Java:

boolean twoSum(int[] input, int sum) {
    for(int i = 0; i < input.length; i++) {
        int current = input[i];
        for(int j = 0; j < input.length; j++) {
            if(i == j) {
                continue;
            }
            if(current + input[j] == sum) {
                return true;
            }
        }
    }
    return false;
}

Just because that's the first thing that comes to mind doesn't make it a bad solution. Sure, it could be more efficient. But I promise you that if I interview you, I will not penalize you for coming up with this and implementing it. Instead, I'll simply ask you if you can now think of a way to make it more efficient.

In fact, I expect this exchange.

So, how can it be improved? Well, simplify it. We see that it's "brute force." Can you pull a "classic" computer science move on this and trade (a little bit of) space complexity for lower time complexity? Yes, you can. If you iterate the array once up front and construct another array storing the location of each number, you can have an O(1) lookup for any given number. I might even tell you that you can count on the input range being bound to 1 <= i <= 100.

Using the example from the provided problem statement, {1, 3, 7}, this lookup array will look like this once it's constructed:

index	0	1	2	3	4	5	6	7	...
value	-1	0	-1	1	-1	-1	-1	2	...

The "value" in the lookup array is the "index" of the input array where that number occurs. The value 1 is in position 0 of the input array. So lookup[1] is 0. The value 3 is in position 2. lookup[3] is 2. And so on.

Code to construct this lookup array looks like this:

int[] lookup = new int[101];
Arrays.fill(lookup, -1);
for(int i = 0; i < input.length; i++) {
    lookup[input[i]] = i;
}

The first two lines create an array and initialize it with values of -1. Since I told you that the range of values is limited to 1 <= i <= 100, we create an array of size 101 so that it has buckets for 1 to 100. (We'll just ignore the 0th bucket.) We need to fill the lookup with a -1 value because by default it will have 0, and that will make us think that any given number is in the 0th bucket of the input array, when it's not. So we use -1 to indicate any number that does not occur in the input array. The given example has 1, 3, and 7 but not 2, 4, 5, or 6. So 2, 4, 5, 6 buckets of the lookup array will all have the value -1 in their bucket of the lookup array. Meanwhile, "1" will have the value 0, "3" will have the value 1, and "7" will have the value 2. Just like the table above.

Now, you can use this "lookup table" to find out if there're two numbers in the input that add up to the given sum. The value stored in any bucket of the lookup array is the index where that number appears. In other words, lookup[3] = 1 because 3 appears in the input array in bucket 1.

Knowing this, you can perform the following steps:

• iterate the input array

• for each value stored in input (input[i]):

  • determine the number that, when added to it, results in the sum
  • lookup that number and see if it occurs in the array somewhere
  • make sure the place it occurs in the array isn't the current number we're looking at, e.g. if we want to check for the sum 6, and the current number is 3, then the complementing value is 3, and we might lookup and find a 3, but its the 3 we're already evaluating.

The resulting code looks like this:

boolean twoSum(int[] input, int sum) {
    // code we already wrote above
    int[] lookup = new int[101];
    Arrays.fill(lookup, -1);
    for(int i = 0; i < input.length; i++) {
        int value = input[i];
        lookup[value] = i;
    }

    // actually finding the sum, if it exists
    for(int i = 0; i < input.length; i++) {
        int toFind = sum - input[i];
        if(toFind > 0 && lookup[toFind] != -1 && lookup[toFind] != i) {
            return true;
        }
    }
    return false;
}

In an interview, we might iterate further on this and figure out a way to reduce it to one pass rather than two in the worst case, but it is already an O(n) solution now!

Simplification FTW

So simplify! If you can think of a simple, but brute force solution, tell me about it and implement it. At least then I can see that you can find a solution, code it, and communicate what it does.

Next, improve it. But still strive for simplicity. Break problems down. Solve the pieces. Then put them back together. This is a much better approach than trying the first thing that comes to mind and painting yourself into a corner.

And a word about that: when your interviewer interrupts your train of thought and redirects you, it's because they want you to succeed, and they are trying to help you from using up time on a dead end path. So listen attentively to your interviewer, and follow their lead. They want you to succeed and are just trying to get you there.

Good luck!