[Sorting and Searching] interview questions #7

[rygh4775]

Missing Int: Given an input file with four billion non-negative integers, provide an algorithm to generate an integer that is not contained in the file. Assume you have 1 GB of memory available for this task. FOLLOW UP What if you have only 10MB of memory? Assume that all the values are distinct and we now have no more than one billion non-negative integers.

[rygh4775]

Approach

• A file with 4 billion non-negative integers
  • int type, 4 bytes (32bits), 2^32 => 4,294,967,296
  • Non-negative integers, 2^31 + 1
  • some duplicates
• 1GB memory limit
  • 1GB -> 1,000MB -> 1,000,000KB -> 1,000,000,000Bytes -> 8 billion bits

We can map all possible integers to a distinct bit with available memory

Solution

void solution(String fileName) throws FileNotFoundException {
        long numOfInts = ((long) Integer.MAX_VALUE) + 1;
        byte[] bytes = new byte[(int) (numOfInts / 8)];

        Scanner scanner = new Scanner(new FileReader(fileName));
        while(scanner.hasNextInt()) {
            int num = scanner.nextInt();
            bytes[num / 8] |= (1 << (num % 8));
        }

        for (int i = 0; i < bytes.length; i++) {
            for (int j = 0; j < 8; j++) {
                if((bytes[i] & (1 << j)) == 0) {
                    System.out.println(i * 8 + j);
                    return;
                }
            }
        }
    }

Time complexity

N is 4 billion.

Best case: O(N) + 1

Worst case: O(N) + O(2^31+1)

Space Complexity

O(2^31+1)

2^31+1 bits