Frontend School

Order Processing System

DSA
medium

Order Processing System

Medium
Queue
Design
Data Structures

Overview

Modern e-commerce platforms handle a continuous stream of customer orders, each with varying urgency. Efficiently managing these orders, especially when processing resources are limited, is crucial for customer satisfaction and operational efficiency. This problem challenges you to design a core component of such a system, focusing on prioritizing critical orders while maximizing throughput within resource constraints.

What you need to do / Task

You are tasked with implementing the OrderProcessingSystem class. This class should manage a pool of incoming orders, prioritize premium orders, and ensure that a fixed maximum number of orders are processed concurrently.

Your implementation must include the following methods:

  1. constructor(capacity: number): Initializes the order processing system with a specified maximum number of orders that can be processed simultaneously.
  2. addOrder(orderId: number, isPremium: boolean): void: Adds a new order to the system. isPremium indicates whether the order should be given higher priority.
  3. startProcessing(): number | null: Attempts to start processing an order.
    • If there are available processing slots AND there are orders waiting, it should select an order to process. Premium orders always take precedence over regular orders.
    • The selected order's ID should be returned. This order is now considered 'in-progress' and occupies a processing slot.
    • If no slots are available OR no orders are waiting, it should return null.
  4. completeOrder(orderId: number): void: Marks an order as completed. This frees up the processing slot occupied by orderId. You can assume orderId was previously returned by startProcessing() and is currently in an 'in-progress' state.

Input & output

Class: OrderProcessingSystem

Constructor:

  • capacity: number: The maximum number of orders that can be processed concurrently.
  • No return value.

Method: addOrder

  • orderId: number: A unique identifier for the order.
  • isPremium: boolean: true if the order is premium, false otherwise.
  • No return value.

Method: startProcessing

  • No parameters.
  • Returns number | null: The orderId of the order that just started processing, or null if no order could be started.

Method: completeOrder

  • orderId: number: The ID of the order to mark as complete.
  • No return value.

Clarifications

  • Unique Order IDs: All orderId values passed to addOrder will be unique.
  • Valid Completion: completeOrder will only be called with orderIds that were previously returned by startProcessing() and are currently in an 'in-progress' state. You do not need to handle cases where an invalid orderId is passed to completeOrder.
  • Order of Processing for Same Priority: If multiple premium orders are waiting, any one of them can be chosen (e.g., FIFO order is fine). The same applies to regular orders.

Examples

1

Example 1

Input:

operations = ["OrderProcessingSystem","addOrder","addOrder","startProcessing","startProcessing","addOrder","startProcessing","completeOrder","startProcessing","completeOrder","startProcessing"], params = [[1],[101,false],[102,true],[],[],[103,false],[],[102],[],[101],[]]

Output:

[null,null,null,102,null,null,null,null,101,null,103]

Note:

  1. Initialize with capacity 1. 2. Add regular order 101. 3. Add premium order 102. 4. Start processing: capacity is 1, premium order 102 is chosen. Returns 102. 5. Start processing: capacity is full (102 is processing). Returns null. 6. Add regular order 103. 7. Start processing: capacity is full (102 is processing). Returns null. 8. Complete order 102. Slot is free. 9. Start processing: capacity is 1, regular order 101 is chosen. Returns 101. 10. Complete order 101. Slot is free. 11. Start processing: capacity is 1, regular order 103 is chosen. Returns 103.
2

Example 2

Input:

operations = ["OrderProcessingSystem","addOrder","addOrder","addOrder","startProcessing","startProcessing","startProcessing","completeOrder","startProcessing","completeOrder","startProcessing"], params = [[2],[201,false],[202,true],[203,false],[],[],[],[202],[],[201],[]]

Output:

[null,null,null,null,202,201,null,null,203,null,null]

Note:

  1. Initialize with capacity 2. 2. Add regular 201. 3. Add premium 202. 4. Add regular 203. 5. Start processing: capacity 2, premium 202 chosen. Returns 202. 6. Start processing: capacity 1, regular 201 chosen. Returns 201. 7. Start processing: capacity full (202, 201 processing). Returns null. 8. Complete 202. Slot free. 9. Start processing: capacity 1, regular 203 chosen. Returns 203. 10. Complete 201. Slot free. 11. Start processing: no orders waiting. Returns null.
3

Example 3

Input:

operations = ["OrderProcessingSystem","addOrder","startProcessing","completeOrder","startProcessing"], params = [[1],[301,true],[],[301],[]]

Output:

[null,null,301,null,null]

Note:

  1. Initialize with capacity 1. 2. Add premium 301. 3. Start processing: 301 chosen. Returns 301. 4. Complete 301. Slot free. 5. Start processing: no orders waiting. Returns null.

Constraints

Constraints & assumptions

  • 1 <= capacity <= 1000
  • 1 <= orderId <= 10^9
  • The total number of addOrder calls will not exceed 10^5.
  • The system should be efficient for a large number of operations.
  • Standard library queue implementations (e.g., Array.prototype.shift for JS, Queue<T> for TS) are allowed.

What interviewers evaluate

  • Correctness: The system correctly prioritizes premium orders and respects the maximum concurrent processing capacity.
  • Data Structure Choice: Appropriate use of queues and other data structures to manage orders and processing state efficiently.
  • Edge Cases: Proper handling of scenarios like an empty system, full capacity, or no premium orders.
  • Clarity & Readability: Clean, well-structured, and understandable code.

Loading editor...