Practice/Google/Leetcode 1756. Design Most Recently Used Queue

Leetcode 1756. Design Most Recently Used Queue

CodingMust

Problem

Design a special queue data structure that maintains elements in order of their most recent access. The queue should support two primary operations:

1. enqueue(val): Add a new value to the end of the queue (most recent position)
2. fetch(k): Retrieve the element at position k (using 1-based indexing), then automatically move that element to the end of the queue (making it the most recently accessed)

The queue is initialized with a capacity parameter n, though the actual number of elements may vary based on operations performed.

The key challenge is implementing the fetch operation efficiently. When you fetch an element at position k, you must return its value and reposition it to the end of the queue, shifting other elements as needed.

Requirements

1. Implement a constructor MRUQueue(n) that initializes the queue with capacity n
2. Implement enqueue(val) to add a value to the end of the queue
3. Implement fetch(k) to return the element at position k (1-indexed) and move it to the end
4. After a fetch(k) operation, the fetched element should be at the most recent position (end)
5. Elements that were after position k should shift left by one position
6. Maintain correct ordering after multiple operations

Constraints

• 1 ≤ n ≤ 2000
• 1 ≤ val ≤ 10^6
• 1 ≤ k ≤ current queue size
• At most 2000 calls will be made to enqueue and fetch combined
• You may assume all fetch operations use valid indices

Examples

Example 1:

` Operations: MRUQueue mru = new MRUQueue(5) mru.enqueue(10) mru.enqueue(20) mru.enqueue(30) mru.fetch(2)

Output: 20 Explanation:

• Initially queue is empty
• After enqueue(10): [10]
• After enqueue(20): [10, 20]
• After enqueue(30): [10, 20, 30]
• fetch(2) returns 20 (at position 2) and moves it to end: [10, 30, 20] `

Example 2:

` Operations: MRUQueue mru = new MRUQueue(3) mru.enqueue(5) mru.enqueue(10) mru.enqueue(15) mru.fetch(3) mru.fetch(2)

Output: fetch(3) returns 15, fetch(2) returns 10 Explanation:

• After enqueues: [5, 10, 15]
• fetch(3) returns 15, queue becomes: [5, 10, 15]
• fetch(2) returns 10, queue becomes: [5, 15, 10] `

Example 3:

` Operations: MRUQueue mru = new MRUQueue(4) mru.enqueue(1) mru.enqueue(2) mru.enqueue(3) mru.fetch(1) mru.enqueue(4) mru.fetch(2)

Output: fetch(1) returns 1, fetch(2) returns 3 Explanation:

• After first three enqueues: [1, 2, 3]
• fetch(1) returns 1, queue becomes: [2, 3, 1]
• enqueue(4): [2, 3, 1, 4]
• fetch(2) returns 3, queue becomes: [2, 1, 4, 3] `