"Last 100 bytes" Interview Scenario

I got this question in an interview the other day and would like to know some best possible answers(I did not answer very well haha):

Scenario: There is a webpage that is monitoring the bytes sent over a some network. Every time a byte is sent the recordByte() function is called passing that byte, this could happen hundred of thousands of times per day. There is a button on this page that when pressed displays the last 100 bytes passed to recordByte() on screen (it does this by calling the print method below).

The following code is what I was given and asked to fill out:

public class networkTraffic {
public void recordByte(Byte b){
}
public String print() {
}
}

What is the best way to store the 100 bytes? A list? Curious how best to do this.

5391 次浏览
小开

Easiest thing is to shove it in an array. The max size that the array can accommodate is 100 bytes. Keep adding bytes as they are streaming off the web. After the first 100 bytes are in the array, when the 101st byte comes, remove the byte at the head (i.e. 0th). Keep doing this. This is basically a queue. FIFO concept. Ater the download is done, you are left with the last 100 bytes.

Not just after the download but at any given point in time, this array will have the last 100 bytes.

@Yottagray Not getting where the problem is? There seems to be a number of generic approaches (array, circular array etc) & a number of language specific approaches (byteArray etc). Am I missing something?

小开

I don't know java, but there must be a queue concept whereby you would enqueue bytes until the number of items in the queue reached 100, at which point you would dequeue one byte and then enqueue another.

public void recordByte(Byte b)
{
if (queue.ItemCount >= 100)
{
queue.dequeue();
}
queue.enqueue(b);
}

You could print by peeking at the items:

public String print()
{
foreach (Byte b in queue)
{
print("X", b);  // some hexadecimal print function
}
}
小开
最佳答案

Something like this (circular buffer) :

byte[] buffer = new byte[100];
int index = 0;


public void recordByte(Byte b) {
index = (index + 1) % 100;
buffer[index] = b;
}


public void print() {
for(int i = index; i < index + 100; i++) {
System.out.print(buffer[i % 100]);
}
}

The benefits of using a circular buffer:

  1. You can reserve the space statically. In a real-time network application (VoIP, streaming,..)this is often done because you don't need to store all data of a transmission, but only a window containing the new bytes to be processed.
  2. It's fast: can be implemented with an array with read and write cost of O(1).
小开

Circular Buffer using array:

  1. Array of 100 bytes
  2. Keep track of where the head index is i
  3. For recordByte() put the current byte in A[i] and i = i+1 % 100;
  4. For print(), return subarray(i+1, 100) concatenate with subarray(0, i)

Queue using linked list (or the java Queue):

  1. For recordByte() add new byte to the end
  2. If the new length to be more than 100, remove the first element
  3. For print() simply print the list
小开

Here is my code. It might look a bit obscure, but I am pretty sure this is the fastest way to do it (at least it would be in C++, not so sure about Java):

public class networkTraffic {
public networkTraffic() {
_ary = new byte[100];
_idx = _ary.length;
}


public void recordByte(Byte b){
_ary[--_idx] = b;
if (_idx == 0) {
_idx = _ary.length;
}
}


private int _idx;
private byte[] _ary;
}

Some points to note:

  • No data is allocated/deallocated when calling recordByte().
  • I did not use %, because it is slower than a direct comparison and using the if (branch prediction might help here too)
  • --_idx is faster than _idx-- because no temporary variable is involved.
  • I count backwards to 0, because then I do not have to get _ary.length each time in the call, but only every 100 times when the first entry is reached. Maybe this is not necessary, the compiler could take care of it.
  • if there were less than 100 calls to recordByte(), the rest is zeroes.
小开

Multithreaded solution with non-blocking I/O:

private static final int N = 100;
private volatile byte[] buffer1 = new byte[N];
private volatile byte[] buffer2 = new byte[N];
private volatile int index = -1;
private volatile int tag;


synchronized public void recordByte(byte b) {
index++;
if (index == N * 2) {
//both buffers are full
buffer1 = buffer2;
buffer2 = new byte[N];
index = N;
}
if (index < N) {
buffer1[index] = b;
} else {
buffer2[index - N] = b;
}
}


public void print() {
byte[] localBuffer1, localBuffer2;
int localIndex, localTag;
synchronized (this) {
localBuffer1 = buffer1;
localBuffer2 = buffer2;
localIndex = index;
localTag = tag++;
}
int buffer1Start = localIndex - N >= 0 ? localIndex - N + 1 : 0;
int buffer1End = localIndex < N ? localIndex : N - 1;
printSlice(localBuffer1, buffer1Start, buffer1End, localTag);
if (localIndex >= N) {
printSlice(localBuffer2, 0, localIndex - N, localTag);
}
}


private void printSlice(byte[] buffer, int start, int end, int tag) {
for(int i = start; i <= end; i++) {
System.out.println(tag + ": "+ buffer[i]);
}
}
小开

Just for the heck of it. How about using an ArrayList<Byte>? Say why not?

public class networkTraffic {
static ArrayList<Byte> networkMonitor;          // ArrayList<Byte> reference
static { networkMonitor = new ArrayList<Byte>(100); }   // Static Initialization Block
public void recordByte(Byte b){
networkMonitor.add(b);
while(networkMonitor.size() > 100){
networkMonitor.remove(0);
}
}
public void print() {
for (int i = 0; i < networkMonitor.size(); i++) {
System.out.println(networkMonitor.get(i));
}
// if(networkMonitor.size() < 100){
//  for(int i = networkMonitor.size(); i < 100; i++){
//      System.out.println("Emtpy byte");
//  }
// }
}
}

提交答案