Do you know how bodybuilders build all that muscle? They choose the best exercises to do amongst an infinite set of possibilities.
So what are the squats and deadlifts of data structures? Here are the GOOD exercises:
1. Dynamic Programming
This is the most common topic for software engineering interviews. Many candidates are apprehensive about DP problems because they require thinking recursively.
For an interviewer, dynamic programming is great because coming up with a new recursive problem is easy. For a candidate, coming up with its answer in 30 minutes is hard.
2. Binary Tree
Probably as common as DP. Interviewers love them because they can literally see what the candidate is thinking. They test how a candidate converts their visual thinking to a programming solution.
Tree traversal, recursion, and finding ancestors/children are common sub-topics here. As a candidate, I think I want a tree problem. They are easy to solve if you are well prepared.
3. Graph Traversal
Almost all the graphs-related problems are on traversal, either Breath First Search (BFS) or Depth First Search (DFS).
Identifying a graph problem is difficult, but solving it is relatively simple. Some global pointers, a check on finding a node, and you should be good to go.
4. Greedy Algorithms
These algorithms are more about finding patterns. They are similar to dynamic programming in that sense. However, the solution is usually iterative and deals with the structure of the problem than a lot of math.
They typically require preliminary operations like sorting or aggregation before the pattern becomes apparent.
5. Ad-hoc Problems
Ad-hoc questions are either newly thought of or from a standard set of interview problems. They tend to test a candidate’s resolve. Solutions often comprise of finding patterns, applying algorithmic techniques, etc… Some honorary mentions are Linked Lists, Arrays, and Stacks.
That's it! Your problem set should cover these topics well.
Also, you really should avoid wasting your time on BAD exercise. Here are the leg presses of algorithms:
-1. Set Theory
Set problems are notoriously hard to understand. You are better off practicing graph algorithms and encapsulating set operations like add, delete, and update into a known set data structure (HashSet or TreeSet).
For an interviewer, set theory problems and hints are difficult to set. An abysmally low pass rate makes this a bad tool (Your manager will likely ask you why everybody who interviewers with you is failing).
-2. Combinatorics
The evil twin of dynamic programming shares a parent with Graphs. The problem with Combinatorics problems is...theory. If you can remember the formulae, or derive them on the spot, the problems look easy.
If not, you can spend 30 minutes staring the problem with no clue on how to make progress.
Interviewers avoid this topic like the plague (how do you share a hint on the formula?). Candidates either pass the question spectaculary or fail miserably, depending more on recollection than on the spot problem solving.
-3. String Problems
By far the worst set of problems designed for competition or interview questions. Most folks memorize (I am not joking) the code for finding a pattern in a string, or finding a palindrome efficiently.
How does that help find a good candidate? Curtain reveal --- IT DOESN'T.
-4. Bitwise Operators
Bitwise operators problems are contrived from set theory. You really have hit the bottom of the barrel when you need to contrive problems from Set Theory.
Benefit: You can add elements to a set, remove them, and find their existence in O(N/64) time instead of O(N) time.
Our response: "Thank you for the opportunity."
-5. Swap variables without a temporary variable
This is the WORST type of question you can get. I suggest asking the interviewer to change the question (seriously).
If they insist that you must solve it, you know the kind of management this company has.
Our response:
Me after coding the KMP algorithm.
As proved above, you need all the “Best of luck”s you can get.
So, best of luck!