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 Take-home Project rounds at Microsoft.

What role is this question designed for?

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

Solve budget queries and shortest path | Microsoft Coding Question

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

Solve budget queries and shortest path

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

1) 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 5) and edge cases such as duplicate prices and budgets smaller than the minimum price. 2) 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.

Quick Answer: 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.

Budgeted Purchases with Sorted Prices

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, using each item at most once, adding items in non-decreasing price order until adding the next item would make the running total exceed `B`. Return, for each query, the maximum number of items purchasable. Implement `solve(prices: List[int], budgets: List[int]) -> List[int]` returning one answer per budget, in the same order as `budgets`. Example: `prices = [1,2,3,4,5]`, `budgets = [5,10,1,0,100]` -> `[2,4,1,0,5]`. With budget 5 you buy items costing 1 and 2 (total 3); adding 3 would reach 6 > 5, so the answer is 2. Design for large inputs (`n, q` up to 2e5). Handle duplicate prices and budgets smaller than the minimum price (answer 0).

Constraints

1 <= n, q <= 2e5 (and n may be 0 in degenerate inputs)
1 <= prices[i] (positive integers)
0 <= budgets[j]
Items are taken greedily cheapest-first; each item used at most once
Prices may contain duplicates

Examples

Input: ([1, 2, 3, 4, 5], [5, 10, 1, 0, 100])

Expected Output: [2, 4, 1, 0, 5]

Explanation: B=5 buys {1,2}=3 (next 3 would reach 6>5) -> 2; B=10 buys {1,2,3,4}=10 -> 4; B=1 buys {1} -> 1; B=0 buys nothing -> 0; B=100 buys all 5.

Input: ([3, 1, 2], [3, 6, 2, 100])

Expected Output: [2, 3, 1, 3]

Explanation: Sorted = [1,2,3], prefix = [0,1,3,6]. B=3 -> 2 items; B=6 -> all 3; B=2 -> 1 item; B=100 -> all 3.

Input: ([5, 5, 5], [4, 5, 14, 15])

Expected Output: [0, 1, 2, 3]

Explanation: Duplicate prices. B=4 < 5 -> 0; B=5 -> 1; B=14 -> 2 (cost 10); B=15 -> 3 (cost 15).

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

Expected Output: [0, 0, 1, 1]

Explanation: Single item costing 10. Budgets below 10 buy nothing; 10 and 20 buy the one item.

Input: ([], [0, 5, 100])

Expected Output: [0, 0, 0]

Explanation: Empty price list — nothing to buy regardless of budget.

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

Expected Output: [0]

Explanation: Budget 1 is below the minimum price 2, so 0 items.

Hints

Because items are taken cheapest-first, the chosen set for any budget is always a prefix of the sorted prices — so sort once.
Precompute prefix sums of the sorted prices; prefix[k] is the cost of buying the k cheapest items.
For each budget B, the answer is the largest k with prefix[k] <= B. Find it with binary search (bisect_right) instead of a DP knapsack, which would be far too slow.

Shortest Path in a Weighted Directed Graph

You are given a directed weighted graph with `n` nodes labeled `1..n` and a list of edges, where each edge is a triple `[u, v, w]` meaning a directed edge from `u` to `v` with non-negative weight `w`. Given a source `s` and target `t`, compute the shortest-path distance from `s` to `t` and return one corresponding path. Implement `shortest_path(n, edges, s, t)` returning `[distance, path]` where `path` is the list of node labels from `s` to `t` inclusive. If `t` is unreachable from `s`, return `[-1, []]`. If `s == t`, the distance is 0 and the path is `[s]`. Use Dijkstra's algorithm with a binary heap on the adjacency-list representation (weights are non-negative). When multiple shortest paths exist, the canonical path is obtained by relaxing edges in the order given and breaking ties toward the smaller node id (heap order).

Constraints

1 <= n; nodes labeled 1..n
0 <= w (non-negative edge weights — Dijkstra applies)
1 <= s, t <= n
The graph is directed; edges may be absent (m can be 0)
If t is unreachable, return [-1, []]; if s == t, return [0, [s]]

Examples

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

Expected Output: [6, [1, 3, 2, 4, 5]]

Explanation: 1->3 (1) ->2 (1) ->4 (1) ->5 (3) totals 6, beating 1->2->4->5 (4+1+3=8) and 1->3->4->5 (1+5+3=9).

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

Expected Output: [10, [1, 2, 3]]

Explanation: Only path 1->2->3 with total weight 10.

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

Expected Output: [-1, []]

Explanation: Node 4 has no incoming edge and is unreachable from 1 -> return [-1, []].

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

Expected Output: [0, [1]]

Explanation: Source equals target: distance 0, path is just [1].

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

Expected Output: [5, [1, 2, 3]]

Explanation: 1->2->3 = 2+3 = 5 beats the direct edge 1->3 = 10.

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

Expected Output: [2, [1, 2, 4]]

Explanation: Two equal-cost paths of weight 2 exist; the canonical one relaxes the smaller-id branch first, yielding 1->2->4.

Hints

Build an adjacency list `graph[u] = [(v, w), ...]` so each edge is visited once; this beats an adjacency matrix for sparse graphs.
With non-negative weights, Dijkstra with a min-heap keyed on tentative distance is optimal. Skip stale heap entries when the popped distance exceeds the recorded distance.
Record a `parent` pointer each time you relax an edge, then walk parents backward from t to s and reverse to recover the path. For negative (but no negative-cycle) weights you would switch to Bellman-Ford, O(n*m).

Quick Overview