My solutions to the algorithm problems.
- Do I need to handle invalid inputs?
- Does the array contain duplicate items?
- Do we allow 0 in the first digit?
For generating permutations without recursion, use a queue. In each iteration, get the length of the queue, pop them out one by one and addLast the generated values.
Consider carefully what the range is, e.g., for a coin count problem, we may need to start the index for 1 and use <= as the ending condition. Also, note that sometimes in DP the previous amount is invalid (e.g., knapsack), need to handle such invalid cases.
Could use the recursive backtracking approach by passing results
down:
- Starting from the 1st element, call 2 recursive functions (one with new element added and the other one without).
- When there are enough elements, add the current result to the
results
array and stop. - When there are not enough elements (
total number n - current number + current result length + 1 <= target number of elements in result
), only call the recursive function with the current element added. - Think about
n - curr + 1 + len <= k
in this way: at positioncurr
, we still haven - curr + 1
elements to visit. Ifk
is larger than the number of elements we have then there's no way we could reachk
elements.
Use DFS, maintaining the current items in the combination.
- End recursion when the sum is equal to (or larger than) the target value.
- Remember to make a copy of the current array when adding to the final results, since the current array keeps mutating.
- To avoid duplicated items, skip items that equal to its previous item.
- Example, target is
5
and input is[1, 1, 2, 2, 2]
, at the first2
, we enter the DFS with[2, 2]
remaining and do not skip the next2
. However, after coming back from that DFS, moving on to the second2
, there's no point doing DFS again at it since we've already included that in our previous search.
Use DFS, maintaining the visited items and avoid continuing on duplication.
- To avoid inserting duplicated item, sort the input array first so that we could easily check whether the current number has been processed.
- Maintain an array of visited items, if the previous item is equal to the current item and the previous item has been visited, stop. This is to eliminating every permutation except the one going through the duplicated items from the back to the front.
- Example:
[1, 1, 1, 2]
, when going deep into the recursion, unless we are going through[1, 1, 1]
from the back to the front, we will eventually come into the case where the previous item is visited before, thus an invalid case.
For problems that requires both subtrees and the relation between the parent and child nodes to meet some criteria, use the following procedure to shorten the code:
- If node is null, consider as "meeting the criteria".
- If one of two subtrees does not meet, negative result.
- If left is not null and left - parent relation does not meet, negative.
- Right side version of last step.
- Now, there can only be: left is null and right meets, right is null and left meets, left & right are both null, positive result.
- First find the last item greater than the item after it, then find the minimum item that is after and larger than it.
- Swap the last increasing index and the minimum larger index.
- Reverse everything after the last increasing index.
Note that when comparing the minimum item after
lastIncreasingIndex
that's larger than it, use>=
instead of>
, since we'd like to get the last item.
- Do not iterator through the whole set of words each time. Try to create possible new words from the current word and check if that new word is in the list.
- Each node does not hold a value, instead, it holds a boolean value indicating whether it's an end point (whole word), and a map from a character to one of its children.
- If we have a small alphabet, we could replace the map with an array of a fixed number of elements (equal to the alphabet size).
- Do not misuse the LinkedList methods
- The foreach loop is a syntax sugar for an iterator, however we do not have access to the iterator when usingthe foreach loop. The only way to remove items while iterating is to use an
Iterator
explicitly.
- Remember to assign the loop variable, do not mix up loop index and item in the list.
- Always remember to check when input is 0, 1 or null.
- When doing binary search, left should be set to mid + 1 if mid is less that the target value.
- Javascript and Java Strings are immutable, keep in mind that we cannot directly operate on strings. Need to build a char array and then join the characters.
- Use a queue for BFS. When we need to track the depth, create a local variable
n
for the size at the beginning of each iteration and removen
items from the queue in each iteration.