Отсутствующее число в файле

Решение

Анализ проблемы

Это классическая задача интервью на понимание ограничений памяти и оптимизации:

Дано:

• 4 миллиарда 32-битных целых чисел в файле
• Диапазон 0 до 2^32-1 (около 4.3 млрд значений)
• Одного числа не хватает
• Ограничена оперативная память

Решение 1: Побитовое XOR

def findMissing(filename):
    result = 0
    
    # XOR всех чисел 0..2^32-1
    for i in range(2**32):
        result ^= i
    
    # XOR с числами в файле
    with open(filename, 'rb') as f:
        while True:
            chunk = f.read(4)
            if not chunk:
                break
            num = int.from_bytes(chunk, byteorder='little')
            result ^= num
    
    return result

Почему работает: a ^ a = 0, поэтому парные элементы исчезают, остаётся непарный.

Решение 2: Математическая сумма

def findMissing(filename):
    n = 2**32 - 1
    expected = n * (n + 1) // 2
    
    actual = 0
    with open(filename, 'rb') as f:
        while True:
            chunk = f.read(4)
            if not chunk:
                break
            num = int.from_bytes(chunk, byteorder='little')
            actual += num
    
    return expected - actual

Решение 3: Битовый массив

def findMissing(filename, memory_mb=512):
    bits = bytearray((2**32 + 7) // 8)
    
    with open(filename, 'rb') as f:
        while True:
            chunk = f.read(4)
            if not chunk:
                break
            num = int.from_bytes(chunk, byteorder='little')
            bits[num // 8] |= (1 << (num % 8))
    
    for i in range(2**32):
        if not (bits[i // 8] & (1 << (i % 8))):
            return i
    
    return -1

Решение 4: Двухпроходный алгоритм

Если памяти совсем мало, разбиваем на части и обрабатываем каждую отдельно.

Сравнение

Рекомендация

На собеседовании:

1. Обсудите ограничения - почему стандартные подходы не работают
2. Предложите XOR решение - O(1) памяти, O(n) времени
3. Объясните почему работает XOR
4. Предложите альтернативы с trade-offs
5. Обсудите тестирование на больших данных