cswork / libraryOpen practice workspace

Coding questions · Codeium

Validate whether a given sequence is a Hamiltonian path

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.

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)

Validate a Hamiltonian Path Description

Hints

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