Paste number 27626: interview problem

Index of paste annotations: 1

Paste number 27626: interview problem
Pasted by: psykotic
When:11 years, 8 months ago
Share:Tweet this! |
Paste contents:
Raw Source | XML | Display As
The problem is to write a set of functions to manage a variable number of byte queues, each with variable length, in a small, fixed amount of memory. You should provide implementations of the following four functions:

Q * createQ();               //Creates a FIFO byte queue, returning a handle to it.
void destroyQ(Q * q);        //Destroy an earlier created byte queue.
void enQ(Q * q, unsigned char b);    //Adds a new byte to a queue.
unsigned char deQ(Q * q);    //Pops the next byte off the FIFO queue.

So, the output from the following set of calls:

Q * q0 = createQ();
enQ(q0, 0);
enQ(q0, 1);
Q * q1 = createQ();
enQ(q1, 3);
enQ(q0, 2);
enQ(q1, 4);
printf("%d", deQ(q0));
printf("%d\n", deQ(q0));
enQ(q0, 5);
enQ(q1, 6);
printf("%d", deQ(q0));
printf("%d\n", deQ(q0));
printf("%d", deQ(q1));
printf("%d", deQ(q1));
printf("%d\n", deQ(q1));

should be:

0 1
2 5
3 4 6

You can define the type Q to be whatever you want.

Your code is not allowed to call malloc() or other heap management routines. Instead, all storage (other than local variables in your functions) should be done in a provided array:

unsigned char data[2048];

Memory efficiency is important. On average while your system is running, there will be a dozen or so queues with an average of 80 or so bytes in each queue. Your functions may be asked to create a larger number of queues with less bytes in each. Your functions may be asked to create a smaller number of queues with more bytes in each.

If you are unable to satisfy a request due to lack of memory, your code should call a provided failure function, which will not return:

void onOutOfMemory();

If the caller makes an illegal request, like attempting to deQ a byte from an empty queue, your code should call a provided failure function, which will not return:

void onIllegalOperation();

Worst-case performance when adding and removing bytes is more important than average-case performance.

There may be spikes in the number of queues allocated, or in the size of an individual queue. Your code should not assume a maximum number of bytes in a queue (other than that imposed by the total amount of memory available, of course!) You can assume that no more than 64 queues will be created at once.

Annotations for this paste:

Annotation number 1: solution
Pasted by:
When:11 years, 8 months ago
Share:Tweet this! |
Paste contents:
Raw Source | Display As
It is late and I didn't think this through as well as I should, but this
should work:

 - using the data area as a buffer containing all queues, commingled
 - each entry is two bytes: a queue number and the data byte
 - creation is simply incrementing a static max queue number 
 - destruction zeroes out all pairs whose queue number is being destructed
   followed by a pass that backfills the created holes
 - adding sticks (queue,value) pair in a zeroed field
    - if we reach the end of buffer before finding empty, call out of memory
 - removing searches forward for first pair from this queue, returns/zeroes it
   and moves up the rest of the table.
    - call error if can't find the requested queue number

A typical case, 12 queues of 80 bytes is 960 bytes. Using pairs means that
the data requirement is double the total data size, which fits in 2048.

Colorize as:
Show Line Numbers

Lisppaste pastes can be made by anyone at any time. Imagine a fearsomely comprehensive disclaimer of liability. Now fear, comprehensively.