Codeium·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Coding round for a software engineer role at Codeium. One algorithmic problem, graph-based, not the hardest thing in the world but there are enough edge cases to trip you up if you're not careful.

Questions Asked (1)

You're given a graph represented as three strings: a list of vertices, a list of edges, and a candidate path. Write a function to determine whether that path is a valid Hamiltonian path. Return 'yes' if it is, or 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

The core logic isn't too bad once you break it down.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, parse the input strings into a vertex set, an adjacency set for O(1) edge lookups, and the candidate path as a list. Then iterate through the path, checking that each vertex is in the vertex set, that consecutive vertices are connected by an edge, and that no vertex is repeated. Return 'yes' if all checks pass, otherwise return the first offending vertex.

Pro tip: Clarify edge cases upfront: what if the path is empty, has a single vertex, or contains vertices not in the graph? Also, confirm whether the graph is directed or undirected, as this affects edge validation.

1. Parse and Preprocess Input

Split the vertex and edge strings into usable data structures: a set of vertices and an adjacency set (or map) for O(1) edge existence checks. Also split the candidate path into a list of vertices.

2. Validate Path Length and Vertex Membership

Check that the path length equals the number of vertices (necessary for Hamiltonian path). If not, return the first vertex that is out of bounds or not in the vertex set.

3. Iterate Through Path for Edge and Uniqueness Checks

For each vertex in the path (starting from the second), verify that it is connected to the previous vertex and that it hasn't been visited before. Return the first vertex that fails either check.

4. Return Result

If the loop completes without violations, return 'yes'. Otherwise, return the offending vertex as soon as it's found.

Key Points to Mention

Time and space complexity: O(V + E) for preprocessing and O(V) for validation, with O(V + E) space.
Handling of edge cases: empty path, single vertex, path with repeated vertices, path with vertices not in the graph.
Choice of data structures: set for vertices, set of tuples or map for edges to ensure O(1) lookups.
Clarify directed vs undirected graph: if undirected, ensure edges are stored symmetrically.
Early termination: return the first invalid vertex immediately to avoid unnecessary checks.
Assumptions about input format: how vertices and edges are delimited (e.g., comma-separated).

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