Design a queue and analyze tradeoffs

Q: Design a queue and analyze tradeoffs

This question evaluates understanding of FIFO data structures, algorithmic complexity analysis, memory and cache behavior, and concurrent access concerns.

Q: How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

Q: What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Optiver.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Optiver during technical interviews.

Question

Design a FIFO queue data structure that supports enqueue, dequeue, peek, and isEmpty. Compare implementations using a singly linked list, a dynamic array, and a circular buffer. Analyze time and space complexity, amortized costs of resizing, memory overhead, and cache locality. Discuss edge cases such as underflow and overflow, potential blocking vs. non-blocking behavior for concurrent access, and when each implementation is preferable.

PracHub · Accepted Answer

def solution(operations, capacity):
    buffer = [None] * capacity if capacity > 0 else []
    front = 0
    size = 0
    results = []

for op in operations:
        cmd = op[0]

if cmd == 'enqueue':
            if size == capacity:
                results.append(False)
            else:
                insert_idx = (front + size) % capacity
                buffer[insert_idx] = op[1]
                size += 1
                results.append(True)

elif cmd == 'dequeue':
            if size == 0:
                results.append('underflow')
            else:
                value = buffer[front]
                buffer[front] = None
                front = (front + 1) % capacity if capacity > 0 else 0
                size -= 1
                results.append(value)

elif cmd == 'peek':
            if size == 0:
                results.append('underflow')
            else:
                results.append(buffer[front])

elif cmd == 'isEmpty':
            results.append(size == 0)

else:
            raise ValueError('Invalid operation: ' + str(cmd))

return results

Quick Overview

Solution

Hints

Quick Overview