De Shaw OA Intern Problems

Problem 1

Given a binary string, find the number of subsequences of length 3 such that no two adjacent characters are the same (e.g., 101, 010).

Constraints: N <= 1e5

Problem 2

Given an array, we want to make it non-increasing by performing the following operations one at a time:

• You can shift 1 from a[i] to a[i+1], after which a[i] becomes a[i]-1 and a[i+1] becomes a[i+1]+1 (if i+1<n)
• You can shift 1 from a[i] to a[i-1], after which a[i] becomes a[i]-1 and a[i-1] becomes a[i-1]+1 (if i-1>=0)

Calculate the minimum moves required to make it non-decreasing.

Constraints: N <= 250, a[i] <= 1e9

Example: a[] = [5, 3, 2, 3, 3, 3] -> [4, 4, 2, 3, 3, 3] -> [4, 3, 3, 3, 3, 3], output is 2.

Problem 3

Given an array a[], find the number of arrays b such that 1 <= b[i] <= a[i], and no two adjacent elements of b are the same (b[i] != b[i+1]). Print it modulo (1e9+7) since the answer is large.

Constraints: N <= 1e5, a[i] <= 1e6

Example: a[] = [2, 3], b[] = [1, 2], [1, 3], [2, 1], [2, 3], output is 4.

Blogger's Review: These three problems not only test fundamental dynamic programming and greedy algorithms but also involve complex state transitions and combinatorial counting. Mastering the solutions to these problems will greatly enhance candidates' programming skills and logical thinking for interviews.