Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Solve graph path, interval deletion, and robbery states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Solve graph path, interval deletion, and robbery

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: HR Screen

Part A — Optimal path with transport modes: You are given a directed weighted graph of a city. Each edge has a travel time and a transport mode label (e.g., walk, bus, subway, bike). Given a source s, destination t, and a set of allowed modes, compute the minimum-time path that only uses edges whose mode is in the allowed set. Describe your algorithm and analyze time/space complexity. Follow-up: if all modes are allowed (no restriction), what algorithm would you choose and why? How do your complexity and implementation details change? Part B — Maximize non-adjacent loot on a circle: Given n non-negative integers where nums[i] is the cash in the i-th house arranged in a circle, compute the maximum cash you can steal if you cannot rob two adjacent houses and the first and last houses are adjacent and cannot both be robbed. Explain your approach and its complexity. Part C — Delete an interval, incl. streaming: You are given a sorted list of non-overlapping half-open intervals [start, end). Implement a function deleteInterval(intervals, del) that removes del from intervals (possibly splitting intervals) and returns the remaining intervals. Follow-up: how would you process a high-throughput stream of delete intervals online? What data structures would you use to keep operations efficient and memory-bounded? Analyze complexities.

Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Solve graph path, interval deletion, and robbery states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Part A — Minimum-Time Path with Allowed Transport Modes

You are given a directed weighted graph of a city with `n` nodes (0-indexed). Each edge is `[u, v, time, mode]`: a directed edge from `u` to `v` with travel time `time` and a transport-mode label `mode` (e.g. `'walk'`, `'bus'`, `'subway'`, `'bike'`). Given a source `s`, a destination `t`, and a list `allowed_modes` of permitted modes, return the minimum total travel time of a path from `s` to `t` that uses only edges whose mode is in `allowed_modes`. If no such path exists, return `-1`. Follow-up (discuss, not coded): if all modes are allowed there is no filtering step — you run plain Dijkstra on the full edge set. With non-negative weights Dijkstra with a binary heap is O(E log V); if some weights could be negative you would switch to Bellman-Ford O(V*E).

Constraints

  • 1 <= n <= 10^4 (number of nodes)
  • 0 <= number of edges <= 10^5
  • 0 <= u, v, s, t < n
  • 1 <= time <= 10^6 (edge weights are positive)
  • mode is one of a small fixed label set (e.g. walk/bus/subway/bike)
  • The graph is directed; edges not in allowed_modes are ignored entirely

Examples

Input: (4, [[0,1,5,'walk'],[0,2,2,'bus'],[2,1,1,'bus'],[1,3,4,'subway'],[2,3,10,'walk']], ['bus','subway'], 0, 3)

Expected Output: 7

Explanation: Allowed = {bus, subway}. Path 0->2 (bus, 2) -> 1 (bus, 1) -> 3 (subway, 4) = 7. The 2->3 'walk' edge is filtered out.

Input: (4, [[0,1,5,'walk'],[0,2,2,'bus'],[2,1,1,'bus'],[1,3,4,'subway'],[2,3,10,'walk']], ['walk'], 0, 3)

Expected Output: -1

Explanation: With only 'walk' allowed, the only walk edge from 0 is 0->1, but 1->3 is 'subway' (disallowed) and 2->3 walk is unreachable. No valid path ⇒ -1.

Hints

  1. Non-negative edge weights ⇒ Dijkstra. Filter edges by allowed mode while building the adjacency list so the search never touches a disallowed edge.
  2. Use a min-heap keyed on accumulated time and the classic 'pop, skip-if-stale (d > dist[u]), relax neighbors' loop. You can early-exit the moment you pop t.
  3. Edge case: s == t returns 0 even with no edges. If t is unreachable under the allowed modes, dist[t] stays infinite ⇒ return -1.

Part B — House Robber on a Circle

There are `n` houses arranged in a circle; `nums[i]` is the non-negative amount of cash in house `i`. You cannot rob two adjacent houses, and because the houses form a circle the first and last houses are also adjacent (you cannot rob both of them). Return the maximum total cash you can steal. This is LeetCode 213 (House Robber II). The circular adjacency is the twist over the linear version.

Constraints

  • 0 <= n <= 100
  • 0 <= nums[i] <= 1000
  • House 0 and house n-1 are adjacent (cannot both be robbed)
  • Empty input returns 0; a single house returns nums[0]

Examples

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

Expected Output: 3

Explanation: Cannot rob house 0 and house 2 (adjacent on the circle), so robbing both 2's is illegal. Best is house 1 alone = 3.

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

Expected Output: 4

Explanation: Rob house 0 (1) and house 2 (3) = 4. House 0 and house 3 are adjacent but we don't pick both.

Hints

  1. Break the circular constraint by reducing to the linear House Robber problem twice: once over houses [0 .. n-2] (excluding the last) and once over [1 .. n-1] (excluding the first). The answer is the max of the two.
  2. Linear House Robber is a 2-variable DP: for each house, curr = max(curr, prev + nums[i]); then shift prev<-curr.
  3. Handle n == 0 and n == 1 separately before splitting, otherwise the slices become empty/degenerate.

Part C — Delete an Interval from a Sorted Interval List

You are given a list `intervals` of sorted, non-overlapping half-open intervals `[start, end)` and a single interval `del_interval = [d_start, d_end)` to remove. Return the set of remaining intervals after deleting `del_interval` from every interval it overlaps. Removing a deletion that lands strictly inside an interval splits that interval into two pieces. The result must remain sorted and non-overlapping. This is LeetCode 1272 (Remove Interval). The follow-up about a high-throughput online stream of deletions is discussed below. Follow-up (discuss, not coded): to process a stream of deletions online and keep memory bounded, store the live intervals in a balanced BST / order-statistics tree keyed by start (e.g. a `std::map` or a sorted container). Each deletion locates the affected range in O(log n), trims/splits the boundary intervals, and erases the fully-covered ones in O(k + log n) where k is the number of intervals destroyed. Total intervals never exceed (initial + number of splits), and splits are bounded by deletions, so memory stays proportional to the number of distinct surviving pieces.

Constraints

  • 0 <= number of intervals <= 10^4
  • Each interval is half-open [start, end) with start < end
  • Intervals are sorted by start and pairwise non-overlapping
  • del_interval is [d_start, d_end) with d_start <= d_end
  • Output preserves sorted, non-overlapping order

Examples

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

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

Explanation: Delete [1,6): [0,2)->[0,1) (left remainder), [3,4) fully covered (removed), [5,7)->[6,7) (right remainder).

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

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

Explanation: Deletion sits strictly inside [0,5), splitting it into [0,2) and [3,5).

Hints

  1. Because intervals are half-open, an interval [start, end) does NOT overlap the deletion [ds, de) when end <= ds or start >= de — keep those unchanged. The touching endpoints (end == ds or start == de) are safe to keep whole.
  2. When there IS overlap, emit up to two surviving pieces: the left remainder [start, ds) if start < ds, and the right remainder [de, end) if end > de. A deletion strictly inside one interval emits both pieces (a split).
  3. Single pass, no sorting needed since the input is already sorted; the output stays sorted automatically.

Loading coding console...