If we are given hints on the runtime requirement of a problem during interviews, we can roughly deduce the algorithm as follows.
Constant time complexity. Could be
- Hashmap lookup
- Finding and applying math formula
log(N) grows VERY slowly.
log(1,000,000) is only about
20. In fact, lookup by primary key in a relational database is
log(N) (many mainstream relational databases such as postgres use B-trees for indexing by default, and search in B-tree is
In coding interviews,
log(N) typically means
- Binary search or variant
- Balanced binary search tree lookup
Linear time normally means looping through a linear data structure a constant number of times. Most commonly this means
- Going through array/linked list
- Two pointers
- Some types of greedy
- Tree/graph traversal
- Heap push/pop
Ktimes. When you encounter problems that look for the "top K elements", you can usually solve them with pushing and popping to a heap,
Ktimes, resulting in
O(K log(N))runtime. e.g., K closest points, merge K sorted lists.
- Binary search K times.
- Sorting. The default sorting algorithm's expected runtime in all mainstream languages is
N log(N). For example, java uses a variant of merge sort for object sorting and a variant of quick sort for primitive type sorting.
- Divide and conquer with a linear time merge operation. Divide is normally
log(N), and if merge is
O(N)then the overall runtime is
O(N log(N)). An example problem is smaller numbers to the right.
Also called quadratic time.
- Nested loops, e.g., visiting each matrix entry
- Many brute force solutions
N < 1000, this is actually not that bad for modern computers. In fact, you can probably pass most Leetcode tests with quadratic time for small
Ns. However, in an interview, your solution usually has to do better than quadratic time to impress the interviewer if there is a better solution.
Grows very rapidly. Often requires memoization to avoid repeated computations and reduce complexity.
- Combinatorial problems, backtracking, e.g. subsets
Grows insanely rapidly. Only solvable by computers for small
N. Often requires memoization to avoid repeated computations and reduce complexity.
- Combinatorial problems, backtracking, e.g. permutations