← Codeium Interview Insights

Codeium·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Apr 2026

Summary

Coding round at Codeium for a software engineer role. One algorithmic problem, graph-based, sounded approachable until I actually had to think through all the edge cases.

Questions Asked (1)

Q1

You're given a graph represented as three strings encoding the vertices, edges, and a candidate path. Determine whether that path is a valid Hamiltonian path. If it is, return 'yes'. If not, return the first vertex where validation breaks down, either because there's no edge connecting it to the previous vertex, or because it's already been visited.

Algorithms & Data Structures
Author's notes

I started by parsing the input strings which took longer than I'd like to admit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Parse the three strings into a vertex set, adjacency set, and path list. Simulate the path while maintaining a visited set, checking at each step that the current vertex is unvisited and connected to the previous vertex. Return 'yes' if all vertices are visited exactly once, otherwise return the first vertex that fails validation.

Pro tip: Clarify edge cases upfront: whether the graph is directed or undirected, if self-loops or multiple edges exist, and whether the path must include all vertices. This shows attention to detail and prevents incorrect assumptions.

1. Parse and Validate Input

Split the vertex, edge, and path strings to extract the set of vertices, adjacency relationships, and the sequence of vertices in the candidate path. Handle any delimiters and ensure the path only contains valid vertices.

2. Check Path Length and Coverage

Verify that the path length equals the number of vertices. If not, it cannot be Hamiltonian; identify the first missing or extra vertex as the failure point.

3. Simulate Traversal with Visited Set

Iterate through the path, maintaining a visited set. For each vertex after the first, check if it has already been visited; if so, return it as the failure. Also check if there is an edge from the previous vertex to the current vertex; if not, return the current vertex.

4. Return Result

If the loop completes without failure, return 'yes'. Otherwise, return the first vertex where validation failed.

Key Points to Mention

  • Definition of a Hamiltonian path: visits every vertex exactly once.
  • Handling of directed vs. undirected graphs and how edge representation affects adjacency checks.
  • Use of a hash set for O(1) visited checks and adjacency lookups.
  • Time complexity: O(V + E) for parsing and O(V) for path validation, where V is number of vertices and E is number of edges.
  • Edge cases: empty graph, single vertex, path with repeated vertices, path missing vertices, disconnected graph.
  • Importance of returning the first failure vertex, not just a boolean.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.