Efficiently Tracking Last N Orders Using a Circular Buffer in TypeScript

A Step-by-Step Guide to Implementing a Space and Time Efficient Log for E-commerce Orders

Problem

You run an e-commerce website and want to record the last N order ids in a log. Implement a data structure to accomplish this, with the following API:

  • record(order_id): adds the order_id to the log
  • get_last(i): gets the ith last element from the log. i is guaranteed to be smaller than or equal to N.
  • You should be as efficient with time and space as possible.

Solution

To solve this problem, we can use a circular buffer (or ring buffer). A circular buffer efficiently handles recording and retrieving the last N items, maintaining constant space and allowing for efficient updates. Let’s break down the approach:

Approach:

Circular Buffer Concept:

  • The buffer will have a fixed size N, and it will "wrap around" when it reaches the end of the buffer.
  • We’ll maintain an array of size N, and a pointer (currentIndex) that keeps track of where the next order ID should be inserted.

Recording an order:

  • Every time we add an order ID, it will be inserted at the position currentIndex % N in the buffer, and the pointer currentIndex will increment.

Retrieving an order:

  • To get the ith last element, we’ll calculate the correct position in the buffer. The element at position (currentIndex - i) % N will give the ith last order. This approach is space efficient, as we only store the last N order IDs, and it’s time efficient, with both record and get_last operations having constant time complexity, O(1).

Step-by-Step Solution:

class OrderLog {
    private log: (number | null)[];  // Array to store the order IDs
    private N: number;  // Size of the buffer (the maximum number of last records to store)
    private currentIndex: number;  // Index where the next order ID should be inserted

    constructor(N: number) {
        this.N = N;
        this.log = new Array(N).fill(null);  // Initialize the buffer with null values
        this.currentIndex = 0;  // Start at the first position
    }

    // Adds an order ID to the log
    record(order_id: number): void {
        this.log[this.currentIndex % this.N] = order_id;  // Insert the order at the current index
        this.currentIndex++;  // Move the index forward
    }

    // Gets the ith last order ID from the log
    get_last(i: number): number | null {
        if (i < 1 || i > this.N) {
            throw new Error("Index out of bounds");
        }
        const index = (this.currentIndex - i + this.N) % this.N;  // Calculate the correct index
        return this.log[index];  // Return the ith last order ID
    }
}

Explanation:

  1. Constructor: Initializes the log with a size N. The log is an array filled with null to represent empty slots, and currentIndex starts at 0.
  2. record(order_id): Adds the given order_id to the buffer at position currentIndex % N. After each insertion, currentIndex is incremented.
  3. get_last(i): Retrieves the ith last element by calculating the correct index in the circular buffer. The formula (currentIndex - i + N) % N ensures that even if the index becomes negative (when currentIndex - i is less than 0), it wraps around to the correct position.

Time and Space Complexity:

  • Time Complexity: Both record and get_last operations are O(1), as array indexing and modulo operations are constant time.
  • Space Complexity: The space used is O(N), since we only maintain an array of size N.

Example Usage:

const orderLog = new OrderLog(5);  // We will store the last 5 order IDs

orderLog.record(101);
orderLog.record(102);
orderLog.record(103);
orderLog.record(104);
orderLog.record(105);

console.log(orderLog.get_last(1));  // Output: 105 (most recent)
console.log(orderLog.get_last(3));  // Output: 103 (third last)
console.log(orderLog.get_last(5));  // Output: 101 (fifth last)

orderLog.record(106);
console.log(orderLog.get_last(1));  // Output: 106
console.log(orderLog.get_last(5));  // Output: 102 (101 is overwritten)

Alternative Approaches:

  • Deque or Linked List: You could also use a doubly linked list or a deque for this problem. However, this would generally result in a more complex implementation and potentially higher memory overhead compared to the circular buffer.

The circular buffer is the most space- and time-efficient solution for this scenario, meeting the requirement to efficiently manage the last N order IDs.

If you like this, please think about buying me a coffee! ☕️.

Burhanuddin’s Code Compendium

Thank you for being a part of the Burhanuddin’s Code Compendium community! Before you go: