Search for duplicate items with limited memory

Question

The following is a question from a Cracking coding interview:

You have an array with all numbers from 1 to N, where N is no more than 32000. The array can have duplicate entries, and you don't know what N is. With only 4 KB of memory, how would you print all duplicate elements in an array?

Method signature

public static void checkDuplicates(int[] array)

The solution then explains how you can use bit-bit to solve this problem, representing each integer as a bit. My confusion, when we run this method, will it not load the entire array in memory to go through it? Now, if the size arrayhas a size, for example, 1 billion (many duplicate elements) will not skip this program, since it loads the entire array in memory, and do we have 32 * 2^10bits in memory ?

Answer 1

This can be a tricky question. I recently chatted at Google and they had questions like yours. I think it is best in these cases to explain your line of thought and cover all cases. These questions are also built by people, so it is possible that they missed the word, etc. If I had to answer this question, I would suggest several answers:

• All memory usage may be 4 KB (problems, etc.)
• Your solutions should fit in 4 KB (mentioned solution)

The text says that:

Only 4 KB of memory is available [...]

Java , int, .

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

- 4KB . , , " ...".

Answer 2

:

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

Answer 3

4Ko, -, , , .

Answer 4

"4 ", . , havent .

. , ; .

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 5

, 32000 (possible values) / 8 (bit in byte) = 4000 ~ 4096 (4 KB).

, , .

4 KB - , , ( ) .

, O(N), , .