How to answer time and space complexity questions in coding interviews?
It doesn’t matter which algorithm you are coding in the technical interview, there is always a follow-up question on finding the time and space complexity of the algorithm. Especially if you are preparing for FAANG or a similar big firms’ technical interview.
If you are not able to answer the right complexity then there is a big chance of rejection, even if you wrote your program very well. Answering the right complexity is your chance to prove your metal in coding as well as improve your code.
The best place to learn and practice complexities is chapter 6th of “Cracking the coding interview” book. It explains the complexities well and also has practice questions. You can easily become a pro in calculating the time and space complexities if you know and understand the following concepts;
- Time and Space complexity of different Data Structures,
- Time and Space complexities of major algorithms,
- Understanding different variables impacting your code complexities,
- Code improvement based on complexity
Now let’s touch on each basic concept.
Time and Space Complexity of different data structures
The first step is always to know the time and space complexities of different data structures as they are the building blocks of any algorithm. Understand the complexities of data structures like an array, HashSet, hashmap/dictionary and linkedlists. When you understand the reason behind these complexities, it will be very easy for you to decide on which data structure to use in the given scenario.
Time and Space Complexities of major algorithms
Even though you will never get any direct questions about the major algorithms in your interview question, but it is always a good idea to understand the complexities of sorting, searching and graph algorithms. It will get you in the practice to calculate the complexity of your own code. Also, it will help you in analyzing recursions, which is one place where even many good candidates get stuck. Thus getting the time and space complexities of the complex algorithms is your chance to shine in your technical interviews.
Understanding different variables impacting your code complexities
As an interviewer, I have always witnessed people using ’N’ as the only variable for their code complexity, even though ’N’ can mean different parameters in different scenarios. For example, if the algorithm involves sequential searching of a long string then ’N’ is the length of the string. But if our code is about the graph algorithm then ’N’ can be vertices count or edges count. Thus, it might be confusing for you and the interviewer.
The best way to make a clean complexity formula is to use totally different char for different parameters. For example, ‘s’ for string’s length, ‘v’ for graph vertices and ‘l’ of level in the tree structure. This will result in a very clean complexity and avoid any confusion.
Code improvement based on complexity
When we finish the code and then start analyzing each step for time and space complexity, this is our chance to optimize the code further. For example, if you are using recursion with super ugly complexity then this is the time you should think about storing the intermediate calculations, this is called memoization.
Watch the loopholes in answering a complexity question
Following is a quick list of the action items to avoid any mess in the time and complexity question;
Always make sure to mention both the time and space complexities of your code. Even if the interviewer has not asked the code complexity but you mentioned them, will give you extra points for attention to detail.
Recheck if asked for worst, best or average complexity. This is a trick to ask even for the best and average complexity, as most candidates only prepare for the worst complexity.
Check if any variable can be ignored from the complexity formula as it may have a constant value. I have seen many times when candidates consider variables for parameters that are actually constants. For example, considering the variable ’n’ as the number of possible unique chars in a string, which can be ignored as for ASCII codes, ‘n’ is always 256.
Lastly, let me provide you a cheatsheet which I always keep handy before an interview. Refer — https://www.bigocheatsheet.com/
I know there already exists a lot of material online on cracking interviews, so make your plan today and if you need a mentor then ping me on my linkedIn
You can also use platforms that can connect you to the existing FAANG employees.
You can find an article on How to crack Microsoft interview in just 2 months here
You can find an article on how to prepare and ace system design interviews here.
