Некоторое время назад я наткнулся на забавную цепочку задач на сайте leetcode.com Сами задачки не слишком сложны, но их решения довольно любопытны. Кроме того, задачки такого типа довольно часто попадаются на собеседованиях в крупных компаниях и понимание методов их решения может быть довольно полезно.
Первая задачка — 136. Single Number (легкая сложность)
Дан непустой массив целых чисел, все элементы которого, кроме одного, встречаются дважды и нужно найти этот элемент, лишенный пары.
Нужно решить задачу за O(n) и c константной по дополнительной памятью.
Пример 1
Вход: nums = [1, 3, 3, 2, 6, 2, 1]
Результат: 6
Пример 2
Вход: nums = [12, 1, 1, 7, 1, 12, 1]
Результат: 7
Пример 3
Вход: nums = [6]
Результат: 6
Посмотреть решение
Мы воспользуемся свойством функции XOR давать 1 только в том случае, когда оба ее операнда неравны друг другу.
Пройдя по всем элементам массива и делая им побитовый xor мы сведем к нулю все одинаковые значения битов, а в результате, то что останется и будет искомым результатом.
Вот короткий код решения на python3:
def single_number_i(nums: list) -> int:
result = 0
for el in nums:
result ^= el
return resultМы используем всего лишь столько дополнительной памяти, сколько занимает int и находим решение за единственный проход по заданному массиву, что дает нам O(n) по сложности. Это чистое и красивое решение.
Вторая задачка - 137. Single Number II (средняя сложность)
Дан непустой массив целых чисел, все элементы которого, кроме одного, встречаются три раза и только единственный элемент встречается однократно и нам нужно найти этот элемент.
Нужно решить задачу за O(n) и c константной дополнительной памятью.
Пример 1
Вход: nums = [3, 1, 3, 3]
Результат: 1
Пример 2
Вход: nums = [12, 1, 1, 5, 1, 12, 12]
Результат: 5
Пример 3
Вход: nums = [6]
Результат: 6
Посмотреть решение
К сожалению, мы не можем воспользоваться предыдущим трюком, так как в данном случае мы не сможем превратить парные биты в нужной позиции в нули. Было бы заманчиво привести данный нам массив к виду из предыдущей задачи, а затем решить его аналогичным способом. Рассуждая таким образом, можно легко заметить, что если бы мы знали, что пробегая по массиву мы уже встречали число N дважды(ну или трижды), то мы могли бы добавить к получаемой нами сумме дополнительный XOR с N, сделав итоговое число XOR c этим числом четным, таким образом убрав его из итоговой суммы, а то что останется и будет нашим ответом.
def single_number_ii(nums: list) -> int:
mem = {}
result = 0
for el in nums:
if not mem.get(el, False):
mem[el] = 1
else:
mem[el] += 1
if mem[el] == 2:
result ^= el
result ^= el
return resultК сожалению, максимально это решение потребует (len(nums)-1)/3 по памяти, что нельзя назвать константным потреблением, так что придется нам искать другое решение.
Попробуем поменять наш подход. Если мы сможем встречая число первый раз класть его в ответ, встречая второй раз - класть в аккумулятор и встречая третий раз обнулять и ответ и аккумулятор, то это бы помогло нам решить задачу за один проход по списку с потреблением дополнительной памяти ровно в два int’a, что соответствует требованию задачи. Итак, снова применим немного побитовой магии:
def single_number_137_ii(nums: list) -> int:
ans, acc = 0, 0
for n in nums:
ans = ans ^ n & ~acc
acc = acc ^ n & ~ans
return ansТаким образом, все тройные числа обнуляются и у нас остается только то число, что встречается лишь единожды.
Третья задачка - 260. Single Number III (средняя сложность)
Дан непустой массив целых чисел, все элементы которого, встречаются по два раза и два элемента в массиве встречаются единожды. Мы должны найти эти уникальные элементы, за O(n) и c константной дополнительной памятью, причем их порядок неважен.
Пример 1
Вход: nums = [1, 2, 1, 3, 2, 5]
Результат: [3, 5]
Пример 2
Вход: nums = [1, -2]
Результат: [-2, 1]
Посмотреть решение
Очевидно, что мы легко сможем убрать все парные числа обычным xor-ом, как мы сделали это во время решении первой задачи. Тогда вся сложность задачи заключается в выявлении любого из уникальных чисел, тогда второе легко можно будет вычислить посчитав xor между этим числом и нашей xor-суммой.
Для этого нам достаточно найти любой отличающийся бит между этими уникальными числами, а затем снова пройти по массиву, сделав суммирование по xor, разделив результаты на две группы - для чисел, где этот бит установлен и для тех, где он равен 0. В результате мы и получаем искомые уникальные элементы.
def single_number_260(nums: list) -> int:
res1, res2 = 0, 0
glob_xor = 0
for n in nums:
glob_xor ^= n
diff_bit = glob_xor & ~(glob_xor + 1)
for n in nums:
if n & diff_bit:
res1 ^= n
else:
res2 ^= n
return [res1, res2]Несмотря на то, что нам пришлось пройти массив 2 раза, это по прежнему O(n) по сложности и всего 2 int’a по памяти.
Примечание 1: Несмотря на то, что int в Python это совсем не то же самое, что int в других языках, тем не менее примем его размер за константу.
Примечание 2: Если вам понравились подобные решения, то могу порекомендовать прекрасную книгу Henry S. Warren, Jr. “Hacker’s Delight”, где описано множество полезных трюков битовой арифметики (в русском переводе, она называется “Алгоритмические трюки для программистов”).
Комментарии (38)
Kreastr
02.10.2023 07:04-6Я не уверен, что представленные решения первой и второй задачи имеют сложность O(n) кроме тех случаев, когда числа уже заданы в двоичной системе счисления (чего нет в условиях), поскольку XOR не получится сделать без преобразования систем счисления, а оно в свою очередь будет сложнее, чем O(n), потому что чем больше n, тем больше будет разрядность используемых в массиве уникальных значений. Да и сам XOR добавит log(n). Так что скорее всего эти решения имеют такую же сложность, что и преобразование систем счисления для чисел, которые не помещаются в аппаратный DEC2BIN целевой платформы.
Вот обобщенное решение для произвольного количества повторяющихся элементов и поиска неповторяющегося при помощи BASEN "XOR" преобразования.
https://gist.github.com/Kreastr/025a1fd08189d736fbe8fe3132a0cb1c
domix32
02.10.2023 07:04+2Вы же в курсе, что для компьютера операция XOR, как и любые другие операции, уже происходят на бинарном представлении вне зависимости от того что вы пишите в своей программе. Вас же не из строк числа парсить просят а вполне себе честные числа обрабатываьт. Ну и ограничения с литкода автор не стал писать - там все числа умещаются в 32 бита и входной массив не менее минимальной необходимой длины.
Так что все эти ваши преобразования не имеют ни малейшего смысла, не говоря уже про уровень потребления памяти.
Kreastr
02.10.2023 07:04-3"Ну и ограничения с литкода автор не стал писать - там все числа умещаются в 32 бита и входной массив не менее минимальной необходимой длины."
Ну не стал и не стал - я комментирую по написанному в статье.
"Вы же в курсе, что для компьютера операция XOR, как и любые другие операции, уже происходят на бинарном представлении вне зависимости от того что вы пишите в своей программе. "
Это все здорово только до тех пор, пока у Вас бинарный формат на входе И все умещается в разрядность процессора. О чем я собственно и пишу. В общем (с точки зрения математики или реализации на условном 8-битном МК) случае эту задачу не получится решить за O(n), потому что 1) используется XOR для которого принята условная константная производительность и потому что 2) входной формат не определен условиями задачи.
Примечательно, что автор статьи сам напоминает, что "К сожалению, вы можете не знать какая вычислительная и пространственная сложность скрывается за библиотечными функциями. " Точно тот же аргумент работает и для операций типа XOR.domix32
02.10.2023 07:04+1пока у Вас бинарный формат на входе И все умещается в разрядность процессора
задачи изначально строятся исходя из этих предпосылок. как в общем и большинство программистских олимпиадных задач - их решают в частном виде с ограничениями и с уже отвалидированными данными, а не в генерализованном виде. Так что странно говорить "у вас тут теорема Ферма без пруфа", когда она изначально и не требовалась.
Kreastr
02.10.2023 07:04То есть Вам совершенно нормально, что математические концепции, которые пердназначены для описания эффективности алгоритмов в пределе (n -> inf в данном случае), используются для описания задачи с предпосылками, которые в общем-то устанавливают для n максимальное значение?
Если да, то, пожалуй, тут больше не о чем дискутировать. „Вы можете получить «Форд-Т» любого цвета, при условии, что этот цвет будет черным.“ — Генри Форд
domix32
02.10.2023 07:04Зачем решать генерализованную задачу, если в заголовке статьи явно указано, что это задачи с литкода со своей областью значений и конкретными требованиями?
Почему генерализованные задачи вами решаются на негенерализованном компьютере? Тогда бы все ожидаемые параметры сошлись бы и не нужно было бы решать не связанные с этим проблемы обработки строк.
wataru
02.10.2023 07:04То есть Вам совершенно нормально, что математические концепции, которые пердназначены для описания эффективности алгоритмов в пределе
Потому что это единственный способ как-то вразумительно сравнивать скорости работы алгоритмов. Ибо считать количество циклов процессора или миллисекунды исполнения невозможно каким-либо осмысленным переносимым способом. У вас состояние кеша чуть-чуть не такое будет изначально и лишних наносекунд или циклов процессора на той же абсолютно программе набежит ощутимое количество.
Алгоритм за O(n), Даже если у вас n ограниченно стоней, почти наверняка будет быстрее алгоритма за O(n^2).
Во всяких библиотеках сортировка, например, отсекает квадратичные методы уже на 10-20 элементах. Так что не надо n устремлять к бесконечности.
Kreastr
02.10.2023 07:04"Так что все эти ваши преобразования не имеют ни малейшего смысла, не говоря уже про уровень потребления памяти."
Не имеют. Просто общее решение для представленного класса задач. Да еще и не для всех вариантов по повторениям (а только от 2 до 9), потому что я ленивый, а для демонстрации принципа этого должно быть достаточною.
Про потребление памяти в задаче нет требований по минимизации. Только, что оно должно быть константным. Опять же. Как автор написал.
vassabi
02.10.2023 07:04все понятно кроме магии с отрицанием в конце
ans = ans ^ n & ~accacc = acc ^ n & ~ansне происходит ли там потери битов?
Alexandroppolus
02.10.2023 07:04+3Можно рассмотреть срез по отдельно взятому биту (например, самому младшему), это можно сделать, потому что биты отрабатываются независимо. Если в искомом числе Х этот бит равен 1, то в соответствующем бите единица встречается 3k+1 раз, иначе 3k раз.
Исходно в ans и acc в этом бите нули, т.е. [ans, acc] = [0, 0]. После первой единицы будет [1, 0], после второй - [0, 1], после третьей - [0, 0], круг замкнулся.
Когда в этом бите встречается 0, он не меняет значение бита в обоих переменных, что легко проверить для всех трех вышеописанных состояний.
Итого единичными в ans останутся только биты, соответствующие единичным битам в Х, а нулевыми - нулевые в Х.
Alexandroppolus
02.10.2023 07:04Стоит ещё добавить, что в некоторых языках/средах указанные решения можно прикрутить к вещественным числам. На примере первой задачи (js, можно выполнить в консоли браузера):
const single = (nums) => { const intSrc = new Int32Array(2); const doubSrc = new Float64Array(intSrc.buffer); const intDest = new Int32Array(2); const doubDest = new Float64Array(intDest.buffer); for (const n of nums) { doubSrc[0] = n; intDest[0] = intDest[0] ^ intSrc[0]; intDest[1] = intDest[1] ^ intSrc[1]; } return doubDest[0]; }; single([23.456, 1.5, 87.1, 23.456, 87.1]); // 1.5Суть решения: общий кусок памяти для целого и вещественного.
wataru
02.10.2023 07:04+5Решение первой задачи отлично обобщается и на вторую. Надо осознать, что xor — это побитовое сложение по модулю 2. Раз нам надо сократить не пары чисел, а тройки, то надо выполнять побитовое сложение по модулю 3. Вообще, в прямом обобщении это стоило бы делать над троичными разрядами, но можно и над двоичными. Тогда решение реализуется через битовые операции:
int singleNumber(vector<int>& nums) { int low = 0; int high = 0; for (auto &n : nums) { int carry = low & n; low ^= n; high |= carry; int nullify = low & high; low ^= nullify; high ^= nullify; } return low; }Тут работа идет фактически отдельно по каждому биту. Старший разряд трочиного значения хранится в битах high, а младший в low. Новое число каждый раз прибавляется к low, при этом если есть переносы, то они идут в high. Потом значения 3 заменяются на 0.
Тут чуть больше кода и операций (если читабельно расписывать), но можно ужать в те же 6 битовых операций, что у вас (если аккуратно расписать таблицу истинности в зависимости от трех входных бит). Зато это логично выводится из предыдущего решения и понятно, почему оно работает.
Kreastr
02.10.2023 07:04Вот не поверите. Ровно то же обощение предложил в https://habr.com/ru/articles/764718/#comment_26019878, но пишут "что все эти ваши преобразования не имеют ни малейшего смысла, не говоря уже про уровень потребления памяти."
wataru
02.10.2023 07:04+2Нет, там вас заминусили за всякие "аппаратный DEC2BIN" и излишнюю мишуру, релевантную только работе с большими числами (кстати, там все также остается линейным, ибо тогда сложность считается от размера входных данных, т.е. суммарного количества разрядов во всех числах). Собственно сама идея считать сумму разрядов по модулю 3 в вашем комментарии почти не указана — надо открывать ссылку и смотреть код. Что за "BASEN xor" такой вообще.
Короче говоря, вы немного не ясно выразились, читатели зацепились за какие-то побочные мысли в вашем комментарии и с ними поспорили.
Kreastr
02.10.2023 07:04Пусть проблема решается для пятикратных повторов. Если взять число пусть даже в двоичной системе счисления, то для каждого шага сложения одной позиции по модулю 5 нужно сначала преборазовать число из входящего формата (предположим двоичного) в пятиричный. Правильно?
wataru
02.10.2023 07:04Нет. Можно работать с каждым битом отдельно. Складывать их по модулю 5. Не обязательно работать с пятиричными разрядами.
Kreastr
02.10.2023 07:04del.
Думаю я понял Ваш подход. Да, так получится O(n), если n это количество бит. Спасибо.wataru
02.10.2023 07:04+1Сколько операций нужно для того, чтобы сложить один бит из n чисел по модулю 5 (со всеми переносами)?
O(n)
И зависит ли это значение от того, что мы складываем по модулю 5, а не, например, по модулю 3?
Да. Чтобы сложить по модулю k один разряд от n чисел надо O(n log(k)) операций. Но в задаче модуль 3 фиксированный, поэтому суммарно получается O(n) на один разряд. Процессор может обрабатывать все разряды за одну операцию, поэтому суммарно решение все еще O(n). Но, если бы не было побитовых операций, то на все разряды надо было бы O(32*n)=O(n).
Если бы числа занимали по M бит то тогда было бы O(n*M). Но тогда бы имело смысл задавать не ограничения на количество чисел, а но общую длину входных данных и это самое n*M было бы как раз размером входных данных и решение оставалось бы линейным.
Kreastr
02.10.2023 07:04Мой аргумент. Может быть немного перефразирую в том, что в
"Но, если бы не было побитовых операций, то на все разряды надо было бы O(32*n)=O(n)."
32 это не просто константа. По условию задачи почти все числа во входном наборе данных могут повторяться только p раз. Поэтому чем больше n, тем больше должна быть минимальная разрядность каждого числа. То есть у Вас не 32n, а plog(n)*n бит. И если считать в битах, то я согласен с оценкой в O(n), а, если в количестве значений входящего массива, то нет.
wataru
02.10.2023 07:04+1В условии задачи задано ограничение, какого размера могут быть числа. Но даже если обобщить на числа ЛЮБОЙ длины, то проблема вот в чем:
И если считать в битах, то я согласен с оценкой в O(n), а, если в количестве значений входящего массива, то нет.
Если числа могут быть большой длины, то нет смысла считать оценку от их количества. Так, любую задачу можно переформулировать, что вам дано одно очень большое число и надо что-то сделать с его разрядами.
Edit: Так, формально, оценки не считают от какого-то входного параметра, как-то количество чисел, максимальное число или битность. Алгоритмы оценивают в зависимости от размера входных данных. Просто совпадает, что если работать с ограниченными числами, то количество чисел и размер входных данных — линейно зависимы.
mentin
02.10.2023 07:04В последнем решении опечатка вроде
diff_bit = glob_xor & ~(glob_xor + 1)
~ должна быть внутри скобочек.
dprotopopov
02.10.2023 07:04К сожалению, мы не можем воспользоваться предыдущим трюком, так как в данном случае мы не сможем превратить парные биты в нужной позиции в нули
Вы неправы! Вы плохо учили математику
1. Реализуем кольцо вычетов по модулю 3: GF(3)
2. Реализуем арифметику (регистры) над GF(3)^n
3. Записываем исходные числа в 3-тичном представлении
4. Повторяем алгоритм как в предыдущей задаче, но не над GF(2), а над GF(3)wataru
02.10.2023 07:04+1Не надо даже никакого троичного представления. Достаточно складывать биты по модулю 3. Релизуется через битовую магию на двух числах (для хранения остатка mod 3 достаточно двух бит): https://habr.com/ru/articles/764718/#comment_26020950
Кстати, внезапно, авторское решение в итоге вычисляет абсолютно вот эту самую сумму по модулю 3: https://habr.com/ru/articles/764718/#comment_26020794
Только завуалированно.
dprotopopov
02.10.2023 07:04Да, вы правы - достаточно инективно отобразить числа в множество с операций и нулём, где у всех элементов порядок 3 и там последовательно провести операцию, а потом вернуться обратно
a-tk
02.10.2023 07:04Если уж задачи на засыпку, то как найти среди четвёрок пару?
wataru
02.10.2023 07:04+1Если пара из разных значений, то это все еще третья задача. Если значения в паре одинаковые, то можно обобщить второе решение: считайте сумму по модулю 4 для каждого бита. В итоге получите удвоенное значение искомого числа в каждом "бите". Надо будет его поделить на 2. Если считать с битовой магией, то ответ будет в high битах:
int findPair(const vector<int>& nums) { int low = 0; int high = 0; for (auto &n : nums) { int carry = low & n; low ^= n; high ^= carry; } return high; }Если значения могут быть и разными и совпадать, то надо подсчитать xor как в решении 3-ей задачи, если там не 0 оказался, то продолжать решать третью задачу, иначе считать сумму по модулю 4.
Alexandroppolus
02.10.2023 07:04+2Похоже, этот подход легко обобщается на случай, когда все числа встречаются К раз, а одно какое-то - менее К раз (но более 0). Функция freakNumber(nums, k) вернёт такое число, и сколько раз оно встретилось:
function freakNumber(nums, k) { const len = Math.ceil(Math.log2(k)); const bits = new Int32Array(len); let carry; const kBits = new Int32Array(len); for (let b = 0; b < len; ++b) { kBits[b] = k & 2**b ? -1 : 0; } for (let i = 0; i < nums.length; ++i) { let n = nums[i]; let nullify = 0; for (let b = 0; b < len; ++b) { carry = bits[b] & n; bits[b] = bits[b] ^ n; n = carry; nullify = nullify | (bits[b] ^ kBits[b]); } for (let b = 0; b < len; ++b) { bits[b] = bits[b] & nullify; } } let count = 0, fn = 0; for (let b = 0; b < len; ++b) { fn = fn || bits[b]; count += bits[b] ? 2 ** b : 0; } return [fn, count]; } freakNumber([34, 3, 3, 34, 7, 34, 3, 3, 34, 34, 7, 3, 7], 5) // число 7, встретилось 3 раза, остальные по 5 раз2 ** b - это 2 в степени b
wataru
02.10.2023 07:04+2Мне нравится, как вы сравниваете счетчики с k. Весьма элегантно.
Вообще, задача еще больше обобщается:
Дано n чисел, там числа встречаются по k раз, и есть еще не более k "лишних" чисел. Эти лишние могут почти как угодно совпадать или быть разными, кроме случая, когда их лишних ровно k — тогда они не могут быть все равны.Это обобщение второй и третьей задач сразу.
Решается также: считаем сумму разрядов по модулю k. Еще считаем m=n%k.
Если в сумме все разряды оказались 0 или m, то значит мы нашли m одинаковых лишних чисел: надо установить в 1 те разряды, где сумма не 0.
Иначе берем любой разряд, где сумма не 0 и не m. Разбиваем входной массив на 2 части по этому биту (0 — в одну сторону, 1 — в другую). Это делается на месте за O(n) алгоритмом partition, как в qsort. Ну и рекурсивно запускаемся от каждой части. Поскольку сумма лишних чисел в этом разряде не 0 и не m, среди лишних есть числа там в обеих полвинках. Значит мы хоты бы одно откусили. Максимум за k рекурсивных вызовов мы найдем все числа.
Это работает за O(k logk n) и потребялет O(k log k) памяти.
Skykharkov
Абстрактно, если конечно, то оно круто. Вот только потом поддерживать такой код... Продираясь через XOR'ы и так далее... А чего не LINQ? Абстрактный вопрос, но вроде-же в Python, LINQ уже давно завезли. И читать такой код приятней и понятнее. И работать будет для любого (ну почти) типа объектов и так далее...
int[] nums = new int[] { 1, 3, 9, 3, 2, 6, 2, 1, 8 };var onlyOne = nums.GroupBy(value => value).Where(item => item.Count() == 1);
Debug.WriteLine(String.Join(", ", onlyOne.Select(item => item.Key)));
//Output - 9, 6, 8
iGeni Автор
К сожалению, вы можете не знать какая вычислительная и пространственная сложность скрывается за библиотечными функциями. По этой причине Ваш код может в фоне потреблять кучу ресурсов, тормозить и течь, несмотря на то, что он выглядит просто. Ну и, кроме того, у вас ресурсы могут быть жестко ограничены железом, например в embed’е.
s207883
Вы навесили кучу абстрактных ограничений на абстрактную же задачу. А, если эта функция выполняется раз в день? Если у нас нет жесткого ограничения по ресурсам? И у нас вообще 10 цифр, тут и оверхед в 90% никто не заметит.
В общих случаях, читаемость лучше, чем скорость работы. Или все уже забыли про вред преждевременной оптимизации?
Еще могу дополнить, что этот код не будет течь и, в общем, будет работать достаточно шустро.
tenzink
Странно читать такой комментарий про учебную задачу с литкода с жёстко прописанными ограничениями на решение. Очевидно, её можно сделать десятками алгоритмически неоптимальных способов (как в примере с LINQ) и иногда это будет нормально для вашего приложения
a-tk
Вывод: в работе Вы не будете решать задачи с литкода в 100%, и даже похожие на них с вероятностью 99.9999%. Точно так же как Вам в работе не понадобятся туча -логий, идущих в комплекте к верхнему образованию, однако человек с верхним образованием показывает лучшие результаты, чем человек со средне-специальным образованием программиста. Почему? Потому что выше уровень эрудиции и насмотренности, и более разнообразная тренировка мозга. Примерно подобный аргумент можно привести для литкода. А можно и не приводить, исходя из первого тезиса.
А потом случается страшное: возникла ситуация, где доказано, что упёрлись в некачественный алгоритм, и надо найти того, кто исправит ситуацию. И тогда самоучки без алгоритмической базы забьются под плинтус, и наступит звёздный час того, кто прошёл таки литкод. Такая ситуация возникает часто? У кого как, но в любом случае не каждый день.
И опять контраргумент: может и хватит пары-тройки человек, которые в это умеют, и стаи велосипедостроителей для перекладывания CRUD-ов?..
wataru
Проблема тут с тем, что почти никогда не очевидно, что где-то нужен "Алгоритм". Ну посморите задачки на литкоде, большинство из них сводятся к "Дано вот это, сделайте вот это вот так и так". Можно просто буквально перевести английский в условный C++ и получить работающее (но очень медленное) решение. В реальной работе еще хуже, ведь надо самому задачу в таком виде и сформулировать еще, так что у разработчика появляется мысль, что это и не задача вообще, а вот такое решение он и придумал. Паузы на подумать, а вдруг тут нужен "Алгоритм", не происходит вообще.
В итоге, эти выделенные пара-тройка алгоритмистов должны будут постоянно ревьювить вообще весь код, или постоянно переписывать огромную часть кода. Или их должна быть половина, или эффекта от них будет мало. И никакой профайлинг никак не поможет, потому что примерно тормозить будут вообще все части кода, которые могут тормозить.
Плюс, если у вас зарплаты и так вкусные, эффективнее требовать от всех умения в алгоритмы на каком-то минимальном уровне (easy-medium задачки с литкода — это далеко не олимпиадный уровень. Этого вполне могут достичь большинство программистов).
Да, сразу оговорюсь, что это относится к приложениям, которые что-то с данными, таки, делают. Если у вас веб-форма в которую пользователь вбивает 2 значения — то вряд ли у вас будет такая проблема. Но фаанги, которые такие интервью и придумали, с этим сталкиваются постоянно. Ну и, когда условные "рога и копыта" с 1000 пользователей, типичной CRUD задачей, и зарплатой чуть ниже медианы рынка требуют литкод интервью, потому что "все так делают" — это глупость.
Skykharkov
Ну смотрите. Я понимаю, что задачка в статье она чисто "олимпиадная", на какое-то условное понимание бинарных операций, раскроет мастерство выполняющего её, в работе с битами и так далее. Это круто, если вы тестируете микроконтроллерщика и так далее. Где ресурсов, условный килобайт ОЗУ и частота 1 кГц на шине... Да, чувак который оперирует битами в уме и на brainfuck напишет это запросто. Я кстати присмотрелся к решению на нем. Чисто в теории... Плюнул. Не хочется терять два дня. :)
Решение с LINQ оно О(n) умножить на 2. "Group" и "Where" - линейные операции. Но вот это "умножить на 2" у вас получится "умножить на 150", когда вы попытаетесь этот код и подход применить на практике. И уж если вы выйдете за рамки задачи делать это с byte или int только (и то вопрос об архитектуре открыт).
Например, вопрос на собеседовании. Задача - перенести 5 литров воды, руками, из точку А в точку Б. Как будете решать? Возьму пятилитровое ведро! Какой вы молодец и умница. А если 300 литров воды? Возьму трехсотлитровое ведро!
Всё! Задача решена!
wataru
Проблема вашего linq, что оно, хоть и работает за линию, но потребляет O(n) памяти на какую-нибудь хеш-таблицу.
Если у вас много данных (а в фаангах, которые такие интервью и спрашивают, данных обычно много), то потребление памяти тоже весьма важно. Ваша задача далеко не единственная, которая будет крутиться на сервере и тарабайты оперативки во все 100500 машин не поставишь. Своп, конечно, есть, но при нем все дичайше торомозит.
Как раз у вашего LINQ константа точно сильно хуже битового решения. Там надо хеши подсчитать, в таблице поискать, счетчики поувеличивать. Оно точно будет раз в 10 медленнее, а то и в десятки.
Это хороший дополнительный вопрос к задаче. Подход отлично обобщается на длинные числа и хорошо с ними работает.