Tech Interviewer: I’m looking for a solution that’s $O(log (n))$.
If you’ve ever gotten a tip like this and not been able to use it, here’s what the interview feedback most likely looked like:
“The candidate couldn’t answer my question. Despite all the hints I gave.”
For tech interview problems, being given the run-time of the solution should be a really big hint. If you’re told the solution is $O(log(n))$ then you should be thinking of a binary search tree, or a heap, or some algorithm that eliminates half the choices on each step (like binary search). Other run times should give you similar thoughts (e.g. if you’re told something is at best $O(n^3)$, you should be thinking possibly three nested for loops or something similar).
Asymptotic analysis is important, not only for tech interviews but for real life software engineering. Software engineers at top companies attend design reviews as much as once per week. During these design reviews, solutions are brainstormed, analyzed quickly, and then evaluated to choose the ones that have the best trade-offs. If you can’t analyze quickly, keeping up in these is hard.
Interview Tip: Know the asymptotic runtimes for operations on basic data structures and also know why those runtimes are the case
There are many data structures, but some of the most commonly used (especially during interviews) and thus important to understand are:
- ArrayList (or vector)
- Linked List
- Heap
- Hash Table
- Binary Search Tree
You should understand the asymptotic run times for each of the common operations and why those run times are correct (e.g. why is inserting into a vector O(1) amortized?) hold.
This leetcode problem is a very commonly asked interview question that is pretty hard to solve without a knowledge of these run times.
Interview Tip: Know the mergesort analysis
One of the most common root causes for failing analysis based questions is not understanding why merge sort takes $O(n \space log(n))$ time. Because merge sort is very similar to many divide and conquer algorithms, and most interviewers have come across some divide and conquer algorithms in the wild, it’s easy for interviewers to come up with their own unique questions that have a similar analysis to merge sort. A quick survey of a few of my friends who work and do interviews at top 4 companies confirmed that a misunderstanding of merge sort’s analysis is one of the top reasons for failing candidates.
The best resource I know of to teach yourself merge sort’s analysis is section 2.3.2 of Introduction to Algorithms. This section of khan academy is also useful.
Interview Tip: Understand the most common amortized analyses
The distinction between an amortized run time and one that isn’t amortized is important. Understanding that inserting into a vector is $O(1)$ amortized, and might actually require $O(n)$ time for a single call, can be very important in certain places. The same goes for inserting into a hash table.
This stackexchange answer has a pretty good explanation of why inserting into a vector is amortized $O(1)$. The amortized analysis chapter (chapter 17) of Introduction to Algorithms is also a good resource.