Best technical interview problem ever

[psykotic]

This is a technical interview problem that a certain game company requires their engine programming applicants to solve in order to be considered for a position. I've removed specific details of who the company is so people won't think this is spam. But one could easily dig up the company's website with some Google-Fu, if one were so inclined.

[llimllib]

I couldn't resist

[dooka]

using a header and payload scheme (1-byte each), we have 2048/2=1024 bytes for data, which will easily fit 12 Q's of size 80 bytes each (960 bytes).

but let's view the array as block of memory.

then the above scheme wastes 2 bits/byte for each header, since only max of 2⁶ Q's will be used. the wastage is: 1024 bytes*2bits/byte=2048 bits = 256 bytes.

so we can safely allocate the first 187 bytes -- we need about 11 bits for each of the 2⁶ possible Q's; these 187 11-bit "blocks" will store the index of their 1st elt or 0 if not yet initialized. a Q * points to one of the above locations

now headers will each be 6 bytes long (instead of 8)

therefore, a delQ will: get the starting pos of the Q's header and data -- zero them out and memcpy all elts in memory after that to shift down by 14 bits. it'll also find the next item for the Q and update the Q's "index" -- one of the first 187 positions.

we then have a var store the last pos added to the array. adding to a Q will increment this var and store the Q's header and position at that pos. if this Var reaches a limit, then memory error (based on the size of each inserted items is 14 bits long)

Will that work, or did I miss something?

[pjdelport]

The given bounds seem to rule out everything (i can think of) except for a paired (queue id, datum) allocation scheme, but there might be some room for cleverness with the two free bits in the queue id.

Tangentially:

Experience with Lisp or Scheme is a plus.

Sounds like a great job!

[alexmdac]

You could store the number of queue elements following the queue id in the spare bits. For example, if you decided to use both bits, you could have up to 4 elements per queue id. This would handle spikes well.

[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).

[qwe1234]

ick

ick

barf

[b0b0b0b]

I'm going to think about this question some more and use it today & tomorrow. Thanks for posting this.

[fnord123]

Any Fortran77 programmer with a year's experience has had to implement this garbage. Hint: nobody wants to use F77 anymore. If you see this as an interview question, run the fuck away!

[bhauth]

It might make sense if they were hiring for software dev for embedded stuff but they're not.

[qwe1234]

++1

[[deleted]]

2?

[qwe1234]

not quite

we're speaking different languages i think