Rubrik onsite interview experience: Queue design using array

Problem Statement Design a system to implement two queues within a single fixed-size array of length $N$. External data structures are permitted for metadata management, but all actual data elemen

Problem Statement Design a system to implement two queues within a single fixed-size array of length $N$. External data structures are permitted for metadata management, but all actual data elements must be stored within the array. The primary challenge is efficient space reclamation: space freed by pop operations must be immediately available for reuse by either queue to prevent fragmentation and exhaustion of the array.

Proposed Solution Implement a block-based allocation strategy (similar to an Unrolled Linked List) to manage array segments dynamically. 1. Array Partitioning * Divide the physical array into $K$ fixed-size blocks. * Each block has a capacity of $N/K$ values. * Each block is defined by a LinkedListNode containing metadata: start_index, end_index, and pointers to adjacent nodes. 2. Metadata Structure * Use a Doubly Linked List (DLL) to maintain the logical order of blocks for each queue and the pool of free space. *

Queue Pointers: Maintain head1 and head2 pointers to track the start of the linked list for Queue 1 and Queue 2, respectively. *

Free Block Management: Maintain a tail or free_list pointer that links to a chain of currently empty blocks. 3. Operational Logic *

Push Operation: When a queue needs to store data, it writes to its current tail block. If the current block is full, an empty block is detached from the free_list and linked to the end of that queue. *

Pop Operation: Elements are removed from the block pointed to by the queue's head. When a block becomes completely empty after a pop operation, it is unlinked from the queue and moved back to the free_list to be reused by either queue.