Summary
Snowflake SWE interview with two coding problems back to back. The graph one was manageable but the rate limiter problem had a tricky sliding window constraint that took me a while to reason through cleanly.
Questions Asked(3)
Classic cycle detection in a directed graph.
Suggested Approach
Model the problem as a directed graph where each course is a node and each prerequisite pair is a directed edge, then apply cycle detection using either DFS with coloring (white/gray/black states) or Kahn's algorithm (topological sort via BFS with in-degree tracking). If a cycle exists, it's impossible to complete all courses; otherwise it is possible. Clearly articulate the time and space complexity of your chosen approach before coding.
Clarify & Model the Problem
Restate the problem as cycle detection in a directed graph, where nodes are courses and directed edges represent prerequisites. Confirm edge cases such as n=0, no prerequisites, or duplicate pairs.
Choose & Explain Your Algorithm
Select either DFS with 3-color node states (unvisited/visiting/visited) or BFS topological sort using in-degree counts (Kahn's algorithm). Briefly justify your choice by comparing their trade-offs in readability, iterative vs. recursive style, and suitability for large inputs.
Build the Graph
Construct an adjacency list from the prerequisite pairs and, if using Kahn's algorithm, compute the in-degree for each node. Walk through a small example to validate your graph construction.
Implement Cycle Detection
For DFS, traverse each unvisited node and flag a cycle if you revisit a 'visiting' (gray) node. For BFS, process nodes with in-degree zero, decrement neighbors' in-degrees, and check if all n nodes were processed at the end.
Analyze Complexity & Edge Cases
State that both approaches run in O(V + E) time and O(V + E) space, where V = n courses and E = number of prerequisite pairs. Discuss edge cases like disconnected graph components, self-loops, and isolated nodes.
Key Points to Mention
This is just the longest path in a DAG, or equivalently the number of levels in the topological order.
Suggested Approach
Model the problem as finding the longest path in a DAG (Directed Acyclic Graph), since the minimum number of semesters equals the length of the critical path through the prerequisite chain. Use topological sort (BFS/Kahn's algorithm) and track the earliest semester each course can be taken by propagating the maximum depth level from prerequisites. The answer is simply the maximum level assigned to any course.
Reframe the Problem
Recognize that since you can take unlimited courses per semester, the bottleneck is purely the longest prerequisite chain. The minimum semesters equals the length of the longest path in the prerequisite DAG.
Build the Graph and In-Degree Array
Construct an adjacency list representing course dependencies and compute the in-degree (number of prerequisites) for each course node. This sets up Kahn's BFS-based topological sort.
BFS Level-by-Level (Topological Sort)
Initialize a queue with all courses that have zero in-degree (no prerequisites) and assign them to semester 1. Process the queue level by level — each level represents one semester — decrementing in-degrees and enqueuing newly unblocked courses.
Track Maximum Semester Depth
Maintain a 'semester' array where semester[i] = max(semester[prerequisite]) + 1 for each course, ensuring each course is scheduled only after all its prerequisites are completed. The answer is the maximum value in this array.
Analyze Complexity and Edge Cases
State time complexity O(V + E) and space O(V + E). Discuss edge cases: a single chain of n courses requires n semesters, while completely independent courses require only 1 semester.
Key Points to Mention
This one tripped me up more than I expected.
Suggested Approach
Simulate the rate limiter by iterating through the sorted timestamps and applying two independent drop conditions: a per-timestamp counter check and a sliding window count check using a deque or two-pointer approach. Track dropped requests separately so they don't pollute the sliding window of processed requests. Clearly separate the two rule evaluations to keep the logic clean and testable.
Clarify the Rules and Edge Cases
Restate both drop conditions clearly: (1) more than 3 requests share the exact same timestamp, and (2) accepting a request would cause more than 20 processed requests within any 10-second window [t-9, t]. Ask whether 'same timestamp' resets after 3 drops or continues dropping all extras.
Choose the Right Data Structures
Use a deque (or queue) to maintain the sliding window of processed request timestamps, enabling O(1) eviction of timestamps outside the 10-second window. Use a counter or dictionary to track how many requests have been seen at the current timestamp for the per-timestamp rule.
Implement the Two-Rule Check
For each incoming timestamp, first check the per-timestamp count — if this is the 4th or more request at this timestamp, mark it dropped. Otherwise, evict stale entries from the deque (those with timestamp < current - 9), then check if the deque size is already 20; if so, drop the request.
Update State Only for Accepted Requests
Only append the timestamp to the sliding window deque and increment the per-timestamp counter when a request is accepted, not dropped. This ensures dropped requests don't inflate the window count or the timestamp frequency count.
Validate with Test Cases
Walk through at least two examples: one where the per-timestamp rule triggers (e.g., four requests at t=5) and one where the sliding window rule triggers (e.g., 21 requests spread across 10 seconds). Also test the boundary condition where the window is exactly 10 seconds wide (e.g., timestamps 1 and 10 should be in the same window).
Key Points to Mention
Discussion(3)
Sign in to join the discussion.
The dropped-only-processed-requests-count rule is where people fall apart on this one. A deque tracking processed timestamps is correct, but the eviction has to happen before both checks, not just before rule 2. I'd also track a per-timestamp counter separately (a hashmap or just a variable you reset when the timestamp changes) to handle rule 1 cleanly without conflating it with the window logic. Mixing the two rules into one data structure is asking for subtle bugs under pressure.
The base case thing is genuinely annoying and I'd argue it's a reasonable thing to clarify upfront rather than discover mid-solution. My read: if n=0 you return 0 because there are no courses to take, so no semesters are needed. If n>=1 and prerequisites is empty you return 1 because you can take everything in a single semester. Those are different cases and collapsing them is what causes the confusion.
For the BFS extension, the cleanest way I've seen it done is to store a dist array initialized to 1 for every node, then when you relax an edge u->v you do dist[v] = max(dist[v], dist[u]+1). Your answer is max(dist). This avoids having to think about "level" as a property of the queue state, which gets messy when you're also tracking the queue for Kahn's cycle check. You're essentially reusing the same topological traversal and just accumulating the longest path as a side effect, so the code barely grows from part A.
Kahn's is the right call for a phone screen. The DFS version with three-color visited states is more error-prone to code fast and you don't need the extra mental overhead. One thing I'd add: when you initialize in-degree counts, make sure you're iterating over all n nodes, not just the ones that appear in the prerequisite list. Nodes with no edges at all still exist and need to end up in your queue. I once submitted a version that silently undercounted the processed node total and returned the wrong answer for disconnected graphs, took me an embarrassing amount of time to find that.