How to Estimate the solutions time complexity [Technique Tuesday]
This is something I do all the time for my mental peace
What’s up my amazing readers,
I really appreciate how consistent you guys have been with the support. I see the stats, and I see a lot of you checking in regularly with the emails/posts to stay updated. That consistency (combined with the high-quality information in this newsletter) will definitely help you.
For this week’s technique, we will go over a technique that I love using as I’m solving problems. It acts as a sanity check for my solution. This technique is definitely super useful in interviews where you have to solve multiple questions within a given time frame. In such cases, you need to be reasonably sure that your solutions are at least close to optimal. So let’s go over the technique, when you should use it, and some important things to remember.
The technique
The technique is relatively simple to understand. As I read the question, I start estimating what kind of time/space complexity the solution will have. As I start solving more of the problem/start coming up with solutions, I update my estimate for the complexity. Obviously, once I finish the question, I will just calculate the complexity normally.
Why do I do this
Some of you might be very confused by this technique. What good is this estimation? Let’s get into it.
As you have to go through stages of coding interviews, you will be expected to solve multiple questions within a time frame (normally 45minutes - 1hour). There is always a chance that you’re given a tricky question, for which you discover a solution. You should don’t know if that solution is the most optimal. In such cases, you don’t want to rely on the interviewer to tell you, because interviewers are evil.
In such cases, I like to use this technique to be reasonably confident that I have an optimal solution (or that I’m at least close) and move on to another question. Thus if you have a lot of questions you have to work through, this technique will serve you well.
How to do it
The technique relies on two things: your intuition and your technical knowledge. A good way to develop them is to get a premium subscription here, for 20% off. That will give you access to detailed solutions, discounted mock interview rates, and exclusive content, which will supercharge your learning.
What’s the next step? Read the question. Very careful. Take note of any important details. This will help you estimate the complexity. For example, if the question needs to traverse the whole list/data structure, then you know that your time complexity is at least O(n). Similarly, when you’re sure that you have to do a certain operation, you know for a fact that your time complexity will be at least the time complexity of that necessary operation.
Once you hit this complexity floor, move on. Move to that next problem. Remember, it’s better that you solve 3 questions decently well, over solving 1 question perfectly but not covering other questions.
Considerations
As you use this technique, keep in mind certain things. Firstly, for this approach to work, you must have developed your skills to a certain point. That will allow you to identify the correct data structures, algorithms, and procedures. Some of you are new here, and not at that level yet. No shame in that, but you will be better off first focusing on the basics. Bookmark this technique, come back to it later, once you’re better.
Secondly, assuming you’re at the level where this technique is useful to you, you have to learn to make a decision. Once you do reach this “complexity floor”, you will have to decide whether to move on to the next question or keep trying to optimize the current question. This will be based on a variety of factors. Here are a few.
How much time do you have left in the interview?
How many questions do you have left? What is the breakdown of the ones left? For many interviews, you will be given a detailed syllabus of what topics might be covered, and the level expected.
Will your interviewer let you come back to the problem later if you have time?
How are you feeling? Don’t overlook this. If you aren’t feeling too good about the question, cut your losses and move on. Don’t waste your time on it. If you’re feeling good about the question, then it makes sense to spend longer on the problem.
Lastly, I will end with a cautionary tale. This approach is great for taking a birds-eye view, getting the macro analysis of the question. It can be easy to lose the micro in such cases, however. This is something that happened to me during an interview. For one of the questions, I (correctly) deduced that the time complexity for the problem would be O(n). However, in the final operation, I added an extra O(n) operation, for something that could be calculated in O(1) time. The overall time complexity stayed O(n) which is why I missed it. The only reason I caught my error was that I had 15 minutes left in that assessment, so I had the time to go through my solutions.
When you use this technique, make sure you remember that such mistakes are possible. Use the time saved by this technique to go through and optimize your solutions later.
Closing
This technique will allow you to play to your strengths by giving you a rough guide on when you can safely jump from a tricky question and have more time to play to your strengths. But at the same time, you have to remember that it is just that. A guide. And it is a guide that depends that relies heavily on your knowledge and decision making. The only way to improve them is through high-quality practice (and Math Mondays!!).
If you liked this post, make sure you fill out this survey. It’s anonymous and will take 2 minutes of your time. It will help me understand you better, allowing for better content.
https://forms.gle/XfTXSjnC8W2wR9qT9
Happy Prep. I’ll see you at your dream job.
The One with the best Tricks/Techniques,
Devansh <3
To make sure you get the most of Technique Tuesdays, make sure you’re checking in the rest of the days as well. Leverage all the techniques I have discovered through my successful tutoring to easily succeed in your interviews and save your time and energy by joining the premium subscribers down below. Get a discount (for a whole year) using the button below
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75