Frontend School

Bigbasket Item Preparation Sequence

DSA
easy

Bigbasket Item Preparation Sequence

Easy
Graph
Topological Sort

Overview

In Bigbasket's fulfillment centers, efficiently preparing and stocking grocery items is critical. Some items have direct prerequisites, meaning one item must be fully prepared or stocked before another can begin. For instance, a base ingredient might need to be processed before it can be used in a final product, or a specific shelf must be stocked before items are placed on it. Ensuring these dependencies are met is crucial for smooth and timely operations.

What you need to do / Task

Your task is to determine a valid sequence in which all grocery items can be prepared, respecting all given prerequisite relationships. If item A is a prerequisite for item B, then A must appear earlier than B in the preparation sequence. If it's impossible to prepare all items due to conflicting or circular dependencies, you should indicate this.

Input & output

  • numItems: An integer representing the total number of distinct grocery items. These items are labeled from 0 to numItems - 1.
  • prerequisites: An array of pairs, where each inner array [u, v] signifies that item u must be prepared before item v.
  • Return: An array of integers representing any valid preparation order for all numItems. If no such order exists (e.g., due to a circular dependency), return an empty array [].

Clarifications

  • Items are 0-indexed, meaning they are identified by integers from 0 up to numItems - 1.
  • A valid preparation order must contain all numItems exactly once.
  • If multiple valid orders exist, any one of them is acceptable.

Examples

1

Example 1

Input:

numItems = 2, prerequisites = [[1, 0]]

Output:

[1,0]

Note:

Item 1 must be prepared before Item 0. A valid sequence is [1, 0].

2

Example 2

Input:

numItems = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]

Output:

[3,1,2,0]

Note:

Item 3 must be prepared before 1 and 2. Items 1 and 2 must be prepared before 0. A valid sequence is [3, 1, 2, 0]. [3, 2, 1, 0] would also be valid.

3

Example 3

Input:

numItems = 2, prerequisites = [[0, 1], [1, 0]]

Output:

[]

Note:

There is a circular dependency: Item 0 requires 1, and Item 1 requires 0. No valid preparation sequence can be formed.

Constraints

Constraints & assumptions

  • 1 <= numItems <= 2000
  • 0 <= prerequisites.length <= numItems * (numItems - 1) / 2
  • 0 <= u, v < numItems for all [u, v] in prerequisites
  • u != v for all [u, v] in prerequisites (no item is a prerequisite for itself)
  • All pairs [u, v] in prerequisites are unique.

What interviewers evaluate

  • Correctness: The solution must correctly identify a valid topological order or detect cycles.
  • Efficiency: The algorithm should operate within optimal time and space complexity for graph traversal.
  • Code Quality: The code should be well-structured, readable, and follow good programming practices.
  • Problem Solving: Demonstrate the ability to model the problem as a graph and apply a standard graph algorithm.

Loading editor...