Quick Overview

This question evaluates understanding of graph traversal and shortest-path concepts, particularly handling multiple mode-restricted subgraphs and multi-criteria comparison of path metrics (time and cost) across modes.

Find optimal commute mode in a city graph

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are designing a route planner that suggests the best way to commute between two points in a city using different transportation modes. The city is represented as an undirected graph with `N` intersections labeled `0 .. N-1` and `M` roads. There are `K` possible commute modes (e.g., walk, bike, drive) labeled `0 .. K-1`. Each road is described as: - `u, v` — the two endpoints of the road (0-based node indices) - `allowed_modes` — a non-empty list of mode IDs in `0 .. K-1` that are allowed to travel on this road For every mode `m`: - If a road is usable by mode `m`, then traveling along that road: - takes `time_per_edge[m]` minutes - costs `cost_per_edge[m]` units of money You are also given: - an integer `S` — the starting intersection - an integer `D` — the destination intersection - an array `time_per_edge[0..K-1]` - an array `cost_per_edge[0..K-1]` ### Task 1. For every commute mode `m` in `0 .. K-1`, considering **only** roads whose `allowed_modes` contains `m`, compute the minimal number of edges from `S` to `D` (if reachable). From that, derive: - total travel time `T[m] = (number_of_edges_m) * time_per_edge[m]` - total travel cost `C[m] = (number_of_edges_m) * cost_per_edge[m]` If `D` is not reachable from `S` using mode `m`, then that mode should be considered **invalid** for the final choice. 2. Among all **valid** modes that can reach `D`, select the **optimal** commute mode according to: - smaller total travel time is better; - if two modes have the same total travel time, smaller total cost is better; - if both time and cost are equal, you may return any one of those modes. Return: - the chosen mode ID, and - the pair `(T[mode], C[mode])` for that chosen mode. If no mode can reach `D`, return an indication that the destination is unreachable (e.g., `-1` as the mode and some sentinel values for time and cost). Some modes may end up with identical `(time, cost)` pairs (duplicates); your algorithm must still handle these ties correctly. ### Constraints - `1 <= N <= 10^5` - `0 <= M <= 2 * 10^5` - `1 <= K <= 10` - The graph is sparse and fits in memory using adjacency lists. - All times and costs are non-negative integers that fit in 32-bit signed integers. ### Requirements - Exploit the fact that for each given mode, all usable roads have the **same** time and cost per edge. You should not treat this as an arbitrary weighted-graph problem that forces you to use a general algorithm like Dijkstra on a combined weighted graph for all modes. - The overall graph traversal per mode should run in linear time with respect to the size of the graph for that mode (i.e., `O(N + M)` per mode or better). - The final step that chooses the optimal mode from the `K` `(time, cost)` pairs must run in **O(K)** time and must **not** sort the list of modes. Describe your approach, discuss its time and space complexity, and then implement the solution in code.

Quick Answer: This question evaluates understanding of graph traversal and shortest-path concepts, particularly handling multiple mode-restricted subgraphs and multi-criteria comparison of path metrics (time and cost) across modes.

Part 1: Compute commute metrics for every mode

You are given an undirected city graph with intersections numbered 0 to N-1. Each road is described by (u, v, allowed_modes), where allowed_modes is a non-empty list of transportation mode IDs. For a fixed mode m, you may travel only on roads whose allowed_modes contains m. Every usable road for mode m takes the same time_per_edge[m] minutes and costs the same cost_per_edge[m] money units. For every mode m in 0 to K-1, compute the minimum number of edges needed to travel from S to D using only roads allowed for that mode. If D is reachable, also compute the total travel time and total travel cost for that mode. If D is not reachable for a mode, mark that mode as invalid with (-1, -1, -1). Return the results for all modes in order.

Constraints

  • 1 <= N <= 100000
  • 0 <= len(roads) <= 200000
  • 1 <= K <= 10
  • 0 <= S, D < N
  • Each road is undirected
  • Each allowed_modes list is non-empty and contains mode IDs in 0..K-1
  • time_per_edge[m] and cost_per_edge[m] are non-negative integers

Examples

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

Expected Output: [(3, 15, 6), (2, 6, 8)]

Explanation: Mode 0 uses path 0-1-2-4 with 3 edges. Mode 1 uses path 0-3-4 with 2 edges.

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

Expected Output: [(0, 0, 0), (0, 0, 0)]

Explanation: Start equals destination, so every mode reaches D with 0 edges.

Hints

  1. For one fixed mode, every usable road has equal weight in terms of edge count, so BFS gives the minimum number of edges.
  2. You do not need Dijkstra here. Build the graph once, then run a separate BFS for each mode.

Part 2: Choose the optimal commute mode

You are given the final travel metrics for several commute modes. Each mode is represented by a pair (time, cost). A mode is invalid if its pair is (-1, -1), meaning the destination cannot be reached using that mode. Choose the best valid mode using these rules: smaller total time is better; if times are equal, smaller total cost is better; if both time and cost are equal, any one of those modes may be returned. Return the chosen mode ID together with its (time, cost). If all modes are invalid, return (-1, (-1, -1)). Your algorithm must run in O(K) time and must not sort the list.

Constraints

  • 1 <= len(mode_metrics) <= 100000
  • Each entry is a tuple (time, cost)
  • A valid mode has time >= 0 and cost >= 0
  • An invalid mode is represented by (-1, -1)

Examples

Input: ([(15, 6), (6, 8), (10, 2)],)

Expected Output: (1, (6, 8))

Explanation: Mode 1 has the smallest total time.

Input: ([(-1, -1), (5, 10), (5, 7), (7, 1)],)

Expected Output: (2, (5, 7))

Explanation: Modes 1 and 2 tie on time, so the cheaper one, mode 2, is chosen.

Hints

  1. You only need a single pass through the list while keeping track of the current best mode.
  2. Update the best answer if you find a smaller time, or the same time with a smaller cost.

Loading coding console...