How to crack the coding interview?

I have given quite a few interviews at companies like Google, Microsoft, De Shaw, Databricks, etc. I have also taken over 100 interviews. Having been on both sides of the interview process, I wanted to share some insights into the process and how can one optimize for success.

Disclaimer: this article is intended for people experienced at leetcode style problem solving and are able to solve the problems itself effortlessly. If you would like tips on that, consider reading my other article — How and why I did over 1000 leetcode problems.

tldr; If I have to summarize everything into one line, then I would say interviewing is simply a game of time management

A typical interview is 45 minutes, if you save 5 minutes, that is 10% more time in the interview. This extra 10% is probably what you needed to make some code improvements to move the rating from no-hire to hire. So there is no time to waste.

We only change companies so many times in our career, I highly advise you to prepare over several months and give it your best shot.

Interview rubrics

This section is to understand the interview process from an interviewer’s perspective.

Generally, companies will have an overall rating system like Hire, Strong Hire, no Hire, etc. The hiring committee will pay significant weight to this rating for making their decision. Each company has its guidelines and policies and each interviewer will give relatively more importance to different things in the interview. However, fundamentally it comes down to a few things such as — how quickly the candidate understood the question, and were they were able to consider trade-offs and come up with an optimal solution, and most importantly, whether were they able to implement it with minimal mistakes in the given time. Let's go over this in detail now:

1. Problem-solving ability: This can be considered as the primary rubric of the interview. It essentially comes down to whether the candidate can come up with a solution to the given problem. Another way to look at this is the ability to think on your feet and adapt current solution to solve new problems.
2. Data-structures and algorithms knowledge: As an interviewer, I give significant importance to this. If a candidate exhibits a deep understanding of certain data structures and can consider trade-offs then it's a significant plus point. On the other hand, if a candidate gives an impression that they are just throwing a data structure at the problem hoping it will stick, then it's a negative point.
3. Communication: How clear is the candidate in their thoughts, are they able to articulate well, etc? Note that good communication doesn’t mean the candidate takes time to explain their solution but rather how concise and clear the explanation was. Other communication traits include how receptive the candidate is to hints and inputs.
4. Coding: This is the second most important rubric, this is something the hiring committee can see for themselves. Good quality variable names, modular code, best practices, etc can go a long way here.

How do I know if I did well in an interview?

One part is finding the optimal solution for the problem. Experienced candidates can intuitively tell if the solution is optimal or not. Discussing with friends after the interview helps here.

The second part is # of problems solved. Many candidates make the mistake of thinking oh I solved the problem, I did great. However very often that was just the warm-up, or it was one question but there was a follow-up to it.

Remember, there is always a follow-up or a bonus question. The only way to get a strong hire rating is to exceed the base expectations. I have had candidates who solve up to 3 follow-ups in an interview. If your interview ends early and you have solved 1–2 problems, then it's a clear sign you did well cause the interviewer ran out of questions.

As a general rule of thumb, if you solve more questions even with hints, that means you did well objectively, therefore, it's easier for the interviewer and the recruiter to defend your case.

Interview Format

A typical interview of 45 minutes can be split as follows:

1. Introduction (2 minutes): This is an ice breaker, it actually adds no value to the interview, I would strongly recommend preparing something basic for this and just speaking it out. The interviewer isn’t listening or noting down what you say, it has no bearing on the result of your interview. Wasting time here is the worst thing you could do.
2. Actual interview (40 minutes): This is the main interview, in 40 minutes, the interviewer will need to present and explain the question. Then you will need to understand it, go through test cases, come up with a base algorithm, explain it, optimize the algorithm, explain and dry run it on the test cases, and finally write code and test it. And this is for just one problem, if there are 1–2 follow-ups, then you will need to do all this for them as well.
3. Questions regarding the company (3 minutes): This is the chance where you can ask questions about the company. The questions can be general like how is the culture, benefits, and perks or it can be specific like what is the Bangalore team working on or what teams are in Bangalore. My favorite question is asking — What is one thing you like about this company and one thing you don’t like? I have found that people have been quite transparent when asked like this. Needless to say, this is a chance for you to get some information as to whether the company is a right fit for you and this has no bearing on the result of the interview.

Interview Tips

Tip 1: Guiding Principle: Optimize for time
Everyone can achieve more with more time, however, of course, you have only 40 minutes and therefore you need to optimize wherever possible. You as the candidate hold most of the control over the pace, you decide how fast you want to explain/code/test. The remaining tips here are all ways to achieve this.

Tip 2: Reading the question carefully and then go through examples thoroughly
This is one place, where you should take your time as if this goes wrong, everything goes wrong. Very often I think I have understood the question but I actually wouldn’t have. An efficient way to make sure is to go through the examples. This not only helps in verifying your understanding but examples can often hint at the approach to solve the problem as well.

Tip 3: Think out aloud
It's very important to think aloud in the interview, the interviewer will know what's happening and be engaged. Moreover, they can hint and guide you to the right solution. Thinking out aloud is unnatural, we generally think better in silence, therefore make sure to practice this. While implementing the solution, it is not that important to think aloud though still preferred because the interviewer can see what you are writing down, so they already have a pretty good idea. However, it can still be helpful when you define some structure to explain why — like “Okay this map stores mapping from user_id to score, and this second map stores an ordered map from the score to a set of user_ids because I want to be able to do XYZ”

Tip 4: Approaching the problem and exploring the solution space
What generally works for me is that I immediately say the naive solution. But it's important to be clear this is a naive solution so that you don’t waste a lot of time on this and the interviewer doesn’t think that you think that this is optimal. I usually say something like this “Oh, my immediate naive approach would be something like run 2 nested loops, consider all sub-arrays, and compute the answer brute force, so this would be an O(N²) algorithm”. This helps me reduce nerves as I have already said some solution in the interview and the interviewer has accepted it. Now we just need to optimize. This also acts as a second sanity check that you have understood the question. After this, you can be like “Okay the second loop is doing repeated work, maybe we can use dynamic programming to maintain X state and reduce it to one loop”. Then do a quick dry run with an example, we will cover this part more in detail later. Once the interviewer is satisfied, jump to the solution.

Feel free to say hand-wavy solutions like “Oh, if we use a heap, we can achieve this in O(logN) time but I would like to go with the binary search”. This indicates that you can consider multiple approaches in parallel and able to choose the optimal one. The interviewer also wants to be fast, so they will only cross-question you if they believe you don’t know what you are talking about or if you say something incorrectly.

Tip 5: Assume the interviewer knows everything
The interviewer is experienced at this question and knows (nearly) all the possible solutions. This is obvious but it is shocking how few candidates take advantage of this.

1. Don’t waste time explaining trivial things — When in doubt, explain briefly and ask does it makes sense to reassure yourself. But for the most part, you can assume the interviewer is following you.
2. When you are confused with an approach, it can be quite daunting. Often we face situations like this is either a complex graph problem or a complex DP problem but I am not sure. You might start with a graph approach but now you aren’t sure and you want to switch to DP. Here, you can ask the interviewer, do you think it makes sense to consider graphs, or should I move to something else like DP? They will usually not give a definite answer but their reaction is all you need to know what to do.
3. Feel free to drop minor facts and pieces of information when you feel like without much detail. Facts such as Oh this is O(N) because of the way it's implemented in Python. This shows that you are aware of this. If the interviewer wants more details they will ask.
4. However, if you are using some very complex approach that is not common knowledge, then it's probably better to not assume the interviewer knows this. Some examples could be things like coordinate compression, BIT, Segment tree, or complex graph algorithms. But as a warning, it is going to be very rare that this sort of complex DS is the intended solution and there should be an easier way.

Tip 6: The interviewer is your friend
Believe it or not, the interviewer wants to see the best in you. Even when you say or do something wrong, they will want to give you a second chance and ask a clarifying question. What this means is that when the interviewer says something, PAY ATTENTION! It is shocking how many people dismiss the interviewer and go on. It not only irritates the interviewer but also means you missed something important. Moreover, this reflects poorly on your collaboration and cultural values.

Therefore, if you say something like oh this is O(N) and the interviewer asks a question like are you sure? if you have an answer, go ahead and explain it and ask them if it makes sense. Be ready to accept that you are wrong. Also, be ready to say I feel this intuitively but I am not sure as I didn’t consider everything.

And if the interviewer gives a hint, be sure to follow it up. Hints are only given if the interviewer believes your current approach doesn’t lead to a solution or we are running out of time. While it might be shocking many candidates don’t consider the interviewer’s inputs and hints seriously.

Tip 7: Familiarize yourself with the coding environment
Companies use different platforms for their interviews — codepair, coderpad, etc. Each tool has different nuances and it's a good idea to be familiar with them before the interview. Google for example used google docs for a very long time and that is a horrible environment to write code. However, I was able to heavily customize it by tweaking several settings and found that it was acceptable for me.

Tip 8: Practice explaining algorithms in the collaborative environment
This is something that is significantly overlooked by candidates including me during their preparation.

One trick is to use the highlight functionality in collaborative environments. This can show the interviewer what number you are looking at, how you are traversing the list etc.

The second is to work on maintaining the state well. This is very problem specific of course but practice can help. Keep it as less verbose as possible, no need to have all the details, not all variables need to be defined, just the main ones. No need to worry a lot about semantics like types, syntax, etc. Optimize for clarity and speed. Trees and graphs in particular are hard to handle.

// Key value map
key_value_mp = {a: 1, b: 2}

// List
l2 = [a, b]

// Matrix
grid = [
A B C D
E F G H
]

Tip 9: Practice writing code fast
This is a lot of practice and just keep in mind that we should optimize for speed. Don’t compromise on variable names or code structure. If long variable names are necessary, then use them. However, use copy-paste or autocomplete features to be fast. Another way to be fast is to use all the language features, for example

// Slow
unordered_map<int, int> mp;
mp[1] = 2
mp[3] = 4
vector<vector<int>> ans;

for (pair<int, int> p: mp) {
  if (p.first > 1 && p.second < 2) {
    // some logic
    vector<int> temp = {p.first, p.second};
    ans.push_back(temp);
  }
}

// Fast
unordered_map<int, int> mp = {{1, 2}, {3, 4}};
vector<vector<int>> ans;

for (auto [k, v]: mp) {
  if (k > 1 && v < 2) {
    // some logic
    ans.push_back({k, v});
  }
}

Of course, elegant solutions require less code, this is something you can achieve by reading others' solutions and practicing.

Tip 10: Develop fast debugging/testing skills
Debugging involves adding log statements at appropriate places and using the information to quickly gauge the rough location of the issue and then finding the issue.

Testing is about how quickly can you write multiple test cases and execute and verify your solution. For example,

// Typical input/output tests 
vector<vector<int>> inputs = {
  {1, 2, 3},
  {3, 4, 6},
};

vector<int> expected_outputs = {4, 5};

for (int i = 0; i < inputs.size(); i++) {
  int output = foo(inputs[i]);
  cout <<"Test " << i << " Input: "
  for(int a: inputs[i]) cout << a <<" ";
  cout << endl;
  if (output != expected_outputs[i]) {
    cout << "Expected " << expected_outputs[i] << " got " << output << endl;
  }
}

cout << "Tests ended" << endl;

// System test

// test 0
{
  Sys sys(10, 2);
  sys.insert(1);
  sys.insert(2);
  cout << sys.compute() << endl;
}

// test 1
{
  Sys sys(10, 2);
  sys.insert(1);
  sys.insert(2);
  cout << sys.compute() << endl;
}

In the above example, for the first type with a typical input/output type problem, it's a good idea to be able to write a basic unit test. Of course, I have written a pretty extensive one, It can simply start with one test and then evolve to this if the interviewer insists on testing several test cases.

In the second example, if it is a system problem where it is not easy to model it as an input/output problem, in that case, it is a good idea to scope it using {} and copy-paste code. This way you can reuse variable names and avoid mistakes such as mixing state.

Tip 11: Write the best code possible
Leave all the competitive style programming to codeforces. Here you should aim to write production-grade code.

1. Good naming conventions
2. Use language best practices
3. Modular, clean code
4. Never have global variables or global state → use classes when required

Of course, also don’t compromise on time. It is often a good idea to implement what is easy first and then improve it after completion. The end code should be clean and this is something the hiring committee takes seriously.

Conclusion

In conclusion, while balancing several things, time is of the essence and a precious resource in the interview. All the tips shared here are intended to be guidelines and you will need to improvise in the interview. Moreover, there is no shortcut for practice, take several mock interviews before the real one. During college, I have taken easily over 50 mock interviews from at least 10 people.