Scénario d’entrevue « Last 100 octets »

Question

J'ai eu cette question dans une interview l'autre jour et je voudrais savoir quelques-unes des meilleures réponses possibles(je n'ai pas de réponse très bien haha):

Scénario: Il y a une page web qui est de la surveillance des octets transmis sur un réseau. Chaque fois qu'un octet est envoyé le recordByte() la fonction est appelée en passant cet octet, cela pourrait se produire des centaines de milliers de fois par jour. Il y a un bouton sur cette page que lorsqu'il est pressé affiche les 100 derniers octets transmis à recordByte() sur l'écran (il le fait en appelant la méthode d'impression ci-dessous).

Le code suivant est ce qu'on m'a donné et demandé de remplir:

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

Quelle est la meilleure façon de stocker les 100 octets? Une liste? Curieux de voir comment mieux le faire.

Answer 1

Quelque chose comme ce (buffer circulaire) :

Les avantages d’utiliser un tampon circulaire :

1. Vous pouvez réserver l’espace statiquement. Dans une application de réseau en temps réel (VoIP, en streaming,..) Cela se fait souvent parce que vous n’avez pas besoin de stocker toutes les données d’une transmission, mais seulement une fenêtre contenant les octets nouveaux à traiter.
2. C’est rapide : peut être implémenté avec une baie à lire et à écrire coût d’o (1).

Answer 2

Je ne sais pas java, mais il doit y avoir un concept de file d’attente par laquelle vous le feriez enqueue octets jusqu'à ce que le nombre d’éléments dans la file d’attente atteint 100, à quel point vous serait dequeue un octet, puis placer un autre.

Vous pouvez imprimer par furtivement les items :

Answer 3

Tampon circulaire à l'aide du tableau:

1. Tableau de 100 octets
2. Garder une trace de l'endroit où la tête de l'index est que je
3. Pour recordByte() mettre l'octet dans Une[i] et i = i+1 % 100;
4. Pour print(), de retour subarray(i+1, 100) concaténer avec subarray(0, i)

La file d'attente à l'aide de liste liée (ou le java File d'attente):

1. Pour recordByte() ajouter un nouveau octets à la fin
2. Si la nouvelle de la longueur à plus de 100, supprimer le premier élément
3. Pour print() il suffit d'imprimer la liste

Answer 4

Voici mon code. Il peut paraître un peu obscur, mais je suis assez sûr que c'est le moyen le plus rapide de le faire (au moins en C++, pas si sûr au sujet de 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;
}

Quelques points sont à noter:

• Aucune donnée n'est alloué/libéré lors de l'appel de recordByte().
• Je n'ai pas utiliser %, car il est plus lent que d'une comparaison directe et à l'aide de la si (direction de la prévision peut aider à ici aussi)
• --_idx plus rapide que de l' _idx-- car aucune variable temporaire est impliqué.
• Je compte à rebours à 0, car alors je n'ai pas à obtenir de l' _ary.length à chaque fois à l'appel, mais seulement 100 fois lors de la première entrée est atteint. Peut-être que ce n'est pas nécessaire, le compilateur pourrait prendre soin d'elle.
• si il y avait moins de 100 appels recordByte(), le reste c'est des zéros.

Answer 5

Chose la plus facile est de se fourrer dans un tableau. La taille maximale que le tableau peut accueillir est de 100 octets. Continuez à ajouter des octets comme elles sont en streaming sur le web. Après les 100 premiers octets sont dans le tableau, lors de la 101e octet vient, de supprimer l'octet à la tête (c'est à dire 0e). Continuer à faire cela. C'est fondamentalement une file d'attente. FIFO concept. Après le téléchargement est terminé, vous êtes de gauche avec la dernière 100 octets.

Pas juste après le téléchargement, mais à un moment donné dans le temps, ce tableau sera la dernière de 100 octets.

@Yottagray n'obtenant Pas où est le problème? Il semble y avoir un certain nombre de principes généraux (tableau, tableau circulaire, etc) et un certain nombre de langue des approches spécifiques (byteArray etc). Ai-je raté quelque chose?