Optiver·Software Engineer·Online Assessment (OA)·Intermediate

Intermediate

Jun 2026

Summary

Optiver software engineer interview with a tree validation problem that looks straightforward until you actually read the constraints carefully. The priority ordering of error codes is where things get interesting and where I think most people trip up.

Questions Asked (1)

Given a list of directed edges, determine if they form a valid binary tree. If not, return the first applicable error code from a fixed priority list (INVALID_INPUT, TOO_MANY_CHILDREN, MULTIPLE_PARENTS, CYCLE, MULTIPLE_ROOTS). If valid, return the in-order traversal as a space-separated string, where left/right child assignment follows edge insertion order.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The core logic isn't that bad.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First clarify the input format and error priority, then design a single-pass algorithm that builds the tree while validating constraints in the given order. Use a hash map to track parent-child relationships and detect cycles, and finally perform an in-order traversal if all checks pass.

Pro tip: Explicitly confirm the error priority and edge cases (e.g., empty list, self-loop, duplicate edges) with the interviewer before coding—this shows attention to detail and prevents wasted effort on the wrong assumptions.

1. Clarify requirements and edge cases

Ask about input format (e.g., list of pairs, node labels), definition of a valid binary tree, and confirm the exact error priority. Discuss edge cases like empty input, single node, duplicate edges, and self-loops.

2. Design validation strategy

Plan to check errors in the given priority order: first validate input (e.g., non-empty, no self-loops), then track children count per node (TOO_MANY_CHILDREN), then parents count (MULTIPLE_PARENTS), then detect cycles (CYCLE), and finally ensure exactly one root (MULTIPLE_ROOTS).

3. Implement tree construction and validation

Iterate through edges, maintaining a map of node to its children (in insertion order) and a map of node to its parent. Check constraints incrementally and return the first error encountered according to priority.

4. Perform in-order traversal

If all validations pass, perform a recursive or iterative in-order traversal starting from the root, respecting left/right child assignment based on insertion order. Return the traversal as a space-separated string.

5. Test and discuss trade-offs

Walk through test cases (valid tree, each error type) and discuss time/space complexity (O(n) time, O(n) space). Mention alternative approaches (e.g., union-find for cycle detection) and their trade-offs.

Key Points to Mention

Error priority order and how to check each condition efficiently without multiple passes.
Using a hash map to track children (with insertion order) and parents for each node.
Cycle detection via DFS or union-find, and why it's necessary after checking parent/child counts.
Ensuring exactly one root by counting nodes with no parent, and handling disconnected components.
In-order traversal implementation (recursive vs iterative) and formatting the output as a space-separated string.
Time and space complexity analysis, and potential optimizations for large inputs.

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