Why we practice algorithm? (not just for interview)
Solving Algorithm problems could help train our mind be used to useful datastructure and algorithms, be ready to use them to solve issues .
instead of CRUD works ,the leetcode problems usually requires good understanding of data structures like tree, graph, heap, even though most of them are unlikely being used in daily work, but when the requirement comming in(path finding, shorted path (weight based), graph/tree traverse, reference counting etc) it will helpful if we can come out with solutions fast and then compare the pros and cons to get an optimal solution.
so we need practise .
Problem Tags
Below are common tags (sorted by number of problems being asked during interview based on my experience). there are much more listed on leetcode
DFS
A classic way traverse tree or graph start from a node reach until end. or within a metrix finding the area by going up,down,left,right .usually every tree or graph or 0–1 metrix searching problem could be related to DFS .
BFS
Unlike DFS. BFS could be done with queue .Find the next reachable nodes, add into queue until queue is empty. unlike DFS, BFS focus more on all “next nodes” from current “parents” queue.
Binary Search
Within sorted array find some value , usually fall into this category .
Heap
When find max or min , or topK issue . usually this structure is available in the language you choose, can directly use it . java, c#, python etc. if not you can also build your heap .
Trie
Given dictionary , build the Trie , do word search or frequency .
Stack
Use min or max stack to compare the top 1 in stack while looping through some array.
Linklist
common problems are like find cycle, common node between 2 link list , reverse , etc .
Greedy
The idea isto use “greedy thinking” find the maximum or minimum .
Sliding window
use start and end position to track the “window” start and end position while looping array, need increase the start when match some condition ,usually need to track the window size also
Two pointers
maintain 2 index while looping array or string
Back Tracking
like DFS ,just that need loop through each possibilities for each recursion .This approach only useful for small amount of input values .
Devide and conquer
The idea is to find a partitioner and devide the issue into smaller ones (e.g. left and right), find the answer for each of them and “merge” the sub-answers . e.g. quick-sort
Union Find
“Group” the parents to the same “root-parent” while finding parent for child node
Dynamic programming
There is an array to store “previous answers” . it may not be easy to come out with this approach in the first time . but when we solved some issue with DFS or back tracking ,then we may find “some issue solved there should be a cache for these previous answers” . this is when DP come to be a solution.
Another pattern is “bottom-up” . try solve the problem with small amount of numbers, see if the answer, the trying to reuse previous answer to solve the problem with more numbers added in.
Topo sort
while traverse graph remove the “out degree=0”
Bit manipulation
use bit operation to solve the issue . e.g. bit mask
How to leet the issues?
By Tag
If not sure where to start ,on leetcode there are many tags (or started from the list above). clicking in each of them can focus only those issues .
so that you “reduced” the difficulty level by knowing where should find the answer (e.g. if choose DFS, you already know this issue should be solved by DFS approach)
Skip the low rating issues first
Those issues with low rating usually because poor description or not related to any algorithm or not a programming issue , e.g. pure math . can skip those issues first if you are not interested .
If you are preparing interview, focus on medium problems first
I have been interviewed with facebook , amazon, google ,microsoft ,indeed . all of them giving me some medium level leetcode problems , like topK (find 5th larges number among millions) , read4, longest palindrome str, binary search , graph traverse, Trie, string permutation, etc . you do not have to solve all the problems ,but make sure have a good understanding on the problems under the common tags .
A timeline
Give yourself time limit while solving issues (e.g. 20 mins) . this will put on a bit stress on yourself to come out with answer within given time, not unlimited .
Discuss
If you stuck , no worry , there are hundreds or thousands of good answers to each of the issue in “discuss tab” .
That’s all . Happy leet coding !
