Solve shortest and label-similar paths

Q: Solve shortest and label-similar paths

This is a Coding & Algorithms interview question from dYdX for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Solve shortest and label-similar paths

Comments (0)