Design Most Recently Used Queue
Difficulty: Medium
Category: DSA
Topics: Array, Hash Table, Stack, Design, Binary Indexed Tree, Ordered Set
Asked at: Google
You are given an integer `n` representing the size of a queue initialized with the integers from `1` to `n` in increasing order (`[1, 2, ..., n]`). You need to design a data structure that supports the following operation:
- `fetch(k)`: Removes the `k`-th element (1-indexed) from the front of the queue, moves it to the end of the queue, and returns its value.
Implement the **Most Recently Used Queue** that supports initializing with `n` and performing multiple `fetch(k)` operations efficiently.
Constraints:
- `1 <= n <= 2000`
- `1 <= k <= current queue size` for each `fetch(k)` operation
- The number of `fetch` operations will not exceed `2000`
Return the value of the element fetched for each `fetch(k)` operation.