Microsoft Interview Question
SDE1sCountry: United States
Interview Type: In-Person
Let the input device write in to ArrayBlockingQueue<Byte>(8), synching between the input device and disk writer will be taken care by Blocking Queue.
Wouldn't this implementation block the input thread when disk writer thread is trying to access the queue members?
We cannot let the input device wait since it needs to immediately write available data to the buffer.
Ok, in that case we need to have two queues of 16 bytes size, the input device first put the data in to the q1, once its full, it will move that in to disk writer and trigger disk writer (using countdown latch). And input device start putting the data in to q2. Once q2 become full(which will happen after 4 seconds), it will swap the queue to disk writer, then start writing in to the swapped queue
maybe use a circle buffer list can solve it:
const int BUFSIZE = 1024;
class ListNode {
public:
char *buffer;
ListNode() { buffer = new char[BUFSIZE]; }
~ListNode() { delete[] buffer; }
};
ListNode *curr_read = new ListNode(), *curr_write = curr_read;
curr_read->next = curr_write;
int curr_read_ind = 0, curr_write_ind = 0;
void input(InputDevice in) {
while (true) {
if (curr_read_ind == BUFSIZE) {
curr_read_ind = 0; // reset read index
if (curr_read->next == curr->write) { // create a new buffer node
ListNode *tmp = new ListNode();
tmp->next = curr->read->next;
curr->read->next = tmp;
}
curr_read = curr->read->next;
}
if (in.hasNext()) {
curr_read->buffer[curr_read_ind] = in.read();
curr_read_ind++;
}
}
}
void output(WriteDevice out) {
while (true) {
while (curr_write == curr_read) {} //wait for input device
while (curr_write_ind != BUFSIZE) { out.write(curr_write->buffer[curr_write_ind]); curr_write_ind += 2; }
curr_write_ind = 0;
curr_write = curr_write->next;
}
}
correct me if I'm wrong, thanks!
Using ArrayBlockingQueue of size 32 bytes, will solve the problem.
- Lakshmanan July 12, 2015