← Snowflake Interview Insights
Topological sort, so I knew the shape of it pretty fast.
Model the services and dependencies as a directed graph, then perform a topological sort using Kahn's algorithm (BFS) or DFS. If the sort processes all nodes, return the order; otherwise, a cycle exists and can be reported by identifying nodes with remaining in-degree or using DFS back edges.
Pro tip: Mention that Kahn's algorithm naturally detects cycles when the output size is less than N, and you can optionally return the cycle path for debugging. Also note that if multiple valid orders exist, any is acceptable unless a specific tie-breaking rule is given.
Confirm whether the graph is directed, if multiple valid orders are acceptable, and how to handle duplicate edges or disconnected components. Ask if the output should be any valid order or a specific one (e.g., lexicographically smallest).
Create an adjacency list for outgoing edges and an in-degree array for each node. Iterate through the given pairs (u, v) to populate these structures.
Use Kahn's algorithm: enqueue all nodes with in-degree 0, then repeatedly dequeue a node, add it to the order, and decrement the in-degree of its neighbors, enqueuing any that reach 0. Alternatively, use DFS with a recursion stack to detect cycles.
If the topological order contains fewer than N nodes, a cycle exists. For Kahn's, the remaining nodes with non-zero in-degree are part of cycles. For DFS, a back edge indicates a cycle; you can reconstruct the cycle path if needed.
State that both approaches run in O(N + E) time and O(N + E) space. Mention that Kahn's is often preferred for cycle detection because it's iterative and avoids recursion depth issues.
AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.
This is basically BFS levels on the topo sort, which flows naturally from part one.
This is a topological sort problem where you need to group nodes into layers based on their dependencies. Use Kahn's algorithm: repeatedly find all nodes with in-degree zero, add them as the current layer, remove them, and update in-degrees of their neighbors. Continue until all nodes are processed.
Pro tip: Mention that this is essentially a level-order topological sort, and clarify that within each layer, the order of services doesn't matter—only the grouping does. Also, be prepared to discuss how to handle cycles if they exist.
Calculate the in-degree (number of unmet dependencies) for each service by iterating over all edges. Initialize a queue with all services that have in-degree zero.
While the queue is not empty, record the current size as the layer size, then process exactly that many nodes. For each node, add it to the current layer and decrement the in-degree of its neighbors; if a neighbor's in-degree becomes zero, add it to the queue.
After processing each batch, add the current layer to the result list. Continue until the queue is empty.
If the total number of processed nodes is less than the total number of services, a cycle exists. In that case, either report the cycle or handle it based on requirements.
AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.
Model the problem as a DAG scheduling problem with K identical machines, then propose a list-scheduling algorithm using critical-path priorities (e.g., HLF or CP) to minimize makespan. Analyze complexity as O(V log V + E) for priority computation and O(V log K) for scheduling, and discuss practical heuristics like work-stealing and dynamic priority adjustment.
Pro tip: Acknowledge that the problem is NP-hard in general, so focus on heuristics and mention that Snowflake's real-world systems often use hybrid approaches combining static priorities with runtime load balancing.
Confirm that services form a DAG, startup times are known, and K cores are identical. Ask if preemption is allowed or if services can be split.
State that minimizing total completion time (makespan) with dependencies is NP-hard. For K=1, it's topological order; for K>1, it's P|prec|Cmax.
Compute each node's critical path length (longest path to sink). Use a priority queue to always schedule the ready node with the highest critical path on an available core.
Time: O(V log V + E) for critical paths, O(V log K) for scheduling. Space: O(V+E). Mention that list scheduling gives a 2-approximation for makespan.
Mention dynamic priority updates, work-stealing, batching small tasks, and handling stragglers. Discuss when to prefer throughput vs. latency.
AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.