How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Databricks.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Databricks during technical interviews.

Solve Grid Path and Graph Sampling | Databricks Coding Question

Quick Overview

This question evaluates graph algorithms and probabilistic/combinatorial reasoning, covering multi-criteria shortest-path optimization (minimizing travel time with a secondary fee objective) and uniform random sampling of edge sets that connect disjoint components.

Solve Grid Path and Graph Sampling

Company: Databricks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

This interview note described two coding problems: 1. **Grid path with shortest time and lowest cost** You are given an `m x n` grid containing a start cell `S`, an end cell `E`, blocked cells, and open cells. You may move up, down, left, or right to adjacent open cells. Each move takes exactly 1 unit of time. Some cells also have a non-negative fee that is paid when you enter that cell. Find a path from `S` to `E` that minimizes total travel time; among all shortest-time paths, choose one with the minimum total fee. Return the minimum time and minimum fee, or report that no path exists. 2. **Uniformly sample edges that connect multiple components** You are given `n` disjoint connected undirected graphs `G1, G2, ..., Gn`. You may add edges only between vertices belonging to different graphs, and any such cross-graph edge is allowed. Write a function that returns a random set of exactly `n - 1` new edges such that, after adding them, the union of all `n` graphs becomes connected. The returned edge set must be sampled **uniformly** from the set of all valid connecting edge sets of size `n - 1`.

Quick Answer: This question evaluates graph algorithms and probabilistic/combinatorial reasoning, covering multi-criteria shortest-path optimization (minimizing travel time with a secondary fee objective) and uniform random sampling of edge sets that connect disjoint components.

Part 1: Shortest-Time Grid Path with Minimum Fee

You are given a rectangular grid and a fee matrix of the same size. Each grid cell is one of 'S', 'E', '.', or '#'. 'S' is the start, 'E' is the end, '.' is an open cell, and '#' is blocked. You may move up, down, left, or right to adjacent non-blocked cells. Every move costs 1 unit of time. When you enter a cell, you pay that cell's fee; the starting cell's fee is not paid because you begin there. Find a path from 'S' to 'E' that minimizes total travel time. If several paths have the same minimum travel time, choose the one with the smallest total fee. Return the pair (minimum_time, minimum_fee), or None if no path exists.

Constraints

1 <= number of rows, number of columns <= 200
grid contains exactly one 'S' and exactly one 'E'
fees[r][c] is a non-negative integer
You may move only in 4 directions: up, down, left, right
Blocked cells are marked with '#'; their fee values, if present, are ignored

Examples

Input: (["S..", "..E"], [[0, 5, 1], [1, 1, 2]])

Expected Output: (3, 4)

Explanation: All shortest paths take 3 moves. The cheapest such path is down, right, right with total fee 1 + 1 + 2 = 4.

Input: (["S.E", "..."], [[0, 100, 1], [1, 1, 1]])

Expected Output: (2, 101)

Explanation: The direct top-row path is shortest with time 2, even though a longer route has a smaller fee. Time has higher priority than fee.

Input: (["S#E"], [[0, 0, 0]])

Expected Output: None

Explanation: The blocked cell prevents any path from S to E.

Input: (["SE"], [[0, 7]])

Expected Output: (1, 7)

Explanation: Edge case: the end is adjacent to the start, so only one move is needed.

Hints

Treat the path score as a pair: first minimize time, then minimize fee.
A priority queue works well because every move adds a non-negative pair (1, fee_of_next_cell).

Part 2: Uniformly Sample Connecting Cross-Graph Edges

You are given the connected components of a graph as a list of vertex sets. Component i is already internally connected, and components are pairwise disjoint. You may add edges only between vertices belonging to different components, and any such cross-component edge is allowed. Return exactly n - 1 new edges so that all components become connected. Every valid connecting edge set of size n - 1 must be equally likely. To make outputs reproducible for testing, your function also receives a seed and should use it to drive its pseudorandom choices. Return the final edge set as a lexicographically sorted list of tuples.

Constraints

1 <= number of components <= 100000
Each component is non-empty
All vertex labels are distinct integers
The total number of vertices across all components is <= 200000
Do not enumerate all valid connecting edge sets; their number can be enormous

Examples

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

Expected Output: []

Explanation: Edge case: there is only one component, so the graph is already connected.

Input: ([[1, 2], [10, 11, 12]], 1)

Expected Output: [(1, 12)]

Explanation: With two components, there is only one component-level tree edge. The seed determines which actual vertex pair is chosen.

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

Expected Output: [(1, 4), (2, 4)]

Explanation: The weighted Prüfer sequence selects component 2, creating component edges (0, 2) and (1, 2). The seed then picks the concrete vertices.

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

Expected Output: [(2, 3), (2, 6), (3, 4)]

Explanation: The sampled component tree has three cross-component links, and the seed fixes the chosen endpoints inside those components.

Hints

If you compress each connected component into one super-node, any valid answer with exactly n - 1 added edges corresponds to a tree on those super-nodes.
For a fixed component tree, count how many concrete vertex-edge choices it expands to. Prüfer sequences can sample trees with degree-dependent weights.

Quick Overview