"Last 100 byte" Scenario Intervista

Question

ho ricevuto questa domanda in un'intervista l'altro giorno e vorrei sapere alcune risposte migliori possibili (non ho risposto molto bene haha):

Scenario: C'è una pagina web che sta monitorando i byte inviati su una rete. Ogni volta che viene inviato un byte, la funzione recordByte() viene chiamata passando quel byte, ciò potrebbe accadere centinaia di migliaia di volte al giorno. C'è un pulsante in questa pagina che quando premuto mostra gli ultimi 100 byte passati a recordByte() sullo schermo (lo fa chiamando il metodo di stampa sotto).

Il codice che segue è quello che mi è stato dato e chiesto di compilare:

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

Qual è il modo migliore per conservare i 100 byte? Una lista? Curioso come meglio farlo.

Answer 1

Qualcosa di simile (buffer circolare):

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]); 
    } 
} 

i vantaggi di utilizzare un buffer circolare:

1. Yo puoi prenotare lo spazio staticamente In un'applicazione di rete in tempo reale (VoIP, streaming, ..) questo viene spesso fatto perché non è necessario memorizzare tutti i dati di una trasmissione, ma solo una finestra contenente i nuovi byte da elaborare.
2. È veloce: può essere implementato con un array con costo di lettura e scrittura di O (1).

Answer 2

La cosa più semplice è inserirla in un array. La dimensione massima che può contenere l'array è 100 byte. Continuate ad aggiungere byte mentre stanno uscendo dal web. Dopo che i primi 100 byte sono nell'array, quando arriva il 101st byte, rimuovere il byte in testa (cioè 0 °). Continua a farlo. Questa è fondamentalmente una coda. Concetto FIFO. Al termine del download, ti rimangono gli ultimi 100 byte.

Non appena dopo il download, ma in qualsiasi momento, questa matrice avrà gli ultimi 100 byte.

@Yottagray Non si ottiene dove si trova il problema? Sembra esserci un numero di approcci generici (array, array circolare, ecc.) & un numero di approcci specifici della lingua (byteArray, ecc.). Mi sto perdendo qualcosa?

Answer 3

Non conosco java, ma ci deve essere un concetto di coda per cui si accodano i byte fino a quando il numero di elementi nella coda ha raggiunto 100, a quel punto si deseleziona un byte e ne si accoda un altro.

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

Si potrebbe stampare da sbirciare le voci:

public String print() 
{ 
    foreach (Byte b in queue) 
    { 
    print("X", b); // some hexadecimal print function 
    } 
} 

Answer 4

Buffer circolare usando array:

1. array di 100 byte
2. tenere traccia di dove l'indice testa i
3. Per recordByte() mettere il byte corrente in A [i] e i = i + 1% 100;
4. Per print(), ritorno subarray (i + 1, 100) concatenare con subarray (0, i)

coda utilizzando lista collegata (o la coda java):

1. Per recordByte() aggiungi nuovo byte alla fine
2. Se la nuova lunghezza deve essere superiore a 100, rimuovere il primo elemento
3. Perstampare l'elenco

Answer 5

Ecco il mio codice. Potrebbe sembrare un po 'oscuro, ma sono abbastanza sicuro che questo è il modo più veloce per farlo (almeno lo sarebbe in C++, non così sicuro di 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; 
} 

Alcuni punti da notare:

• Nessun dato è allocato/deallocato quando si chiama recordByte().
• non ho usato%, perché è più lento di un confronto diretto e con il caso (branch prediction potrebbe aiutare anche qui)
• --_idx è più veloce di _idx-- perché nessuna variabile temporanea è coinvolto.
• Conto all'indietro a 0, perché quindi non devo ottenere _ary.length ogni volta nella chiamata, ma solo ogni 100 volte quando viene raggiunta la prima voce. Forse questo non è necessario, il compilatore potrebbe prendersene cura.
• se ci sono meno di 100 chiamate a recordByte(), il resto è zero.

Answer 6

soluzione multithread con 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]); 
    } 
} 

Answer 7

Solo per il gusto di farlo. Che ne dici di usare un ArrayList<Byte>? Di ', perché no?

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"); 
     // } 
     // } 
    } 
}