At the technical interviews

Now that you have a better understanding of the theory behind time and memory complexity, let’s talk about how to best apply what you’ve learned at your interview.

Computing and discussing the complexity of a solution will come up very often at tech interviews. You should be able to identify the time and memory complexity of a solution fairly fast. It should not be taking you a long time. The answer should come to you almost instantly. Keep in mind that no complicated math is expected to be needed here. Don’t expect that someone will require you to use the Master Theorem, for example. Most likely, with very few exceptions, we are talking standard complexities here.

Don’t worry if you don’t feel confident enough right now. Training is the best way to become really smooth when it comes to computing the complexity of a solution. As you solve problems using the Algorithm Design Canvas, always make sure to fill in the box about complexity for each solution you design. Don’t skip this vital step. Doing this will help you get better.

One more thing: practice shows that usually time complexity is somewhat more discussed. However, you must remember that very often there is a tradeoff between time and memory. A solution can be tweaked to use more memory and become faster and vice versa. Because of that, both complexities are important. You may even be in a situation where your solution can be pushed in any of the two directions. In such cases, it’s wise to ask the interviewer which resource is more valuable. The answer will hopefully allow you to decide how to shape your solution.

Summary

In this section you learned:

• Why time and memory complexity are so important and where they fit in the coding interview.
• Given an algorithm, how to figure out its complexity.
• Given an algorithm’s complexity, build up the intuition about whether that complexity is “sufficient”: would it work fast enough and consume reasonable amounts of memory given the algorithm’s constraints.