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 Stripe.

What role is this question designed for?

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

Plan bicycle routes on a city map | Stripe Coding Question

Quick Overview

This question evaluates graph algorithms and pathfinding competencies, multi-criteria optimization and weighting, data structure selection, heuristic design, handling dynamic updates and closures, and correctness and edge-case reasoning for route planning.

Plan bicycle routes on a city map

Company: Stripe

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You are given a city bicycle network as a weighted graph where edges encode distance, bike-lane availability, elevation gain, and traffic risk. Compute the bicycle route that minimizes a composite cost (e.g., time penalized by risk and elevation), subject to constraints such as avoiding roads without bike lanes or honoring temporary closures. Support alternative routes (top K), dynamic updates when a road closes, and turn-by-turn directions. Describe the data structures, the algorithmic choices (e.g., Dijkstra, A*, multi-criteria search), heuristics, tie-breaking, and the complexity. Include how you would validate correctness and handle edge cases like disconnected components.

Quick Answer: This question evaluates graph algorithms and pathfinding competencies, multi-criteria optimization and weighting, data structure selection, heuristic design, handling dynamic updates and closures, and correctness and edge-case reasoning for route planning.

You are building a bicycle route planner on a city map represented as an undirected weighted graph. Each road is given as (u, v, distance, bike_lane, elevation_gain, traffic_risk). The composite bicycle cost of a road is distance + 2 * elevation_gain + 3 * traffic_risk. Given a start intersection, an end intersection, a number K, a boolean flag require_bike_lanes, and a list of temporarily closed roads, return up to K distinct simple routes from start to end with minimum total composite cost. Each route should be returned as turn-by-turn directions, represented by the list of intersections on that path. Filter out closed roads first and, if require_bike_lanes is True, also filter out roads whose bike_lane value is 0. Sort routes by total cost; if two routes have the same cost, the lexicographically smaller path comes first. If fewer than K feasible routes exist, return all of them. Re-running the function with a different closed_roads list models dynamic updates. Because no coordinate heuristic is provided, use exact shortest-path search rather than A*. Validate correctness by ensuring every returned path is simple, feasible, correctly costed, and sorted. If the graph becomes disconnected after filtering, return [].

Constraints

1 <= n <= 100
0 <= len(roads) <= 500
1 <= distance <= 1000
0 <= elevation_gain <= 100
0 <= traffic_risk <= 100
bike_lane is either 0 or 1
1 <= k <= 10
Roads are undirected
There is at most one undirected road between any pair of intersections

Examples

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

Expected Output: [(9, [0, 3, 4]), (12, [0, 1, 4]), (12, [0, 2, 4])]

Explanation: No roads are filtered out. The cheapest route is 0->3->4 with cost 4+5=9. The next two routes both cost 12, so [0, 1, 4] comes before [0, 2, 4] lexicographically.

Input: ([(0, 1, 1, 0, 0, 0), (1, 3, 1, 1, 0, 0), (0, 2, 2, 1, 0, 0), (2, 3, 2, 1, 0, 0), (0, 3, 10, 1, 0, 0)], 0, 3, 3, True, [(3, 0)])

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

Explanation: Road 0-3 is closed even though it is listed as (3, 0), and road 0-1 is removed because it has no bike lane. Only 0->2->3 remains, with total cost 2+2=4.

Input: ([(0, 1, 1, 1, 2, 0), (1, 3, 1, 1, 0, 1), (0, 2, 2, 1, 0, 0), (2, 3, 3, 1, 1, 0), (0, 3, 8, 1, 0, 0)], 0, 3, 3, False, [])

Expected Output: [(7, [0, 2, 3]), (8, [0, 3]), (9, [0, 1, 3])]

Explanation: Composite costs matter: 0->2->3 costs 2 + (3 + 2*1) = 7, direct 0->3 costs 8, and 0->1->3 costs (1 + 2*2) + (1 + 3*1) = 9.

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

Expected Output: []

Explanation: Requiring bike lanes removes road 2-3, so the destination becomes unreachable after filtering.

Input: ([], 5, 5, 4, False, [])

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

Explanation: When start equals end, the zero-length simple route is valid even if there are no roads.

Solution

def solution(roads, start, end, k, require_bike_lanes, closed_roads):
    import heapq
    from collections import defaultdict

    if k <= 0:
        return []
    if start == end:
        return [(0, [start])]

    def normalize(a, b):
        return (a, b) if a <= b else (b, a)

    closed = {normalize(u, v) for u, v in closed_roads}
    graph = defaultdict(list)

    for u, v, distance, bike_lane, elevation_gain, traffic_risk in roads:
        if normalize(u, v) in closed:
            continue
        if require_bike_lanes and bike_lane == 0:
            continue

        cost = distance + 2 * elevation_gain + 3 * traffic_risk
        graph[u].append((v, cost))
        graph[v].append((u, cost))

    if start not in graph or end not in graph:
        return []

    for node in graph:
        graph[node].sort(key=lambda item: item[0])

    heap = [(0, (start,), start)]
    routes = []

    while heap and len(routes) < k:
        total_cost, path, node = heapq.heappop(heap)

        if node == end:
            routes.append((total_cost, list(path)))
            continue

        visited = set(path)
        for neighbor, edge_cost in graph[node]:
            if neighbor in visited:
                continue
            heapq.heappush(heap, (total_cost + edge_cost, path + (neighbor,), neighbor))

    return routes

Time complexity: O(S log S), where S is the number of partial simple paths explored; in the worst case this is exponential in the number of intersections.. Space complexity: O(S * N) in the worst case, where S is the number of stored path states and N is the path length..

Hints

First build a filtered adjacency list that removes closed roads and, when required, roads without bike lanes.
Find the best route with Dijkstra, then generate the next best simple routes by deviating from previously accepted paths (Yen's algorithm).

Quick Overview