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.

Solve binary-search knapsack & graph shortest path

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.

Hints

  1. Build a prefix-sum array P where P[i] is the total weight of the first i items. P[0] = 0.
  2. Because weights are non-negative, P is non-decreasing, so it is sorted — a prerequisite for binary search.
  3. 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.

Hints

  1. Convert the edge list into an adjacency list. Because the graph is undirected, add each edge in both directions.
  2. Use a min-heap (priority queue) keyed by current best distance. Pop the closest unsettled node, then relax its neighbors.
  3. 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.

Loading coding console...