Задача с собеседования Google | Разбираем LeetCode

Разбираю алгоритмы с собеседований Google, Apple, Amazon и тд на LeetCode. Разберем самые эффективные способы решения.
Алгоритмы и Структуры данных

[unborghild]

Чел, который просто хотел устроится уборщиком в офисе

[vitakindnature]

"Нам дан массив, где каждый элемент имеет пару. Нужно найти элемент массива, который пары не имеет". Логически неправильное построение условия задачи. Можно просто сразу ответить, что согласно условию такого элемента нет.

[Sergey-Primak]

условие задачи не соответствует задаче!
нам дан массив, где каждый элемент имеет пару!
значит нет элементов без пары

[morgot]

Алгоритм сработает, если в массиве нет пары у 0 или 1 числа. Если 2 числа без пары - будет их xor объединение. Например. Если в массив из примера добавить число 3, [4, 3, 1, 2, 1, 2] то результат функции будет 7
Но вообще да, интересное решение задачи

[mishagunter]

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

[igorlu]

Такое решение работает только если есть один не парный элемент, если есть 2, то результат будет xor от них, а если 3 то результатом может быть и ноль, к примеру xor между [101, 001, 100] = 0. Отсюда вопрос, где в реальной жизни может пригодится такое решение?

[milenaakm]

Спасибо, теперь я знаю, почему я не работаю в Гугл

[abervalg]

В условии не было сказано что число без пары единственное.

[soneroen]

Какой же тернистый путь мне еще предстоит пройти

[ismism]

a = [1, 3, 1, 3, 5, 9, 5, 8]
b = list(filter(lambda x: a.count(x) == 1, a))
print(b if b else 'все парные')

На выход список из непарных

[petrchibisov]

Решение в js подходит только для целых 32 битных чисел.

[frayz]

Я возможно чего-то не понимаю, но решить такую на питоне дело простое . Перебирать количество всех элементов через count пока не встретишь единицу и вывести соответствующий элемент

[azathoth]

Как по результатам работы подобного алгоритма верифицироать, когда в массиве нет числа без пары, а когда число без пары -- ноль?

[Dmitriitube]

Эти все задачи на собеседованиях вообще имеют связь с реальностью с тем, что потом придется делать после приема?

[redeyes]

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

[margaritasato]

Почему было решено использовать постфиксный инкремент в цикле, а не префиксный?

[Virisound]

Разве где-то используют ещё побитовые операторы?

[МаксимПушкин-вю]

Для питонистов все гораздо проще
num = (4, 1, 2, 1, 2)
a = set(num)
b = (sum(a) * 2) - sum(a)
print(b)

[DronSIG]

Не желая принимать и понимать xor люди в комментах пишут простыни с темплейтами и разными count’ами…
Решение из видео имеет не только лучшую алгоритмическую сложность, но и очень эффективно, если все это разложить на asm по тактам.

[aladales]

А если в массиве будет пара нулей, как определить на выходе, что это положительный результат функции?