Thu 28 July 2016 | -- (permalink)
These are my notes on two frequent topics from a month of software engineering interviews.
Backtracking is a recursive algorithm used to search through possible sets of paths until the one we want is found.
We can think of it as exploring an unknown maze methodically for hidden treasures. Whenever we come to a fork, we try each of the crossroads. If one leads to a dead end, simply backtrack and attempt the next crossroad.
Problems which make use of backtracking usually seem complicated at first glance due to the large number of possible paths to a solution. Some examples of these are Sudoku, subset generation and permutation generation.
Backtracking also lends itself well to dynamic programming if different forks lead to the same location.
- The final result can usually be constructed in two ways: The first way is to pass a list by reference, and append the sub-result to the list whenever the base case is reached. We can also return the value instead.
- We might need a way to store partially built outputs. That can be done by passing a
currentvariable into the recursive backtracking call.
- Depth First Search is a specific form of backtracking applicable to graphs.
- You often find yourself using a for loop / if-elses to generate forks.
Array problems are extremely common.
- If your algorithm is O(N^2) or worse, it often means you are recomputing some values over and over. Try doing some preprocessing such as building a cumulative sum array, or finding the total sum.
- Finding two non-repeating elements in an array of repeating elements demonstrates an interesting application of the XOR operator. XORing every element results in duplicated pairs cancelling out.
- If we need to solve for two unknowns, consider building two equations using the sum and product of the entire array.