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

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

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

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

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

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

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

Пусть A1, A2 ... An — набор ненулевых перфокарт, X — это результат XOR'а всех возможных перфокарт. A — уникальная перфокарта.

Тогда имеем:
(A1 xor A2 xor ... xor An) xor A = X

Предположим, что A — неуникально. Так как операция xor — ассоциативна и коммуникативна, то положим A1 = A.

Тогда имеем:
(A1 xor A) xor (A2 xor A3 xor ... xor An) = X, так как A1 xor A = 0, то:
A2 xor A3 xor .... xor An = X

Т.е. A=A1=0. Что противоречит условию, что все перфокарты ненулевые.

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

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

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

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

X=0 Если число бит на перфокарте >1.


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

Чтобы это работало, нужно быть уверенным,что что в последовательности отсуствует только одна карта.
Например для набора:

1 0 1
1 1 0
0 1 1
0 0 0

XOR вернет 0, хотя уникальные искомые карты есть.

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

Супер, но я нигде не увидел что каждая перфокарта встречается не более 1 раза.

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

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

C>Пусть A1, A2 ... An — набор ненулевых перфокарт, X — это результат XOR'а всех возможных перфокарт. A — уникальная перфокарта.

C>Тогда имеем:
C>(A1 xor A2 xor ... xor An) xor A = X

C>Предположим, что A — неуникально. Так как операция xor — ассоциативна и коммуникативна, то положим A1 = A.

C>Тогда имеем:
C>(A1 xor A) xor (A2 xor A3 xor ... xor An) = X, так как A1 xor A = 0, то:
C>A2 xor A3 xor .... xor An = X

C>Т.е. A=A1=0. Что противоречит условию, что все перфокарты ненулевые.

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

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

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

Как было справедливо замечено, метод может давать сбои при наличии 2-х (или другого четного количества) одинаковых перфокарт.

Мой первый метод (предложенный) — надо просто найти либо минимальное, либо максимальное значение (сравнивая перфокарты в алфавитном порядке), и, соответственно — декрементировать или инкрементировать результат. Метод плох тем, что выдаст ошибку в случае если в колоде присутствуют крайние случаи — чистая карта и полностью дырявая карта.

Второй метод — используем бит-вектор на 256*80=20480 бит. Это хоть и больше 80 байт, но все равно O(1) памяти, то есть, на одну перфокарту. Изначально очищаем его. Первый байт на перфокарте ассоциирован с битами в векторе 0...255, второй — 256...511 и т.д. Мы просто устанавливаем биты, соответствующие значениям в байтах. В конце мы составляем уникальное значение очень простым и очевидным способом. Ну, либо, возвращаем код ошибки, в случае если весь бит-вектор оказался единичным. Но это тоже неправильно, поскольку можно легко составить такую колоду, которая быстро забьет все единицами. Нам всего-то надо 256*80 карт. Это большая колода, но не фантастически большая. Какие будут еще предложения?

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

MS>Какие будут еще предложения?
А если попробовать совместить мой метод, и ещё считать число изменений каждого бита?

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

C>А если попробовать совместить мой метод, и ещё считать число изменений каждого бита?
А толку-то?
Вот получил ты, что каждый бит менялся дважды. И что? Какой карты точне нет в колоде?

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

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

Так за один проход, или O(N)?

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

KK>Так за один проход, или O(N)?

За один проход. Считаем, что у нас нет никакой возможности вернуться ни к началу, ни к предыдущей перфокарте.

Мое решение задачи: при указанных условиях задача решения не имеет.

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

MS>Недавно был на неком интервью и там возникла такая задача...

жаль, что карты такие короткие, были бы бесконечной длины — было бы все проще

Здравствуйте, Аноним, Вы писали:

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

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

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

U>На самом деле, не все так плохо. 2^640 — очень большое число, подозреваю что намного больше, чем количество элементарных частиц во вселенной. Поэтому алгоритмом, который для любой реально существующей в жизни последовательности перфокарт выдавал бы правильные результаты с вероятностью очень близкой к единице будет генерация случайной перфокарты и проверка ее неналичия в колоде

Можно, кстати, генерить 100 карт, например...

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

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


А какой разброс значений? Целые числа? Строки? Ведь ты написал что на перфокарте строка в 80 байт. Что она из себя представляет? Длинное целое? Одно значение? Много? Каждый байт — это уже отдельное значение или надо интерпретировать строку в челом как 80байтное число? Или как? То что ты ответил случайно на случайный вопрос в котором не доконца изложены условия — то это тебе закономерно повезло.

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

...
А>>жаль, что карты такие короткие, были бы бесконечной длины — было бы все проще
U>На самом деле, не все так плохо. 2^640 — очень большое число, ...

Для карт бесконечной длины можно применить диагональный метод:

Инвертируем первый бит первой карты, второй бит второй карты, N-й бит N-ой карты... Из этих бит получается карта, которой гарантированно нет в исходной колоде. Естественно, длина нашей колоды для этого алгоритма ограничена 640 картами.

Здравствуйте, Аноним, Вы писали:

А>Инвертируем первый бит первой карты, второй бит второй карты, N-й бит N-ой карты... Из этих бит получается карта, которой гарантированно нет в исходной колоде. Естественно, длина нашей колоды для этого алгоритма ограничена 640 картами.

Можно немного улучшить этот алгоритм, если новый бит задействовать только для карты, у которйо все предыдущие совпали...