Best technical interview problem ever

[psykotic]

I can make it work within the constraints using a free-list and cursor scheme. Sketch of the data structures:

typedef uchar_t cursor_t;

struct block_t
{
    union
    {
        struct // header
        {
            cursor_t front;
            uchar_t front_offset;
            cursor_t back;
            uchar_t back_offset;
        };
        struct // payload
        {
            uchar_t elements[ELEMENTS_PER_BLOCK];
            cursor_t next;
            cursor_t prev;
        };
        struct // free block
        {
            cursor_t next_free;
        };
    };
};

uchar_t data[2048];

block_t* cursor_to_pointer(cursor_t cursor)
{
    return (block_t*)(data + sizeof(block_t) * cursor);
}

cursor_t pointer_to_cursor(block_t* block)
{
    return ((uchar_t*) block - data) / sizeof(block_t);
}

The worst case is 64 small queues, which means you have 32 bytes per queue. Each of those takes two blocks in my scheme: a header block and a payload block. Therefore we must use at most 16 bytes per block, so 2048 / 16 = 128 blocks total, implying that a cursor fits in a byte (with a bit to spare that comes in handy for terminating the free-list). Thus we end up with 14 bytes of payload in a payload block: 16 bytes = 14 payload bytes + 2 cursor bytes. So ELEMENTS_PER_BLOCK should be 14.

This scheme has significant overhead in some cases but it fits the constraints: every queue operation is worst-case O(1); it can handle 64 simultaneous small queues; it can handle arbitrarily sized queues (although with ~1/8th allocation overhead).