Most technical programming interviews have at least one or more programming whiteboard exercise. These generally include questions like
1. Write an algorithm to reverse a linked list.
2. Write a function to sort a binary tree.
3. Write an algorithm to remove duplicates and sort an arbitrary long input string comprised of single digit numbers.
Almost all of such questions require you to explain your thinking on whiteboard and then design and explain your algorithm or function on the whiteboard in real time. So how do you answer algorithmic questions and make sure that your thinking and direction covers various different aspects that an interviewer is looking for.
Here is one such list that you can keep at the back of your mind when attempting to solve such questions. Some of them may not be valid for some questions, but you should try to model your answer around these tenets.
Understand the question: Make sure you repeat the question. The goal is to understand exactly what the interviewer is looking for in your answer.
Asks clarifying questions to understand what the interviewer is looking for: This is an extension of the first point. You need to ask as many clarification questions as necessary to make sure you are solving the right problem. Most questions will have ambiguity built into them and it is your job to make sure you get them clarified.
Paraphrase the problem: Once you have clearly understood the question, paraphrase it. This helps make sure to the interviewer that you really get the question and the subtleties associated with it.
Call out assumptions: Before and as you are designing the algorithm, make sure to clearly spell out any assumptions that you are making. For example, array index starts at 0, the input is assumed to be made only of numbers, etc. Unsaid assumptions have a bad habit of coming back and biting you later in the exercise.
Articulate at least one or two acceptable input and output: If possible, it is always good to show one or two possible input cases and the desired output from your solution. This helps both you and interviewer to make sure that you are on track to understanding the question.
Define broad solution: Once you have reached this stage, define a broad outline of the solution. No code, just the big ticket steps. For example, Sort the input, find the most common elements, use hashmaps, clean output to remove duplicates, etc.
Define possible other solutions (using hashtags, linked lists, trees, etc): Once you have a broad solution, make sure that you discuss or highlight some alternative approaches. This shows that you can think from a higher perspective and evaluate alternate approaches.
Draw a “manual run” on the whiteboard for input/output: To make sure that your high level solution really works, manually run your input through that to make sure you get the desired output.
Define the high level design: Now is the time to start hashing out your high level design components. Basic functions, data structures, core logic. A lot of your time would be spent here understanding and building your design.
Define the basic algorithm: Here you would be defining the core logic and algorithm for your problem. Make sure you keep talking about your approach.
Discuss time taken by algorithm (1, log(n), etc): Once you have the detailed design in place, discuss the performance characteristics of your solution. Think about minor tweaks or improvements you can do here to improve the performance.
Talk about error handling: This is very important. You should at least talk about different error conditions and how your algorithm would handle it. You can keep the whiteboard clean by not writing every possible case, but make sure you talk about them.
Handle edge cases: Any good algorithm handles edge cases without going through the entire process very fast. Make sure you spend a few minutes thinking and articulating about them.
Testing: Once you think you have the final design ready, force yourself to turn-off your brain and run a couple of inputs through the algorithm. Follow exact steps there and do not use your brain. Basically, be the computer and test. Test. Test again. You will surely uncover a few things here that you might have missed (e.g. <= instead of ==).
Regularly check in to see if the interviewer is on the same page as you: This is a very important step and needs to be done through out the interview. You need to keep the interviewer engaged and focused. Speak clearly, slowly, think aloud and make sure interviewer is following you.
Hopefully this will help you answer algorithmic programming interview questions in a much better cleaner way using a templated approach.
In the next post we will look at such a templated approach to solving design interview questions.