Dynamic programming sounds fancier than it is. At its core, it is an optimization method. Let’s take a look at a problem from the foundations of the backtracking algorithms, we can brute force a working solution, then optimize it with dynamic programming.
Starting with the house robber problem.
The lowest common ancestor (LCA) is the question where given two nodes and the root of the tree. Write a function to determine the first node that contains both nodes.
Input:
tree: node
n1: node
n2: nodeOutput:
ancestor_node: nodeNotes:
both n1 and n2 are in the tree
Assuming both nodes belong to the same tree, we can always just return the root node of the tree. Since by definition the root node must be an ancestor node to nodes n1 and n2.
The root node is not always the lowest common ancestor. A node further down the tree…
Combinations and Permutations are a common set of interview problems that require generating various sequences based on rules.
You can solve this problem with an iterative or recursive solution. I will work out the intuition behind both examples and discuss the pros and cons between them.
The standard input output of the question requires us to build out the list of all possible combinations of size 2 given an input.
Input: n = [1,2,3,4]; k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]Recursive Solution
The combination is any 2 pairs from the list [1,2,3,4]. A brute force solution…
Nick Ma
🤓 I like learning boring complicated stuff and making it sound easy. 💻 🤔
