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
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