Frontend School

Warehouse Package Scheduling

DSA
medium

Warehouse Package Scheduling

Medium
Graph
Topological Sort
Kahn's Algorithm
DFS

Overview

Flipkart's warehouses handle millions of packages daily. Efficient processing and loading are crucial for timely deliveries and customer satisfaction. Some packages have interdependencies – for instance, a fragile item might need special packaging before it can be combined with other items on a pallet, or certain documents must be processed before their associated physical packages can be moved. This problem focuses on determining a valid sequence for processing packages based on these dependencies to ensure smooth and error-free operations.

What you need to do / Task

Implement a function that takes the total number of packages and a list of their direct dependencies, then returns a valid processing order.

  1. Given numPackages (an integer representing the total count of packages, labeled from 0 to numPackages - 1) and dependencies (an array of [prerequisite, dependent] pairs).
  2. A dependency [p, d] signifies that package p must be fully processed before package d can begin processing.
  3. Your function should return any valid processing order for all numPackages. Each package must appear exactly once in the returned order.
  4. If it's impossible to process all packages due to circular dependencies (e.g., A depends on B, B depends on C, and C depends on A), return an empty array [].

Input & output

  • numPackages: An integer, N, representing the total number of unique packages, identified by zero-based indices from 0 to N-1.
  • dependencies: An array of number[] where each inner array [p, d] denotes a direct dependency: package p must be processed before package d.
  • Return: An number[] representing a valid processing order of all packages. If no such order exists due to circular dependencies, return an empty array [].

Clarifications

  • Packages are identified by zero-based indices (0, 1, ..., numPackages - 1).
  • Dependencies are direct; if A must precede B, and B must precede C, you will be given [A, B] and [B, C], but not necessarily [A, C] (though A indirectly precedes C).
  • If dependencies is empty, any order is valid. A simple natural order [0, 1, ..., numPackages-1] is acceptable.
  • If numPackages is 0, an empty array [] should be returned.

Examples

1

Example 1

Input:

numPackages = 4, dependencies = [[1,0],[2,0],[3,1],[3,2]]

Output:

[3,1,2,0]

Note:

Package 3 must be processed before 1 and 2. Packages 1 and 2 must be processed before 0. A valid processing order is 3, then 1, then 2, then 0. Another valid order would be [3,2,1,0].

2

Example 2

Input:

numPackages = 3, dependencies = [[0,1],[1,2],[2,0]]

Output:

[]

Note:

There is a circular dependency (0 -> 1 -> 2 -> 0), which means no valid processing order can be achieved for all packages. Thus, an empty array is returned.

3

Example 3

Input:

numPackages = 3, dependencies = []

Output:

[0,1,2]

Note:

With no dependencies, any order is valid. The simplest is the natural order of package indices.

Constraints

Constraints & assumptions

  • 1 <= numPackages <= 10^5
  • 0 <= dependencies.length <= min(numPackages * (numPackages - 1) / 2, 10^5)
  • 0 <= prerequisite, dependent < numPackages for all [prerequisite, dependent] pairs.
  • All prerequisite and dependent values in dependencies are valid package indices within the numPackages range.
  • No duplicate dependency pairs will be provided in the input.

Out of scope

  • Optimizing for a specific processing order (e.g., lexicographically smallest, minimizing idle time, or maximizing throughput). Any valid topological sort is acceptable.
  • Handling invalid input types or values (e.g., negative numPackages, prerequisite or dependent outside of [0, numPackages-1] range).

What interviewers evaluate

  • Correctness in identifying a valid topological order for packages.
  • Ability to detect and gracefully handle circular dependencies by returning an empty array.
  • Efficient graph construction and traversal (considering both time and space complexity).
  • Clean, readable, and well-structured code that adheres to best practices.

Loading editor...