← Citadel Interview Insights

Citadel·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Jun 2026

Summary

Citadel software engineer interview that focused on graph problems, specifically course scheduling with topological sort. Pretty algorithmic heavy, no fluff.

Questions Asked (1)

Q1

Given a list of courses and their prerequisites, return a valid ordering in which all courses can be completed. If no valid ordering exists due to a cycle, return an empty array.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

Knew this was topological sort the second I read it, which was a relief.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the courses and prerequisites as a directed graph and perform a topological sort using either Kahn's algorithm (BFS with in-degree tracking) or DFS with cycle detection. If the topological sort produces an ordering containing all courses, return it; otherwise, return an empty array to indicate a cycle.

Pro tip: At Citadel, interviewers value clean, efficient code and clear communication. Before coding, briefly explain your approach and mention the time and space complexity (O(V+E) time, O(V+E) space). Also, discuss how you would handle edge cases like duplicate prerequisites or disconnected graphs.

1. Clarify and Model the Problem

Confirm input format (e.g., number of courses, list of prerequisite pairs) and that courses are labeled 0 to n-1. Model the problem as a directed graph where an edge u->v means u must be taken before v.

2. Choose an Algorithm

Decide between Kahn's algorithm (BFS) and DFS-based topological sort. Both are valid; Kahn's is often easier to explain and implement iteratively.

3. Implement Topological Sort

For Kahn's: compute in-degrees, enqueue nodes with in-degree 0, then repeatedly dequeue and reduce in-degrees of neighbors. For DFS: perform post-order traversal and reverse the result, using a recursion stack to detect cycles.

4. Detect Cycles and Return Result

If the topological ordering contains all courses, return it; otherwise, return an empty array. In Kahn's, this is when the processed count is less than the number of courses.

5. Analyze Complexity and Test

State time and space complexity (O(V+E)). Walk through a simple example and a cycle case to verify correctness.

Key Points to Mention

  • Graph representation: adjacency list for efficiency
  • Topological sort algorithms: Kahn's (BFS) vs DFS
  • Cycle detection: in-degree count or recursion stack
  • Time and space complexity: O(V+E) time, O(V+E) space
  • Handling edge cases: empty input, no prerequisites, multiple valid orderings
  • Trade-offs: iterative vs recursive, memory usage, and clarity

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