Rubrik interview | Online
Summary
Designed two queues using an array of fixed size N to efficiently utilize empty spaces after elements are popped.
Full Experience
Got this question in Rubrik interview.
Design two queues using an array of fixed size N.
The interviewer said you can use an external data structure but the elements must be in the queue.
The problem here is that once the elements in the queue gets popped, it creates empty space which must be then utilized.
How can we solve this problem?
Few approaches I have in my mind:
Create K blocks. Each blocks store N/K values.
Each block store indices from i x N/K to (i+1) x (N/K)
Doubly Linkedlist points to the blocks
DLL tail -> always empty blocks for fast query of empty blocks
class LinkedListNode:
self.start_index
self.end_index
self.next_node = NULL
Linkedlist -> Keep track of blocks
head1 -> start for queue1
head2 -> start for queue2
tail -> to get empty block
While popping if the block gets empty it is moved to tail and the head is moved to next node using pointer
Is this alright?
Interview Questions (1)
Design two queues using an array of fixed size N.
The interviewer said you can use an external data structure but the elements must be in the queue.
The problem here is that once the elements in the queue gets popped, it creates empty space which must be then utilized.