Solve capital selection and grid escape
Company: Two Sigma
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement two functions for algorithmic practice:
1) MaximizeCapitalAfterProjects(k, initialCapital, requiredCapital, profit): You may pick at most k projects. At each selection, you can start any project whose requiredCapital[i] <= current capital and immediately gain profit[i]. Return the maximum capital achievable after up to k selections. Optimize for n up to 2e5 and justify data-structure choices and time/space complexity.
2) MinTimeToExitSewer(grid, heights): grid contains 'S' (start), 'E' (exit), '#' (wall), and '.' (open). heights is an equally sized matrix of nonnegative integers. You move 4-directionally one cell per minute, starting at time 0 from 'S'. At minute t, all cells with heights[r][c] <= t are flooded and impassable. Find the minimum arrival time to 'E' before flooding, or return -1 if impossible. Discuss algorithm, correctness, edge cases, and complexity for grids up to 5e5 cells.
Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Solve capital selection and grid escape states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Maximize Capital After Projects
You are given an integer `k` (the maximum number of projects you may complete), an integer `initialCapital`, and two integer arrays `requiredCapital` and `profit` of equal length `n`. Project `i` requires `requiredCapital[i]` capital on hand to start, and completing it adds `profit[i]` to your capital (the required capital is NOT consumed — it is only a threshold).
Starting from `initialCapital`, you may complete at most `k` projects, one at a time. Before each pick, every project whose `requiredCapital[i] <= current capital` is startable; you choose one, add its profit to your capital, and that project cannot be reused. Choosing greedily, return the maximum capital achievable after at most `k` selections.
This is the classic "IPO" problem. The optimal strategy at every step is to take the most profitable project that is currently affordable. Sort projects by required capital so you can unlock newly-affordable projects as capital grows, and keep the profits of all currently-affordable projects in a max-heap. Each of up to `k` rounds pops the largest available profit.
Return `initialCapital` early if no project is ever affordable or `k == 0`.
Constraints
- 0 <= k <= n
- 1 <= n <= 2 * 10^5
- 0 <= initialCapital <= 10^9
- 0 <= requiredCapital[i] <= 10^9
- 0 <= profit[i] <= 10^4
- requiredCapital.length == profit.length
Examples
Input: (2, 0, [0, 1, 1], [1, 2, 3])
Expected Output: 4
Explanation: Start cap=0. Only project 0 (req 0, profit 1) is affordable; take it -> cap=1. Now projects 1,2 (req 1) are affordable with profits 2,3; take 3 -> cap=4. After 2 picks, max capital is 4.
Input: (3, 0, [0, 1, 2], [1, 2, 3])
Expected Output: 6
Explanation: Pick profit 1 (cap 0->1), then profit 2 (cap 1->3), then profit 3 (req 2<=3, cap 3->6). All three picked greedily by affordability.
Hints
- At each step the optimal choice is the most profitable project you can currently afford — a greedy argument: taking a smaller profit now never increases what you can reach later.
- Sort projects by required capital, then advance an index to unlock every project whose threshold is now <= your capital, pushing their profits into a max-heap.
- Use a max-heap (negate values with Python's min-heap). Each round pops the largest affordable profit; stop early if the heap is empty (nothing affordable) or after k picks.
Minimum Time to Exit the Flooding Sewer
You are given a character grid `grid` and an equally sized integer matrix `heights` of nonnegative values. The grid contains exactly one `'S'` (start), exactly one `'E'` (exit), `'#'` cells (walls, impassable), and `'.'` cells (open). You move 4-directionally (up/down/left/right), one cell per minute, starting at time `0` on the `'S'` cell.
Flooding rule: at minute `t`, every cell whose `heights[r][c] <= t` is flooded and impassable. You may occupy a cell at minute `t` only if it is NOT flooded at that minute, i.e. `heights[r][c] > t`. In particular, the start must satisfy `heights[start] > 0`, otherwise you can never even stand on it.
Return the minimum arrival time at `'E'`, or `-1` if it is impossible to reach the exit before it floods (or if there is no path at all).
Because every move costs exactly one minute, the first time BFS reaches a cell is the earliest possible arrival time. Run a standard BFS from `'S'`: when stepping into a neighbor at arrival time `nt = t + 1`, reject it if it is a wall or if it would already be flooded (`heights <= nt`). Edge cases: missing `S`/`E`, `S == E` (answer `0` when `heights[S] > 0`), start cell already flooded, and an exit walled off or always flooded.
Constraints
- 1 <= R * C <= 5 * 10^5
- grid[r][c] is one of 'S', 'E', '#', '.'
- Exactly one 'S' and at most one 'E'
- 0 <= heights[r][c] <= 10^9
- heights has the same dimensions as grid
Examples
Input: ([['S', '.', 'E']], [[9, 9, 9]])
Expected Output: 2
Explanation: Straight corridor with tall heights. Move S(t0)->.(t1)->E(t2). Earliest arrival is 2.
Input: ([['S', '#', 'E']], [[9, 9, 9]])
Expected Output: -1
Explanation: A wall '#' separates S from E and there is no alternate route, so E is unreachable.
Hints
- Every move costs exactly one minute, so a uniform-cost BFS from S labels each reachable cell with its earliest possible arrival time — the first time you touch a cell is optimal.
- When stepping into a neighbor that you would arrive at time nt = t + 1, it must NOT be flooded yet: require heights[neighbor] > nt. Walls ('#') are always blocked.
- Handle the corner cases first: no S or no E -> -1; the start itself flooded (heights[S] <= 0) -> -1; S already on E -> 0.