Complexity
For every idea you have at an interview, it’s super important to be able to evaluate its efficiency. Efficiency is measured by computing the underlying algorithm’s time and memory complexity.
Why is complexity so important?
Solving problems is not just about finding a way to compute the correct answer. The solution should work quickly enough and with reasonable memory usage. Otherwise, even the smartest solution is not useful. Therefore, you have to show the interviewer two things:
- Your solution is good enough in terms of speed and memory.
- You are capable of evaluating the time and memory complexity of various algorithmic solutions.
Usually, if you fail to evaluate these parameters of your solutions this will reduce your chances of passing a technical interview. The interviewer needs to know that if you get hired, you will be able to choose wisely the solutions that you implement.
Essential readings
If you feel unsure about your knowledge in this topic we have prepared a separate section with some explanations for you. It is called Computational Complexity and comes right after this section.
In it you will find a few lessons and links to very useful resources that will give you more information. In the lessons we provide you will also find some guidance about how to discuss complexities at your tech interviews.
We’ve also compiled the Complexity Handout, which includes the complexities of many of the best-known algorithms. Like with all handouts, feel free to print it out and reference it. However, keep in mind that there’s zero value in you just memorizing these. Instead, read the theoretical articles and make sure you can come up with these complexities yourself.
Download the Complexity Handout (PDF).
Example
We will continue with the example ZigZag task and how complexity can be evaluated for it at an interview. You may want to go through the Computational Complexity section first if you are not familiar with everything in the video.
What’s next
In the next lesson, we’ll finally turn our attention to writing some code! Like with all other areas of the Canvas, there are some rules on how to do it right, as well as some common misconceptions about writing code during interviews. Read on!