Здравствуйте, McSeem2, Вы писали:

MS>Недавно был на неком интервью и там возникла такая задача — есть колода перфокарт, последняя из которых должна однозначно определять конец последовательности. Одна перфокарта представляет собой строку символов длиной 80 байт. Надо за один проход — O(N) и с памятью O(1) вычислить любое уникальное значение, не имеющееся в этой колоде, либо же вернуть код ошибки, если (теоретически) в колоде 2^640 уникальных карт. Я сразу лихо сказал, что надо использовать бит-вектор на одну перфокарту, на что мне было сказано, что все круто, дальше можно не продолжать. Но на самом-то деле, это было лишь мое предположение, я типа угадал. А как конкретно решать эту задачу — я не знал.

MS>Я уже потом придумал решение, но хотелось бы убедиться, что оно оптимально и непротиворечиво. Кто что думает?
Сначала считаем число, которое получится, если заXORить все возможные перфокарты — это у нас будет константа X.

Теперь XORим все перфокарты последовательно и XORим на X. Результат будет либо нулём (уникальной перфокарты не существует, или она полностью состоит из нулей) или уникальной перфокартой.