How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Two Sigma.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Two Sigma during technical interviews.

Solve capital selection and grid escape | Two Sigma Coding Question

Quick Overview

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.

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.

Input: (1, 0, [0, 1, 1], [1, 2, 3])

Expected Output: 1

Explanation: With only k=1 pick and cap=0, only project 0 (profit 1) is affordable. Result is 1.

Input: (0, 5, [0, 0], [10, 20])

Expected Output: 5

Explanation: Edge case: k=0 selections allowed, so capital stays at the initial 5.

Input: (5, 2, [3, 4, 5], [10, 20, 30])

Expected Output: 2

Explanation: Edge case: every project needs more than the starting capital of 2, so nothing is ever affordable and the heap is empty. Return initial capital 2.

Input: (2, 1, [1, 1, 2], [5, 4, 100])

Expected Output: 106

Explanation: cap=1: projects with req 1 give profits 5,4; take 5 -> cap=6, unlocking req-2 project (profit 100); take 100 -> cap=106.

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.

Input: ([['S', '.', 'E']], [[9, 1, 9]])

Expected Output: -1

Explanation: The only middle cell floods at t>=1 (height 1). Arriving there at t=1 means heights(1) <= 1, flooded, so the path is blocked.

Input: ([['S', 'E']], [[5, 5]])

Expected Output: 1

Explanation: S and E are adjacent; one move arrives at E at time 1 (height 5 > 1, not flooded).

Input: ([['S', '#', '.'], ['.', '#', '.'], ['.', '.', 'E']], [[9, 9, 9], [9, 9, 9], [9, 9, 9]])

Expected Output: 4

Explanation: Walls force the route down the left column and across the bottom: (0,0)->(1,0)->(2,0)->(2,1)->(2,2)=E, four moves.

Input: ([['S', 'E']], [[0, 5]])

Expected Output: -1

Explanation: Edge case: the start cell has height 0, so at time 0 it is already flooded (heights <= 0). You can never stand on S; return -1.

Input: ([['S']], [[5]])

Expected Output: -1

Explanation: Edge case: grid has a start but no exit, so reaching E is impossible; return -1.

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.

Quick Overview