Quick Overview

This question evaluates understanding of graph theory concepts—specifically Hamiltonian paths, graph representation parsing, and sequential edge validation— within the Coding & Algorithms domain and emphasizes practical application of graph traversal and validation rather than purely theoretical proofs.

Validate whether a given sequence is a Hamiltonian path

Company: Codeium

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

You are given `strArr`, an array of **three strings** describing an undirected graph and a proposed vertex visit order: 1. `strArr[0]`: a comma-separated list of vertices in parentheses, e.g. `"(A,B,C)"` 2. `strArr[1]`: a comma-separated list of undirected edges in parentheses, e.g. `"(A-B,C-D)"` 3. `strArr[2]`: a comma-separated list of vertices representing the proposed path order, e.g. `"(C,A,B)"` Task: - Determine whether the proposed order is a **Hamiltonian path**: it must visit **every vertex in the graph exactly once**, and every consecutive pair in the order must be connected by an edge. Output: - Return `"yes"` if the order forms a Hamiltonian path. - Otherwise, return the **first vertex in the given order where the path fails**, meaning the earliest vertex `order[i]` such that either: - `order[i]` is not a vertex in the graph, or - `order[i]` has already appeared earlier in the order, or - there is **no edge** between `order[i-1]` and `order[i]` (for `i > 0`). Assumptions/constraints: - The graph has at least 2 vertices and is connected. - Vertices are represented by single tokens like `A`, `B`, `X`, etc. Examples: - Input: `["(A,B,C)", "(B-A,C-B)", "(C,A,B)"]` → Output: `"yes"` - Input: `["(X,Y,Z,Q)", "(X-Y,Y-Q,Y-Z)", "(Z,Y,Q,X)"]` → Output: `"Q"` (because there is no edge between `Q` and `X`)

Quick Answer: This question evaluates understanding of graph theory concepts—specifically Hamiltonian paths, graph representation parsing, and sequential edge validation— within the Coding & Algorithms domain and emphasizes practical application of graph traversal and validation rather than purely theoretical proofs.

Parse a graph and proposed order, returning yes or the first vertex where the path fails.

Constraints

  • Graph is undirected

Examples

Input: (['(A,B,C)', '(B-A,C-B)', '(C,B,A)'],)

Expected Output: 'yes'

Explanation: Valid path.

Input: (['(X,Y,Z,Q)', '(X-Y,Y-Q,Y-Z)', '(Z,Y,Q,X)'],)

Expected Output: 'X'

Explanation: Fails at X after Q.

Hints

  1. Check membership, duplicates, and each consecutive edge in order.

Loading coding console...