Solve budget queries and shortest path
Overview
This question evaluates algorithmic design and data-structure selection for efficient preprocessing and query answering, along with shortest-path computation and graph representation choices, testing complexity analysis, large-input handling, path reconstruction, and edge-case reasoning in the Coding & Algorithms domain.
Microsoft
Aug 1, 2025, 12:00 AM
Software Engineer
Take-home Project
Coding & Algorithms
0
0
- Budgeted purchases with sorted array: You are given an array prices of n positive integers and q budget queries. For each budget B, you may buy items starting from the cheapest price, using each item at most once, until the running total would exceed B. Return, for each query, the maximum number of items purchasable. Design an algorithm that preprocesses prices and answers all queries efficiently. Specify the data structures used, time and space complexity, and implement a function solve(prices: List[int], budgets: List[int]) -> List[int]. Consider large inputs (n, q up to 2e
- and edge cases such as duplicate prices and budgets smaller than the minimum price.
- Shortest path in a weighted graph: You are given a directed weighted graph with n nodes (1..n) and m edges; each edge is a triple (u, v, w) with non-negative weight w. Given source s and target t, compute the shortest path distance from s to t and also return one corresponding path. If t is unreachable, return -1 and an empty path. Choose appropriate graph representations and algorithms, justify your choices, and provide time/space complexity. Discuss how you would parse large, line-based input efficiently and how your solution changes if some edges can have negative (but no negative-cycle) weights.