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 binary-search knapsack & graph shortest path

Quick Overview

This question evaluates a candidate's ability to apply algorithmic optimization by using binary search instead of dynamic programming for a knapsack-style selection problem and to construct and compute shortest paths on a weighted graph from custom input.

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

##### Question Given a sorted list of items, design an efficient solution (using binary search) to achieve the target objective instead of a dynamic-programming knapsack approach. Given a weighted graph provided in a custom input format, build the graph and compute the shortest path between two nodes.

Quick Answer: This question evaluates a candidate's ability to apply algorithmic optimization by using binary search instead of dynamic programming for a knapsack-style selection problem and to construct and compute shortest paths on a weighted graph from custom input.

Maximum Items Within Capacity (Binary Search on Prefix Sums)

You are given a list `weights` of item weights sorted in non-decreasing (ascending) order, and an integer `capacity`. You want to fit as many items as possible (taking the cheapest items first, i.e. a prefix of the sorted list) without exceeding `capacity`. Instead of a dynamic-programming knapsack, build the prefix-sum array of `weights` and use **binary search** to find the largest number of items whose total weight is at most `capacity`. Return that count. The prefix-sum array is non-decreasing, so binary search runs in O(log n) after the O(n) prefix build. Example: `weights = [1, 2, 3, 4, 5]`, `capacity = 10`. Prefix sums are `[0, 1, 3, 6, 10, 15]`. The largest prefix sum that is <= 10 is 10 (taking the first 4 items: 1+2+3+4 = 10), so the answer is 4.

Constraints

0 <= len(weights) <= 10^5
weights is sorted in non-decreasing order
1 <= weights[i] <= 10^9
0 <= capacity <= 10^14

Examples

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

Expected Output: 4

Explanation: Prefix sums [0,1,3,6,10,15]; largest <= 10 is 10 (4 items: 1+2+3+4).

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

Expected Output: 5

Explanation: All five items sum to 15, exactly the capacity.

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

Expected Output: 0

Explanation: Even the cheapest item (weight 2) exceeds capacity 1.

Input: ([], 100)

Expected Output: 0

Explanation: No items available, so 0 can be taken.

Input: ([5], 5)

Expected Output: 1

Explanation: Single item of weight 5 fits exactly in capacity 5.

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

Expected Output: 0

Explanation: Zero capacity admits no items.

Input: ([3, 3, 3], 8)

Expected Output: 2

Explanation: Prefix sums [0,3,6,9]; largest <= 8 is 6, so 2 items.

Hints

Build a prefix-sum array P where P[i] is the total weight of the first i items. P[0] = 0.
Because weights are non-negative, P is non-decreasing, so it is sorted — a prerequisite for binary search.
Find the largest index i such that P[i] <= capacity. That index i is your answer (number of items taken). bisect_right(P, capacity) - 1 gives it directly.

Shortest Path in a Weighted Graph (Dijkstra)

You are given an integer `n` (the number of nodes, labeled `0` to `n-1`) and a weighted **undirected** graph described by an edge list `edges`, where each edge is `[u, v, w]` meaning there is an edge between node `u` and node `v` with non-negative weight `w`. Build the graph from this custom input format and compute the **shortest path distance** from `source` to `target` using Dijkstra's algorithm. Return the total weight of the shortest path, or `-1` if `target` is not reachable from `source`. If `source == target`, the distance is `0`. Example: `n = 5`, `edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5]]`, `source = 0`, `target = 3`. The shortest path is `0 -> 2 -> 1 -> 3` with total weight `1 + 2 + 1 = 4`.

Constraints

1 <= n <= 10^4
0 <= len(edges) <= 10^5
0 <= u, v < n
0 <= w <= 10^6 (non-negative weights, so Dijkstra applies)
0 <= source, target < n

Examples

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

Expected Output: 4

Explanation: Path 0->2->1->3 with weight 1+2+1 = 4 beats 0->2->3 (1+5=6) and 0->1->3 (4+1=5).

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

Expected Output: 3

Explanation: Only path is 0->1->2->3, total 3.

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

Expected Output: -1

Explanation: Node 3 is isolated and unreachable from 0.

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

Expected Output: 0

Explanation: Source equals target with no edges; distance is 0.

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

Expected Output: 20

Explanation: Two-hop path 0->1->2 (20) beats the direct edge 0->2 (100).

Input: (6, [[0, 1, 7], [0, 2, 9], [0, 5, 14], [1, 2, 10], [1, 3, 15], [2, 3, 11], [2, 5, 2], [3, 4, 6], [4, 5, 9]], 0, 4)

Expected Output: 20

Explanation: Classic Dijkstra example: 0->2->5->4 = 9+2+9 = 20 is the shortest route to node 4.

Hints

Convert the edge list into an adjacency list. Because the graph is undirected, add each edge in both directions.
Use a min-heap (priority queue) keyed by current best distance. Pop the closest unsettled node, then relax its neighbors.
Skip stale heap entries: when you pop (d, node), if d is greater than the recorded dist[node], ignore it. Return dist[target], or -1 if it stayed infinite.

Quick Overview