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 question evaluates proficiency in algorithm design and data-structure selection across two problems: constrained capital maximization (greedy selection with priority-structure reasoning and complexity trade-offs) and time-dependent grid pathfinding (graph traversal under temporal obstacles and arrival-time feasibility).