Beginner (Constest score <= 1800):
Basic data structure
Array/Vector, Queue, Stack, Linked List, Sorted Map/TreeMap, UnSorted Map/HashMap, Priority Queue/Heap, Tree, Graph.
You may need to know the implementation details of Linked List, And you may need to know how to build a stack/queue from linked list.
For Sorted Map/TreeMap, UnSorted Map/HashMap, Priority Queue/Heap. You need to be familiar with API provided by your programming language.
Most of the languages don't support Tree and Graph natively. You need to know how to represent Tree and Graph by yourself.
Recursion
You may need to know how recursion works. And what is the relationship between recursion and stack. How to emulate a recursion call by stack.
You may need to know some classical Recursion algorithms. For example, Quick Sort, Preorder Vist, Inorder Visit, Postorder Vist， Euclidean Algorithm, and so on.
You may need to know how to use the memoization technique to implement Dynamic Programming in a top-down fashion. From my point of view, I think coming up with a top-down DP solution is much easier and more intuitive than traditional bottom-up DP.
Basic Algorithm Concept
Sort You may need to be familiar with several sort algorithms. For example, Bubble Sort, Insert Sort, Heap Sort, Merge Sort, and Quick Sort of course.
Breadth First Search You may need to know how to write a general BFS algorithm by Queue. And you may need to know some basic applications of BFS, for example, finding the shortest path in an unweighted graph.
Depth First Search You may need to know how to write a general DFS algorithm by Recursion. And you may need to know some basic applications of DFS, for example, Preorder visit.
Divide and Conquer This one is not very common in Leetcode. If you're not interested in. I think you can skip this topic. But you may want to know how to implement quicksort.
Dynamic Programming This is a notoriously well-known hard topic. The most difficult part is recognizing the problem is a DP problem. You have to do a lot of practice to get the intuition. I think we can start from the well know one, for example. Longest Common Subsequence, Longest Increasing Subsequence.
Greedy From my point of view. I think the greedy problem is the toughest one. You have to have good intuition to resolve the greedy problem. And it's commonly super hard to prove if the greedy is correct. I am not good at greedy problems at all. Luckily enough, there're not very many greedy problems in LC. We can start from the classical ones, for example, Dijkstra and course schedule (The first example in Introduction to Algorithms third edition, Chapter 16).
Binary search You need to find a good binary search template. And then the hard part becomes how to identify the problem is actually can be solved by binary search.
It's a lot of concepts here. Luckily, most of them are related to each other. For example, you don't need to learn Divide and Conquer independently. You can almost always learn Divide and Conquer with Recursion together. And most of the algorithm concepts are related to data structures very much, you can try to learn them together. For example, how to visit a tree by DFS (Preorder visit) or in a BFS way. (Level order visit)
I believe if you can be familiar with all the concepts mentioned above. You can at least reach a 1800+ rating. And it's may enough for Amazon interview from the statistical data shown before!
Intermediate level (Contest score 1800 - 2100)
If the main reason to do leetcode is for seeking new opportunities, I think it's already a good time to start. At this moment, you should already be familiar with most of the concepts mentioned above and should be comfortable with most of the medium problems. From my point of view, I think your algorithm skill should be good enough for most of the normal SED roles.
If you still want to pursue a breakthrough, then you may have to learn some "advanced" topics which may rarely be used in routine development. I think the 11 topics below may be helpful.
Difference Array
BIT Tree (Fenwick Tree)
Basic Math, such as the Sieve algorithm and inverse modular
Trie
Advance String Algorithms, such as KMP and Rolling Hash
Monotonic Stack
Sliding Window
Bit Manipulation
Union Set
Bitmask DP
Graph Algorithm, such as Floyd Algorithm, and Minimal Spanning Tree.
Top comments (0)