Technical Interviewing and Programming Challenges are a hot topic right. Some people love them, some loathe them, but the fact is that technical testing is here to stay and widely used by many of the Worlds best companies. Therefore, if you want high-quality career opportunities with fantastic organisations, on top projects, and earn the big bucks - then you have to clear the testing phases. In my search for material to help our candidates navigate this tricky and critical interview stage, I came across the "Tech Interview Handbook" by Yangshun Tay on Github. Quite honestly, this is the most comprehensive resource we have seen and something that has been written by an engineer, for engineers. The original Github page is https://yangshun.github.io/tech-interview-handbook/. The Github page has several other useful links to help people prepare and refresh for tough technical testing interviews and challenges, but below is a snapshot.
Interview Formats
Interviews are a multi-stage process, and each stage can consist of vastly different formats.
Various formats
Pop quiz
Pop quizzes are meant to be a quick and dirty way of weeding out extremely weak (or even non-technical) candidates. They are structured questions and have clear-cut answers which makes them possible to be administered by recruiters/non-technical folks. It is not a very common interview format these days.
Examples:
What is 4 & 5 (in binary)? Answer: 4
What is the time complexity of bubble sort? Answer: O(n^2)
Take-home assignment
There have been numerous debates on whether asking algorithm questions are a good way of assessing individual abilities as they aren't exactly the most relevant skills needed for a job. Take-home assignment is a format designed to address the shortcomings of the algorithm interview by getting candidates to work on larger projects which allow them to demonstrate software design skills.
However, this interview format takes up more time from both the candidates and the company and hence it is not as commonly seen in large companies where they have a high volume of candidates. This format is more common among startups and small companies.
Examples
Build a flights listing app
Build a snake game
Phone interview
Phone interviews are the most common format and every candidate will face this at least once while interviewing. You will be asked to speak with an interviewer either over a phone call or VoIP (Skype/Hangout). A question will be given to you and you will work on that question using an online collaborative editor (CoderPad/CodePen/Google Docs).
You are usually not allowed to execute the code even if the editor supports execution. So don't rely on that for verifying the correctness of your solution. Formats would differ slightly depending on the roles you are applying to. Many companies like to use CoderPad for collaborative code editing. CoderPad supports running of the program, so it is possible that you will be asked to fix your code such that it can be run. For front end interviews, many companies like to use CodePen, and it will be worth your time to familiarize yourself with the user interfaces of such web-based coding environments.
Onsite
If you have made it to this stage, congratulations! This is usually the final stage before an offer decision. Candidates who made it to the onsite stage will be required to have an in-person interview at the office. If you are an overseas candidate, companies might even fly you in and pay for your accommodations!
The onsite stage usually consists of multiple rounds (coding, system design, behavioral) and is expected to last for a few hours. Since you are onsite, it is possible that you will be asked to do a whiteboard exercise with an interviewer, usually either solving an algorithm question or doing a system design question. It is also possible that you have to bring your own laptops and work on a project/solve a coding problem on the spot.
For onsite interviews at smaller (non-public) companies, most will allow (and prefer) that you use your own laptop. Hence it is important that you prepare your development environment in advance.
If the company provides lunch, you might also have a lunch session with an employee where you can find out more about the company culture.
Formats of famous companies
Airbnb
Recruiter phone screen
Technical phone interview:
1 or 2 x Algorithm/front end on CoderPad/CodePen
On-site (General):
2 x Algorithm coding on CoderPad
1 x System design/architecture
1 x Past experience/project
2 x Cross-functional
On-site (Front End):
2 x Front end coding on CodePen. Use any framework/library
1 x General coding on your own laptop
1 x Past experience/project
2 x Cross-functional
Tips:
All sessions involve coding on your own laptop. Prepare your development environment in advance
You are allowed to look up APIs if you need to
They seem to place high emphasis on compliable, runnable code in all their coding rounds
Cross-functional interviews will involve getting Airbnb employees from any discipline to speak with you. These interviews are mostly non-technical but are extremely important to Airbnb because they place a high emphasis on cultural fit. Do look up the Airbnb section of the behavioral questions to know what sort of questions to expect
Dropbox
Recruiter phone screen
Technical phone interviews:
2 x Algorithm/front end on CoderPad/CodePen
On-site (Front End):
2 x Front end on CodePen. Only Vanilla JS or jQuery allowed
1 x General coding on CoderPad
1 x All around. Meet with an Engineering Manager and discussing past experiences and working style
Tips:
You can code on your own laptop and look up APIs
Dropbox recruiters are very nice and will give you helpful information on what kind of questions to expect for the upcoming sessions
One of the front-end sessions involve coding up a pixel-perfect version of a real page on www.dropbox.com. You'll be given a spec of the desired page and you'll be asked to create a working version during the interview
Recruiter phone screen
Technical phone interviews:
1 or 2 x Algorithm/front end on Skype/CoderPad
On-site (Front End):
2 x Technical coding interview on whiteboard (Ninja)
1 x Behavioural (Jedi). Meet with an Engineering Manager and discussing past experiences and working style
1 x Design/architecture on whiteboard (Pirate)
Tips:
You are only allowed to use the whiteboard (or wall). No laptops involved
For the Jedi round, you may be asked a technical question at the end of it. Front end candidates will be given a small HTML/CSS problem nearing the end of the session
For the Ninja rounds, you may be asked one to two questions depending on how fast you progress through the question
Recruiter phone screen
Technical phone interview:
1 or 2 x algorithm on Google Doc
On-site:
1 or 2 x Front end on whiteboard. May be required to use Vanilla JS (or at the most, jQuery) depending on the question. (Front End only)
2 to 4 x Algorithm on whiteboard
1 x General Cognitive Ability, Leadership and "Googleyness".
Team matching
Speak with managers from different teams who are interested in your profile
Tips:
In rare cases, candidates may even be allowed to skip the phone interview round and advanced to on-site directly
For non-fresh grads, you only receive an offer if you are successfully matched with a team
Palantir
Recruiter phone screen
Technical phone interview:
1 x Algorithm over HackerRank CodePair and Skype
On-site (General):
2 x Algorithm on whiteboard
1 x Decomposition (system design) on whiteboard
On-site (Front End):
1 x Front end on your own laptop. This session lasts about 1.5 hours. Use any library/framework
1 x Decomposition (system design) on whiteboard
Tips:
I opted to use React and had to set up projects on the spot using create-react-app
You may be asked to meet with Engineering Managers after the technical sessions and it's not necessarily a good/bad thing
Coding Interview Overview
Coding interviews are tough. But fortunately, there is a tried and proven method to get better at them. With a combination of studying, practicing questions and doing mock interviews, getting that dream job can become a reality.
Decide on a programming language
Study CS fundamentals
Practice solving algorithm questions
Internalize the Do's and Don'ts of interviews
Know what signals and behaviors interviewers are looking out for
Practice doing mock interviews
Interview successfully to get the job
Picking a Language
Before anything else, you need to pick a programming language to do your interviews in. Most companies will let you code in any language you want, the only exception I know being Google, where they only allow candidates to pick from Java, C++, JavaScript or Python for their algorithmic coding interviews.
Some languages are more suited for interviews#
There are some languages which are more suitable than others for coding interviews and some languages you absolutely want to avoid. From my experience as an interviewer, most candidates pick Python or Java. Other commonly seen languages include JavaScript, Ruby and C++. I would absolutely avoid lower-level languages like C or Go, simply because they lack many standard library functions and data structures and some may require manual memory management.
Personally, Python is my de facto choice for algorithm coding interviews because it is succinct and has a huge library of functions and data structures available. One of my top reasons for recommending Python is that it uses consistent APIs that operate on different data structures, such as len(), for ... in ... and slicing notation on sequences (strings/lists/tuples). Getting the last element in a sequence is arr[-1] and reversing it is simply arr[::-1]. You can achieve a lot with minimal syntax in Python.
Java is a decent choice too but having to constantly declare types in your code means extra keystrokes which results in slower coding/typing speed. This issue will be more apparent when you must write on a whiteboard during on-site interviews. The reasons for choosing/not choosing C++ are like Java. Ultimately, Python, Java and C++ are decent choices of languages.
Use a language you are familiar with
Most of the time, it is recommended that you use a language that you are extremely familiar with rather than picking up a new language just for doing interviews because the company uses that language heavily or just because you want to show that you are trendy.
If you are under time constraints, picking up a new language just for interviewing is hardly a good idea. Languages take time to master and if you are already spending most of your time and effort on mastering algorithms, there is barely spare effort left for mastering a new language. If you are familiar with using one of the mainstream languages, there isn't a strong reason to learn a new language just for interviewing.
If you have been using Java at work for a while now and do not have time to be comfortably familiar with another language, I would recommend just sticking to Java instead of picking up Python from scratch just for the sake of interviews. Doing so, you can avoid having to context switch between languages during work vs interviews. Most of the time, the bottleneck is in the thinking and not the writing. It takes some getting used to before one becomes fluent in a language and be able to wield it with ease.
The exception to the norm
One exception to the convention of allowing you to "pick any programming language you want" is when you are interviewing for a domain-specific position, such as Front End/iOS/Android Engineer roles, in which you would need to be familiar with coding in JavaScript, Objective-C/Swift and Java respectively. If you need to use a data structure that the language does not support, such as a Queue or Heap in JavaScript, perhaps try asking the interviewer whether you can assume that you have a data structure that implements certain methods with specified time complexities. If the implementation of that data structure is not crucial to solving the problem, the interviewer will usually allow this. In reality, being aware of existing data structures and selecting the appropriate ones to tackle the problem at hand is more important than knowing the intricate implementation details.
Study and Practice
Recap CS fundamentals
If you have been out of college for a while, it is highly advisable to review CS fundamentals — Algorithms and Data Structures. Personally, I prefer to review as I practice, so I scan through my college notes and review the various algorithms as I work on algorithm problems from LeetCode and Cracking the Coding Interview.
This interviews repository by Kevin Naughton Jr. served as a quick refresher for me.
The Medium publication basecs by Vaidehi Joshi is also a great and light-hearted resource to recap on the various data structures and algorithms.
If you are interested in how data structures are implemented, check out Lago, a Data Structures and Algorithms library for JavaScript. It is pretty much still WIP but I intend to make it into a library that is able to be used in production and also a reference resource for revising Data Structures and Algorithms.
Mastery through practice
Next, gain familiarity and mastery of the algorithms and data structures in your chosen programming language.
Practice coding questions
Practice coding algorithms using your chosen language. While Cracking the Coding Interview is a good resource for practice, I prefer being able to type code, run it and get instant feedback. There are various Online Judges such as LeetCode, HackerRank and CodeForces for you to practice questions online and get used to the language. From experience, LeetCode questions are the most similar to the kind of questions being asked in interviews whereas HackerRank and CodeForces questions resemble competitive programming questions. If you practice enough LeetCode questions, there is a good chance that you would have seen/done your actual interview question (or some variant) on LeetCode before. If you are more of a visual person, Coderust explains the common algorithm questions through step-by-step visualizations which makes understanding the solutions much easier.
Space/time complexities
Learn and understand the time and space complexities of the common operations in your chosen language. For Python, this page will come in handy. Also, find out the underlying sorting algorithm that is being used in the language's sort() function and its time and space complexity (in Python its Timsort which is a hybrid sort). After completing a question on LeetCode, I usually add the time and space complexities of the written code as comments above the function body to remind myself to analyze the algorithm after I am done with the implementation.
Practice good coding style
Read up on the recommended coding style for your language and stick to it. If you have chosen Python, refer to the PEP 8 Style Guide. If you have chosen Java, refer to Google's Java Style Guide.
Internalize the pitfalls
Find out and be familiar with the common pitfalls and caveats of the language. If you point them out during the interview and intelligently avoid falling into them, you will usually impress the interviewer and that results in bonus points for your feedback, regardless of whether the interviewer is familiar with the language or not.
Broaden exposure
Gain broad exposure to questions from various topics. In the second half of the article, I mention algorithm topics and practice questions for each topic. Do around 100–200 LeetCode questions and you should be good.
Practice, practice and more practice!
Best Practice Questions
Here is a suggested schedule for revising and practicing algorithm questions on LeetCode. Sign up for an account if you do not already have one, it's critical to your success in interviewing!
When practicing, you are advised to treat it like a real coding interview and check through thoroughly before submitting. Consider even manually coming up with some test cases and running through them to verify correctness!
Week 1 - Sequences
In week 1, we will start off easy and do a mix of easy and medium questions on arrays and strings. Arrays and strings are the most common types of questions to be found in interviews; gaining familiarity with them will help in building strong fundamentals to better handle tougher questions.
Optional
Week 2 - Data Structures
The focus of week 2 is on linked lists, strings and matrix-based questions. The goal is to learn the common routines dealing with linked lists, traversing matrices and sequence analysis (arrays/strings) techniques such as sliding window.
Week 3 - Non-Linear Data Structures
The focus of week 3 is on non-linear data structures like trees, graphs and heaps. You should be familiar with the various tree traversal (in-order, pre-order, post-order) algorithms and graph traversal algorithms such as breadth-first search and depth-first search. In my experience, using more advanced graph algorithms (Dijkstra's and Floyd-Warshall) is quite rare and usually not necessary.
Optional
Week 4 - More Data Structures
Week 4 builds upon knowledge from previous weeks but questions are of increased difficulty. Expect to see such level of questions during interviews. You get more practice on more advanced data structures such as (but not exclusively limited to) heaps and tries.
Optional
Week 5 - Dynamic Programming
Week 5 focuses on Dynamic Programming (DP) questions. Personally, as an interviewer, I'm not a fan of DP questions as they are not really applicable to practical scenarios and frankly if I were made to do the tough DP questions during my interviews I'd not have gotten the job. However, companies like Google still ask DP questions and if joining Google is your dream, DP is unavoidable.
DP questions can be hard to master and the best way to get better at them is... you guessed it - practice! Be familiar with the concepts of memoization and backtracking.
Practically speaking the return of investment (ROI) on studying and practicing for DP questions is very low. Hence DP questions are less important/optional and you should only do them if you're very keen to have all bases covered.
During the Coding Interview
Congratulations, you are ready to put your skills into practice! In a real coding interview, you will be given a technical question by the interviewer, write code in a real-time collaborative editor (phone screen) or on a whiteboard (on-site) to solve the problem within 30–45 minutes. This is where the real fun begins!
Your interviewer will be looking out for signals that you fit the requirements of the role and it is up to you to display those signals to them. Initially, it may feel weird to be talking while you are coding as most programmers do not have the habit of explaining out loud as they are typing code. However, it is hard for the interviewer to know what you are thinking just by looking at the code that you type. If you communicate your approach to the interviewer before you start coding, you can validate your approach with them and the both of you can agree upon an acceptable approach.
Before the interview (remote)
For phone screens/remote interviews, prepare paper and pen/pencil to jot down and visualize stuff. If you are given a question on trees and graphs, it usually helps if you draw out some examples of the data structure given in the question.
Use earphones and make sure you are in a quiet environment. You do not want to be holding a phone in one hand and only be able to type with the other. Try avoiding using speakers because if the echo is bad, communication is harder and repeating of words will just result in loss of valuable time.
Self-introduction
Prepare a self-introduction by following the self-introduction section.
Upon receiving the question
Many candidates jump into coding the moment they hear the question. That is usually a big mistake. Take a moment to repeat the question back at the interviewer and make sure that you understand exactly what they are asking. Repeating back/rephrasing the question will reduce the chances of miscommunication.
Always seek clarification about the question upon hearing it even if it you think it is clear to you. You might discover something that you have missed out and it also sends a signal to the interviewer that you are a careful person who pays attention to details. Some interviewers deliberately omit important details to see if you ask the right questions.
Some common questions you can ask:
How big is the size of the input?
How big is the range of values?
What kind of values are there? Are there negative numbers? Floating points? Will there be empty inputs?
Are there duplicates within the input?
What are some extreme cases of the input?
Can I destroy the original array/graph/data structure?
How is the input stored? If you are given a dictionary of words, is it a list of strings or a Trie?
After you have sufficiently clarified the scope and intention of the problem, explain your high-level approach to the interviewer even if it is a naive solution. If you are stuck, consider various approaches, and explain out loud why it will/will not work. Sometimes your interviewer might drop hints and lead you towards the right path.
Start with a brute force approach, communicate it to the interviewer, explain the time and space complexity and why it is bad. It is unlikely that the brute force approach will be one that you will be coding. At this point, the interviewer will usually pop the dreaded "Can we do better?" question, meaning that they are looking for a more optimal approach. In my opinion, this is usually the hardest part of the interview. In general, look for repeated work and try to optimize them by potentially caching the calculated result somewhere and reference it later, rather than having to compute it all over again. There are some tips on tackling topic-specific questions that I dive into details below.
Only start coding after you and your interviewer have agreed on an approach and they have given you the green light.
What to do when stuck
Getting stuck during coding interviews is extremely common. But do not worry, that is part of the process and is a test of your problem-solving abilities. Here are some tips to try out when you are stuck:
Talk through what you initially thought might work and explain why it doesn't
This can help guide you on the right track by avoiding the pitfalls
Come up with more test cases and write them down
A pattern may emerge
Think about how you would solve it without a program
You may spot a pattern and come up with a general algorithm for it
Recall past questions related to the topic, what similar questions in the past have you encountered and what techniques did you use?
Enumerate through the common data structures and whether they can be applied to the question
Dictionaries/maps are extremely common in making algorithms more efficient
Look out for repeated work and determine if you can cache those computations
Trade-off memory for speed
While coding
Write your code with good coding style. Reading code written by others is usually not an enjoyable task. Reading horribly formatted code by others makes it worse. Your goal is to make your interviewer understand the code you have written so that they can quickly evaluate if your code does what you say it does and whether it solves the given problem. Use clear variable names, avoid single letter names unless they are for iteration. However, if you are coding on a whiteboard, you might not want to use extremely verbose variable names for the sake of reducing the amount you have to write. Abbreviations are usually fine if you explain what it means beforehand.
Always be explaining what you are currently writing/typing to the interviewer. This is not about literally reading out what you are typing to the interviewer. Talk about the section of the code you are currently implementing at a higher level, explain why it is written as such and what it is trying to achieve.
While coding, if you find yourself copying and pasting code, consider whether it is necessary. If you find yourself copying and pasting one large chunk of code spanning multiple lines, it is usually an indicator that you can refactor by extracting those lines into a function and defining parameters for the differences in them. If it is just a single line you copied, usually it is fine. Do remember to change the respective variables in your copied line of code where relevant. Copy-paste errors are a common source of bugs even in day-to-day coding!
After coding
After you have finished coding, do not immediately announce to the interviewer that you are done. In most cases, your code is usually not perfect and contains some bugs or syntax errors. What you need to do now is to review your code.
Firstly, look through your code from start to finish as if it is the first time you are seeing it, as if it was written by someone else and you are trying to spot bugs in it. That is exactly what your interviewer will be doing. Look through and fix any minor issues you may find.
Next, come up with small test cases and step through the code (not your algorithm!) with those sample input. What interviewers usually do after you have finished coding would be to get you to write tests. It is a huge plus if you write tests for your code even before they prompt you to do so. You should be emulating a debugger when stepping through and jot down or say out the values of the important variables as you step through the lines of code.
If there are duplicated chunks of code in your solution, it would be a good chance to refactor it and demonstrate to the interviewer that you are one who values code quality. Also, look out for places here you can do short-circuit evaluation.
Lastly, give the time/space complexity of your code and explain why it is such. You can even annotate certain chunks of your code with the various time/space complexities to demonstrate your understanding of your code and the APIs of your chosen programming language. Explain any trade-offs in your current approach vs alternative approaches, possibly in terms of time/space.
If your interviewer is happy with the solution, the interview usually ends here. It is also not uncommon that the interviewer asks you extension questions, such as how you would handle the problem if the whole input is too large to fit into memory, or if the input arrives as a stream. This is a common follow-up question at Google where they care a lot about scale. The answer is usually a divide-and-conquer approach — perform distributed processing of the data and only read certain chunks of the input from disk into memory, write the output back to disk, and combine them later.
Coding Signals
The point of interviews is for interviewers to extract signals from certain candidate behaviors. In coding interviews, the signals can be broadly classified into the following categories: Problem Solving, Technical Competency, Testing, and Communication.
When interviewers take down interview feedback, these are likely what is on their feedback sheet.
Problem-solving
Understanding the problem
👍 Understood the key aspects of the problem quickly
👎 Had difficulty in understanding the key aspects of the problem
Solution/approach
👍 Approached the problem in a systematic and logical manner
👎 Did not demonstrate a logical thought process for approaching the problem
Improving the solution
👍 Suggested a more efficient solution when prompted, or proactively coming up with a better solution
👎 Had difficulty in coming up with a more efficient solution even after being prompted
Trade-offs analysis
👍 Explained the trade-offs of different approaches clearly and correctly
👎 Failed to describe trade-offs of different approaches
Hinting
👍 Did not require any major hints
👎 Needed plenty of hints
Technical competency
Speed
👍 Quickly implemented a working solution
👎 Was not able to complete the solution
Correctness/Accuracy
👍 Implemented the solution correctly (e.g., working solution, minimal bugs)
👎 Unable to correctly implement a solution (e.g., non-working solution, incorrect logic, and/or serious bugs)
Complexity analysis
👍 Able to determine the algorithmic time and space complexity
👎 Was not able to determine the algorithmic time and space complexity (explain why TC came up with such an answer)
Mastery of chosen programming language
👍 Demonstrated mastery of the chosen programming language
👎 Does not seem to be familiar with the chosen programming language
Implementation
👍 Implementation was clean and straightforward
👎 Implementation was unnecessarily complex and/or messy
Coding style
👍 Coding style was neat (proper indentation, spacing and no bad practices)
👎 Coding style was messy (inconsistent indentation, weird spacings, etc)
Testing
Common cases
👍 Tested their code against various typical cases
👎 Failed to test the code against typical cases
Corner cases
👍 Found and handled corner/edge cases
👎 Failed to consider corner/edge cases
Self-correction
👍 Identified and corrected bugs in the code (where applicable)
👎 Was not able to discover and fix bugs even after being prompted
Communication
Clarify problem
👍 Appropriately asked good, clarifying questions about the problem
👎 Failed to confirm understanding/ask appropriate questions
Communicating approach
👍 Able to explain overall approach, technical terms and acronyms (where applicable)
👎 Failed to effectively explain overall approach, technical terms and acronyms (where applicable)
Algorithms Introduction
This section dives deep into practical tips for specific topics of algorithms and data structures which appear frequently in coding questions. Many algorithm questions involve techniques that can be applied to questions of similar nature. The more techniques you have in your arsenal, the higher the chances of passing the interview. They may lead you to discover corner cases you might have missed out or even lead you towards the optimal approach!
For each topic, study links are recommended to help you master the topic. There is a list of recommended common questions to practice which in my opinion is highly valuable for mastering the core concepts for the topic.
If you are interested in how data structures are implemented, check out Lago, a Data Structures and Algorithms library for JavaScript. It is pretty much still WIP but I intend to make it into a library that is able to be used in production and also a reference resource for revising Data Structures and Algorithms.
General tips
Clarify any assumptions you made subconsciously. Many questions are under-specified on purpose.
Always validate input first. Check for invalid/empty/negative/different type input. Never assume you are given the valid parameters. Alternatively, clarify with the interviewer whether you can assume valid input (usually yes), which can save you time from writing code that does input validation.
Are there any time/space complexity requirements/constraints?
Check for off-by-one errors.
In languages where there are no automatic type coercion, check that concatenation of values are of the same type: int/str/list.
After finishing your code, use a few example inputs to test your solution.
Is the algorithm meant to be run multiple times, for example in a web server? If yes, the input is likely to be preprocess-able to improve the efficiency in each call.
Use a mix of functional and imperative programming paradigms:
Write pure functions as much as possible.
Pure functions are easier to reason about and can help to reduce bugs in your implementation.
Avoid mutating the parameters passed into your function especially if they are passed by reference unless you are sure of what you are doing.
However, functional programming is usually expensive in terms of space complexity because of non-mutation and the repeated allocation of new objects. On the other hand, imperative code is faster because you operate on existing objects. Hence you will need to achieve a balance between accuracy vs efficiency, by using the right amount of functional and imperative code where appropriate.
Avoid relying on and mutating global variables. Global variables introduce state.
If you have to rely on global variables, make sure that you do not mutate it by accident.
Generally, to improve the speed of a program, we can either: (1) choose a more appropriate data structure/algorithm; or (2) use more memory. The latter demonstrates a classic space vs. time tradeoff, but it is not necessarily the case that you can only achieve better speed at the expense of space. Also, note that there is often a theoretical limit to how fast your program can run (in terms of time complexity). For instance, a question that requires you to find the smallest/largest element in an unsorted array cannot run faster than O(N).
Data structures are your weapons. Choosing the right weapon for the right battle is the key to victory. Be very familiar about the strengths of each data structure and the time complexities for its various operations.
Data structures can be augmented to achieve efficient time complexities across different operations. For example, a hash map can be used together with a doubly-linked list to achieve O(1) time complexity for both the get and put operation in an LRU cache.
Hashmaps are probably the most commonly used data structure for algorithm questions. If you are stuck on a question, your last resort can be to enumerate through the common possible data structures (thankfully there aren't that many of them) and consider whether each of them can be applied to the problem. This has worked for me sometimes.
If you are cutting corners in your code, state that out loud to your interviewer and say what you would do in a non-interview setting (no time constraints). E.g., I would write a regex to parse this string rather than using split() which may not cover all cases.
References
http://blog.triplebyte.com/how-to-pass-a-programming-interview
http://www.geeksforgeeks.org/must-do-coding-questions-for-companies-like-amazon-microsoft-adobe/
Array
Notes
Is the array sorted or partially sorted? If it is, some form of binary search should be possible. This also usually means that the interviewer is looking for a solution that is faster than O(n).
Can you sort the array? Sometimes sorting the array first may significantly simplify the problem. Make sure that the order of array elements do not need to be preserved before attempting a sort.
For questions where summation or multiplication of a subarray is involved, pre-computation using hashing or a prefix/suffix sum/product might be useful.
If you are given a sequence and the interviewer asks for O(1) space, it might be possible to use the array itself as a hash table. For example, if the array only has values from 1 to N, where N is the length of the array, negate the value at that index (minus one) to indicate presence of that number.
Arrays are sequences
Are there duplicate values in the array, would it affect the answer?
When using an index to iterate through array elements, be careful not to go out of bounds.
Be mindful about slicing or concatenating arrays in your code. Typically, slicing and concatenating arrays require O(n) time. Use start and end indices to demarcate a subarray/range where possible.
Sometimes you can traverse the array from the right rather than from the left.
Master the sliding window technique that applies to many subarray problems.
When you are given two arrays to process, it is common to have one index per array (pointer) to traverse/compare both. For example, we use the same approach to merge two sorted arrays.
Corner cases
Empty sequence
Sequence with 1 or 2 elements
Sequence with repeated elements
Recommended LeetCode questions
Binary
Study links
Notes
Questions involving binary representations and bitwise operations are asked sometimes and you must be familiar with how to convert a number from decimal form into binary form (and vice versa) in your chosen programming language.
Some helpful utility snippets:
Test kth bit is set: num & (1 << k) != 0.
Set kth bit: num |= (1 << k).
Turn off kth bit: num &= ~(1 << k).
Toggle the kth bit: num ^= (1 << k).
To check if a number is a power of 2, num & num - 1 == 0.
Corner cases
Be aware and check for overflow/underflow
Negative numbers
Recommended LeetCode questions
Dynamic Programming
Study links
Notes
Dynamic Programming (DP) is usually used to solve optimization problems. The only way to get better at DP is to practice. It takes some amount of practice to be able to recognize that a problem can be solved by DP.
Sometimes you do not need to store the whole DP table in memory, the last two values or the last two rows of the matrix will suffice.
Recommended LeetCode questions
0/1 Knapsack
Geometry
Notes
When comparing euclidean distance between two pairs of points, using dx2 + dy2 is sufficient. It is unnecessary to square root the value.
To find out if two circles overlap, check that the distance between the two centers of the circles is less than the sum of their radii.
Sample questions
You have a plane with lots of rectangles on it, find out how many of them intersect.
Which data structure would you use to query the k-nearest points of a set on a 2D plane?
Given many points, find k points that are closest to the origin.
How would you triangulate a polygon?
Graph
Study links
Notes
Be familiar with the various graph representations, graph search algorithms and their time and space complexities.
You can be given a list of edges and tasked to build your own graph from the edges to perform a traversal on. The common graph representations are:
Adjacency matrix.
Adjacency list.
Hashmap of hashmaps.
A tree-like diagram could very well be a graph that allows for cycles and a naive recursive solution would not work. In that case you will have to handle cycles and keep a set of visited nodes when traversing.
Graph search algorithms:
Common - Breadth-first Search, Depth-first Search
Uncommon - Topological Sort, Dijkstra's algorithm
Rare - Bellman-Ford algorithm, Floyd-Warshall algorithm, Prim's algorithm, Kruskal's algorithm
In coding interviews, graphs are commonly represented as 2-D matrices where cells are the nodes and each cell can traverse to its adjacent cells (up/down/left/right). Hence it is important that you be familiar with traversing a 2-D matrix. When traversing the matrix, always ensure that your current position is within the boundary of the matrix and has not been visited before.
A simple template for doing depth-first searches on a matrix goes like this:
defdfs(matrix):
# Check for an empty graph.
ifnot matrix:
return []
rows, cols = len(matrix), len(matrix[0])
visited = set()
directions = ((0, 1), (0, -1), (1, 0), (-1, 0))
deftraverse(i, j):
if (i, j) in visited:
return
visited.add((i, j))
# Traverse neighbors.
for direction in directions:
next_i, next_j = i + direction[0], j + direction[1]
if0 <= next_i < rows and0 <= next_j < cols:
# Add in your question-specific checks.
traverse(next_i, next_j)
for i in range(rows):
for j in range(cols):
traverse(i, j)
A similar template for doing breadth-first searches on the matrix goes like this:
from collections import deque
defbfs(matrix):
# Check for an empty graph.
ifnot matrix:
return []
rows, cols = len(matrix), len(matrix[0])
visited = set()
directions = ((0, 1), (0, -1), (1, 0), (-1, 0))
deftraverse(i, j):
queue = deque([(i, j)])
while queue:
curr_i, curr_j = queue.popleft()
if (curr_i, curr_j) notin visited:
visited.add((curr_i, curr_j))
# Traverse neighbors.
for direction in directions:
next_i, next_j = curr_i + direction[0], curr_j + direction[1]
if0 <= next_i < rows and0 <= next_j < cols:
# Add in your question-specific checks.
queue.append((next_i, next_j))
for i in range(rows):
for j in range(cols):
traverse(i, j)
NOTE: While DFS is implemented using recursion in this sample, it could also be implemented iteratively like BFS. The key difference between the algorithms lies in the underlying data structure (BFS uses a queue while DFS uses a stack). The deque class in Python can function as both a stack and a queue
For additional tips on BFS and DFS, you can refer to this LeetCode post
Corner cases
Empty graph
Graph with one or two nodes
Disjoint graphs
Graph with cycles
Recommended LeetCode questions
Hash Table
Sample questions
Describe an implementation of a least-used cache, and big-O notation of it.
A question involving an API's integration with hash map where the buckets of hash map are made up of linked lists.
Implement data structure Map storing pairs of integers (key, value) and define following member functions in O(1) runtime: void insert(key, value), void delete(key), int get(key), int getRandomKey(). (Solution)
Object-Oriented Programming
Sample questions
How would you design a chess game? What classes and objects would you use? What methods would they have?
How would you design the data structures for a bookkeeping system for a library?
Explain how you would design a HTTP server? Give examples of classes, methods, and interfaces. What are the challenges here?
Discuss algorithms and data structures for a garbage collector?
How would you implement an HR system to keep track of employee salaries and benefits?
How would you implement an Elevator system?
Recursion
Notes
Recursion is useful for permutation, because it generates all combinations and tree-based questions. You should know how to generate all permutations of a sequence as well as how to handle duplicates.
Remember to always define a base case so that your recursion will end.
Recursion implicitly uses a stack. Hence all-recursive approaches can be rewritten iteratively using a stack. Beware of cases where the recursion level goes too deep and causes a stack overflow (the default limit in Python is 1000). You may get bonus points for pointing this out to the interviewer. Recursion will never be O(1) space complexity because a stack is involved, unless there is tail-call optimization (TCO). Find out if your chosen language supports TCO.
Recommended LeetCode questions