Amazon New Grad Interview Question: TaskScheduler, Fully Analyzed (Topological Sort)

OOD questions have been showing up a lot in Amazon new-grad interviews lately, so here's a careful breakdown of this one.

1. Core algorithm: topological sort on a DAG

This is the heart of the problem: Kahn's algorithm (in-degree + BFS).

Graph modeling

• Task = node
• "A depends on B" → directed edge B → A (B runs first, then A)
• Build an adjacency list graph and an in-degree map indegree

Kahn's algorithm

• Initialize the queue with every task that has in-degree 0 (no dependencies)
• BFS loop: pop the front task, visit its successors, decrement their in-degrees, and enqueue any that reach 0
• Collect the execution order order as the result

Edge case (the hidden test)

If order ends up shorter than the number of tasks, the graph has a dependency cycle and you should raise an exception. The original code leaves this part unfinished — completing it is a common ask.

Reference implementation

from collections import defaultdict, deque

class CyclicDependencyError(Exception):
    pass

class TaskScheduler:
    def __init__(self):
        self.graph = defaultdict(list)     # B -> [tasks that depend on B]
        self.indegree = {}

    def add_task(self, task, depends_on=()):
        self.indegree.setdefault(task, 0)
        for dep in depends_on:
            self.indegree.setdefault(dep, 0)
            self.graph[dep].append(task)
            self.indegree[task] += 1

    def schedule(self):
        indegree = dict(self.indegree)     # copy so schedule() can be called repeatedly
        queue = deque(t for t, d in indegree.items() if d == 0)
        order = []
        while queue:
            task = queue.popleft()
            order.append(task)
            for nxt in self.graph[task]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    queue.append(nxt)
        if len(order) != len(indegree):
            raise CyclicDependencyError("tasks contain a dependency cycle")
        return order

Time O(V + E), space O(V + E).

Discussion: is this OOD or an upgraded LeetCode problem?

Do you see this as an OOD question, or a LeetCode problem in disguise?

My take: it tests both.

• Algorithmic core: topological sort.
• OOD shell: the class interface (add_task / schedule), whether scheduling can be called repeatedly, how to define exception types, and whether to support task priorities or parallel execution later.

Would love to hear your take!