Design log Order records

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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
Input
["OrderLog(3)", "record", "record", "record", "get_last", "get_last"]
[[3],          [10],       [20],      [30],      [1],       [2]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
OrderLog orderLog = new orderLog(3); // log = []
orderLog.record(10);  // log = [10]
orderLog.record(20);  // log = [10, 20]
orderLog.record(30);  // log = [10, 20, 30]
orderLog.get_last(1); // Retrieves the most recent order ID (30).
orderLog.get_last(2); // Retrieves the second-most recent order ID (20).

Solution

Method 1 - Using Circular Array

We can first define following:

OrderLog: The class representing the log.
N: The maximum number of order IDs to store.
orders: A circular array to store the order IDs.
head: Index pointing to the oldest order ID in the array.

Record method

First we implement record method.

record(order_id): Adds the new order ID to the log.
- It updates the head index using modulo (%) to achieve circular behavior within the array.
- This ensures that the latest order ID is always stored at the most recently accessed position.
get_last(i): Retrieves the ith last order ID from the log.
- It checks for invalid index values.
- It calculates the actual index in the array by considering the head position and the requested position (i).
- The modulo operation is used again to handle cases where the requested position might be beyond the beginning of the array (due to the circular nature).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class OrderLog {
  vector<int> log;
  int N, idx = 0, count = 0;
public:
  OrderLog(int n) : log(n), N(n) {}
  void record(int order_id) {
    log[idx] = order_id;
    idx = (idx + 1) % N;
    if (count < N) count++;
  }
  int get_last(int i) {
    if (i > count) return -1;
    return log[(idx - i + N) % N];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
type OrderLog struct {
  log   []int
  n     int
  idx   int
  count int
}
func NewOrderLog(n int) *OrderLog {
  return &OrderLog{log: make([]int, n), n: n}
}
func (o *OrderLog) Record(orderId int) {
  o.log[o.idx] = orderId
  o.idx = (o.idx + 1) % o.n
  if o.count < o.n {
    o.count++
  }
}
func (o *OrderLog) GetLast(i int) int {
  if i > o.count {
    return -1
  }
  return o.log[(o.idx-i+o.n)%o.n]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class OrderLog {
  private final int N;
  private final int[] orders;
  private int head; // Index of the oldest order ID

  public OrderLog(int N) {
    this.N = N;
    this.orders = new int[N];
    this.head = 0;
  }

  public void record(int orderId) {
    orders[head] = orderId;
    head = (head + 1) % N; // Update head using modulo to handle circular behavior
  }

  public int getLast(int i) {
    if (i < 0 || i >= N) {
      throw new IllegalArgumentException("Index out of bounds");
    }
    // Calculate the actual index based on head and requested position
    int actualIndex = (head - i - 1 + N) % N;
    return orders[actualIndex];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class OrderLog:
  def __init__(self, n):
    self.n = n
    self.orders = [None] * n  # Initialize array with None values
    self.head = 0  # Index of the oldest order ID

  def record(self, order_id):
    self.orders[self.head] = order_id
    self.head = (self.head + 1) % self.n  # Update head using modulo

  def get_last(self, i):
    if 0 <= i < self.n:
      # Calculate actual index based on head and requested position
      actual_index = (self.head - i - 1 + self.n) % self.n
      return self.orders[actual_index]
    else:
      raise IndexError("Index out of bounds")

Complexity

record()

⏰ Time complexity: O(1), due to the constant-time array access and update.
🧺 Space complexity: O(n), as we are storing the elements in array

getLast()

⏰ Time complexity: O(1), Runs in constant time (O(1)) as well, because the calculation of the actual index using modulo is also a constant-time operation.
🧺 Space complexity: O(n), as we are storing the elements in array

Problem#

Examples#

Solution#

Method 1 - Using Circular Array#

Record method#

Code#

Complexity#