Master Queue & Deque Problems in Python
Queues look simple on paper, but they quietly decide how real systems behave under pressure.
⏱️ Estimated reading time: 12 minutes
Generally
accepted, queuing (queue) is a first-in-first-out (FIFO) data structure. In
reality, queues are used in many non-academic contexts as a means of survival.
All
systems that deal with any kind of traffic, task, request, or data at scale
eventually face this same fundamental problem: it is impossible for everything
to be processed simultaneously. When traffic arrives at a system faster than it
can be processed or handled, that system needs to determine what stays in the
queue, what is dropped, and the order in which it will process traffic. At this
point, we begin to view queues as more than just a structure for storing data;
they also represent the design of a system.
In
large-scale systems (i.e., an e-commerce site selling out of an item due to
demand and the associated product returns and replacement orders; an online
video platform attempting to manage tens of millions of users watching videos
at the same time, etc.) queues are used as a harbour between demand (requests)
and a predetermined capacity (the maximum number of workers available to
process requests). Queues provide an element of fairness, stability, and
predictability to otherwise chaotic workloads.
Queues
also aid in learning how people in the real world design their systems under
stress. Qubing allows you to develop a framework for designing and building
systems by forcing you to consider the components of flow, ordering, and
constraint. These are all restrictions that an engineer must solve for when
designing schedulers, background, worker, message pipeline, and rate-limited
API applications.
When
you expand your understanding of the applications of queuing beyond the
textbooks, you find that most of the complex problems you face with respect to
writing better code are, in fact, not difficult to code. Instead, it is about
how you perform and order your operations.
🟢 EASY (Foundational +
Pattern Building)
I.
Implement Queue using Array / List
🧠 Explanation
The most common mistake we see when using a Queue via Stacks is when you Pop an item from the Queue, you immediately reverse the Stack to preserve FIFO characteristics (even though this maintains the FIFO characteristics – results in many unnecessary repetitive calls, increased execution time).
The ultimate goal here is
not to simply store items that are inserted into the Queue, but to ensure that
the order of insertion is preserved while only allowing LIFO operations on the
Stack. In order to manage item insertion efficiently without incursions on
execution time, our technique involves a horizontal arrangement of two Stacks
to maintain the order of elements in each Stack and only when necessary will we
rearrange the order of the items stored in both Stacks.
⚙️Logic in Steps
1.
Two internal stacks are maintained:
a. One
stack handles all incoming elements.
b. The
other stack is responsible for serving elements in queue order.
2.
Every push operation adds elements
directly to the input stack, preserving insertion order.
3.
When a pop or peek operation is requested,
the solution first checks whether the output stack already contains elements
ready to be served.
4.
If the output stack is empty, all elements
from the input stack are transferred into it one by one.
5.
This reversal places the oldest element on
top, effectively restoring FIFO behaviour.
6.
Once transferred, repeated pop and peek
operations can be performed without additional movement until the output stack
is exhausted.
7.
The queue is considered empty only when both
stacks contain no elements, ensuring accurate state tracking.
Time Complexity
1.
push() → O(1)
2.
pop() → O(1) amortized
3.
peek() → O(1) amortized
Although transferring
elements appears expensive, each element moves between stacks only once,
keeping overall operations efficient.
Space Complexity
O(n): All elements are
stored across the two stacks in the worst case.
📝Key Takeaways from This
Problem and Solution
1. Though
the FIFO behaviour can be simulated using a LIFO construct through controlled
reversal, creating separate insertion and removal responsibilities is an
effective way to improve the logic and efficiency of programming.
2. Delaying
expensive operations until the very last moment helps optimise overall
performance.
3. In
many circumstances, amortised analysis is more important than the absolute
worst-case costs of operations in the design of a system.
4. This design reflects real-world scheduling and buffering strategies that are used by many scalable systems.
🧠 Explanation
Using nested loops to
check each character individually is an error many will encounter while solving
this issue. Although it will probably function correctly for smaller input
sizes, as the length of the string increases, this method will become less efficient.
The solution offered here
uses two distinct frequency counters to keep track of character frequencies and
order. Using two separate counters will allow the solution to be as efficient
as possible.
⚙️Logic in Steps
1. A
frequency array is a method of counting the number of occurrences of each
character in a given string.
2. A
queue is used to keep track of which characters are next in line to be
processed and where they came from in the original string.
3. As
you read through the string, you will add the character and the index to the
queue and update their frequency counts.
4. Once
the string has been processed, you will begin working with the queue; you will
look at the first character in the queue.
5. If
the first character has a frequency of 1, then return that index. If the first
character does not have a frequency of 1, remove it from the queue and keep
going through the queue until either:
6. A
unique character is found after processing all the items in the queue, or -1 is
returned.
⏱ Time and Space Complexity
Time Complexity:
O(n): Each character is
processed at most twice.
Space Complexity:
O(n): Frequency map and
queue store up to n elements.
📝Key Takeaways from This
Problem and Solution
1. Separation
of the order and frequency is critical to solve the efficiency problem.
2. Queue
is the most appropriate data structure to find the first valid element in a
list.
3. When
performance is critical, do not use pop(0) on a list.
4. When
constraints are of the form 10⁵ and larger, linear time solutions are required
to solve.
5. This
problem/pattern is common in stream processing and Data Validation Systems.
🧠 Explanation
A common error people
make when solving this problem is using nested loops to compare each character
against all other characters. Although looping through a small number of
characters can allow one to do this, the size of the strings increases quickly,
which makes this method inefficient.
The major challenge in
this problem is meeting two requirements at once:
1.
Finding characters that appear only once.
2.
Keeping the characters in the same order
they were originally found so that the first character that appears only once
is returned.
To address the
requirements of correctness and efficiency, the approach to the problem
separates these responsibilities.
⚙️Logic in Steps
- A frequency map is used to keep track
of how many times each character appears in the string.
- A queue is used to maintain the order
of characters as they appear, along with their original indices.
- As the string is traversed, each
character’s frequency is updated and the character-index pair is added to
the queue.
- After processing all characters, the
queue is checked from the front:
a. If
the front character has a frequency of exactly one, its stored index is
returned immediately.
b. Otherwise,
it is removed from the queue and the process continues.
- If the queue is exhausted without
finding a unique character, -1 is returned.
⏱ Time and Space Complexity
Time Complexity:
O(n): Each character is
processed at most twice. Once while counting frequency and once while checking
the queue.
Space Complexity:
O(n): The frequency map
and queue may store up to n elements in the worst case
📝Key Takeaways from This
Problem and Solution
1.
To achieve maximum efficiency, both order
and frequency should be treated separately.
2.
Queues are an excellent way to quickly
find the earliest valid element.
3.
Using a hash map makes it possible to look
up an element's frequency in constant time.
4.
When working with very large data sets
(where multiple constraints could apply) the use of linear time methods becomes
necessary.
5. This pattern is frequently encountered in the creation of stream processing engines and the validation of real-time data.
IV.
Moving Average from Data
Stream
🧠 Explanation
The apparent challenge
presented looks to be a counting task, but there is a significant difference in
the problem as the timestamps of each request must always be greater than the
previous timestamp. Therefore, process the requests in a staggered fashion
based on these request timestamps instead of checking every other request
timestamp multiple times.
This is a good situation
for using a Queue, as the requests come into the Queue in chronological order,
and as time progresses old requests must be removed in the order that they
arrived.
⚙️Logic in Steps
1. A
queue is used to store timestamps of incoming requests.
2. Every
new request time t is added to the queue.
3. Any
timestamp that is older than t - 3000 milliseconds is no longer relevant and is
removed from the front of the queue.
4. After
removing outdated requests, the remaining elements in the queue represent valid
requests in the required time range.
5. The
size of the queue is returned as the answer.
⏱ Time and Space Complexity
1. Time
Complexity:
Amortized O(1) per ping (each timestamp is added once and removed once)
2. Space
Complexity:
O(n) where n is the number of requests within the last 3000 ms
📝Key Takeaways from This
Problem and Solution
1. Using
timestamps that are strictly greater than the last timestamp will not require
sorting or rescanning.
2. The
combination of a sliding window and a queue creates an optimal strategy.
3. Removing
stale data quickly from the system will allow the system to remain fast and
efficient.
4. The
concept behind this is similar to that of real-world systems such as rate
limiters and request monitoring systems.
🟡 MEDIUM
(Industry-Relevant, Interview Favourite)
🧠 Explanation
One of the most common
mistakes made when implementing a queue with arrays is thinking that after
reaching the end of the array with rear index, there will be no further space
available; however, when items are dequeued from a queue, there will be empty memory
positions at the front of the array. A Circular Queue allows for these empty
spaces to be reused by implementing circular indexing in which the last index
is logically tied back into the first index.
Circular Queue
implementation eliminates the confusion between full and empty because the
application of an extra variable keeps track of how many items are currently in
the queue.
⚙️Logic in Steps
1.
All elements of a queue are stored in one
fixed-size array and memory is used in an orderly fashion.
2.
It uses two pointers:
a. One
pointer, the front points to the first inserted item.
b. While
the other pointer, the rear points to the last inserted item.
3.
Both pointers circularly step through the
array, using modulo arithmetic.
4.
A separate variable to count the number of
elements in the queue is maintained to help distinguish when the queue is full,
and when it is empty.
5.
When enqueueing (inserting an element into
the queue) the queue is checked to see if it is full, the rear pointer is
updated, and then the new item is added to the queue.
6.
When dequeueing (deleting an element from
the queue) the queue is checked to see if it is empty, and the first element
(pointed to by the front pointer) is deleted, and the front pointer is updated
accordingly.
7.
The Front() and Rear() operations return
the elements pointed to by the front and rear pointers respectively, and return
-1 if the queue is empty.
8.
A queue is deemed to be empty when the
count of elements is 0, and it is considered full when the count of elements is
equal to the size of the array holding its elements.
⏱ Time and Space Complexity
1. Time
Complexity: O(1) for all operations
2. Space
Complexity: O(k), where k is the queue capacity
📝Key Takeaways from This
Problem and Solution
1.
Circular index enables array based queues
to use memory more efficiently.
2.
Since you have an element count available,
you can perform state validation more easily.
3.
The modulo function allows you to move
circularly much more efficiently.
4.
The solution is cost effective, safe, and
provides a slightly better opportunity for success during a job interview with
an HR rep.
🧠 Explanation
In normal Queue or Deque
implementations, both ends of the structure required management for Insertions
and Removals. The inefficiencies associated with these types of operations can
grow excessive as a result of having to shift elements from the front of the
queue after each insertion or removal. Circular Deques take advantage of this
inefficiency by using fixed capacity and providing for re-Usability at both
ends of the structure without displacement.
The Circular Deque
implementation uses a Deque structure as a basis, but applies safety and
circular behaviour through an additional layer or enforcement of size
constraints.
⚙️Logic in Steps
1. When
creating (initialising) the deque a fixed maximum size is set, which will limit
the number of elements it may hold.
2. The
double-ended queue allows for inserting and deleting elements from both ends.
3. Adding
an element will only be possible if the deque isn't full.
4. Removing
an element will only be possible if the deque isn't empty.
5. When
inserting an element it will be added to the end of the deque, with a boolean
return value indicating success.
6. When
deleting an element it will be removed safely. A boolean return value indicates
if the operation was successful.
7. When
accessing the front or rear of the deque, you will get either the value or -1
if it was empty.
8. To
determine whether the deque is empty (0) or full (maximum number) simply look
at the number of elements in the deque compared to the defined maximum size.
⏱ Time and Space Complexity
1.
Time Complexity: O(1)
for all operations
2.
Space Complexity:
O(k), where k is the maximum size of the deque
📝Key Takeaways from This
Problem and Solution
1.
A circular deque allows for insertion and
deletion at both ends easily.
2.
It must also be enforced through enforced
capacity limits for true circularity.
3.
Insertion/deletion is performed in a
constant time basis with excellent performance.
4.
The empty and full state is safely
validated to avoid any runtime issues.
5.
The proposed design closely relates to how
queues operate in the real world.
VII.
Rotten Oranges (994)
🧠 Explanation
The purpose of this
challenge is to figure out how to arrange a sequence of distinct integers into
an arrangement, such that as you draw cards according to the set of
instructions given, they will be displayed in ascending order.
Rather than simulating
the progression of drawing cards from the empty deck to complete the hand
(which can be quite challenging due to having no knowledge of how the deck will
be ordered to begin with), this solution takes a different approach and builds
the deck in an opposite direction. Using the final result that you wish to
achieve, you can quickly find out what was the correct way to begin stacking
the cards in order to arrive at your intended destination.
⚙️Logic in Steps
1.
Organizing the deck in Ascending Order
Sorting
the deck in ascending order gives the correct order of revealed cards in
ascending order.
2.
Using A Deque to Create a Reverse Order of
Cards
Because
deques allow constant-time additions and removals at both ends, they are best
suited for an operation that must first be done in reverse.
3.
Reversing The Processing of Cards
To
process cards in this way, iterate over the sorted deck from the largest to
smallest card. Each card represents the last one revealed in this order.
4.
How To Reverse The “Moving The Top Card To
The Bottom” Operation
When
moving top cards to the bottom of the original sequence, after revealing a
card, the next top card is moved to the bottom. Thus, reversing that operation
would entail:
5.
If the deque is non-empty, remove the last
card of the deque and insert it at the front (top).
Insert
the current card at the front (top of the deck). This step simulates putting
the card back on top of the deck before continuing the reverse process.
6.
Continue Processing Until All Cards Have
Been Processed
The
final result is a deque, which instructs how to recreate the initial order of
cards that yields a true increasing reveal sequence.
⏱ Time and Space Complexity
1.
Time Complexity:
a. Sorting
the deck: O(n log n)
b. Deque
operations: O(n)
c. Overall:
O(n log n)
2.
Space Complexity:
Extra
space for the deque: O(n)
📝Key Takeaways from This
Problem and Solution
1.
This problem is solved more easily by
using reverse simulation as opposed to forward simulation.
2.
The best data structure for this type of
application is deque because of the speed of operating from the front and rear
of the structure.
3.
Frequently in problems, when you know what
the outcome will be, the initial state can be deduced by reversing operations.
4.
The solution shows an excellent
understanding of queues, deques, and algorithm-based reasoning, providing a
distinct advantage in interview settings.
VIII.
Task Scheduler (621)
🧠 Explanation
The goal of this problem
is to create a schedule for non-continuous tasks using n periods of time
between the tasks. Therefore, we must minimise the total number of periods used
in the schedule.
Rather than continually
simulating every step of the schedule, we will be focusing on the frequency of
each task to determine the maximum number of idle time slots that can exist in
a schedule that meets all requirements.
⚙️Logic in Steps
1. Count
How Many Times A Task Occurs
The
Counter data structure can be used to find out how many times each task
appears.
2. Find
Maximum Frequency
The
maximum frequency that any task has will determine the minimum number of
available idle time slots.
3. Count
How Many of Those Have that Maximum Frequency
Multiple
tasks may share a maximum frequency value.
4. Compute
Minimum Number of Time Intervals
To
compute the minimum number of time intervals, use the total amount of tasks and
the length of time needed to schedule all tasks with the maximum frequency and
their respective cooldowns.
5. Return
Which is Largest
The
result will either be the number of tasks or the minimum number of available
idle time slots to complete all tasks while observing cooldown periods.
6. The
minimum number of CPU intervals required to finish all tasks while observing
cooldowns is given by the result.
⏱ Time and Space Complexity
1.
Time Complexity:
O(n) → counting + max
2.
Space Complexity:
O(1) → only 26 possible letters
📝Key Takeaways from This
Problem and Solution
The highest traffic
control generates the least idle time. Simulation of schedules can be performed
using a counting method called greedy, along with an associated formula. Both
methods produce the same results for multiple tasks with equal maximum frequencies.
In addition, they are time-efficient and will yield accurate answers within an
interview environment.
Conclusion
1.
Become proficient at all aspects of
enqueue, dequeue, and boundary handling for basic or circular queues.
2.
Learn double-ended deque operations so you
can flexibly insert and remove items.
3.
Utilize frequency count technique along
with sliding window techniques to efficiently process real-time queries.
4.
Use reverse simulation & scheduling
techniques to either reconstruct or optimize sequences.
5.
Improve your understanding of task
scheduling and cooling off periods for constraint-based algorithms.
6.
Obtain expertise in the application of
modular arithmetic and indexing when dealing with circular data structures.
7.
Use analytical skills to minimize both
time and space complexity when working with queues or deques.
If you
missed the Previous part
The last
item added to a stack (Last In) will be the first to be removed (First Out when
performing Pop operations) on this LIFO data structure. Examples of how stacks
support these common algorithmic patterns include evaluating expressions,
backtracking, and managing function calls.
Mastering Stack Data Structures: Easy to Medium LeetCode Problems Explained
Coming Up
A heap is a specialized
tree data structure that allows for efficient implementation of priority-based
operations. Heaps are the basis for priority queues, heap sorting algorithms,
and real-time scheduling of tasks.
If you liked this, Follow Raw Unfiltered Talks
Comments
Post a Comment