My friend Reed who is enrolled at digipen right now showed me an interview question for a company that he was looking at applying to. Basically, they screen their applicants using a programming quiz that you are supposed to code up and submit with your resume. It was a pretty engaging problem and I started working through some possible solutions. This morning I had some time and so I wrote up one possible solution to the problem.
I’ll find out later the specifics of the problem but the basic idea is to implement a byte queue interface using a fixed 2048 buffer.
- The interface should be able to create a number of queues that can be used independently.
- The maximum number of queues that can be created is 32
- The operations are ‘queue* create(), enq(Q, byte) and deq(Q,byte*).
- If you run out of memory call a procedure (outofmemory()) if your queue fills up I can’t remember if you’re supposed to return an error or call another procedure (it doesn’t matter too much)
- Given 2048 bytes of static data allocation implement a queue interface
- Make sure that your implementation works well with a few large or many small queues
- I think there was something about ensuring it was optimized for the common case and that it did not have bad worst case performance.
Before you read the stuff below see if you can come up with your own implementation. Click to view my mini-queue implementation.
At a command prompt type gcc -o miniqueue miniqueue.c to compile. There is a set of small functional tests that exercise various aspects of the queue.
Here’s a description of how I implemented my version. I’m sure there are plenty of other ways to implement it, this is just an easy and fast way to do it:
The 2048 byte block is divided up into 32 blocks. Each block is a standalone queue utilizing a small circular buffer but can also be joined to other blocks to create a larger queue.
When you create the first queue the code initializes a freelist and gives you the first block off of the freelist.
To enqueue we will find the last block attached to your chain of blocks and add elements to that block. If it is full we will aquire another one or fail if none are available.
To dequeue we will return the first element of the first block and move the head of the circular buffer. If the block is empty after this operation we will collapse the data from the next block (if it exists) into it and return the collapsed block to the freelist.
Overall I’m pretty happy with this implementation. Post a comment if you see anything wrong with my code or have any questions or comments on your own implementation.