I took Google’s online campus hiring written test yesterday. Skip algorithms for a day and your skills slide right back down.

Problem A. Password Attacker

  • Description

How many passwords of length M can be formed from N distinct characters, such that every password uses all N characters at least once?

  • Solution 1: Brute Force

For each solution to the equation below, add the number of distinct permutations. If one solution is X1, …, Xn, that group contributes M! / (X1! * X2! * ... * Xn!). Sum over all solutions.

sigma(Xi) = M , Xi >= 1 and 1 <= i <= N

Small cases with M <= 15 can pass with DFS, but M <= 100 is too large.

  • Solution 2: DP

Let dp[i, j] be the number of length-i passwords using exactly j distinct characters from the set of N. The answer is dp[M, N]. Recurrence:

dp[0, 0] = 1
dp[0, i] = 0 ( 1 <= i <= M )
dp[i, j] = dp[i-1, j] * j + dp[i-1, j-1] * (n - (j-1))

Here dp[i-1, j-1] * (n - j + 1) means the first i-1 positions used only j-1 distinct characters, so position i can pick any of the remaining n - (j-1) characters.

S(n, k) counts ways to partition n distinct elements into k non-empty unlabeled subsets. Recurrence:

S(n, k) = S(n-1, k-1) + S(n-1, k) * k

We partition M password positions into N labeled groups, so we also permute the N groups. Total: N! * S(M, N).

Problem B. New Years Eve

  • Description

Cups hold 250 units of liquid. Level 1 has 1 cup, level 2 has 3 cups, level 3 has 10 cups, … level N has N * (N+1) / 2 cups. Cup j on level i sits on cups j, j+i, and j+i+1 on level i+1. When a cup on level i overflows, liquid splits evenly into those three cups below. If you pour B bottles of 750 units into the top cup, how much liquid ends up in cup N on level L?

  • Solution

Straight simulation — nothing fancy.

Problem C. Card Game

  • Description

Given a sequence of length N, A1, A2, …, An, and an integer K. In one move, pick three consecutive elements that form an arithmetic progression with common difference K, and remove that triple. What is the minimum number of elements left after any sequence of such moves?

  • Solution: DP

Let dp[i, j] be the minimum number of elements left after optimal play on subarray Ai … Aj. The answer is dp[1, n].

Consider these cases:

  1. If Ai survives: dp[i+1, j] + 1
  2. If Aj survives: dp[i, j-1] + 1
  3. If both Ai and Aj survive: dp[i+1, j-1] + 2
  4. If both Ai and Aj are removed: either a triple Ai ... Am ... Aj is removed, giving dp[i+1, m-1] + dp[m+1, j-1] (i < m < j), or the segment splits at m into Ai ... Am and Am+1 ... Aj, giving dp[i+1, m] + dp[m+1, j]

Problem D. Parentheses Order

  • Description

Given N and K, among all valid strings of N pairs of parentheses sorted in lexicographic order, what is the K-th string?

  • Solution: DP

Reduce to counting: with a fixed prefix of j consecutive left parentheses and i remaining pairs available, the number of valid completions is t(n, k). For example, in ((((*)*)*)*), there are 4 consecutive left parentheses; each * stands for zero or more matched pairs, and the * placeholders account for 10 pairs total, so the state is t(10, 4). Recurrence:

t(n, k ) = sigma( h(i) * t(n - i, k - 1 ) )  ( 0 <= i <= n)

Here h(i) is the Catalan number, with recurrence:

h(0) = h(1) = 1 
h(n) = sigma(h(i) * h(n-1-i))   (0 <= i < n)