Hulu 2022 Campus Recruitment: 5 Algorithmic Challenges with Solutions

Problem 1: Angel Particles

In a linear pipe, particles have distinct positions, identical speed, and move either left (L) or right (R). They can pass through each other without interaction. Given the speed v and an initial string s of 'L', 'R', and '.' characters, output the pipe state at each time step using 'X' for occupied positions and '.' for empty, ending when all particles have left the pipe.

Input

First line: integer v (1 ≤ v ≤ 10). Second line: string s (1 ≤ |s| ≤ 50) composed of 'L', 'R', '.'.

Output

Multiple lines, each a string representing the pipe at successive time steps, using only 'X' and '.'. The final line consists entirely of '.' indicating all particles have exited.

Sample

2
..R....

Output:

..X....
....X..
......X
.......

Solution

Simulate each particle with a class Particle storing position and direction (1 for right, -1 for left). At each step, reset a boolean array hasParticle, update positions by position += direction * v, mark occupied cells, and print the line. Stop when no particle remains.

Problem 2: Sophie‑N Numbers

Define a Sophie‑N number as an integer whose digit sum modulo N equals 0. Compute the count of Sophie‑N numbers within the closed interval [A, B].

Input

Three positive integers: N, A, B.

Output

An integer representing the count of Sophie‑N numbers in [A, B].

Sample

62 19260817 20210817

Output:

21

Solution

Use digit DP. Let f[i][j] be the number of ways to form a prefix of length i whose digit sum modulo N is j. Transition by enumerating the next digit cur (0‑9) and updating f[i][j] += f[i‑1][(j‑cur) mod N]. Compute f(m) for m = B and m = A‑1, then answer = f(B) – f(A‑1). Complexity O(N · log B).

Problem 3: Optimal Activity Point on a Tree

Given a tree with N nodes (areas) each having a population Zi and weighted edges (roads) of length C, find a node that minimizes the total weighted distance from all people to that node. Output the minimal total cost.

Input

First line: integer N (1 ≤ N ≤ 100000). Next N lines: integer Zi for each node. Following N‑1 lines: three integers A B C describing an undirected edge of length C.

Output

Single integer: the minimal possible total cost.

Sample

5
1
1
1
0
0
2
1 3 1
4 3 3
3 2 2
4 5 3

Output:

15

Solution

Root the tree arbitrarily. Perform a DFS to compute for each subtree the total population and the cost when the root is the activity point. Then reroot using the formula

F_y = F_x + (totalPopulation – 2·subtreePopulation_y)·edgeLength

to obtain costs for all nodes in linear time, keeping the minimum.

Problem 4: Devil Maze

A rectangular maze (≤ 9 × 9) contains cells marked '0' (empty), '1' (impassable demon soldier), '2' (impassable ally soldier), 's' (start), 'e' (exit), and 'd' (intelligent devil). The player and devil move alternately; the player moves first. Each move can be up to yourSteps (player) or devilSteps (devil) steps in the four cardinal directions, possibly staying still. The player cannot occupy the same cell as the devil. Determine the minimum number of player moves (≤ 1000) needed to reach the exit without being caught; output -1 if impossible.

Input

yourSteps
devilSteps
m
maze rows (each of length n)

Output

Minimum number of player moves to reach the exit, or -1.

Sample

3
2
5
0s000
00100
10001
d0200
0002e

Output:

4

Solution

Model the game as a two‑player turn‑based search. Use DFS with memoization on the pair of positions (player, devil) and depth limit (≤ 92, derived from worst‑case move count). Prune when the player reaches the exit before the devil or when the devil can capture. For cases where the player can outrun the devil without crossing, a BFS shortcut can be applied.

Problem 5: Hell Triangle

Given points C₁…Cₙ in the first and fourth quadrants (no three collinear) and a fixed base AB on the Y‑axis (A(0,1), B(0,-1)), select the largest subset of points such that the triangles formed with AB are pairwise non‑intersecting (they may be nested). Output the maximum size of such a subset.

Input

N
x₁ y₁ x₂ y₂ … xₙ yₙ

Output

Maximum number of selectable points.

Sample

6
1 0.2 1.6 -0.6 0.6 0 2 -0.2 3 -0.5 0.2 1.05

Output:

4

Solution

Sort points by the slope of line AC (ascending) and by slope of line BC (descending). The longest common subsequence of the two orders corresponds to the largest set of non‑intersecting triangles. Transform the problem into a longest increasing subsequence after re‑indexing one order, which can be solved in O(N log N) time.