My favorite programming problem for a coding interview
During my time at Google, I conducted more than two hundred interviews. And the main thing I learned from this work is that conducting quality interviews is very difficult. It’s all about the signals we send and receive. Both the interviewer and the candidate themselves have less than an hour to give their best. Sometimes, for various reasons, we receive false or inaccurate signals from each other. Such is human nature.
Over the years, I’ve developed a coding question that I really like. This is an terribly simple and at the same time tricky question. The solution takes no more than 30 lines of code, but it gives me all the necessary signals to make the right assessment of the candidate. Also, my question is highly scalable and suitable for both interns and experienced engineers. Here I am not trying to prove that my question is better than any other. I just want to explain how it helps me as an interviewer and what I look for in a programming interview.
There will be things in this article that you may disagree with. This is fine. This is just my opinion, and since I’m retired, I no longer pose a threat to interviewers or Google engineers when making hiring decisions! 😉
A few words about me
When I was an aspiring engineer, I regularly read the site joelonsoftware.com. One of the articles that left a lasting impression on me was guide on conducting interviews. The most important decision you can make in less than an hour is whether to hire or not to hire based on whether the person is smart and can get the job done. Does the interview allow you to verify both?
Personally, I came to coding from electronics. Signed up for courses on data structures and even wrote a maze solving program for our graduation project Micromouse. I had no formal training in computers, and although the program worked perfectly (getting electrical equipment to work was an order of magnitude more difficult!), I could not name the algorithm I used. Therefore, I prefer to stay away from questions that test whether a candidate has taken specific CS courses. This is not my strongest point.
I usually interview general software engineers, front-end engineers, or conduct code quality assessments for executives and managers.
When conducting a coding interview, I aim to determine how well a person fits the needs of my engineering team in solving the day-to-day tasks of testing, programming, and debugging. How a candidate approaches and solves a problem is more important than their degree.
Attention, question!
We have an array sorted in ascending order:
a = [ 3, 4, 6, 9, 10, 12, 14, 15, 17, 19, 21 ];Define a function f(a, x) that would return x, the nearest smallest number, or -1 on error.
That is:
f(a, 12) = 12
f(a, 13) = 12First, let me note that this question is very easy to understand. Of course, provided that you know something about programming. You don’t need to be a genius, a doctor of mathematical sciences, to comprehend it – so the question is quite fair to all candidates. In addition, it does not require further explanation – which would take up precious minutes of our interview.
The array appearing in the problem is deliberately composed in such a way as not to include 0 and negative numbers – this would add absolutely nothing to the solution of the problem. There are 11 elements in the array, which gives us an index space from 0 to 10. 10 is easily divisible by 2, so the midpoint can be determined without problems – this is the number 12. It is exactly in the middle of the list – this is our first test case. And the next example, the number 13, requires searching in the other half of the elements. All these little subtleties will guide the interview in the right direction.
First of all, I invite candidates to come up with their own test cases, like the ones I outlined above. At first glance, this may seem like an inappropriate question for a programming interview, but it actually reveals how familiar the candidate is with TDD and boundary conditions. As a rule, after some prompting, the candidate comes up with the following list:
f(a, 12) = 12 // Найдено заданное число
f(a, 13) = 12 // Найдено меньшее число
f(a, 2) = -1 // Число слишком мало и выходит за границы массива
f(a, 22) = 21 // Число слишком велико и выходит за границы массива
f(a, 3) = 3 // Левая граница массива
f(a, 21) = 21 // Правая граница массива
f([], x) = -1 // Массив пуст
f(null, x) = -1 // Неверные аргументыBelieve it or not, most developers are unable to complete this list. Someone forgets about array boundaries. Some people ignore values of x that are too large or small. Some candidates do not think to check the entered data for accuracy. Some unique people even do brute force: f(a, x), where x = Int.MIN before Int.MAX.
There are still some people who don’t understand what I’m trying to get out of them with this question.
But in fact, from every reaction, every “signal” I get a lot of additional information about the candidate.
We then move on to discuss the algorithm. Yes, you can write something like a loop for For O(n). If I’m interviewing a young and green intern, this is a perfectly acceptable answer. At one time I was interviewing college students, and I can tell you: a well-written cycle and the ability to debug it for all test cases is a guaranteed offer.
As for more experienced candidates, I would like to see them implement binary search: O(log n). First we discuss the algorithm, I make sure that the person is thinking in the right direction, and only then I ask him to write the code. If everything goes according to plan, you can run the finished version and debug all eight test cases. At this moment I step aside and observe.
welcome back
So how long did it take you to write code? Did the process take half an hour? Or even a whole hour? Did the algorithm work as it should the first time? Does midpoint calculation work correctly for elements from both halves? Did you resort to an iterative solution? Have you taken into account the possibility of getting into an endless loop? Or did you choose a recursive approach? Have you created an auxiliary method? How do you find the smaller value? Does your code pass all 8 tests, or did you have to add special if/else for a number of cases? Do not worry. The first time I solved this problem, I suffered no less than you.
Omelette test
Many years ago I read the book “The Making of a Chef.” It talked about three ways to transform a person into a master chef. One of them was to pass the exam to become a certified chef. Another implied that you could, like Michael Symon, be an accomplished chef and then build a restaurant empire backed by a stack of TV shows. And then there is the Thomas Keller path. He started out as a dishwasher, then trained with French master chefs, eventually becoming one of the best chefs in the world.
I’ve always believed that there are similarities between chefs and programmers. An experienced chef has characteristic traits. The way they cook, fry, steam, serve. The way they hold a knife and cut vegetables. They have very few unnecessary movements, everything is smooth, and the result, naturally, is an excellent dish.
In the film The Hundred-Foot Journey (translator’s note: known in Russia as “Spices and Passions”), the main character, Hassan Kadam, was asked to cook an omelette. With one bite from Madame Mallory (played by Helen Mirren), he knows whether he should work in her kitchen.
I think this is true for programmers too. My interview question is the same “omelet” test. I look for signs of an experienced programmer in the way a person approaches solving a popular, well-known problem.
Solution
In fact, there are many possible solutions to this problem. Here, for example, is the most primitive iterative approach:
function f(a, x) {
if (a == null || a.length == 0) return -1;
var answer = -1;
var low = 0;
var high = a.length — 1;
while(low <= high) {
var mid = Math.floor((low + high) / 2);
if (a[mid] == x) {
return x;
} else if (a[mid] < x) {
answer = a[mid];
low = mid + 1;
} else {
high = mid — 1;
}
}
return answer;
}As for binary search, it looks something like this: while(low <= high)divide into two parts until we find the required number.
The less than or equal to comparison operator is important because eventually the array of numbers will collapse to size 1 and the contents of the loop will need to be executed. Incrementing/decrementing the midpoint is also important, because otherwise there is a risk of ending up in an infinite loop.
Finding the next smallest number is a little more difficult. A smart solution would be to combine linear search with binary search, initialize answer as -1, then update the value of the variable whenever a[mid] will be less than x. If x cannot be found, the answer will always be the smallest value found.
Even more advanced practitioners can add additional checks to check for x boundary values.
// Например, вот так:
if (a == null || a.length == 0) return -1; // f(null, x), f([], x)
if (x < a[0]) return -1; // f(a, 2)
if (x == a[0]) return a[0]; // f(a, 3)
if (x >= a[a.length — 1]) return a[a.length — 1]; // f(a, 21), f(a, 22)Why use binary search
Binary search is one of the most difficult “simple” programming problems. The algorithm looks trivial, but implementing it is absolute hell. John Bentley, a former CMU professor, wrote in his book Programming Pearls that only 10% of professional programmers are able to implement it correctly, including graduate students.
“I was amazed: given enough time, only about ten percent of professional programmers were able to get this little program right.”
In his book, he wrote that it took specialists 16 years to write an algorithm without errors!
“…in section 6.2.1 of Sorting and Searching, Knuth notes that although the first implementation of binary search was published in 1946, the first published bug-free version did not appear until 1962.”
John Bentley, Gems of Programming (first edition)
But wait a minute, there is still one small mistake in the above solution. Can you find her?
In 2006, Joshua Bloch, Google’s chief Java architect, author of Effective Java, and a former graduate student of Bentley’s, revealed that Java contained a hidden bug for nine years! Calculating the midpoint led to going beyond the array boundaries when working on large amounts of data!
var mid = Math.floor(low + high) / 2); // плохо
var mid = low + Math.floor((high — low) / 2); // хорошоBasic binary search is surprisingly difficult to implement. Adding the twist of the next smallest number only adds to the challenge. In the case of searching for the number 13, when you are debugging two or three levels deep in binary search, it is not so easy to keep in mind the low, high, middle values and the stack.
A working solution should be approximately 30-40 lines of code. This is small enough for an hour-long interview, and you can easily proofread the code and make notes in the margins. This question covers the entire life cycle of a programmer’s work – from test cases to writing code and debugging it. Overall, the interview is “simple” enough for the hiring committee to understand the candidate’s caliber and evaluate my recommendation.
To hire or not to hire?
There is no perfect way to evaluate a candidate. I was probably too harsh or too lenient on several candidates in the outcome of my issue. I’m also a human being.
As with the chef analogy above, I look for signs in a person of essential skills, akin to a chef’s ability to chop vegetables or stand at the stove. At a minimum, the compiler should not complain about primitive errors.
Here is a list of the simplest signals that I expect from a candidate:
Adequate names of variables and functions.
Find_X_Or_Next_Smallest_Impl_Factory_Builder_Singleton(...)definitely doesn’t work.The parentheses surrounding functions, loops, and conditions are closed, and all the necessary code is placed inside.
The candidate is aware that array indices start at 0 and end at the number of array elements – 1.
Variables are initialized with the correct initial values and are in the correct scopes.
The candidate uses == in conditions rather than just =. Parentheses open and close where needed.
The code is correctly indented and/or semicolons
The code is readable and clear. How would you write: if (a[mid] < x) or if(x>a[mid])? One of the options is much easier to read.
And a couple more signals of a different kind:
Completeness in defining all test cases.
General understanding of the process: from problem definition to testing and implementation.
Ability to use a whiteboard to visualize binary search, debug, and explain how your code works.
General communication skills.
The ability to not dwell on mistakes and move forward quickly.
The ability to write simple code without spaghetti from a thousand if/else.
My expectations for each candidate level
For a strong trainee or L3 engineer, I would expect him to be able to master binary search in an hour with a little help, especially with test cases and debugging, while making confident strides along the way with minimal syntax errors.
As for mid-level L4 engineers, they should be able to define most test cases, implement a working binary search solution with minor errors, and debug it with minimal assistance. Strong candidates will finish with plenty of time for the second question.
As for the L5 Senior Engineer, he should be able to carry the interview through to the end and finish with enough time remaining for the systems design question. Most likely, such candidates will write the prerequisites and be aware of the midpoint overflow bug. There may be minor bugs/errors, but progress should be fast.
Essentially, I always evaluate whether I would hire this person to work on my team or not, and which team member is he/she most like? Does their code and behavior indicate that they are smart and can get things done? The best thing I can read or write in a job application package is that the interview was like a discussion with a fellow engineer at Google.
Afterword
Thank you for reaching this section of the article. I hope you found it entertaining and informative. My goal isn’t to brag about my amazing interview question, because frankly, it’s dead simple, but to emphasize that you don’t have to be super-complicated to make a decision. Instead of focusing on whether candidates know what you know, look at not only what code they write, but also how they write it. The style and pace in which they work and debate are signals, important signs of mastery. Does your coding interview question include test cases? And if there were, would the interviews become more informative? Can you get the same signals with simpler questions? The hiring committee would greatly appreciate research in this area!
As far as I know, one of my old teammates still uses this question. He loves it for its simplicity and breadth of coverage, as well as for the accuracy of its “trigger” in making the final recommendation.
Acknowledgments
I learned about this issue myself from a colleague at Google. Unfortunately, over the years I no longer remember his name. In any case – thank you!
