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 .
Below are common tags (sorted by number of problems being asked during interview based on my experience). there are much more listed on leetcode
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 .
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.
Within sorted array find some value , usually fall into this category .
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 .
Given dictionary , build the Trie , do word search or frequency .
Use min or max stack to compare the top 1 in stack while looping through some array.
common problems are like find cycle, common node between 2 link list , reverse , etc .
The idea isto use “greedy thinking” find the maximum or minimum .
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
maintain 2 index while looping array or string
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
“Group” the parents to the same “root-parent” while finding parent for child node
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.
while traverse graph remove the “out degree=0”
use bit operation to solve the issue . e.g. bit mask
How to leet the issues?
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 .
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 .
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 !