Microsoft·Software Engineer·Onsite - Coding / Algorithms·Intermediate

Intermediate

Jun 2026

Summary

Microsoft SWE interview with two fairly meaty coding and algorithms questions. Both required you to think about complexity and justify your design choices out loud, not just write code. Felt more like a systems-thinking exercise than a pure LeetCode grind.

Questions Asked (2)

Given an array of item prices and a list of budget queries, find the maximum number of items you can buy for each budget (buying cheapest first, no item reuse). Preprocess the prices so queries are answered efficiently. Handle large inputs (up to 2e5 for both) and edge cases like duplicate prices or budgets below the minimum price.

Algorithms & Data Structures

Author's notes

Sort plus prefix sums is the move here, then binary search per query.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Sort the prices and compute prefix sums to enable O(log n) binary search per query. For each budget, binary search the prefix sums to find the largest index where the cumulative sum is ≤ budget, which gives the maximum number of items. This preprocessing handles large inputs efficiently and naturally deals with duplicates and edge cases.

Pro tip: Mention that you can use binary search on the prefix sums because they are strictly increasing (assuming positive prices). Also, clarify that if prices can be zero, the prefix sums may have duplicates, but binary search still works with a proper implementation (e.g., using upper_bound).

1. Sort and Preprocess

Sort the array of prices in ascending order. Compute the prefix sum array where prefix[i] is the sum of the first i prices (with prefix[0] = 0).

2. Handle Edge Cases

Check if the budget is less than the smallest price; if so, the answer is 0. Also, consider if the budget is greater than or equal to the total sum; then the answer is the total number of items.

3. Binary Search for Each Query

For each budget, perform a binary search on the prefix sum array to find the largest index i such that prefix[i] ≤ budget. The answer is i.

4. Optimize and Analyze Complexity

Explain that sorting takes O(n log n) and each query takes O(log n), so total time is O(n log n + q log n), which is efficient for n, q ≤ 2e5.

Key Points to Mention

Sorting the prices to enable buying cheapest first.
Prefix sums to quickly compute cumulative costs.
Binary search (or upper_bound) on prefix sums for each query.
Time complexity: O(n log n + q log n) and space complexity O(n).
Handling duplicate prices: sorting and prefix sums naturally handle duplicates.
Edge cases: budget below minimum price (answer 0), budget ≥ total sum (answer n).

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

Given a directed weighted graph with non-negative edge weights, find the shortest path distance and the actual path between two nodes. Return -1 and an empty path if the target is unreachable. Discuss your graph representation, algorithm choice, complexity, how you'd parse large line-based input efficiently, and how the solution changes if some edges can have negative weights (with no negative cycles).

Algorithms & Data StructuresTechnical Trade-offsSystem Design

Author's notes

Dijkstra with an adjacency list, reconstruct the path by tracking predecessors.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem constraints (e.g., graph size, edge weight ranges, input format) and then present a complete solution using Dijkstra's algorithm with an adjacency list representation. Explain the algorithm step-by-step, including path reconstruction, complexity analysis, and efficient input parsing. Finally, discuss the extension to negative weights using Bellman-Ford or Johnson's algorithm, highlighting the trade-offs.

Pro tip: Emphasize the importance of early termination in Dijkstra when the target is reached, and mention that for very large graphs, using a Fibonacci heap can improve theoretical complexity, but a binary heap is often more practical due to lower constant factors.

1. Clarify requirements and constraints

Ask about graph size, edge weight ranges, input format, and whether the graph is static or dynamic. This determines the choice of algorithm and data structures.

2. Choose graph representation and algorithm

For non-negative weights, use an adjacency list and Dijkstra's algorithm with a priority queue. For negative weights (no negative cycles), use Bellman-Ford or Johnson's algorithm if all-pairs is needed.

3. Implement shortest path with path reconstruction

Maintain a distance array and a predecessor array. After computing distances, backtrack from the target using predecessors to build the path. If the target is unreachable, return -1 and an empty path.

4. Analyze complexity and optimize

Dijkstra with binary heap: O((V+E) log V) time, O(V+E) space. Bellman-Ford: O(VE) time. Discuss trade-offs and potential optimizations like early termination.

5. Handle large input efficiently

Use fast I/O methods (e.g., BufferedReader in Java, sys.stdin in Python) and parse line-by-line. Avoid unnecessary object creation and use primitive arrays where possible.

Key Points to Mention

Dijkstra's algorithm for non-negative weights, with a priority queue (binary heap) for efficiency.
Path reconstruction using a predecessor array, and handling unreachable targets.
Time and space complexity: O((V+E) log V) for Dijkstra, O(VE) for Bellman-Ford.
Efficient input parsing for large graphs: buffered reading, tokenization, and avoiding regex.
Negative weights: use Bellman-Ford or Johnson's algorithm; discuss why Dijkstra fails.
Trade-offs between different algorithms and data structures (e.g., binary heap vs. Fibonacci heap).

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