The Leetcode short list

I start to prepare the code interviews after the recent layoff. I am not sure whether the whiteboard coding test still makes senses in the AI era, so I would focus on covering the bases instead of drilling down the details.

Algorithms

When working with array and string, pay attention to the boundary.

• Rotate Array

The dynamic programming solves the sub problem first, then rebuild the problem in the bottom-up fashion.

• Frog Jump (solution)
• Coin Change (solution)
• House Robber (solution)
• Maximum Subarray (solution)

The topological sorting is commonly used for the dependency resolution, and it can be solved by the dfs.

• Alien Dictionary (solution)

We might use two cursors pointing to the lower bound and upper bound to reduce the search spaces.

• Three sum (solution)
• Container with Most Water (solution)

The HeapSort is always underestimated, it shines as we can amortize cost in the push and pop operations.

• Huffman coding (solution)
• K-way merge

Data structures

Binary tree divides the search space into halves. It is commonly implemented as Red-black tree. A similar data structure is Skip list.

The parent node MAY present the aggregated states of the children, such as segment tree, and Quadtree.