PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates understanding of shortest-path algorithms and reachability in weighted graphs (including directed vs. undirected handling and paths that must include an intermediate node) as well as interval scheduling and resource-allocation skills for minimizing and assigning concurrent rental requests.

  • medium
  • Google
  • Coding & Algorithms
  • Software Engineer

Solve Shortest Paths and Rental Allocation

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given two independent coding problems. ## Problem 1: Shortest path in a weighted graph You are given a weighted graph where each edge has a non-negative distance. Given a start node `source` and a target node `target`: 1. Determine whether `target` is reachable from `source`. 2. If it is reachable, return the shortest distance from `source` to `target`. 3. Follow-up: suppose the path must pass through a required intermediate node `mid`. Determine whether such a path exists and, if it exists, return the minimum total distance from `source` to `target` while visiting `mid`. Clarify whether the graph is directed or undirected, and handle either case according to the input representation. ## Problem 2: Assign car rental requests to the minimum number of cars You are given a list of car rental requests. Each request has: - `pickup_time` - `return_time` You are also given a `Car` class with fields similar to: ```python class Car: def __init__(self, id): self.id = id self.rental_record = [] ``` Implement the following: 1. Return the minimum number of cars required to satisfy all rental requests, assuming one car cannot serve overlapping requests. 2. Follow-up: actually assign requests to cars. For each `Car` instance, record the requests assigned to that car in `car.rental_record`. A car can be reused if its previous request has already ended before the next request starts. State clearly whether `return_time == pickup_time` counts as non-overlapping.

Quick Answer: This question evaluates understanding of shortest-path algorithms and reachability in weighted graphs (including directed vs. undirected handling and paths that must include an intermediate node) as well as interval scheduling and resource-allocation skills for minimizing and assigning concurrent rental requests.

Part 1: Determine Reachability in a Weighted Graph

You are given a weighted graph with non-negative edge weights. For this sub-problem, the weights do not affect the answer; only connectivity matters. Nodes are labeled from 0 to n - 1. Given a source node and a target node, return whether target is reachable from source. If directed is True, each edge (u, v, w) can only be used from u to v. If directed is False, each edge can be used in both directions.

Constraints

  • 1 <= n <= 10^5
  • 0 <= len(edges) <= 2 * 10^5
  • 0 <= u, v < n for every edge
  • 0 <= w <= 10^9 for every edge
  • 0 <= source, target < n

Examples

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

Expected Output: True

Explanation: There is a directed path 0 -> 1 -> 2.

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

Expected Output: False

Explanation: Even as an undirected graph, nodes 0 and 3 are in different connected components.

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

Expected Output: True

Explanation: Because the graph is undirected, 2 can reach 0 through node 1.

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

Expected Output: True

Explanation: A node is always reachable from itself.

Hints

  1. Build an adjacency list, but only add the reverse edge when directed is False.
  2. A BFS or iterative DFS from source is enough because you only need to know whether any path exists.

Part 2: Shortest Distance from Source to Target in a Weighted Graph

You are given a weighted graph with non-negative edge weights. Nodes are labeled from 0 to n - 1. Return the shortest distance from source to target. If target is unreachable, return -1. If directed is True, each edge (u, v, w) is directed from u to v. If directed is False, each edge is undirected.

Constraints

  • 1 <= n <= 10^5
  • 0 <= len(edges) <= 2 * 10^5
  • 0 <= u, v < n for every edge
  • 0 <= w <= 10^9 for every edge
  • 0 <= source, target < n

Examples

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

Expected Output: 6

Explanation: The shortest path is 0 -> 1 -> 2 -> 4 with total weight 2 + 3 + 1 = 6.

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

Expected Output: -1

Explanation: Node 3 is unreachable from node 0.

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

Expected Output: 10

Explanation: In the undirected graph, 2 -> 1 -> 0 has total weight 6 + 4 = 10.

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

Expected Output: 0

Explanation: The distance from a node to itself is 0.

Hints

  1. Because all edge weights are non-negative, Dijkstra's algorithm is a good fit.
  2. You can stop early when the target node is removed from the min-heap.

Part 3: Shortest Source-to-Target Path That Must Pass Through a Required Node

You are given a weighted graph with non-negative edge weights. Nodes are labeled from 0 to n - 1. Find the minimum total distance of a path from source to target that must visit the required intermediate node mid. If no such path exists, return -1. If directed is True, each edge (u, v, w) is directed from u to v. If directed is False, each edge is undirected.

Constraints

  • 1 <= n <= 10^5
  • 0 <= len(edges) <= 2 * 10^5
  • 0 <= u, v < n for every edge
  • 0 <= w <= 10^9 for every edge
  • 0 <= source, target, mid < n

Examples

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

Expected Output: 7

Explanation: The best valid route is 0 -> 1 -> 2 -> 4 with distance 2 + 2 + 3 = 7.

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

Expected Output: -1

Explanation: The required node 3 is not reachable from the source.

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

Expected Output: 7

Explanation: In the undirected graph, 3 -> 2 -> 1 -> 0 has total distance 1 + 1 + 5 = 7.

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

Expected Output: 5

Explanation: Since source is already mid, the answer is just the shortest distance from 0 to 2.

Hints

  1. Any shortest path from source to target that must pass through mid can be split into source -> mid and mid -> target.
  2. Since all weights are non-negative, run Dijkstra twice instead of searching over full paths directly.

Part 4: Minimum Number of Cars Needed for Rental Requests

You are given a list of rental requests, where each request is a pair (pickup_time, return_time). A car can handle at most one active request at a time. Return the minimum number of cars required to satisfy all requests. Requests may be given in any order. Assume that return_time == pickup_time is non-overlapping, so a car returned at time t can be reused for another request starting at time t.

Constraints

  • 0 <= len(requests) <= 2 * 10^5
  • 0 <= pickup_time <= return_time <= 10^9
  • Requests may be unsorted

Examples

Input: ([(1, 4), (2, 5), (7, 9)],)

Expected Output: 2

Explanation: The first two requests overlap, so at least two cars are needed.

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

Expected Output: 1

Explanation: Because return_time == pickup_time is allowed, one car can serve all three requests.

Input: ([],)

Expected Output: 0

Explanation: No requests means no cars are needed.

Input: ([(0, 10), (1, 3), (2, 6), (4, 5), (7, 8)],)

Expected Output: 3

Explanation: At the peak, three requests overlap in time.

Hints

  1. Sort requests by pickup_time before processing them.
  2. Use a min-heap of current return times to track when cars become available.

Part 5: Assign Rental Requests to Specific Cars

You are given a list of rental requests, where each request is a pair (pickup_time, return_time). Create cars with consecutive ids starting from 0 and assign every request to a car so that no car has overlapping requests. Record each assigned request in that car's rental_record. Return the final assignment as a list of dictionaries in ascending car id order, where each dictionary has keys 'id' and 'rental_record'. Requests may be given in any order. Assume that return_time == pickup_time is non-overlapping, so a car returned at time t can be reused for another request starting at time t. Your assignment should use the minimum possible number of cars.

Constraints

  • 0 <= len(requests) <= 2 * 10^5
  • 0 <= pickup_time <= return_time <= 10^9
  • Requests may be unsorted
  • Car ids must start at 0 and increase by 1 as new cars are created

Examples

Input: ([],)

Expected Output: []

Explanation: No requests means no cars are created.

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

Expected Output: [{'id': 0, 'rental_record': [(5, 8)]}]

Explanation: A single request needs one car.

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

Expected Output: [{'id': 0, 'rental_record': [(1, 4), (4, 6)]}, {'id': 1, 'rental_record': [(2, 3)]}]

Explanation: At time 4, both cars are free, and the smallest free id is reused.

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

Expected Output: [{'id': 0, 'rental_record': [(1, 3), (3, 5), (5, 7)]}, {'id': 1, 'rental_record': [(2, 4)]}]

Explanation: Sorting by pickup time allows one car to handle the chain 1-3, 3-5, 5-7.

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

Expected Output: [{'id': 0, 'rental_record': [(0, 1), (1, 2)]}, {'id': 1, 'rental_record': [(1, 3)]}]

Explanation: The request ending at time 1 frees a car that can immediately be reused by one of the requests starting at time 1.

Hints

  1. Sort requests by pickup_time, then greedily reuse any car that has already become free.
  2. Use one min-heap for busy cars by return time, and another min-heap for free car ids to make the output deterministic.
Last updated: May 2, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Solve Rooms and Top-K Streams - Google (medium)
  • Find Containing Range - Google (medium)
  • Rearrange Tasks With Cooldown - Google (medium)
  • Implement Employee Management and Expression Evaluation - Google (medium)
  • Solve Three Array and Matrix Path Problems - Google (medium)