How to answer time and space complexity questions in coding interviews?

Photo by ThisisEngineering RAEng on Unsplash
  1. Time and Space complexities of major algorithms,
  2. Understanding different variables impacting your code complexities,
  3. Code improvement based on complexity

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.

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;

Good Luck!!

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Navita Pareek

Navita Pareek

Started as a Software Engineer, now an Entrepreneur.