← Oracle Interview Insights

Oracle·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Oracle SWE interview with a graph/topological sort problem. The simplifying constraint they gave made it more approachable than a full DAG question, but you still had to know your cycle detection.

Questions Asked (1)

Q1

Given n courses labeled 0 to n-1 and a list of prerequisite pairs where b must be taken before a, return any valid ordering to complete all courses. Each course has at most one direct prerequisite.

Algorithms & Data Structures
Author's notes

The one-prerequisite constraint is a gift if you notice it early.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the courses as a directed graph where edges represent prerequisites, then perform a topological sort. Since each course has at most one direct prerequisite, the graph is a collection of chains and trees, allowing for a simpler traversal or even a direct mapping approach.

Pro tip: Clarify with the interviewer whether the input is guaranteed to be a valid DAG (no cycles). If cycles are possible, you must detect and handle them; otherwise, you can assume a solution exists and focus on efficiency.

1. Understand the problem and constraints

Restate the problem: given n courses and prerequisite pairs (b before a), return any valid order. Note the constraint: each course has at most one direct prerequisite, which simplifies the graph structure.

2. Choose a representation

Represent the graph using an adjacency list for prerequisites (b -> a) and an array to track in-degrees or a map from course to its prerequisite. Since each course has at most one prerequisite, you can also use a parent array.

3. Select an algorithm

Use topological sort: either Kahn's algorithm (BFS with in-degree tracking) or DFS with cycle detection. Given the constraint, you can also process chains directly by following prerequisites.

4. Implement and handle edge cases

Write code to compute the order. Handle cases like no prerequisites, multiple disconnected components, and possible cycles (if not guaranteed acyclic). Return any valid order.

5. Analyze complexity and test

State time and space complexity (O(n + m) for graph traversal). Walk through a small example to verify correctness, including edge cases.

Key Points to Mention

  • Topological sorting is the standard approach for dependency resolution.
  • The constraint of at most one direct prerequisite simplifies the graph to a set of chains or trees, allowing for a simpler solution.
  • Kahn's algorithm (BFS) vs. DFS: discuss trade-offs, such as ease of cycle detection.
  • Time complexity: O(n + m) where n is number of courses and m is number of prerequisite pairs.
  • Space complexity: O(n + m) for storing the graph and auxiliary data structures.
  • Handling cycles: if the graph may contain cycles, detect and return an error or empty list.

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