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

If you’re not a medium member, you can read the story through this link.

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…