Задачка

[pilot911]

Есть массив парных чисел, среди которых одно число не повторяется: {38, 95,10, 8, 95, 38, 10}

Как найти это число?

 

[Gas]

было ж недавно, был озвучен интересный вариант с xor'ом

 

[pilot911]

было ж недавно, был озвучен интересный вариант с xor'ом

не могу найти, дай ссылку, пож-та

 

[Gas]

не помню где это было, только идея запомнилась, цикл + xor, hint: any_value XOR число XOR число = any_value

 

[Adelf]

перексорить все числа и результатом будет искомое число.

 

[Adelf]

ммм... дай-ка постебусь. Собеседование не можешь пройти?

 

[pilot911]

ммм... дай-ка постебусь. Собеседование не можешь пройти?

собеседование проходил в РБК

просто веселят такие задания.. к чему про алгоритмы спрашивать, когда простейшее решение находится в интернете+поиск подходящих функций на пхп.нет для массивов

 

[Adelf]

pilot911
нуу.. предположу, что пытаются посмотреть как ты будешь решать задачи. Работа программиста - это решить задачу и (необязательно)закодить ее. Вот способность делать первое и проверяют. решение же можно и самому найти не только в интернете.

 

[pilot911]

$array = array("yes", "hello", "yes", "world", "hello");
$new_array = array_count_values($array);

Array
(
[yes] => 2
[hello] => 2
[world] => 1
)

дальше обычный

$value = array_search(1, $array);

 

[pilot911]

pilot911
нуу.. предположу, что пытаются посмотреть как ты будешь решать задачи. Работа программиста - это решить задачу и (необязательно)закодить ее. Вот способность делать первое и проверяют. решение же можно и самому найти не только в интернете.

понимаешь, если бы мне дали доступ в интернет и попросили решить задачу - один разговор, а когда вот так абстрактный конь в вакууме, которого не встречаешь в жизни никогда, практически, то, естественно, странно было бы ожидать хорошего результата

 

[Adelf]

pilot911
Есть и в реальной жизни задачи, решения которых ты не найдешь в инете. Что будешь делать?
Твой способ - долгий.

 

[pilot911]

pilot911
Есть и в реальной жизни задачи, решения которых ты не найдешь в инете. Что будешь делать?
Твой способ - долгий.

давай сравним с твоим способом

ПС. приведи задачу, решение которой не найти в нете

 

[Adelf]

array_count_values - его сложность явно как минимум O(n * log(n)).
Мой способ - O(n).

>> ПС. приведи задачу, решение которой не найти в нете
А ты обратись к товарищам из *****. У них наверняка найдется с десяток

 

[pilot911]

тот топик, где обсуждается эта задача http://phpclub.ru/talk/threads/Задачки-для-новичков.67112/#post-598444

 

[phprus]

просто веселят такие задания.. к чему про алгоритмы спрашивать, когда простейшее решение находится в интернете+поиск подходящих функций на пхп.нет для массивов

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

На приведенную задачу, я бы предложил решение в котором в начале в один цикл строится то, что выдает функция array_count_values, а вторым циклом написал бы поиск того ключа, у которого значение 1. А решение с XOR не факт что бы вспомнил сразу. Хотя если бы мне дали уточнение, что решить надо через XOR, тогда такой ответ в один цикл становится очевидным.

array_count_values - его сложность явно как минимум O(n * log(n)).
Мой способ - O(n).

Не правильно. Оба способа O(n), но различаются константой, которая в оценке O() не учитывается.
Рассмотрим работу array_count_values - в цикле перебрать все элементы (О(n)), для каждого элемента проверить его наличие в hash-таблице (О(1)), если его нет - добавить (О(1)) если есть, увеличить счетчик (О(1)). Как результат имеем суммарную сложность О(n).
Сложность array_search тоже О(n), так как необходим перебор всех элементов.
Оба шага последовательно дадут суммарную сложность опять-же О(n).

ПС. приведи задачу, решение которой не найти в нете

Таких задач примерно две бесконечности минус одна . Я сейчас работаю в области, где таких задач много, правда с WEBом она практически никак не связана.

 

[c0dex]

pilot911
РБК ебл@ны, я туда ходил, более тупого собеседования у меня не было. Началось все с вопроса, "а сколько строк кода вы пишете в день?" Послал нахрен сразу.

 

[pilot911]

в РБК задачи с хайлоадом, в общем, неплохие знания приобретаешь

тут главное - какие люди вокруг

 

[Gas]

Если для прохождения собеседования обязательны экзотические варианты решения (тот же xor), то очень большая вероятность взять вместо опытного хорошего программиста, просто эрудированного человека. Я хоть в своё время 2 года на asm'е программировал и работа с битовыми операциями для меня не пустой звук, но когда первый раз задачу встретил, такое нестандартное (для webdev'а) решение на ум не пришло. Правда я на работу в РБК и не претендую.

 

[HraKK]

Я задаю такую задачку на собеседование. С 1 нюансом - надо найти это число не выделяя новую память.

С числами кстати можно решить сложением и вычитанием. Ксор только для символов.

А у гугля надо найти 2 числа за 1 проход. Это интереснее.

 

[zerkms]

HraKK
Какая разница, выделяешь ты память или нет - ну собирай сумму в текущем (или первом) элементе. Усложнения задачи никакого.

А вот про сложение и вычитание - интересно. Не верю, что это в принципе реально.