A Script for the Algorithm | Data Structure Coding Interview
Disclaimer: This post deals with the traditional “coding” interview where the focus is on solving one or more coding problems. I have interviewed in a double-digit number of companies from India, the US, and Europe and this post is a culmination of those experiences. This is the stable, generic approach I use in my interviews.
Interviews have certain aspects of randomness due to factors like the company you’re interviewing for, the interviewer, job role etc. Despite this, there are certain steps you can take which will help the interviewer judge the clarity of your thought process, thoroughness while solving problems, and overall problem solving ability. While the two scripts below try to provide a general path on approaching problems during an interview, remember that you have to improvise depending on how the interview is going, and the best way to achieve good results is to be yourself during the interview. A calm mindset while approaching the interview helps significantly, and there is no better way to establish a rapport with the interviewer than to be sincere :).
Another important aspect of the interviewing that I have noticed a lack of, is that most people try to approach an interview as a showcase-my-abilities experience, or a me-vs-the-company battle. It is not. An interview is a journey you and the interviewer take together where you solve a problem and get to know each other better(not just your abilities, but also who you are). Don’t be afraid to ask questions or speak your mind.
As an interviewee, you do not always play at the backhand. An example of this is concepts which I’m not completely sure about. I’ll often let the interviewer know that I’ll be looking it up, or straight up Googling it. I follow it up by explaining exactly what it was that I looked up and how that concept helps with my solution. Actively guiding the interview showcases that you can take charge when needed and bring the problem to its logical conclusion. After all, you are interviewing the company and judging it as much as they are you. Don’t come on too strong though ;).
Solving a problem
Remember: Think out loud! (more tips on this at the end)
Solving a particular coding problem usually involves the following steps:
I discuss the flow of the interview and each step in detail below:
- Question – This is the question that is provided by the interviewer. You need to read it in thorough detail. Read it multiple times if necessary. There are multiple ways to approach it at this point. If you have a general idea of how to solve the problem, good for you. If not, try to identify if the problem is a mutation of a known, classical problem(e.g. searching in a graph), or some combination of those. If this doesn’t work either, try to come up with the simplest way you can solve the problem. Don’t think about complexities and optimizations at this point.
- Discussion – Your first step should be telling the interviewer exactly what you’re thinking and how you are working on refining the idea. It is important that you talk to the interviewer because they will help guide you in the right direction and correct any obvious mistakes you might be making. You might also have missed some details previously, and the interviewer can point those out to you. You know that feeling when someone you’re talking to is obviously wrong and you can’t help it but try and correct them? Yeah, that’s what we’re going for.
ASK QUESTIONS.I cannot stress this enough. Interviewers are often banking on the interviewee asking clarification questions and might leave out a detail or two to see if you understand the problem enough to notice it. They might have made a mistake and won’t know till you ask them. Any assumptions you make should be clarified. And the most important thing discussing the problem with the interviewer does at this point, is open up two-way communication and build a rapport between you two from the get go. Both of you are more comfortable and will have a better overall interview experience. Win-win!
- Test Case check – At this point in the interview when I understand the question really well, I will often look at the test cases to identify if the idea I’m thinking of works with the given test cases. Are there any obvious gotchas that they show me? Can I come up with a test case where my solution is still in a grey area? Can I ask the interviewer about this grey area and get more test cases? And as always, think out loud.
- Discuss Brute-force – Unless I am sure I have an efficient solution completely figured out in my head, I always, always, always, discuss the brute-force solution with the interviewer. The brute-force solution is usually easy to implement, gets working (pseudo?)code written down which the interviewer can use to score you/come back to later, and has easier time and space complexity discussions. Usually when discussing the brute-force solution, basic optimizations become obvious, and it gives us future paths which are useful in coming up with an efficient solution.
My process with this is to explain all the steps in my algorithm to the interviewer as a gist, since we will be going into more detail while writing actual code.
Edit:Divye has correctly pointed out that over time, as you practice giving interviews, you develop an intuition of developing the efficient solution in the first go. “But if a preconceived notion of needing to start out with brute force exists, often you lose out on that spark.”, as he wisely put it. I have noticed that I tend to rely more on my instinct, now that I know that I will follow a process and only need to worry about coming up with a solution. Experience helps with this too, I’m sure. Others have pointed out that an efficient solution can strike you midway at any step, and depending on the time remaining, you should judge whether to switch to that solution. Sound advice. But you always have this process to fall back on in case anything starts going awry ;).
Another good point brought up is thinking about the competition. Somebody out there is going to come up with an optimal solution no matter what. It’s a question of showcasing technical ability vs superiority. I am fine with the former, but you do you.
- Implement Brute-force – There is a decision to be made here: Should you implement the brute-force solution, or is it better to discuss and implement a more efficient solution? The more efficient solution will score you more points in that vertical, but if you are unable to come up with a complete efficient solution, it is better to have complete brute-force code. Completeness scores high as a measure because it showcases that you could correctly assess the constraints, including your abilities and the problem, and come up with a solution that works. Taking this decision involves quick judgment on your abilities and how deeply you understand the problem. I tend to not give myself the benefit of doubt and implement the brute-force if I cannot map out an efficient solution in my head yet. Leave a few minutes if the time for the interview is ending to complete the final discussions.
There are some general coding tips at the end of this section.
- Discuss Efficient solution – Wooo! Look at you discussing an efficient solution! You can get here either before implementing a brute-force solution, or after. In either case, you should be able to talk out loud how you came up with the approach or optimizations (if you knew it before, why didn’t you just implement it before?). Depending on the time remaining, and whether I have implemented a brute-force solution already, I will go into significant detail explaining this solution if I feel I will not be able to implement it completely, or less detail otherwise.
- Implement Efficient solution – If you’re here, you’re in a good spot in the interview :). This is you putting your best foot/solution forward, so you can confidently go forward. Again, leave some time at the end for further discussions. Coding tips are at the end.
- Dry run cases – Use the given test cases to verbally, STEP-BY-STEP walk through each line of your code and how it will execute. You don’t need to write down the intermediate values if you’re confident, but in some complex cases, I prefer writing those variable values down. This catches basic errors in your code, makes it easier for the interviewer to understand exactly what you’ve done, and shows the interviewer that you care about testing your code.
- Edge cases – The next step is stress-testing your code. Try out null values. Check for overflows. Any complex logic in your code? Make an edge case for that. Try out as many crazy inputs in your code as you can. DRY RUN THEM VERBALLY so your interviewer knows what you’re trying out. Increases your confidence in your code, and shows the interviewer how well you understand the system and underlying constraints.
- Time & Space complexity – I prefer having this discussion before discussing scalability, concurrency etc. so that we have bolted down this problem as solved and completed our discussion. Everything else is a perk. I usually approach time and space complexity in a bottom-up fashion, starting from the most basic operation and going up the tree. This approach verifies my values, and shows that I understand the process of calculating the complexity. I usually write this down at the end of my code in comments.
- Further discussion – Depending on the company, the time remaining and how the interview has gone, I will often discuss further with the interviewer, for e.g., how do I implement such an algorithm concurrently? How would I scale this approach to X users? How would I manage memory in case this grows too large?
- Please use good variable names!var1 is useless when you come back to the code 2 months later, and to understand what the variable does. activeUserCounter is a much better descriptor. The typing speed argument should not matter (auto-complete, copy-paste), and the benefits are absolutely worth it.
- Follow a standard coding style. I don’t care what you use unless you’re doing something unheard of, but follow a consistent pattern. This is often language and convention dependent.
- Don’t be afraid of classes/functions etc. Sure, you might feel that they add extra time not spent on writing logic, but if it simplifies understanding of your code, it will often be worth it. Not just for the interviewer, if you structure your code well, you have less cognitive load when writing other parts of your code.
The Technical Interview Script
A technical interview is not just problem-solving, though that is primary. The basic script looks like:
- YOU NEED AN ELEVATOR PITCH. Don’t worry, it doesn’t make you one of those MBA-types. And you will invariably be asked to describe yourself at the beginning of the interview. The elevator pitch for an engineer is usually a 2 minute monologue on your work, or your journey, interspersed with some technical details and some real-life impact. You don’t need to explain everything. You shouldn’t say too little either. Remember the skirt analogy. If you don’t have one, make one and then tell it to as many people as you can and ask them what they think. In a few iterations, you should have something ready. Also, practice it till you can speak it confidently, since this is the first impression you’re going to leave on the interviewer.
- N Questions – Depending on the company, you will be expected to solve some questions. We’ve already discussed the question approach beforehand.
- Your questions – Depending on the time remaining, you can ask all the questions that might be plaguing you about the company. Don’t hesitate. Don’t be an idiot, but if you have a genuine doubt, no matter what it is, you shouldn’t hesitate. I usually ask about the creative freedom and ownership responsibilities because I am always curious about those, but your mileage may vary. Depending on how my interview went, I usually ask the interviewer if I performed well in all verticals they were judging me on.
- Call me maybe? – Well, that’s it. You’re done with the interview and now the only thing to do it wait. I’m not good at that, so best of luck! 🙂
These are my practices(?) for practicing interviews:
- Nothing replaces the real thing. Give mock interviews. I’m lucky enough to have friends who are already interviewers, and know how to create an atmosphere of a real interview. We try to not be friends during that time and recreate an interview as much as possible. Finding people who can interview you is a difficult personal journey, but I would spend significant time finding these people so that I can get working on this part of the process.
I started interviewing after I had revised all my concepts, and solved a large number of problems of all types on an online judge(I used Leetcode). Thus, I learnt to jump from question to solution in my head, detracting from training in the process of solving a question. In hindsight, that is the wrong approach, and I should have started right after I had revised most of my theory concepts and was practicing problems. A lot of steps in the question script came about as a result of feedback from my mock interviews. I had to consciously change how I approached solving problems while interviewing, and that is definitely the hard way. Why not just train yourself to think the interview way when practicing from the first time?
- If (and this is not a political statement) in the years post 2020, paper-pen and whiteboard interviews are in fashion again, you need to practice solving problems on the medium. You can still pull off a decently similar experience using video calls and paper-pen, or a whiteboard, I imagine. Most of my post quarantine interviews have been completely over telephone or video, though.
Thinking out loud
Ok, I know this is the bane of coding rounds in interview. If you say things out loud, you’re gonna think slower and might not be able to finish, but if you don’t, the interview is just a black hole where sometimes you might discuss something, but there is a major communication gap between you two. It is hard in the beginning, but if you remember to do a few simple things, you should be doing this in no time!
- Practice by teaching someone in extreme detail. It doesn’t matter what algorithm or concept you teach, this will help you in being able to talk about detailed aspects of the work using simple language and analogous concepts which will help you when you’re trying to explain what you’re thinking of on the fly. I notice that I clear the idea out in my head the fastest if I explain a concept to a friend from a widely different field, e.g. binary to decimal conversion and vice versa to my doctor friend.
- You don’t have to say everything – Knowing what to say is an art form in itself, but a simple tradeoff I make is if I know I’m not going to be able to talk while performing a task, e.g. dry-running on a case, I will prefix all my silent computations in my head by explaining what I will be doing in my head, e.g. “I’m about to try and prove if collinearity exists in this case, so I might fall silent, but I’ll try to keep you updated on what I’m thinking”. In any case, every few minutes I will let them know where I am.
- You don’t have to be completely coherent – They know you’re thinking on the fly and might not have things figured out in your head. You might talk about unrelated topics, concepts which you’re skimming to see if they fit the problem, or weird ideas which pop up in your head. They don’t have to be coherent together. But you should speak in complete sentences as much as possible :p. And once you’ve ideated and have an approach ready, you should be fairly coherent then.
- Ask them questions – You don’t have to be the only one talking. I often ask validation questions when talking, e.g. “Does that sound good?”. The responses often let me know how confidently the interviewer understands what I’m talking about, and I can course correct if I make any mistakes. These questions also buy you some time while making the interviewer pay active attention to you.
That does it for this post. Phew. That was a long one, wasn’t it? This is a very subjective post, and let me know any comments/suggestions/improvements.
Originally, I wrote and posted this on July 1st, 2020 at Algorithms and me