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.

Solve shortest and label-similar paths

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.

Hints

  1. 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.
  2. 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.
  3. 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).

Hints

  1. 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.
  2. 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]).
  3. 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.

Loading coding console...