3
\$\begingroup\$

This is a fairly popular interview question that I conceptually understand but have never really attempted to implement. In other similar implementations of this in Java I have seen they typically operate on an array of boolean values which kind of irks me. It turns out that the way the JVM works however is that it will allocate 8 bits for a single boolean primitive. Granted I believe that an array of booleans actually does allocate a single bit for each value but just as a personal challenge I decided to use an array of byte and through bitwise operations utilizing each bit for a boolean value of N.

This means that the byte array will really be N / 8 or a single bit representing each possible random number that COULD occur in a list of numbers that just happens to be of N length as well.

The strategy is to construct my bytes by scanning each randomly generated number, determining which byte and bit that number correlates to in my byte array, and flipping the appropriate bit when that number is encountered. When the scan is finished I simply inspect each bit and the first 0 bit I encounter means that bit location in my array represents the smallest integer that is not in the list of randomly generated numbers.

It should consume roughly 1/8th of memory from if I were to use a List and is 1/4 faster than sorting the list of random numbers.

import junit.framework.TestCase;

public class TestSmallestNumberNotInList extends TestCase {

    static final int N = 30000000;
    static int[] numbers = null;
    static {
        numbers = new int[N];
        for (int i = 0; i < numbers.length; i++)
            numbers[i] = Math.abs((int)(Math.round(Math.random() * N)));
    }

    public void testFindSmallestNumberNotInList() throws Exception {

        long startTime = System.currentTimeMillis();

        int byteArrayLength = (int) Math.ceil(N / 8);
        byte[] bitset = new byte[byteArrayLength];

        for (int number : numbers) {
            int byteIndex = (int)Math.floor(number / 8);
            byte b = bitset[byteIndex];
            int bitMod = (int)(number % 8);

            // The bit value will be 1 if we encountered this number before
            int bitVal = b>>>(32-bitMod) & 0x00000001;
            if (bitVal == 1)
                continue;

            //Get a byte mask to OR against the existing byte, flipping just the one bit
            //we are concerned with.
            byte byteMask = (byte)(1<<bitMod);
            b = (byte)(b | byteMask);

            //assign the new byte value for the byte array
            bitset[byteIndex] = b;
        }

        //Scan the byte array for the first 0 bit, this ((index * 8) + bitmodulus) is the smallest
        //integer not in the list.
        int location = 0;
        for (int i = 0; i < bitset.length; i++) {
            byte b = bitset[i];
            if (b == 0xFF) {
                location += 8;
                continue;
            } else {
                for (int j=8; j>=1; j--) {
                    if ((b>>>(j) & 0x00000001) == 1)
                        location++;
                }
                break;
            }
        }

        long duration = System.currentTimeMillis() - startTime;

        System.out.println("Total Memory: " + Runtime.getRuntime().totalMemory());
        System.out.println("Free Memory: " + Runtime.getRuntime().freeMemory());
        System.out.println("Smallest number not in the list is " + location);
        System.out.println("Time to execute in milliseconds: " + duration);
    }

    private static String getBitString(int x) {
        StringBuffer buf = new StringBuffer();
        for (int i=1; i<=32; i++) buf.append(x>>>(32-i) & 0x00000001);
        return buf.toString();
    }
}

I believe the output is correct although I really haven't unit tested the results. It certainly seems correct. I was wondering if I am making any glaring mistakes in my arithmetic or code or if you have any other possibilities or suggestions for improvement?

\$\endgroup\$
  • 1
    \$\begingroup\$ docs.oracle.com/javase/6/docs/api/java/util/BitSet.html \$\endgroup\$ – palacsint Apr 26 '12 at 20:43
  • 1
    \$\begingroup\$ Maybe I missed something here, but why not sort the array and walk through it until numbers[idx] != counter++ with counter = numbers[0];? Maybe even utilize a binary search... \$\endgroup\$ – Bobby Apr 27 '12 at 9:37
  • \$\begingroup\$ @palacsint Wow... was never aware of that class! Like I said though this is more of a skills exercise. If I were going to deploy such code into a production environment it would be unit tested and I would likely use the BitSet class. \$\endgroup\$ – maple_shaft Apr 27 '12 at 11:59
  • \$\begingroup\$ @Bobby The metrics I ran performed the sort operation on the list in almost 5 seconds. This method sorts this list in a little under a second so it is over 4 times faster. \$\endgroup\$ – maple_shaft Apr 27 '12 at 12:00
  • 1
    \$\begingroup\$ However, the implementation using sort is simpler. Performance doesn't matter until it matters; until then, maintainability is king. \$\endgroup\$ – Wayne Conrad May 3 '12 at 22:49
5
\$\begingroup\$

So just a few things that I am seeing here. You are using Math.floor, ceil on integers which is totally unnecessary, integers by definition don't have a decimal portion. You also don't need to cast an int as an int.

To make this run faster and take up less stack space, in the for loop where you set the bits you don't need to check anything, just do the bit twiddling you want.

int bitMod = 0x1 << (number % 8);
byte b = number / 8;
bitset[b] |= bitMod;

Getting the position of the bit you want to change and then just or ing it won't change any other bits.

Finally, I don't know why you did it the way you did, but your final for loop doesn't work correctly. It starts with the Most Significant Bit and moves down, instead of the least moving up. Here is a version that I have tested and found to work.

for (int j=0; j<8; j--) {
    if ((b & (1 << j)) != 0){
        location++;
    } else {
        break;
    }
}

Finally, just to see what kind of memory this might be using, I called the free memory before and after to compare the difference. It looks like this program uses 56 MB, and takes under 100 ms after my few changes.

actual lowest is 1
(Initial Implementation)
Free Memory: 563760
Smallest number not in the list is 2
Time to execute in milliseconds: 156
2 is in the list true

(Optimized and cleaned up)
Free Memory: 563760
Smallest number not in the list is 1
Time to execute in milliseconds: 93
1 is in the list false

Here is the class I used to test.

public class TestSmallestNumberNotInList {

static final int N = 3000000;
static int[] numbers = null;
static {
    numbers = new int[N];
    for (int i = 0; i < numbers.length; i++) {
        numbers[i] = Math.abs((int)(Math.round(Math.random() * N)));
    }
}

public void testFindSmallestNumberNotInList() {

    Runtime.getRuntime().gc();
    Runtime.getRuntime().gc();
    Runtime.getRuntime().gc();
    long total = Runtime.getRuntime().totalMemory();
    long free = Runtime.getRuntime().freeMemory();
    long startTime = System.currentTimeMillis();

    int byteArrayLength = (int) Math.ceil(N / 8);
    byte[] bitset = new byte[byteArrayLength];

    for (int number : numbers) {
        int byteIndex = (int)Math.floor(number / 8);
        byte b = bitset[byteIndex];
        int bitMod = (int)(number % 8);

        // The bit value will be 1 if we encountered this number before
        int bitVal = b>>>(32-bitMod) & 0x00000001;
        if (bitVal == 1)
            continue;

        //Get a byte mask to OR against the existing byte, flipping just the one bit
        //we are concerned with.
        byte byteMask = (byte)(1<<bitMod);
        b = (byte)(b | byteMask);

        //assign the new byte value for the byte array
        bitset[byteIndex] = b;
    }

    //Scan the byte array for the first 0 bit, this ((index * 8) + bitmodulus) is the smallest
    //integer not in the list.
    int location = 0;
    for (int i = 0; i < bitset.length; i++) {
        byte b = bitset[i];
        if (b == 0xFF) {
            location += 8;
            continue;
        } else {
            for (int j=8; j>=1; j--) {
                if ((b>>>(j) & 0x00000001) == 1)
                    location++;
            }
            break;
        }
    }

    long duration = System.currentTimeMillis() - startTime;

    System.out.println("Total Memory: " + (total - Runtime.getRuntime().totalMemory()));
    System.out.println("Free Memory: " + (free - Runtime.getRuntime().freeMemory()));
    System.out.println("Smallest number not in the list is " + location);
    System.out.println("Time to execute in milliseconds: " + duration);
    boolean isInList = false;
    for (int next : numbers){
        if (location == next){
            isInList = true;
            break;
        }
    }
    System.out.println(location + " is in the list " + isInList);
}

public void testMine() {
    Runtime.getRuntime().gc();
    Runtime.getRuntime().gc();
    Runtime.getRuntime().gc();
    long total = Runtime.getRuntime().totalMemory();
    long free = Runtime.getRuntime().freeMemory();
    long startTime = System.currentTimeMillis();

    int byteArrayLength = numbers.length / 8;
    byte[] bitset = new byte[byteArrayLength];

    for (int number : numbers) {
        int byteIndex = number / 8;
        int bitMod = (1 << (number % 8)) & 0xFF;
        bitset[byteIndex] |= bitMod;
    }

    //Scan the byte array for the first 0 bit, this ((index * 8) + bitmodulus) is the smallest
    //integer not in the list.
    int location = 0;
    for (int i = 0; i < bitset.length; i++) {
        byte b = bitset[i];
        if (b == 0xFF) {
            location += 8;
            continue;
        } else {
            for (int j=0; j<8; j++) {
                if ((b & (1 << j)) != 0){
                    location++;
                } else {
                    break;
                }
            }
            break;
        }
    }

    long duration = System.currentTimeMillis() - startTime;

    System.out.println("Total Memory: " + (total - Runtime.getRuntime().totalMemory()));
    System.out.println("Free Memory: " + (free - Runtime.getRuntime().freeMemory()));
    System.out.println("Smallest number not in the list is " + location);
    System.out.println("Time to execute in milliseconds: " + duration);

    boolean isInList = false;
    for (int next : numbers){
        if (location == next){
            isInList = true;
            break;
        }
    }
    System.out.println(location + " is in the list " + isInList);
}


public void getSmallestNotInList() {
     int lowest = 0;
     boolean notLowest = true;
     while (notLowest){
         int last = lowest;
         for (int i=0; i<numbers.length; i++){
             if (numbers[i] == lowest){
                 lowest++;
                 break;
             }
         }
         if (last == lowest){
             break;
         }
     }
     System.out.println("actual lowest is " + lowest);
}
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.