Katkat
Back

Solve Grid Path and Graph Sampling

DatabricksSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to solve a shortest-path problem with multiple constraints using Dijkstra's algorithm, followed by understanding sampling techniques for connected graph structures.

Part 1: Constrained Pathfinding

Given a directed graph where each edge has both a travel_time and a toll_fee, write a function to find the minimum travel_time required to get from a source node start to a destination end, such that the total toll_fee does not exceed a budget K.

Function Signature

def min_time_within_budget(n, edges, start, end, K):

  • n: Number of nodes (labeled 0 to n-1).
  • edges: A list of tuples (u, v, time, fee).
  • K: Maximum allowable total fee.

Return the minimum time, or -1 if no such path exists.

Examples

Example 1: n=3, edges=[(0,1,10,5), (1,2,10,5), (0,2,25,2)], K=8 Output: 25 (Path 0->2 is cheaper and fits budget, path 0->1->2 exceeds budget).

Part 2: Graph Sampling

You are given an undirected graph with V vertices. Describe an algorithm to sample a spanning forest that connects all vertices in a set S (where S is a subset of V) such that every valid spanning forest is selected with uniform probability.

Constraints

  • n up to 1,000.
  • K up to 100.
  • Time complexity should be better than exponential.

Hints

Hint 1

For the shortest path, consider state-space expansion where your state is represented by (current_node, current_fee_spent).

Hint 2

Use a priority queue to always expand the path with the smallest accumulated time for a given budget state.

Hint 3

For the graph sampling part, consider how Wilson's algorithm or random walks on graphs can be used to generate uniform spanning trees.

Follow-up questions

  • How does your shortest-path approach change if you want to find the Pareto-optimal frontier of (time, fee) pairs?
  • What is the time complexity of your shortest-path solution in terms of V, E, and K?
  • If the graph is massive and stored on disk, how would you modify your approach to sampling?