Design Most Recently Used Queue

#1 Most AskedMedium

Design Most Recently Used Queue #1 Most Asked

Medium

16 views

Topics:

ArraysLinked ListsStacks

Design a data structure to implement a queue-like data structure that follows the Most Recently Used (MRU) principle.

Implement the MRUQueue class:

MRUQueue(int n) initializes the queue with n elements: [1, 2, 3, ..., n].
fetch(int k) moves the k^th element 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, 8]

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); // Moves the 8th element (2) to the end of the queue to become [1, 4, 5, 7, 8, 3, 6, 2] and returns it.

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the initial list and the value of 'k'?
Can the initial list contain duplicate elements, and if so, how should duplicates be handled during retrieval and reordering?
What should be returned if 'k' is out of bounds (e.g., k <= 0 or k > current number of elements)?
When an element is retrieved and moved to the end, does this also count as a 'use' for the purpose of determining MRU order for future retrievals, or is it only the retrieval itself that triggers the move?
Are there any constraints on the data types of the elements in the list (e.g., only integers, positive integers, etc.)?

Brute Force Solution

Approach

We want to design a special kind of queue that always keeps track of the most recently used items. The brute force approach involves examining every single possible arrangement or sequence of operations to see how it affects the order of items.

Here's how the algorithm would work step-by-step:

Imagine you have a collection of items. When a new item comes in or an existing item is requested, we need to make sure it's moved to the very front of our tracking list.
To see how the 'most recently used' property works, we can simulate the process by trying out each item one by one as if it were the next one to be accessed.
For each item you consider accessing, pretend you are actually accessing it and then rearrange your entire tracking list to put that item at the front.
You do this for every item currently being tracked.
By doing this for every item in turn, you are essentially checking every single possible next step and observing how it changes the order.
This exhaustive checking allows you to confirm the behavior of your 'most recently used' tracking mechanism for all potential scenarios.

Code Implementation

class MostRecentlyUsedQueue:
    def __init__(self):
        self.tracked_items = []

    def access_item(self, item_to_access):
        # We must move the accessed item to the front, signifying it's the most recent.
        if item_to_access in self.tracked_items:
            self.tracked_items.remove(item_to_access)
        self.tracked_items.insert(0, item_to_access)

    def get_queue_order(self):
        # Simulating access for every item to observe potential state changes.
        original_order = list(self.tracked_items)
        all_possible_next_states = []

        # This loop represents examining each item as the 'next' accessed.
        for _ in range(len(original_order)):
            # To check each item, we simulate accessing it and record the resulting order.
            current_item_to_simulate = original_order[_]
            simulated_queue = MostRecentlyUsedQueue()
            simulated_queue.tracked_items = list(original_order)
            simulated_queue.access_item(current_item_to_simulate)
            all_possible_next_states.append(simulated_queue.tracked_items)

        # This final order is representative of the current state after all simulations.
        return self.tracked_items

Big(O) Analysis

Time Complexity

O(n^2) – The brute force approach described involves iterating through each item currently being tracked. For each item, we simulate accessing it and then rearrange the entire tracking list to move that item to the front. If there are 'n' items in the queue, simulating the access and rearrangement for each of these 'n' items will require operations proportional to 'n' for the rearrangement itself (e.g., shifting elements). This nested operation, performing an 'n' cost operation for each of the 'n' items, results in approximately n * n total operations. This simplifies to a time complexity of O(n²).

Space Complexity

–

Optimal Solution

Approach

The goal is to keep track of items that are used most recently. Instead of searching through everything each time, we'll organize the items so the most recently used one is always easy to find and move to the front.

Here's how the algorithm would work step-by-step:

Imagine a list where the very first item is the most recently used, and the last item is the least recently used.
When an item is used, find it anywhere in the list.
Once found, take it out from its current spot.
Then, put that same item right at the beginning of the list, making it the new most recently used item.
If you need to get the most recently used item, it's always the one at the very front.
If an item isn't in the list yet, just add it to the front as the most recently used.
This way, the order of the list constantly updates to reflect what was used most recently.

Code Implementation

class MostRecentlyUsedQueue:
    def __init__(self):
        self.recent_items_list = []

    def use_item(self, item_value):
        # If the item is already in the queue, we need to move it to the front.
        if item_value in self.recent_items_list:
            self.recent_items_list.remove(item_value)
        # New or existing items are always placed at the front to signify most recent use.
        self.recent_items_list.insert(0, item_value)

    def get_most_recently_used(self):
        # The front of the list is maintained as the most recently used item.
        if not self.recent_items_list:
            return None
        return self.recent_items_list[0]

    def get_all_items_in_order(self):
        # This method provides the current state of the queue from most to least recently used.
        return self.recent_items_list

Big(O) Analysis

Time Complexity

O(n) – The core operation is finding an item in the list and moving it to the front. If we use a data structure that allows O(1) removal and O(1) insertion at the front, like a doubly linked list, finding the item takes O(n) in the worst case (traversing the list). Once found, removing and re-inserting at the front are O(1) operations. If an item is not present, adding it to the front is also O(1). Therefore, each 'use' operation has a worst-case time complexity of O(n) due to the potential search. If we perform m 'use' operations, the total time complexity would be O(m*n), but typically in interview contexts, 'n' refers to the maximum size of the queue, so we analyze a single operation as O(n).

Space Complexity

O(N) – The primary auxiliary data structure needed is a doubly linked list to maintain the order of elements. Each node in the linked list stores an item and pointers to the previous and next nodes, contributing a constant amount of space per item. Therefore, if there are N items in the queue at any given time, the total auxiliary space required is proportional to N. This results in a linear space complexity of O(N) to store the elements themselves.

Edge Cases

Case	How to Handle
Empty initial list for initialization	The data structure should initialize as empty and handle subsequent operations gracefully.
K value is out of bounds (less than 1 or greater than current size)	An exception or specific error value should be returned to indicate an invalid retrieval index.
Retrieving the very last element (most recently used)	This should be a valid operation and correctly move the last element to the end (which is itself).
Retrieving the first element (least recently used)	This should correctly move the first element to the end and update its recency.
Initial list contains duplicate elements	The data structure should treat each instance of a duplicate element as distinct for recency tracking.
Large number of elements and frequent retrievals	The chosen data structure (e.g., doubly linked list with a hash map) must provide efficient O(1) average time complexity for both operations to scale.
Initial list has only one element	Retrieving the 1st most recently used element should return that element and keep it at the end.
All elements in the initial list are identical	The structure should correctly manage the recency of each identical element, moving the retrieved one to the end.

Empty initial list for initialization

How to Handle:

The data structure should initialize as empty and handle subsequent operations gracefully.

K value is out of bounds (less than 1 or greater than current size)

How to Handle:

An exception or specific error value should be returned to indicate an invalid retrieval index.

Retrieving the very last element (most recently used)

How to Handle:

This should be a valid operation and correctly move the last element to the end (which is itself).

Retrieving the first element (least recently used)

How to Handle:

This should correctly move the first element to the end and update its recency.

Initial list contains duplicate elements

How to Handle:

The data structure should treat each instance of a duplicate element as distinct for recency tracking.

Large number of elements and frequent retrievals

How to Handle:

The chosen data structure (e.g., doubly linked list with a hash map) must provide efficient O(1) average time complexity for both operations to scale.

Initial list has only one element

How to Handle:

Retrieving the 1st most recently used element should return that element and keep it at the end.

All elements in the initial list are identical

How to Handle:

The structure should correctly manage the recency of each identical element, moving the retrieved one to the end.