Design Most Recently Used Queue

Design Most Recently Used Queue is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Design Patterns pattern, in the Design (General/Specific) subpattern.

Problem statement

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.

Topics and companies

Topics: Array, Hash Table, Stack, Design, Binary Indexed Tree, Ordered Set.

Reported in interviews at Google.

How to practise Design Most Recently Used Queue on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(sqrt(n)) per fetch operation. Each fetch may require traversing up to O(sqrt(n)) buckets and rebalancing up to O(sqrt(n)) elements. time and O(n). All elements are stored exactly once in the buckets, and the number of buckets is O(sqrt(n)). space.

Open Design Most Recently Used Queue in the code editor, or read the Design Most Recently Used Queue editorial for a worked solution with its approach and complexity analysis.

Where Design Most Recently Used Queue sits in the DSA pattern sheet

• Design Patterns pattern guide
• Design (General/Specific) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Design Most Recently Used Queue

Other problems that use the same Design (General/Specific) and Design Patterns techniques:

• All O`one Data Structure — Hard, same subpattern
• Design a Stack With Increment Operation — Medium, same subpattern
• Design a Text Editor — Hard, same subpattern
• Design Circular Deque — Medium, same subpattern
• Design Circular Queue — Medium, same subpattern
• Design Compressed String Iterator — Easy, same subpattern