Implement Random Connectivity and Grid Routing
Company: Databricks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
This entry contains two independent coding problems.
## Problem 1: Uniformly connect node groups
You are given `k` non-empty, disjoint groups of unique node IDs, for example:
```text
groups = [[1], [2, 3], [4, 5, 6]]
```
Treat each group as an already-connected component. You may add an undirected edge only between two nodes that belong to different groups. To add such an edge, choose one node from one group and one node from another group.
Implement a function that returns exactly `k - 1` edges such that all groups become connected. The result must be random, and every valid minimal connecting edge set should be sampled uniformly at random.
Example valid outputs for the input above include:
```text
[(1, 3), (2, 5)]
[(1, 6), (3, 4)]
```
Each output contains `k - 1 = 2` edges and connects all three groups.
Requirements:
- Do not add edges within the same group.
- Return a minimal connected structure, so the number of edges must be exactly `k - 1`.
- The sampling distribution should be uniform over all valid minimal connecting edge sets.
- Be prepared to explain why simple enumeration or a standard randomized minimum-spanning-tree-style approach may not produce a uniform random result.
## Problem 2: Find the best transportation mode on a grid
You are given a 2D grid. Each cell contains one of the following values:
```text
S = start
D = destination
X = obstacle
1 = Walk
2 = Bike
3 = Car
4 = Train
```
You are also given arrays `cost[1..4]` and `time[1..4]`, where `cost[m]` and `time[m]` are the per-step cost and per-step time for transportation mode `m`.
You may move only up, down, left, or right. Diagonal movement is not allowed. Obstacles cannot be entered.
### Base version
You must choose exactly one transportation mode and use that mode for the entire trip from `S` to `D`. For a chosen mode `m`, you may move through cells labeled `m`, plus the start and destination cells.
Return the mode that reaches the destination with the smallest total travel time. If multiple modes have the same minimum time, return the one with the smallest total cost.
### Follow-up 1
Now allow switching between transportation modes during the route. Switching modes adds a given penalty. Compute the optimal route from `S` to `D` under the same objective: minimize total time, then minimize total cost.
### Follow-up 2
Add a maximum number of allowed mode switches. Compute the optimal route while respecting this switch limit.
Quick Answer: This question evaluates understanding of randomized combinatorial sampling and graph connectivity by requiring a uniformly random minimal set of inter-group edges that connects disjoint components, and it probes reasoning about sampling distributions and biases that can arise from naïve randomized or MST-style approaches; category/domain: Coding & Algorithms, graph theory and randomized algorithms, level: conceptual understanding with practical algorithm design considerations. The grid routing problem evaluates shortest-path and multi-criteria optimization skills—finding time-minimal routes with cost tie-breaking, mode-switch penalties, and switch-count constraints—testing the ability to model augmented state spaces and perform constrained search; category/domain: Coding & Algorithms, graph algorithms and dynamic programming, level: practical algorithm implementation and optimization.
You are given a rectangular grid where each cell is one of: 'S' (start), 'D' (destination), 'X' (obstacle), or '1'..'4' (a transportation mode). You may move up, down, left, or right.
This problem asks you to solve the follow-up version of the grid-routing task: mode switching is allowed, but each switch adds a time penalty and you may use at most max_switches switches.
Rules:
- Entering a numbered cell 'm' means that step uses transportation mode m.
- Each step taken with mode m adds time[m-1] to total time and cost[m-1] to total cost.
- If you move from a numbered cell of one mode to a numbered cell of a different mode, you switch modes before entering the new cell. That adds switch_penalty to total time and uses 1 switch.
- Moving from S to your first cell starts a mode and does not count as a switch.
- Moving into S or D from an active mode uses your current mode for that step.
- If S and D are adjacent, you may move directly from S to D in one step using any one mode, and that does not count as a switch.
Return a tuple (minimum_time, minimum_cost) among all valid routes from S to D that use at most max_switches switches. Compare routes lexicographically: minimize total time first, and among those, minimize total cost. If D is unreachable, return (-1, -1).
Constraints
- 1 <= rows, cols <= 100
- grid contains exactly one 'S' and exactly one 'D'
- Each grid cell is one of 'S', 'D', 'X', '1', '2', '3', '4'
- len(cost) == 4 and len(time) == 4
- 1 <= cost[i], time[i] <= 10^6
- 0 <= switch_penalty <= 10^6
- 0 <= max_switches <= 20
Examples
Input: (["S11", "XX1", "11D"], [5, 7, 9, 11], [2, 3, 4, 5], 4, 0)
Expected Output: (8, 20)
Explanation: The only valid route uses mode 1 for 4 steps: S -> 1 -> 1 -> 1 -> D. Total time is 4*2 = 8 and total cost is 4*5 = 20.
Input: (["S1D", "222"], [5, 1, 8, 8], [2, 1, 4, 4], 3, 0)
Expected Output: (4, 4)
Explanation: Top route uses mode 1 for 2 steps: time 4, cost 10. Bottom route uses mode 2 for 4 steps: time 4, cost 4. Same time, so choose lower cost.
Hints
- A plain BFS is not enough because steps have different time and cost values. Think about shortest paths on a weighted graph.
- Your state needs more than just (row, col). The best route can depend on the current mode and how many switches you have already used.