Handling Massive Datasets

Identifying Missing Integers in a 4-Billion-Element File with 1GB Memory The range of a 32-bit unsigned integer spans 0 to 4,294,967,295. A file containing 4 billion such integers guarantees some numbers are missing. To find all missing values using 1GB of RAM, construct a bitmap. Since 2^32 bits equates to 512MB, allocate a byte array of size 2^32 / 8. Iterate through the dataset, setting the corresponding bit for each encountered number. After processing, any bit remaining unset indicates a missing integer.

Finding a Single Missing Number under Severe Memory Constraints (3KB or Constant Variables) With only 3KB of memory, allocate an unsigned integer array sized to the largest power of 2 that fits (e.g., 512). Divide the 2^32 range into 512 distinct intervals. Count the frequency of numbers falling into each interval. The interval containing fewer than 2^32 / 512 numbers holds the missing value; narrow the search recursively. If restricted to a few variables, use a binary search strategy: split the integer range in half, count the elements in each half, and recursively target the half that is under-populated.

Extracting Top 100 Elements from 10 Billion Records Partition the data into multiple smaller files using a hash function. Maintain a max-heap for each partition to track its local maximums. Establish a global max-heap containing the top elements from all partition heaps. Extract the maximum from the global heap, then push the next element from the corresponding partition heap into the global heap. Repeat this extraction exactly 100 times.

Detecting Duplicates in 4 Billion Numbers with 1GB Memory To identify numbers appearing exactly twice, deploy a 2-bit bitmap. The states 00, 01, 10, and 11 represent zero, one, two, and multiple occurrences respectively. Since 2^32 * 2 bits requires exactly 1GB, traverse the dataset and update the state transitions. Finally, scan the bitmap for the 10 state.

Computing the Median of 4 Billion Numbers using 10MB Memory Allocate an integer array sized to fit the 10MB limit (approximately 2.5 million integers). Map the entire 32-bit range onto this array to count frequencies. Determine which interval contains the median, then re-apply the counting mechanism strictly within that interval until the precise median value is located.

Sorting a 10GB File with 5GB Memory Approach A: Implement a min-heap sized to hold frequency records fitting within 5GB. Process the data in sequential ranges (e.g., from Integer.MIN_VALUE to Integer.MIN_VALUE + range_size). Extract and write sorted elements for each range before proceeding to the next. Approach B: Use a max-heap occupying the allowed 5GB. Populate it with elements; if an element is smaller than the heap's root, replace the root. After a full pass, the heap contains the smalest K elements, which can be written to disk. Repeat the process for elements larger than the previously recorded maximum.

Bit Manipulation Techniques

Finding the Maximum of Two Integers Without Comparison Operators Avoiding overflow is critical. Use the sign bit and mutually exclusive conditions to determine the result.

public class MaxFinder {
    private static int invert(int val) { 
        return val ^ 1; 
    }
    
    private static int isPositive(int val) { 
        return invert((val >> 31) & 1); 
    }

    public static int findMaxSecure(int x, int y) {
        int diff = x - y;
        int xSign = isPositive(x);
        int ySign = isPositive(y);
        int diffSign = isPositive(diff);
        
        int signsDiffer = xSign ^ ySign;
        int signsMatch = invert(signsDiffer);
        
        int pickX = signsDiffer * xSign + signsMatch * diffSign;
        int pickY = invert(pickX);
        
        return pickX * x + pickY * y;
    }
}

Validating Powers of 2 and 4 A number is a power of 2 if its binary representation contains exactly one 1. This is verified by checking if n & (n - 1) equals 0. For a power of 4, the single 1 bit must reside in an even position, wich can be confirmed by masking with 0x55555555.

public class PowerChecker {
    public static boolean isPowerOfTwo(int val) {
        return val > 0 && (val & (val - 1)) == 0;
    }

    public static boolean isPowerOfFour(int val) {
        return isPowerOfTwo(val) && (val & 0x55555555) != 0;
    }
}

Implementing Arithmetic Operations Using Bitwise Logic Addition relies on summing without carry (XOR) and calculating the carry (AND shifted left). Subtraction adds the negation (two's complement). Multiplication shifts and adds based on the multiplier's bits. Division shifts the divisor and subtracts when possible.

public class BitwiseMath {
    public static int add(int left, int right) {
        int sum = left;
        while (right != 0) {
            sum = left ^ right;
            right = (left & right) << 1;
            left = sum;
        }
        return sum;
    }

    private static int negate(int val) {
        return add(~val, 1);
    }

    public static int subtract(int left, int right) {
        return add(left, negate(right));
    }

    public static int multiply(int left, int right) {
        int product = 0;
        while (right != 0) {
            if ((right & 1) == 1) {
                product = add(product, left);
            }
            left <<= 1;
            right >>>= 1;
        }
        return product;
    }

    private static boolean isNegative(int val) {
        return val < 0;
    }

    public static int divide(int dividend, int divisor) {
        int absDividend = isNegative(dividend) ? negate(dividend) : dividend;
        int absDivisor = isNegative(divisor) ? negate(divisor) : divisor;
        int quotient = 0;

        for (int i = 31; i >= 0; i = subtract(i, 1)) {
            if ((absDividend >> i) >= absDivisor) {
                quotient |= (1 << i);
                absDividend = subtract(absDividend, absDivisor << i);
            }
        }
        return isNegative(dividend) ^ isNegative(divisor) ? negate(quotient) : quotient;
    }
}