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 Take-home Project rounds at Codeium.

What role is this question designed for?

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

Validate whether a given sequence is a Hamiltonian path

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.

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.

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

Expected Output: 'B'

Explanation: Repeated vertex.

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

Expected Output: 'C'

Explanation: Missing C deterministically.

Hints

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

Quick Overview