Guest blog by Andrei Margreloiu Microsoft Student Partner at University College London
My name is Andrei Margeloiu and I’ve been a competitive programmer for the last five years.
I’ve participated in the World Finals of Google HashCode, the largest algorithmic competition organised by Google, and before that, I won three Gold Medals in the Computing Olympiad in Romania. Having this experience, I’ve published the online course “Introduction to Algorithms and Data Structures in C++” that has been helping over 8000 students from 135 countries with their first steps in the field.
Summer Internships, placements and jobs
Now I’m studying Computer Science at University College London and meanwhile, I’m creating a course to help students and young professionals to prepare for the coding interview in the big tech companies. Hence, in this article, I want to share my experience with the coding interview and tell you the straightest way to pass it. You can reach me here.
Top Tips for passing a coding interview
The article has three parts and it will take approximately 30 minutes to read.
1. What is the coding interview?
2. How to prepare for the coding interview?
3. How to give your best during the coding interview?
What is the coding interview?
Let me ask you a question: have you ever dreamed of working in a big tech company, like Microsoft? If so, be sure that most of us did, too. And because there is such a high demand for a few dozen jobs, they need a way to see which candidates are better prepared.
Before you get invited to the coding interview, you need to apply for the position and have a CV that shines among the others. In this article, I’ll talk about the actual coding interview and how you can prepare for it, and not about the application process for the job.
For most tech companies, the coding interview consists of Algorithms & Data structures problems. Think of these as problem-solving questions, in which the interviewer is looking to evaluate your ability to solve a problem that you haven’t seen before. One interview takes roughly 45 minutes and you are given one or two coding problems. The interviewer is expecting you to find the most optimal solution, code it and explain what you have just coded.
Lastly, you will have the chance to ask him some questions about the company or anything that interests you. We will comprehensively discuss all these steps in the last part of this article.
How to prepare for the coding interview?
I want to be clear with you from the beginning: there is no such shortcut or trick to pass the interview. The single way to find optimal solutions to algorithmic problems is by practicing, solving as many problems as possible. In short, it’s hard work.
You may not like it and start looking somewhere else for a trick to understand how to solve interview questions, but it doesn’t exist. Think for a second: if there would be such a trick, why wouldn’t everyone use it and pass the interview?
So, you need to understand that the single variable of passing the interview is how much you practice before. Your experience, intelligence and everything else is already fixed. Hence, the time spent on practice will make the difference between the candidates who pass and fail.
The coding interview is a fight with yourself, and the single way to win it is to practice a lot.
The first step is to feel comfortable with a mainstream coding language, such as C/C++, Java or Python. Some companies also accept other languages, and the clear majority stick with these three. Pick the one you like most and stick with it. Don’t decide halfway through preparation that you want to change the language! For the rest of the article, I will assume that you’ve chosen a language and know well its syntax.
Now, typically the coding interview is all about Algorithms and Data structures. They include some fundamental topics that you need to understand thoroughly, and don’t even consider going to the interview without feeling comfortable with them.
Below there is a list of the Algorithms and Data structures that you need to know. I've written them in order of their importance and it is the best learning path.
1) Big O complexity: It’s a must and forms the underlying foundation of your algorithmic thinking. Understand what it means and arrive at the point when you can say the complexity of a basic algorithm just from looking at it.
2) Arrays: You should be familiar with the concept of arrays at this point. This topic refers to problems where the array is used just for storage and the solution includes basic techniques, such as iterating with two pointers. A classic problem is to check if a given array is a permutation.
3) Strings: Know how to manipulate a string in your language, and be familiar with problems that ask you to concatenate or rotate them.
4) Linked Lists: It’s common to encounter a linked list problem in the interview. Here you need to pay special attention to the corner cases. Think what happens if the linked list is empty? Or it has just one element? Or you want to iterate until the last element? When you solve a problem with linked lists, think twice about the corner cases.
5) Hash Tables: Fundamental data structure that is present in most interviews. If you go deeper in one topic, choose hash tables. Be fluent in the hash tables library of your language and practice at least five problems. In the end, take this challenge: How would you find the longest subarray with distinct entries?
6) Stacks: Be familiar with the idea that you can manipulate just one end of the stack. Solve this challenge: Implement a Stack with a MAX API, meaning that at every moment you can ask what is the maximum element in the stack.
7) Queues: Don’t confuse them with stacks, because they have two ends. Implement the classic problem of simulating a queue using two stacks.
8) Greedy: This technique is quite simple and you probably use it every day. It basically refers to taking the best decision possible at a specific moment, without considering future consequences. Practice a few problems, and don’t think that any problem can be solved using Greedy.
9) Primitive types: It is mostly concerned with bit manipulation and basic operations on numbers. However, some problems can become quite tricky. How can you count the number of 1’s in a binary representation?
10) Binary trees: Focus on traversals, common ancestors and recursively iterate through the trees.
11) Heaps: They are widely used in real world application, so get to know heaps! Practice until you can be confident when to use a min-heap or a max-heap. How would you print the biggest five elements from a number sequence? Do you use a min-heap or a max-heap?
12) Searching: Searching is a core subject that everyone should know. So, practice at least three problems using binary search.
13) Sorting: Be sure that you can implement mergesort and quicksort. Know very well their best, average and worst case complexities. If you have time, also learn Heapsort.
14) Binary Search Trees: They are widely asked in the coding interview, and you need to be able to implement all their basic operations, including the deletion of an element!
15) Backtracking: It basically means generating all possible solutions and take the ones which respect to your requirements. Implement a generator of the power set of the set and the n-Queen problem.
16) Graphs: They are probably the most used data structure in computer science. Did you know that every social network is just a huge graph? Practice on making a copy of the graph in memory and detecting cycles in graphs.
17) Dynamic programming: Dynamic programming is seen by most as the scariest topic. But it’s the most beautiful if you understand the thinking behind it. So, practice the top five most common questions and stick with them until you understand where the recurrences come from.
In the course, I'm creating now, I'm explaining each topic in this order. I'm still working on the course, but you can get early access to some of the lessons and also help me with your feedback, by joining the course Facebook group.
If many topics are unfamiliar to you, it means that you need to start practicing right after this article. No more searching online other guides, just go and practice. Remember that the interview is a fight with yourself, the more you practice, the higher your chance of winning. It’s up to you to increase your problems comfort zone.
How to give your best during the coding interview?
The interview has five parts which we’ll discuss in depth. Watch the explanatory videos for real examples.
This part commences the interview and takes about three to five minutes. The interviewer wants to find out more about you and gives you the chance to present yourself. Typically, he is interested in what projects you have worked on before and which was the most impressive one. Now, this is your chance to shine, so don’t waste it!
Don’t try to be flattering. It’s easy to spot a fake personality that tries to trick you. Me and everyone else hate those people, so be sure you show your true personality.
You need to know beforehand what you are going to say about your favourite project, so prepare it before the interview. Now, most people say just two short sentences, which is bad. Which answer do you like more?
1) "I worked on a web application to better manage patients in hospitals. I wrote the backend in Node.js."
The way you present yourself really matters
2) "A project that I really enjoyed was about creating a web application for the National Health Services of the UK to help them to better manage the patients in the hospital. It was part of the University curriculum, it took two months and I have been the leader of a team of three.
We took the project from a basic idea and turned it into a real application. I was responsible for coding the backend in Node.js and database in MongoDB. It was the first application I've ever created for a client and I wasn't familiar with the web technologies. The developing process was iterative, and we made some mistakes on the way.
In the end, we over-delivered with many features, and my favourite one is that the users can update the rooms of the hospital, instead of being hard coded.
I learned many things from this project, especially how to work in a team. There were some moments in which technical or team problems arose, but in the end, everything went well and we got the highest mark of the year!"
Turn this presentation into your advantage! The interviewer is truly interested in finding more about you, so start with a concise introduction of the project, explaining what it's about. Then say what was your contribution (if you helped the team with a smart idea, say it!), and what you learnt from the developing process. You can also mention what difference you made for the users.
You should talk one-two minutes about your project.
2) Understand the problem
The interviewer will briefly tell you the problem statement that you need to solve. I said ‘briefly’ because he won’t give you many details about the constraints, corner cases or how you receive the data. It’s part of your job to ask for everything that you need to solve the problem. Repeat the statement loud to be sure that you got it correctly.
3) Search for a solution
Now you need to find an optimal solution to the given problem. I want to be straight with you, and tell you that you won't magically find an optimal solution if you didn't practice a lot before.
I know that finding the solution might not come naturally to you from the beginning. So, the first thing when you receive the problem is to make an idea of the data structure that you need to use.
After you spot the data structure, think of typical algorithms and problems that you have seen before using this data structure. For example, if you receive a problem with trees, it's clear that you need to use algorithms specific to trees, such as recursion, right? If you receive a problem telling you to find the minimum or maximum, then think of heaps, sorting or stacks. And the list of such examples continues.
The key here is that practice will tell its word now, and I have good news for you! Many interview questions are similar, so there is a high chance that you practiced a similar problem before and you can build a solution starting from that.
The Moral here is basic:
The more you practice, the faster you will find optimal solutions
Now, the other thing that is crucial at this step is to talk aloud. The interviewer is interested in seeing your thinking process and hearing your explanations. Most people stay quiet for three minutes while thinking of a solution, and that is the worst strategy possible for them.
Don't be one of them! Make the interviewer really understand what you want to say, and don't assume he gets bored while hearing to you. He is there to listen to your thinking process. Don't be scared that you might start with a bad solution, there is time to improve it!
The two things I want you to remember is to practice a lot before and talk aloud during the interview, period.
Keep in mind to talk aloud and explain what you are thinking.
Now, in the following video we'll move to finding an optimal solution for the problem. I want you to pay special attention to how I speak and explain. Think that now you are the interviewer and I am the candidate. I will try to do my best to explain. If you understand what I'm explaining, it means that I'm doing a great job as a candidate. If something is unclear to you, it means that it would also be unclear for the interviewer! So, feel free to judge me as a candidate and leave a comment if something doesn’t make sense. I’ll read all of them.
4) Code the solution
Now we arrived at the interesting part, coding the solution. To do well in this part, you must feel comfortable with the language that you are coding in, even if you don't have an IDE to help you. Some companies ask you to code on a blackboard or Google docs, where there is no word highlight, so make sure that you feel comfortable with the language.
Now, moving to the coding itself, I want to tell you something.
This part is not all about coding, it's also about talking loud and explaining what you are coding.
The interviewer doesn't want you to code in silence for ten minutes and then say that you finished. He wants you to talk aloud and explain everything that you write.
The reason is simple: he doesn't know what you are coding if you don't explain. So, make his job easier and talk while you are coding.
Also, make your code look clean and neat. No one likes messy codes that one can barely read. Be sure that your code is explanatory.
After you finished coding, there is a high chance that you missed a bug. That's not a problem at all! Your job is to repair the code by yourself. So, tell to the interviewer: "I have just finished coding. Can I have a look at the code to be sure there are no mistakes?". He would happily say "Yes, let's go through your code".
Then you walk him through each line of code and explain again what is happening there. If you see a mistake, tell it! Don't pretend that the code is perfect, you will just hurt yourself! So simply say: "I see that there is a bug. Here is the solution to solve it ...", and you make the changes.
In the end, you should arrive at an optimal solution that works and is bug free
5) Ask questions
And here we came, the moment after you finished coding the problems. Now the interviewer will give you the chance to ask him any question that you might be interested in.
Many people say that they don't have any questions, and that is a huge mistake. They miss a big chance to find out more about the company and the job itself!
I really encourage you to ask at least two questions. It's your chance to find out what it is like to work in that company!
You can ask: "How do you find the culture of the company?" or "What do you like most about your job? or "How was your first week here?" or "Do you get to choose which project to work on?" or "What project do you normally give to interns?". You can pretty much ask anything about the company and his job.
Ask questions in the end! Don’t skip them
The coding interview is all about you finding a solution and explaining it. There are two things you need to remember from this article: to practice a lot before the interview and articulate your thinking process during the interview. They are equally important and if you master both, then you’ve passed the interview!