When coming into a tricky problem in coding interviews, you have no idea where to start with, and ugh, you mind just goes totally blank.
The good news? It always happens to the best of us. Here’s something I’d like to share.
Most interview algorithms are adopted from some coding practice websites like leetcode, codeforce, etc. On these websites, each problem has a runtime limitation, and this is what we can cheat on.
At most cases, an allowed executing time for a problem is 1 or 2 seconds, and we know that a cpu could calculate about 10^8 times per second. So We can guess a problem solution’r big O from input test case range because we have to write a program that is able to finish in 1 second.
The following is the cheating sheet.
|n <= 30, Exponential||DFS|
|n <= 100, O(n^3)||Dp, Floyed|
|n <= 1000, O(n^2)/O(nlogn)||DP, Binary Search|
|n <= 10^5, O(nlogn)||Binary Search, Heap, Map/Set, Binary Indexed Tree|
|n <= 10^6, O(n)||Two Pointers, Hash, KMP, Union Find, Heap, Dijkstra|
|n <= 10^9||mathematical Problem|
What I want to remind you is this does not apply to all questions. We don’t want to get stuck in real interviews. So, practice more interview questions on leetcode, and it gets easier and faster.