Is Design Most Recently Used Queue easy or hard?

The problem is rated Medium on LeetCode. A basic array simulation is straightforward, but the optimized solution requires understanding Fenwick Trees or ordered sets to efficiently support k-th element queries.

Design Most Recently Used Queue Python/Java solution

Most implementations maintain an array for element storage and a Fenwick Tree for index tracking. Python, Java, and C++ versions follow the same pattern: binary search on the tree to find the k-th active index, remove it, then append the element to the end while updating the tree.

How to solve Design Most Recently Used Queue in O(log n)?

Store elements in indexed positions and maintain a Fenwick Tree tracking which indices are active. Use prefix sums and binary search to locate the k-th active index in O(log n). After retrieving the value, mark the position inactive and append the element at the end with another update.

What is the best approach for Design Most Recently Used Queue?

The most efficient approach uses a Binary Indexed Tree (Fenwick Tree) combined with binary search to locate the k-th active element. Each fetch operation becomes O(log n) for both querying and updating the structure. This avoids the costly shifting required in a simple array implementation.

Is Design Most Recently Used Queue asked at Google/Amazon/Meta?

Problems involving queue design, order statistics, and Fenwick Trees appear frequently in interviews at companies like Google, Amazon, and Meta. Variants that require finding the k-th element in a dynamic structure are especially common in system design and data structure rounds.

What data structure is used in Design Most Recently Used Queue?

The optimal implementation uses a Binary Indexed Tree (Fenwick Tree) to track active indices and support prefix sum queries. Some solutions also model the structure as an ordered set that supports k-th element lookup and dynamic updates.

What is the time complexity of Design Most Recently Used Queue?

The optimal solution runs in O(log n) time per fetch operation using a Fenwick Tree or order statistics structure. A naive array-based implementation requires O(n) time because removing the k-th element shifts remaining elements.

Description Hints 3 Solution Video 7:13

1756. Design Most Recently Used Queue

Medium78.0% acceptance2 companiesPremium elsewhere, free here

Design a queue-like data structure that moves the most recently used element to the end of the queue.

Implement the MRUQueue class:

MRUQueue(int n) constructs the MRUQueue with n elements: [1,2,3,...,n].
int fetch(int k) moves the k^th element (1-indexed) to the end of the queue and returns it.

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 3^rd 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 5^th 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 2^nd 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 8^th 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.

Follow up: Finding an O(n) algorithm per fetch is a bit easy. Can you find an algorithm with a better complexity for each fetch call?

Asked at 2 companies

Verizon

Google

Topics

Hints open one at a time

Hint 1

You can store the data in an array and apply each fetch by moving the ith element to the end of the array (i.e, O(n) per operation).

Hint 2

A better way is to use the square root decomposition technique.

Hint 3

You can build chunks of size sqrt(n). For each fetch operation, You can search for the chunk which has the ith element and update it (i.e., O(sqrt(n)) per operation), and move this element to an empty chunk at the end.

7:13

Still stuck?Read the written solution, or watch a walkthrough.

Open solution