Design Most Recently Used Queue - Practice Coding Problems

Design Most Recently Used Queue - Problem

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 kth element (1-indexed) to the end of the queue and returns it.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["MRUQueue", "fetch", "fetch", "fetch"], values = [3, 1, 2, 3]

› Output: [1, 2, 3]

💡 Note: MRUQueue(3) creates [1,2,3]. fetch(1) returns 1, queue becomes [2,3,1]. fetch(2) returns 3, queue becomes [2,1,3]. fetch(3) returns 3, queue becomes [2,1,3].

Example 2 — Repeated Fetch

$ Input: operations = ["MRUQueue", "fetch", "fetch"], values = [2, 2, 1]

› Output: [2, 1]

💡 Note: MRUQueue(2) creates [1,2]. fetch(2) returns 2, queue becomes [1,2]. fetch(1) returns 1, queue becomes [2,1].

Example 3 — Single Element

$ Input: operations = ["MRUQueue", "fetch"], values = [1, 1]

› Output: [1]

💡 Note: MRUQueue(1) creates [1]. fetch(1) returns 1, queue remains [1].

Constraints

1 ≤ n ≤ 2000
1 ≤ k ≤ current queue length
At most 2000 calls will be made to fetch

Visualization

Tap to expand

Understanding the Visualization

Input

Queue [1,2,3,4,5] and fetch(3)

Process

Move element at position 3 to end

Output

Return 3, queue becomes [1,2,4,5,3]

Key Takeaway

🎯 Key Insight: Choose data structure that minimizes movement cost - linked list beats array

Asked in

G Google 15 a Amazon 12 f Facebook 8

The key insight is choosing the right data structure for efficient element movement. The brute force array approach requires O(n) time per fetch due to element shifting. The doubly linked list approach achieves O(1) per fetch by direct node manipulation. Best approach is doubly linked list. Time: O(1) per operation, Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Doubly Linked List	O(1)	O(n)	Use doubly linked list for efficient removal and append operations
Array with Linear Movement	O(n)	O(n)	Store elements in array, move by shifting elements one by one

Doubly Linked List — Algorithm Steps

Create doubly linked list with array of node pointers
For fetch(k): access node via array[k-1]
Remove node from current position
Append node to tail
Update array positions

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial List

Doubly linked list [1↔2↔3↔4↔5]

Remove Node 3

Unlink node 3 from position

Append to Tail

Link node 3 at end: [1↔2↔4↔5↔3]

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct ListNode {
    int val;
    struct ListNode* prev;
    struct ListNode* next;
} ListNode;

typedef struct {
    ListNode* head;
    ListNode* tail;
} MRUQueue;

MRUQueue* mruQueueCreate(int n) {
    MRUQueue* obj = (MRUQueue*)malloc(sizeof(MRUQueue));
    obj->head = (ListNode*)malloc(sizeof(ListNode));
    obj->tail = (ListNode*)malloc(sizeof(ListNode));
    obj->head->val = 0;
    obj->tail->val = 0;
    obj->head->next = obj->tail;
    obj->tail->prev = obj->head;
    obj->head->prev = NULL;
    obj->tail->next = NULL;
    
    for (int i = 1; i <= n; i++) {
        ListNode* node = (ListNode*)malloc(sizeof(ListNode));
        node->val = i;
        ListNode* prevNode = obj->tail->prev;
        prevNode->next = node;
        node->prev = prevNode;
        node->next = obj->tail;
        obj->tail->prev = node;
    }
    
    return obj;
}

int mruQueueFetch(MRUQueue* obj, int k) {
    ListNode* curr = obj->head->next;
    for (int i = 0; i < k - 1; i++) {
        curr = curr->next;
    }
    
    // Remove from current position
    curr->prev->next = curr->next;
    curr->next->prev = curr->prev;
    
    // Add to end
    ListNode* prevNode = obj->tail->prev;
    prevNode->next = curr;
    curr->prev = prevNode;
    curr->next = obj->tail;
    obj->tail->prev = curr;
    
    return curr->val;
}

int* solution(char operations[][20], int* values, int opCount, int* returnSize) {
    int* results = (int*)malloc(opCount * sizeof(int));
    int resultCount = 0;
    MRUQueue* mruQueue = NULL;
    
    for (int i = 0; i < opCount; i++) {
        if (strcmp(operations[i], "MRUQueue") == 0) {
            mruQueue = mruQueueCreate(values[i]);
        } else if (strcmp(operations[i], "fetch") == 0) {
            results[resultCount++] = mruQueueFetch(mruQueue, values[i]);
        }
    }
    
    *returnSize = resultCount;
    return results;
}

int main() {
    char operations[100][20];
    int values[100];
    int opCount = 0;
    
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    char* token = strtok(line, "[],\"\n ");
    while (token != NULL) {
        if (strlen(token) > 0) {
            strcpy(operations[opCount], token);
            opCount++;
        }
        token = strtok(NULL, "[],\"\n ");
    }
    
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[],\n ");
    int valCount = 0;
    while (token != NULL) {
        if (strlen(token) > 0) {
            values[valCount++] = atoi(token);
        }
        token = strtok(NULL, "[],\n ");
    }
    
    int returnSize;
    int* result = solution(operations, values, opCount, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Direct node access and O(1) removal/append operations

✓ Linear Growth

Space Complexity

O(n)

Linked list nodes plus array of node references

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Doubly Linked List — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler