Interview algorithm problems

Doing practise to explain the ideas behind the solutions.

Leetcode

Interesting problems

Some interesting problems.

11. Container With Most Water

Solution: two pointers from two sides, greedy check the smaller one and remove it.

375. Guess Number Higher or Lower II

The goal is buidling a balanced tree which balances two sides’ cost.

Solution: DP, set dp[i][j] as the minimum cost to build a tree from i to j.

The naive solution is O(n^3), and it can be optimized to O(n^2), because dp[i][0:n] is monotonic.

546. Remove Boxes

Solution: DP.

dp[i][j][k] -> the max score for removing boxes from i to j and leaving k boxes if boxes[i] == boxes[j].

if boxes[i] != boxes[j]: only dp[i][j][0] is valid.

658. Find K Closest Elements

Solution: Binary search

Very interesting binary search, it’s the same to find the k smallest element in two sorted lists.

673. Number of Longest Increasing Subsequence

Solution: DP, Segment tree, Binary search

I joked my friend that this problem can be solved by binary search. And after a while, I found that it can be done by binary search…

DP is a clear way to solve this problem, but the running time is $O(n^2)$.

By using segment tree, it give us the ability to insert element and query the sum of subarray in $O(\log{n})$ time. Then, it improves the overall running time to $O(n\log{n})$.

But for this specific problem, with more observations, we can solve it by extending the LIS algorithm. The running time will become $O(n \log{n})$ for LIS and $O(n)$ for extension. I just write a simplest version, which does both parts in $O(n\log{n})$ time. It solved the problem in 8ms for C++. Update: I modified the code a little bit to implement the O(n) extension, then it achieved 4ms running time, and faster than 100% of submissions, lol.

843. Guess the Word

An interactive problem

Solution: design a score for each word according to preivous queries, and query the word of top score.

992. Subarrays with K Different Integers

Solution: two pointers, hard to explain in one sentence. The basic idea is fixing right side of the subarray, and maintaining the valid range for the left side.

1000. Minimum Cost to Merge Stones

variant of merge stones problem: only adjacent stones can be merged.

Solution: DP. dp[i][j] is the minimum cost to merge i to j.

dp[i][j] = min(dp[i][k] + dp[k+1][j])
if (j - i + 1) % (K - 1) == 1 or K == 2: dp[i][j] += sum(stones[i:j+1])

Interesting interview algorithm problems

Interview algorithm problems

Leetcode

Interesting problems

Recommended problems