← Microsoft Interview Insights

Microsoft·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Microsoft coding round, one algorithmic problem about maximizing capital by selecting projects greedily. Pretty focused session, no fluff.

Questions Asked (1)

Q1

You have n projects, each with a profit value and a minimum capital requirement. Starting with some initial capital w and allowed to complete at most k projects, how do you maximize your total capital?

Algorithms & Data Structures
Author's notes

This one took me a minute to see the greedy angle.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a greedy strategy with a min-heap to always select the most profitable project among those currently affordable. Iterate up to k times, each time adding all projects whose capital requirement is met, then pick the one with maximum profit and update capital. This ensures optimal capital growth at each step.

Pro tip: Clarify that projects can be done in any order and each at most once, and mention that if no project is affordable, we stop early. Also, note that the greedy choice is safe because capital only increases, so previously unaffordable projects may become affordable later.

1. Sort projects by capital requirement

Sort the list of projects in ascending order of their minimum capital requirements. This allows efficient scanning as capital grows.

2. Use a min-heap for affordable projects

Initialize a min-heap (or priority queue) to store profits of projects that are currently affordable. Also, maintain a pointer to the sorted projects.

3. Iterate up to k times

In each iteration, add all projects with capital requirement <= current capital to the heap. If the heap is empty, break early. Otherwise, pop the project with maximum profit (using a max-heap or negating values for min-heap) and add its profit to capital.

4. Return the final capital

After at most k iterations or when no more projects can be afforded, return the accumulated capital as the maximum possible.

Key Points to Mention

  • Greedy algorithm: always pick the most profitable affordable project.
  • Use a min-heap (or priority queue) to efficiently retrieve the maximum profit among affordable projects.
  • Sort projects by capital requirement to efficiently add newly affordable projects.
  • Time complexity: O(n log n + k log n) due to sorting and heap operations.
  • Space complexity: O(n) for the heap and sorted list.
  • Edge cases: initial capital may be less than all requirements, k may be larger than n, or no projects affordable.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.