Suche nach doppelten Elementen mit begrenztem Speicher

Question

Die folgende Frage ist die Codierung Interview von Cracking:

Sie haben einen Array mit allen Zahlen von 1 bis N, wobei N höchstens 32.000. Das Array kann doppelte Einträge enthalten und Sie wissen nicht, was N ist. Mit nur 4 KB Speicher verfügbar, wie würden Sie alle doppelte Elemente im Array drucken?

die Methodensignatur ist

public static void checkDuplicates(int[] array) 

dann die Lösung erklärt, wie man Bitvektor verwenden können, diese zu lösen, indem jede ganze Zahl als Bit repräsentiert. Meine Verwirrung ist, wenn wir diese Methode ausführen, lädt es nicht das gesamte Array im Speicher, um es zu durchlaufen? Nun, wenn die array Größe sagen, zum Beispiel 1 Milliarde (viele wiederholte Elemente) wird dieses Programm nicht fehlschlagen, da es das gesamte Array im Speicher lädt und der Speicher, den wir haben, 32 * 2^10 Bits ist?

Answer 1

Dies könnte eine knifflige Frage sein. Ich habe kürzlich bei Google interviewt und sie hatten eine Art von Fragen wie Ihre. Ich denke, das Beste in diesen Fällen zu tun, um Ihre Gedankenlinie zu erklären und jede Fälle abdecken. Diese Fragen werden von Menschen zu konstruiert, so ist es möglich, dass sie verpasst ein Wort usw. Wenn ich diese Frage zu beantworten, hatte ich mit mehreren Antworten kommen würde:

• Alle Speichernutzung 4 KB sein könnte (Probleme usw.)
• Ihre Lösungen in 4 KB (Die genannte Lösung)

der Text passen sollte, so dass:

Mit nur 4 KB Speicher zur Verfügung [...]

012.351.

Da Java in terms of passing values eine interessante Sprache ist, erstellen Sie keine neue Instanz des int-Arrays, wenn es an die Methode übergeben wird.

public class Test { 
    public static void main(String[] args) { 
     int[] stuff = {1}; 
     System.out.println("before: " + stuff[0]); 
     doStuff(stuff); 
     System.out.println("after: " + stuff[0]); 
    } 
    public static void doStuff(int[] array){ 
     array[0]=10; 
    } 
} 

Aufgrund dieses Verhaltens ist Ihr 4KB für Ihren inneren Verarbeitungsalgorithmus verfügbar. Ich denke, dass diese Beschränkung nur dazu dient, die "Ich mache eine Kopie davon und ..." Art von Lösungen zu verhindern.

Answer 2

4Ko scheint die zulässige Menge an Speicher für die Funktion nicht das gesamte Programm zu sein und sogar nicht, Speicherinhalt in eine Datei austauschen kann in solchen Fällen look here sehr hilfreich sein.

Answer 3

Die mittlere "4KB für die Fertigstellung der Aufgabe", so dass Ihr Code nicht mehr Platz benötigt. Hier ist der Code in meinem Kopf gekocht, aber nicht getestet.

Grundsätzlich verwenden Sie einfach den Wert der Zahl als Index in einem Bit-Vektor. Wenn bereits eingestellt, Nachricht drucken; ansonsten setze es.

public class BitVectorMagic { 
    static public void checkDuplicates(final int[] pArray) { 
     final int neededBytes = (pArray.length/8) + 1; 
     final byte[] bitVector = new byte[neededBytes]; 

     for (int i = 0; i < pArray.length; i++) { 
      final int value = pArray[i]; 
      final int byteIndex = value/8; 
      final int indexInByte = value % 8; 

      final byte bitByte = bitVector[byteIndex]; 
      final byte bit = getBit(bitByte, indexInByte); 
      if (bit > 0) { 
       System.out.println("Duplicate value " + value + " at pos " + i); 
      } else { 
       final byte writeBitByte = setBit(bitByte, indexInByte); 
       bitVector[byteIndex] = writeBitByte; 
      } 
     } 
    } 


    private static byte setBit(final byte pBitByte, final int pIndexInByte) { 
     final byte or = (byte) (0x01 << pIndexInByte); 
     return (byte) (pBitByte | or); 
    } 


    static private byte getBit(final int pByte, final int pIndexInByte) { 
     return (byte) ((pByte >> pIndexInByte) & 1); 
    } 
} 

Answer 4

Die Idee der Frage ist, dass 32000 (possible values)/8 (bit in byte) = 4000 ~ 4096 (4 KB).

Der ursprüngliche Array-Speicher wird nicht gezählt, da es keine vernünftige Einschränkung für seine Größe gibt, da keine Begrenzung für die Anzahl der Replikate angegeben ist.

4 KB ist die Menge an Speicher, die die Methode verwenden könnte, und da die Methode den Zeiger auf das Eingabe-Array empfängt (es besteht keine Notwendigkeit, ihre Werte zu kopieren), wird die Array-Größe nicht gezählt.

Soweit ich weiß, alle O(N) Speicher schätzt Konten für extra Speicher-Algorithmus könnte das Problem zu lösen.

Answer 5

Nachfolgend finden Sie eine getesteten Code:

public void checkDuplicates(int[] nums){ 
    int bytesNeeded = (nums.length/8) + 1; 
    byte[] bitSet = new byte[bytesNeeded]; 

    for(int i=0; i<nums.length; i++){ 
     int n = nums[i]; 
     int byteIndex = n/8; 
     int indexInByte = n % 8; 

     byte bit = (byte)(bitSet[byteIndex] & (1 << indexInByte)); 
     if(bit > 0){ 
      System.out.print(nums[i] + " "); 
     }else{ 
      bitSet[byteIndex] |= 1 << indexInByte; 
     } 
    } 
}