Quick Overview

This question evaluates understanding of graph algorithms (topological ordering and cycle detection), layered dependency extraction, and parallel scheduling under resource constraints, testing algorithm design and complexity reasoning in the Coding & Algorithms domain.

Schedule dependent services with layered startup

Company: Snowflake

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given N services and dependency pairs (u -> v) meaning u must start before v. 1) Produce a valid startup order if one exists; otherwise detect and report a cycle. 2) Output the services by dependency layers (all in-degree-0 services first, then the next layer, etc.). 3) Given each service i has a startup time t[i] and there are K CPU cores, schedule startups to minimize total completion time while respecting dependencies; describe your algorithm, complexity, and practical heuristics for parallel execution.

Quick Answer: This question evaluates understanding of graph algorithms (topological ordering and cycle detection), layered dependency extraction, and parallel scheduling under resource constraints, testing algorithm design and complexity reasoning in the Coding & Algorithms domain.

Service Startup Order (Topological Sort with Cycle Detection)

You are given `n` services labeled `0..n-1` and a list of dependency pairs `edges`, where each pair `[u, v]` means service `u` must start before service `v`. Return any valid startup order (a topological ordering) of all services. If no valid order exists because the dependencies contain a cycle, return an empty list `[]`. Use Kahn's algorithm (BFS on in-degrees): repeatedly take a service whose remaining in-degree is 0, append it to the order, and decrement the in-degree of its dependents. If you cannot place all `n` services, a cycle exists. Example: `n = 4`, `edges = [[0,1],[0,2],[1,3],[2,3]]` -> `[0,1,2,3]` is valid (service 0 first, then 1 and 2, then 3).

Constraints

  • 0 <= n <= 10^5
  • 0 <= edges.length <= 2 * 10^5
  • Each edge is [u, v] with 0 <= u, v < n and u != v
  • Return [] if and only if the dependency graph contains a cycle

Examples

Input: (4, [[0, 1], [0, 2], [1, 3], [2, 3]])

Expected Output: [0, 1, 2, 3]

Explanation: 0 has no dependencies, so it starts first; 1 and 2 depend only on 0; 3 depends on both 1 and 2 and comes last.

Input: (3, [[0, 1], [1, 2], [2, 0]])

Expected Output: []

Explanation: 0->1->2->0 forms a cycle, so no valid startup order exists.

Hints

  1. Compute the in-degree (number of unmet dependencies) of every service.
  2. Start with all services whose in-degree is 0 — these can start immediately.
  3. As each service 'starts', decrement its dependents' in-degrees; enqueue any that reach 0.
  4. If you process fewer than n services, the remaining ones are stuck in a cycle, so return [].

Dependency Layers (Level-by-Level Startup)

You are given `n` services labeled `0..n-1` and dependency pairs `edges` where `[u, v]` means `u` must start before `v`. Group the services into startup layers: layer 0 contains every service with no dependencies (in-degree 0); layer 1 contains every service whose only dependencies are in layer 0; and so on. All services in the same layer can be started in parallel. Within each layer, return the service ids in ascending order. Return the list of layers. If the dependencies contain a cycle (so not all services can be placed), return an empty list `[]`. Example: `n = 4`, `edges = [[0,1],[0,2],[1,3],[2,3]]` -> `[[0],[1,2],[3]]`.

Constraints

  • 0 <= n <= 10^5
  • 0 <= edges.length <= 2 * 10^5
  • Each edge is [u, v] with 0 <= u, v < n and u != v
  • Within each layer, ids must be in ascending order
  • Return [] if and only if the dependency graph contains a cycle

Examples

Input: (4, [[0, 1], [0, 2], [1, 3], [2, 3]])

Expected Output: [[0], [1, 2], [3]]

Explanation: Layer 0: {0}; layer 1: {1,2} (both depend only on 0); layer 2: {3} (depends on 1 and 2).

Input: (3, [[0, 1], [1, 2], [2, 0]])

Expected Output: []

Explanation: The cycle 0->1->2->0 leaves no service with in-degree 0, so no layering is possible.

Hints

  1. Run Kahn's algorithm, but process the queue one full level at a time (like BFS levels).
  2. Snapshot the current queue size before draining the layer — everything in it belongs to the same layer.
  3. Sort each layer's ids before adding it to the result for deterministic output.
  4. If the total number of placed services is less than n, a cycle exists, so return [].

Minimum Startup Makespan on K Cores

Each of the `n` services labeled `0..n-1` has a startup time `t[i]`, with dependency pairs `edges` where `[u, v]` means `u` must finish before `v` may start. You have `k` CPU cores; each core runs one service at a time, and a service runs uninterrupted for `t[i]` time units. Simulate a list-scheduling policy and return the total completion time (makespan) — the moment the last service finishes. A service becomes ready when all of its dependencies have finished. Whenever a core is free and one or more services are ready, start the ready service with the smallest id (deterministic tie-break). If the dependencies contain a cycle so that some service can never run, return `-1`. This greedy list-scheduling rule (start the available task on the next free core) is the standard practical heuristic for parallel dependency-aware startup; the critical path (longest weighted dependency chain) is a lower bound on any schedule's makespan. Example: `n=4`, `edges=[[0,1],[0,2],[1,3],[2,3]]`, `t=[1,2,3,4]`, `k=2` -> `8`.

Constraints

  • 0 <= n <= 10^5
  • 0 <= edges.length <= 2 * 10^5
  • 1 <= k <= n (when n >= 1)
  • 0 <= t[i] <= 10^9
  • Each edge is [u, v] with 0 <= u, v < n and u != v
  • Return -1 if and only if the dependency graph contains a cycle

Examples

Input: (4, [[0, 1], [0, 2], [1, 3], [2, 3]], [1, 2, 3, 4], 2)

Expected Output: 8

Explanation: 0 runs [0,1]; then 1 ([1,3]) and 2 ([1,4]) run in parallel on 2 cores; 3 starts at 4 and finishes at 8.

Input: (3, [], [5, 2, 4], 1)

Expected Output: 11

Explanation: With 1 core and no dependencies, services run back to back: 5 + 2 + 4 = 11.

Hints

  1. A service is ready only after every dependency finishes — track unmet dependency counts like Kahn's algorithm.
  2. Use a min-heap of ready service ids (smallest-id tie-break) and a min-heap of running services keyed by finish time.
  3. Fill all free cores with ready services, then jump time forward to the next finish event and release those cores.
  4. When a service finishes, decrement its dependents' counts and enqueue any that become ready. If fewer than n services ever finish, there is a cycle: return -1.

Loading coding console...