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

What role is this question designed for?

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

Solve shortest and label-similar paths

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 shortest and label-similar paths states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: dYdX

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Part A — Unweighted shortest path: You are given an undirected, unweighted graph with vertices labeled 0..n-1 and an edge list. Given start node s and target node t, return both the length and one actual shortest path (as a list of vertices). If no path exists, return an empty list. Discuss your algorithm and its time and space complexity. Part B — Path matching a label sequence with minimal mismatches: Each vertex i has a string label name[i]. Given a sequence target[0..m-1] of labels, find a path v0..v_{m-1} such that consecutive vertices are adjacent in the graph and the number of indices i where name[v_i] != target[i] is minimized. Return one optimal vertex sequence. Explain your approach, how you reconstruct the path, and analyze complexity for n up to 10^4, edges up to 10^4, and m up to 10^3.

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 shortest and label-similar paths states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Unweighted Shortest Path with Reconstruction

You are given an undirected, unweighted graph with `n` vertices labeled `0..n-1` and an edge list `edges`. Given a start node `s` and a target node `t`, return a two-element list `[length, path]` where `length` is the number of edges on a shortest path from `s` to `t` and `path` is one actual shortest path as a list of vertices from `s` to `t`. If `s == t`, return `[0, [s]]`. If no path exists, return `[-1, []]`. Use breadth-first search (BFS) from `s`: BFS visits vertices in non-decreasing distance order, so the first time you reach `t` you have a shortest path. Track a parent pointer for each visited vertex and walk it back from `t` to `s` to reconstruct the path. With `n` vertices and `E` edges, BFS runs in O(n + E) time and O(n + E) space (adjacency list + visited/parent arrays + queue).

Constraints

1 <= n <= 10^4
0 <= number of edges <= 10^4
edges[i] = [u, v] with 0 <= u, v < n, u != v
0 <= s, t < n
The graph is undirected and unweighted; it may be disconnected and may contain cycles.

Examples

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

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

Explanation: Shortest route from 0 to 3 is 0->1->2->3 of length 3; the alternative 0->1->4->5->3 has length 4.

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

Expected Output: [-1, []]

Explanation: Vertices 0 and 3 lie in different connected components, so no path exists.

Input: (1, [], 0, 0)

Expected Output: [0, [0]]

Explanation: Start equals target: the path is just [0] with length 0.

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

Expected Output: [4, [0, 1, 2, 3, 4]]

Explanation: A simple path graph; the only route from 0 to 4 has length 4.

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

Expected Output: [1, [0, 2]]

Explanation: The direct edge 0-2 gives a length-1 path, shorter than 0->1->2.

Hints

BFS explores nodes in order of increasing distance, so the first time you dequeue (or reach) t you already have a shortest path — no need to keep searching.
Store a parent[] pointer when you first discover each node; to rebuild the path, walk parent[] from t back to s and reverse the result.
Handle s == t (length 0, path [s]) and the disconnected case (return [-1, []]) explicitly.

Path Matching a Label Sequence with Minimal Mismatches

Each vertex `i` of an undirected graph (`n` vertices, edge list `edges`) has a string label `name[i]`. Given a target sequence `target[0..m-1]` of labels, find a walk `v0, v1, ..., v_{m-1}` such that consecutive vertices are adjacent in the graph (edge between `v_{i-1}` and `v_i`) and the number of indices `i` where `name[v_i] != target[i]` is minimized. Return one optimal vertex sequence (length `m`). Vertices may repeat. This is dynamic programming over positions (the same shape as LeetCode 1548). Let `dp[i][v]` be the minimum number of mismatches for a walk of length `i+1` that ends at vertex `v` and is aligned with `target[0..i]`. Base case: `dp[0][v] = (name[v] != target[0])`. Transition: `dp[i][v] = min over neighbors u of dp[i-1][u]) + (name[v] != target[i])`. The answer cost is `min_v dp[m-1][v]`; reconstruct the path with a parent table. To make the output deterministic, sort each adjacency list and scan vertices in ascending order, keeping the first minimizing choice. Complexity is O(m * (n + E)) time because each position relaxes every edge once.

Constraints

1 <= n <= 10^4
0 <= number of edges <= 10^4
1 <= m <= 10^3 (length of target)
name has length n; target has length m; labels are arbitrary strings
Consecutive vertices in the returned walk must be adjacent; vertices may repeat.
If m >= 2 and the graph has no edges, no valid walk of length m exists; return an empty list.

Examples

Input: (5, [[0,1],[1,2],[2,3],[3,4]], ['a','b','c','d','e'], ['a','b','c'])

Expected Output: [0, 1, 2]

Explanation: Vertices 0,1,2 have labels a,b,c matching target exactly along the path edges 0-1 and 1-2, giving 0 mismatches.

Input: (3, [[0,1],[1,2]], ['x','y','z'], ['a','b','c'])

Expected Output: [0, 1, 0]

Explanation: No label matches any target, so every valid walk costs 3 mismatches; [0,1,0] is one optimal walk (edges 0-1 and 1-0).

Input: (4, [[0,1],[1,2],[2,3],[3,0]], ['p','q','p','q'], ['p','q','p'])

Expected Output: [0, 1, 0]

Explanation: name[0]=p, name[1]=q match target p,q; returning to 0 (label p) matches target[2]=p, so 0 mismatches. (Path 0-1-2 is equally optimal; the deterministic tie-break returns this one.)

Input: (1, [], ['a'], ['a'])

Expected Output: [0]

Explanation: Single vertex, single target label that matches: the walk is just [0] with 0 mismatches.

Input: (2, [[0,1]], ['a','b'], ['b','a','b'])

Expected Output: [1, 0, 1]

Explanation: Vertex 1=b, 0=a, 1=b matches target b,a,b exactly while alternating across the single edge, for 0 mismatches.

Hints

Think position-by-position: dp[i][v] = cheapest way to align target[0..i] onto a walk ending at vertex v. Initialize dp[0][v] with just the mismatch at v.
The transition only looks at neighbors of v in the previous position: dp[i][v] = min(dp[i-1][u] for u adjacent to v) + (name[v] != target[i]).
Keep a parent[i][v] = the u that achieved the minimum, then walk it back from the best end vertex to reconstruct one optimal sequence. Sort adjacency lists for a deterministic tie-break.

Quick Overview