Solve capital selection and grid escape

Q: Solve capital selection and grid escape

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).

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Implement two functions for algorithmic practice:

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.
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.

Solve capital selection and grid escape

Overview

Comments (0)