Design Most Recently Used Queue

Problem Statement

The task is to design a specialized queue-like data structure, referred to as MRUQueue (Most Recently Used Queue). This structure must support a specific operation where an element, when accessed, is not only returned but also moved to the end of the queue, marking it as the most recently used.

Here are the functionalities to implement:

• MRUQueue(int n): This initializes the MRUQueue with n continuous elements starting from 1 up to n encapsulated in an ordered form. For instance, initializing with n = 8 will give a queue like [1,2,3,4,5,6,7,8].

• int fetch(int k): This method should access the k-th element (considering 1-based indexing), return it, and post the access, relocate this k-th element to the back of the queue. This operation marks it as the most recently utilized item.

Examples

Example 1

Input:

["MRUQueue", "fetch", "fetch", "fetch", "fetch"]
[[8], [3], [5], [2], [8]]

Output:

[null, 3, 6, 2, 2]

Explanation:

MRUQueue mRUQueue = new MRUQueue(8); // Initializes the queue to [1,2,3,4,5,6,7,8].
mRUQueue.fetch(3); // Moves the 3rd element (3) to the end of the queue to become [1,2,4,5,6,7,8,3] and returns it.
mRUQueue.fetch(5); // Moves the 5th element (6) to the end of the queue to become [1,2,4,5,7,8,3,6] and returns it.
mRUQueue.fetch(2); // Moves the 2nd element (2) to the end of the queue to become [1,4,5,7,8,3,6,2] and returns it.
mRUQueue.fetch(8); // The 8th element (2) is already at the end of the queue so just return it.

Constraints

• 1 <= n <= 2000
• 1 <= k <= n
• At most 2000 calls will be made to fetch.

Approach and Intuition

Here, let's interpret the operation and behavior using the provided examples:

1. Initialization:

   • When an instance of MRUQueue is created with a specific size, say n = 8, it internally constructs an ordered sequence ranging from 1 to n: [1,2,3,...,n].

2. Fetching Operation:

   • Fetch a Specific Element: Upon calling fetch(k), the queue should allow us to access the k-th element. This part of the operation can be visualized as plucking out the k-th item from its current position.
   • Rearrange the Queue: Once the k-th element is accessed, it should then be appended to the end of the queue. This indicates that the particular element has been used most recently.

Given the constraints, each of these steps needs to be efficient:

• The maximum queue size (n) is up to 2000, which implies the need for managing a collection up to this limit effectively.
• The operation of relocating an element to the end should minimally disrupt the order of other elements.
• Efficiently handling up to 2000 calls to fetch, ensuring quick access and modification of the queue.

Throughput and performance are crucial, especially when the queue operations (access and rearrange) are performed repeatedly. Each operation should aim for optimal time complexity to handle real-time constraints effectively.

Solutions

class BinaryIndexedTree {
private:
    vector<int> bit;
    
public:
    BinaryIndexedTree(int sz) : bit(sz + 1, 0) {}
    
    int prefixSum(int idx) {
        int total = 0;
        while (idx > 0) {
            total += bit[idx];
            idx &= idx - 1;
        }
        return total;
    }
    
    void update(int idx, int val) {
        idx += 1;
        while (idx < bit.size()) {
            bit[idx] += val;
            idx += idx & -idx;
        }
    }
};
    
class RecentlyUsedQueue {
private:
    int currSize;
    BinaryIndexedTree fenwick;
    vector<int> elements;
    
public:
    RecentlyUsedQueue(int n) : currSize(n), fenwick(n + 2000), elements(n + 2000, 0) {
        for (int i = 0; i < n; ++i) {
            fenwick.update(i, 1);
            elements[i] = i + 1;
        }
    }
    
    int fetchElement(int k) {
        int start = 0, end = currSize;
        while (start < end) {
            int middle = (start + end) / 2;
            if (fenwick.prefixSum(middle) < k) {
                start = middle + 1;
            } else {
                end = middle;
            }
        }
    
        fenwick.update(start - 1, -1);
        fenwick.update(currSize, 1);
        elements[currSize] = elements[start - 1];
        currSize++;
    
        return elements[start - 1];
    }
};