Katkat
Back

Solve capital selection and grid escape

Two SigmaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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.