Problem Statement (Asked By Twitter)

You manage an e-commerce website and need to keep track of the last N order IDs in a log. Design a data structure that supports the following operations efficiently:

1. record(order_id) – Adds the given order_id to the log.
2. get_last(i) – Retrieves the i-th most recent order ID from the log. It is guaranteed that i ≤ N.

Your implementation should optimize both time and space usage.

Problem link: https://leetcode.com/problems/reorder-data-in-log-files/description/

Disclaimer: Try solving the problem on your own first! Use this solution only as a reference to learn and improve.

---

Explanation:

An array is an ideal data structure for this problem since it allows constant-time indexing.
We can initialize an array of size N and maintain a log of recent orders. When recording new orders:

1. Naïve Approach:
   • Store orders in an array.
   • If the array is full, remove the oldest order and shift all elements left.
   • This results in O(N) time complexity due to shifting.
2. Optimized Approach (Circular Buffer / Ring Buffer):
   • Maintain a fixed-size array.
   • Keep track of the current index for inserting new orders.
   • When full, overwrite the oldest order instead of shifting elements.
   • Retrieve the i-th most recent order using modular arithmetic.

This ensures that both recording and retrieving orders take O(1) time.

Naïve Solution (O(N) Time for record()):

import java.util.ArrayList;
import java.util.List;

class Log {
    private final int capacity;
    private final List<Integer> log;

    public Log(int n) {
        this.capacity = n;
        this.log = new ArrayList<>();
    }

    public void record(int orderId) {
        if (log.size() >= capacity) {
            log.remove(0); // Remove the oldest order (slow operation)
        }
        log.add(orderId);
    }

    public int getLast(int i) {
        return log.get(log.size() - i);
    }

    public static void main(String[] args) {
        Log orderLog = new Log(5);
        orderLog.record(101);
        orderLog.record(102);
        orderLog.record(103);
        orderLog.record(104);
        orderLog.record(105);
        orderLog.record(106); // Oldest (101) is removed

        System.out.println(orderLog.getLast(1)); // Output: 106
        System.out.println(orderLog.getLast(3)); // Output: 104
    }
}

This approach works but record() takes O(N) time due to shifting elements in ArrayList.remove(0).

Optimized Solution (Ring Buffer / Circular Buffer, O(1) Time for record()):

class CircularLog {
    private final int[] log;
    private final int capacity;
    private int curIndex;

    public CircularLog(int n) {
        this.capacity = n;
        this.log = new int[n];
        this.curIndex = 0;
    }

    public void record(int orderId) {
        log[curIndex] = orderId; // Overwrite the oldest order
        curIndex = (curIndex + 1) % capacity; // Move index in circular fashion
    }

    public int getLast(int i) {
        int index = (curIndex - i + capacity) % capacity; // Handle negative indices
        return log[index];
    }

    public static void main(String[] args) {
        CircularLog orderLog = new CircularLog(5);
        orderLog.record(101);
        orderLog.record(102);
        orderLog.record(103);
        orderLog.record(104);
        orderLog.record(105);
        orderLog.record(106); // Overwrites 101

        System.out.println(orderLog.getLast(1)); // Output: 106
        System.out.println(orderLog.getLast(3)); // Output: 104
    }
}

Explanation of Circular Buffer:

1. Efficiently Overwriting Old Data:
   • New orders are inserted at curIndex, overwriting old values instead of shifting elements.
2. Maintaining Order:
   • curIndex = (curIndex + 1) % capacity ensures that we wrap around when reaching the array’s end.
3. Retrieving Last iii Orders:
   • Compute the correct index using:

index=(curIndex−i+capacity) mod capacity

This prevents negative indices when curIndex < i.

Complexity Analysis:

Operation	Naïve Approach	Circular Buffer
record()	O(N) (due to shifting)	O(1) (direct overwrite)
getLast(i)	O(1)	O(1)

Circular Buffer is much more efficient for large N, ensuring constant-time performance.

---

Did this solution help you understand the concept better? Let me know your thoughts in the comments below! Don’t forget to follow us on Instagram @coderz.py for more DSA tips and solutions to ace your coding interviews.