Got this question in Rubrik interview.

Design two queues using an array of fixed size N.

There 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?