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 Technical Screen rounds at Apple.

What role is this question designed for?

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

Maximize funds with capital-gated projects

Quick Overview

Maximize funds with capital-gated projects evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: Apple

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You start with initial funds W and may undertake at most K projects. Each project i has a required capital C[i] and yields profit P[i]; you can only start project i if your current funds are at least C[i], and upon completion your funds increase by P[i]. Choose up to K projects to maximize your final funds. Design an efficient algorithm, specify the data structures, analyze time and space complexity, and justify correctness. Discuss how your solution scales when N is as large as 2e5.

Quick Answer: Maximize funds with capital-gated projects evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

You start with initial funds `w` and may undertake at most `k` projects. Each project `i` has a required capital `capital[i]` and yields profit `profits[i]`. You can only start project `i` if your current funds are at least `capital[i]`, and upon completion your funds increase by `profits[i]` (profits are additive; capital is not consumed). Choose up to `k` projects to maximize your final funds and return that maximum. This is a classic greedy + heap problem: at each of the `k` steps, among all projects affordable with the current funds, pick the one with the largest profit. Function signature: `solution(k, w, profits, capital)` returns the maximum final funds. Example: `k=2, w=0, profits=[1,2,3], capital=[0,1,1]` -> `4`. First only project 0 (capital 0) is affordable; take it (funds 0 -> 1). Now projects 1 and 2 (capital 1) are affordable; take project 2 (profit 3) for funds 1 -> 4.

Constraints

0 <= k <= N
0 <= w (and intermediate funds) fit in 64-bit integers
len(profits) == len(capital) == N, with N up to 2e5
0 <= profits[i], 0 <= capital[i]
Each project may be taken at most once

Examples

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

Expected Output: 4

Explanation: Only project 0 (capital 0) is affordable first -> funds 1. Then projects with capital 1 unlock; take profit 3 -> funds 4.

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

Expected Output: 6

Explanation: Chain all three: 0->1 (project0), unlock capital1->take profit2 funds 3, unlock capital2->take profit3 funds 6.

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

Expected Output: 0

Explanation: No project has capital <= 0, so nothing is affordable; funds stay 0.

Input: (2, 3, [5, 4, 3], [3, 4, 5])

Expected Output: 12

Explanation: With w=3 take capital3/profit5 -> 8; now capital4 and capital5 affordable, take max profit4 -> 12.

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

Expected Output: 7

Explanation: k=0 means no projects may be taken; funds remain 7.

Input: (5, 1, [], [])

Expected Output: 1

Explanation: Empty project list; funds remain the initial 1 regardless of k.

Input: (10, 0, [4], [0])

Expected Output: 4

Explanation: Single affordable project taken once; k larger than N is harmless since each project is taken at most once.

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

Expected Output: 5

Explanation: All four are affordable; with k=2 take any two (profit 1 each) -> 3 + 2 = 5.

Hints

Greedy choice: at each step you want the affordable project with the highest profit, because taking it never reduces (and may increase) which projects become affordable later.
Sort projects by required capital so you can sweep in a pointer and unlock projects as your funds grow.
Use a max-heap keyed on profit to hold all currently affordable, not-yet-taken projects; pop the top each round.
Stop early if you run out of affordable projects (heap empty) before reaching k picks.

Quick Overview