Finding duplicate elements with limited memory

Question

The following is a question from Cracking the coding interview:

You have an array with all numbers from 1 to N, where N is at most 32,000. The array may have duplicate entries and you do not know what N is. With only 4KB of memory available, how would you print all duplicate elements in the array?

The method signature is

public static void checkDuplicates(int[] array)

Then the solution explains how you can use bit vector to solve this by representing each integer as a bit. My confusion is when we run this method, won't it load the entire array in memory to loop through it? Now if the array is of size say,for example, 1 billion (many repeated elements) won't this program fail since it loads the entire array in memory and the memory we have is 32 * 2^10 bits?

I think the problem asks for 4KB _additional_ to what's already used by the array. Although I would say that with no time constraints, you should be able to do this even in constant space, as you could just repeatedly loop the array and count each number from 1 to 32k, using O(32k*n) time. — tobias_k, Jul 24 '16 at 20:28
But the problem states "With only 4KB of memory available"!! I agree it can be solved in constant space but with the given problem statement the solution would only work if array is of size 2^10 — Vivin, Jul 24 '16 at 20:36
With only 4KB of memory available, how would you print all duplicate elements in the array? Feels like it refers to the amount of memory you are allowed to consume to print the duplicates which is just shy of 4KB. — AppX, Jul 24 '16 at 21:06

score 5 · Answer 1 · answered Mar 15 '17 at 05:23

Below is a tested 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; 
        }
    }
}

score 4 · Accepted Answer · edited May 23 '17 at 10:29

This could be a tricky question. I recently interviewed at Google and they had some sort of questions like yours. I think the best to do in those cases to explain your line of thought and cover each cases. Those questions are constructed by humans too, so it is possible that they missed out a word etc. If I had to answer this question I would come up with multiple answers:

All memory usage could be 4KB (Problems etc)
Your solutions should fit into 4KB (The mentioned solution)

The text says that:

With only 4KB of memory available [...]

Because Java is an interesting language in terms of passing values, you do not create a new instance of the int array when it is passed to the method.

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

Because of this behaviour your 4KB is available for your inner processing algorithm. I think that this limitation is only to prevent the "I make a copy of it and..." kind of solutions.

score 0 · Answer 3 · answered Aug 04 '16 at 13:46

0

4Ko seems to be the allowed amount of memory to the function not to the whole program and even not, swapping memory content into a file can be very helpful in such cases look here.

answered Aug 04 '16 at 13:46

whyn0t

301
2
14

score 0 · Answer 4 · answered Aug 07 '16 at 09:40

The mean "4KB for completing the task" so your code is not meant to take up more space. Here's the code is cooked up in my mind but havent tested.

Basically just use a the value of the number as an index in a bit-vector. If already set, print message; otherwise set it.

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

score 0 · Answer 5 · edited Aug 07 '16 at 19:08

The idea of question is that 32000 (possible values) / 8 (bit in byte) = 4000 ~ 4096 (4 KB).

The initial array memory is not counted since there is no reasonable restriction on its size because no bounds on number of replicates given.

4 KB is the amount of memory the method could use, and since the method receives the pointer to the input array (there is no need to copy its values) the array size is not counted.

As far as I know, any O(N) memory estimates accounts for extra memory algorithm could use to solve the problem.

Finding duplicate elements with limited memory

5 Answers5