Frontend School

Critical Order Buffer

DSA
medium

Critical Order Buffer

Medium
Queue
Deque
Design
Data Structures

Overview

Blinkit's order processing system utilizes a pre-processing buffer to manage incoming orders efficiently. This buffer has a fixed capacity and is designed to prioritize critical orders, ensuring they are accepted even when the buffer is full, by displacing less critical orders.

What you need to do / Task

Implement the OrderBuffer class with the following specifications:

  1. constructor(capacity: number): Initializes the buffer with a specified maximum capacity.

  2. addOrder(orderId: number, isCritical: boolean): number | null: Attempts to add a new order to the buffer. The behavior depends on the buffer's current state and the isCritical flag of the new order:

    • If the buffer has available space (i.e., its current size is less than capacity), the new order is simply added to the end of the buffer.
    • If the buffer is full (size === capacity):
      • If the new order is non-critical: It is rejected immediately. No changes are made to the buffer.
      • If the new order is critical: The system attempts to make space. It searches for the oldest non-critical order currently in the buffer. If such an order is found, it is removed from the buffer, and the new critical order is added to the end. If all existing orders in the buffer are critical, the new critical order is rejected.

    The method should return the orderId of any order that was displaced (either an existing order removed from the buffer, or the new order itself if it was rejected). If no order was displaced (i.e., the new order was simply added to an available slot), return null.

Input & output

OrderBuffer(capacity: number)

  • capacity: The maximum number of orders the buffer can hold.

addOrder(orderId: number, isCritical: boolean): number | null

  • orderId: A unique identifier for the incoming order (number).
  • isCritical: A boolean flag indicating if the order is critical (true) or non-critical (false).
  • Returns: number | null. The orderId of the displaced order, or null if no order was displaced.

Clarifications

  • Oldest non-critical: If multiple non-critical orders exist in the buffer, always prioritize displacing the one that arrived earliest.
  • Unique orderId: All orderIds provided will be unique.
  • capacity = 0: If capacity is 0, all addOrder calls will result in the new order being rejected (displaced).

Examples

1

Example 1

Input:

operations = ["OrderBuffer","addOrder","addOrder","addOrder"] params = [[2],[101,false],[102,true],[103,false]]

Output:

[null,null,null,103]

Note:

Initialize buffer with capacity 2.

  1. addOrder(101, false): Buffer has space. Add [101, false]. Buffer: [[101, false]]. Returns null.
  2. addOrder(102, true): Buffer has space. Add [102, true]. Buffer: [[101, false], [102, true]]. Returns null.
  3. addOrder(103, false): Buffer is full. New order is non-critical. It is rejected. Returns 103. Buffer remains: [[101, false], [102, true]].
2

Example 2

Input:

operations = ["OrderBuffer","addOrder","addOrder","addOrder"] params = [[2],[201,false],[202,true],[203,true]]

Output:

[null,null,null,201]

Note:

Initialize buffer with capacity 2.

  1. addOrder(201, false): Buffer has space. Add [201, false]. Buffer: [[201, false]]. Returns null.
  2. addOrder(202, true): Buffer has space. Add [202, true]. Buffer: [[201, false], [202, true]]. Returns null.
  3. addOrder(203, true): Buffer is full. New order is critical. Oldest non-critical is 201. 201 is removed, 203 is added. Returns 201. Buffer: [[202, true], [203, true]].
3

Example 3

Input:

operations = ["OrderBuffer","addOrder","addOrder","addOrder","addOrder"] params = [[1],[301,true],[302,true],[303,false],[304,true]]

Output:

[null,null,302,303,304]

Note:

Initialize buffer with capacity 1.

  1. addOrder(301, true): Buffer has space. Add [301, true]. Buffer: [[301, true]]. Returns null.
  2. addOrder(302, true): Buffer is full. New order critical. All existing orders are critical. New order 302 is rejected. Returns 302. Buffer: [[301, true]].
  3. addOrder(303, false): Buffer is full. New order non-critical. New order 303 is rejected. Returns 303. Buffer: [[301, true]].
  4. addOrder(304, true): Buffer is full. New order critical. All existing orders are critical. New order 304 is rejected. Returns 304. Buffer: [[301, true]].

Constraints

Constraints & assumptions

  • 1 <= capacity <= 200
  • 1 <= orderId <= 10^9
  • The number of calls to addOrder will not exceed 10^5.
  • Time complexity for addOrder should be efficient enough to pass within typical time limits (e.g., O(capacity) is acceptable).

What interviewers evaluate

  • Correctness: The solution correctly implements the logic for adding orders, handling capacity, and prioritizing critical orders.
  • Edge Cases: The implementation robustly handles edge cases such as full buffer, empty buffer, all critical orders, and capacity of 1.
  • Data Structure Choice: Appropriate use of data structures (e.g., a queue-like structure) to manage orders and their properties.
  • Time Complexity: The addOrder operation performs within acceptable time limits given the constraints.

Loading editor...