# Interesting interview algorithm problems

# Interview algorithm problems

Doing practise to explain the ideas behind the solutions. Only problems I feel interesting.

# Leetcode

## 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.

**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])

## Recommend problems

Good problems to practise. Classic problems, problems with multiple solutions, and so on.

**410. Split Array Largest Sum**

DP soltion is O(n^2). Binary search can reach O(nlogn).

**1044. Longest Duplicate Substring**

Example for Suffix Array.