Несколько замечаний
- Все задачки на логику и/или о программировании. Никакого психологического подтекста и круглых люков.
- Решение не приводится умышленно. Однако, я уверяю вас, что почти у всех задач есть простое и красивое решение. Наслаждайтесь!
Задачи
Вот они.
Зеркальные строки в SQL
Предположим, что у нас есть таблица со строковой колонкой и мы хотим найти схожие строки, основываясь на каком-либо условии (например, это может быть полнотекстовый поиск или некоторая внутренняя функция, которая получает на входе два значения и возвращает true/false). Итак, мы пишем self-join и, конечно же, получаем дубли среди значений. То есть у нас появляются зеркальные пары в результате и итоговых значений ровно в два раза больше, чем хотелось бы. Вопрос: как удалить из результата по одному любому элементу из каждой зеркальной пары и оставить там только уникальные значения с точностью до перестановок?
- существует одно неочевидное свойство строк и базовых SQL-операторов, которым можно воспользоваться...
- Или можно погуглить, при правильном запросе ответ будет в первой ссылке на stackoverflow.
Поиск "дырок" с помощью SQL
Это отличная задачка для оценки знаний по всем базовым возможностям SQL.
Предположим, что у нас есть таблица с одной интовой колонкой. Мы ничего не знаем о минимуме/максимуме значений в ней. Так же, мы не знает ничего о количестве строк в таблица и, в общем случае, оно варьируется и мы на него опираться не должны. Ещё мы знаем, что среди значений есть пропуски, длина которых не превышает единицы. Например, для таблицы из 5 (пяти) элементов: 1, 2, 4, 6, 7. Вопрос: напишите один SQL-запрос используя только базовые операторы (то есть без процедурщины и переменных), который вернёт значение всех "дырок". Для вышеозначенного примера, результат должен быть 3, 5. Помните, что на месте пропусков нет NULL -значений. Значений 3 и 5 физически нет в таблице.
- если ходу не получается, напишите в несколько запросов или с использованием pl/sql, а затем, если ваша идея верна, сможете логически перейти к одному запросу.
- наиболее красивым запрос будет в случае, если запрос для вышепреведённых входных условий вернёт не "3, 5", а "3, 5, 8".
Циклы в односвязном списке
Это задачка про алгоритмы и сложность.
Предположим, то у нас есть конечный односвязный список. Мы знаем, что в нём, возможно, есть цикл. То есть, один из последующих элементов ссылается на какой-то из предыдущих. Нужно описать способ нахождения циклов в такой структуре за конечное время. Так же, нужно предоставить оценку времени и памяти, необходимой для выполнения предложенного алгоритма.
Продолжение
Нужно модифицировать результат так, чтобы сложность по памяти была O(1). То есть, чтобы потребление памяти не зависело от размера списка.
- помните, что так же как масса может превращаться в энергию, так и временнaя сложность, может конвертироваться в потребление памяти и наоборот.
Хранищиде ключ-значение
Ещё одна задачка на совместное написание кода и его обсуждение в ходе написания.
Напишите key-value storage на любом желаемом языке. Добавьте функцию set_all, которая принимает на вход значение и устанавливает его для всех существующих ключей. Оцените затраты времени и памяти для полученной реализации.
А теперь сделайте set_all, работающим за O(1).
А можно сделать так, чтобы сложность методов get и set осталась как в самом начале, а set_all продолжил работать за O(1)? Если да, то реализуйте. Если нет — докажите почему это невозможно.
Спасение людей
А в этой задаче надо подумать и порассуждать вместе с собеседуемым. А реализация — это дело техники и не особо интересна.
Представим, что у нас есть группа людей. Количество значения не имеет. Всю группу выстраивают в линию в затылок друг другу и каждому на голову одевают чёрную или белую шляпу. Никто не знает цвета шляпы, которая на него надета. Однако, все видят, что происходит перед ними и слышал, что происходит за ними. После этого, к спине последнего из группы полходит незнакомец с пистолетом. Он спрашивает "какой у тебя цвет шляпы?" Ответом может быть только "черный" или "белый". Никаких других сообщений быть не может. Если человек угадал — его отпускают. Иначе происходит выстрел и, в любом случае, процесс повторяется с "новым" последним членом в очереди.
Важное уточнение: перед началом этого негуманного опыта, все члены группы могут встретиться и продумать свою стратегию выживания.
Вопрос: как максимизировать число выживших и существует ли точная оценка числа выживших в зависимости от размера группы?
- подуайте, как может каждый член собрать всю доступную информацию и передать её в одном бите?
- может быть чётность/нечётность или оператор XOR смогут вам помочь?
Вот и всё. Теперь ваша очередь решить какую-нибудь из задач и рассказать о своей интересной подборке с/для собеседований.
Комментарии (73)
paranoya_prod
16.10.2018 10:41В варианте с шапками погибнет только один — последний, при условии, что люди договорились как передать инфу о цвете шапки и количество шапок обоих цветов им неизвестно.
Kaiser
17.10.2018 15:11+1С шапками очень популярная, легкая и из разряда не рекомендованных к собеседованиям. Но такого рода задачи интересно просто решать в свободное от работы время.
Вариант этой задачи от Михаила на порядок интереснее, где количество заключенных алеф-0 и нужна бесконечная память: habr.com/post/54824
hatari90
16.10.2018 10:50Вопрос по поводу задачи «Поиск „дырок“ с помощью SQL».
Мы ничего не знаем о минимуме/максимуме значений в ней.
Но использовать min/max в подзапросе можно? Если да, мне видится такой вариант:
select tv1.VALUE + 1 VALUE from TEST_VALUES tv1 left join TEST_VALUES tv2 on tv2.VALUE = tv1.VALUE + 1 where tv2.VALUE is null and tv1.VALUE <> (select max(VALUE) from TEST_VALUES) order by 1
Хотя SQL у меня так себе.Loriowar Автор
16.10.2018 10:55На самом деле решений у этой задачки масса. Я её упоминал в своей статье "В дцатый раз про собеседования". Мне там десяток или полтора разных вариантов прислали. Было очень интересно обсуждать.
vassabi
16.10.2018 20:55Помните, что на месте пропусков нет NULL -значений.
хмммм
where tv2.VALUE is null
UPD: а, извините, не заметил что селект по tv1.
stu5002
16.10.2018 12:28Очень заинтриговала задача про решение циклов в списке со сложностью по памяти O(1). Ответ то будет?)
Loriowar Автор
16.10.2018 12:31Там никакого космоса, если подумать и взять подсказки, то решается за 5-25мин неспешного размышления. Один из знакомых-фронтендеров после 3мин раздумия воскликнул "этож jQuery-way!" и тут же выдал ответ. Так что наслаждайтесь. Ответ успеете найти.
JustDont
16.10.2018 12:58Ответ элементарно гуглится. Не хотите сразу ответ — подумайте о разнообразных способах итерации через список.
berez
16.10.2018 15:55Гуглите алгоритм «заяц и черепаха».
Хотя нет, это про поиск конкретного места зацикливания.
faiwer
16.10.2018 16:04Подсказка: представьте себе самый ужасный, самый не оптимальный, самый отвратительный алгоритм. Да, это он :)
спойлерещё подсказка: кол-во ваших переменных (потребление памяти) не должно зависеть от кол-ва звеньев в цепи. Т.е. по сути у вас может быть ровно 2, или 3, или 5 переменных. Задумайтесь, что вы в них можете указать. Производительность алгоритма при этом не важна, пусть хоть вечность ищет (при условии что найдёт).
tamakio
17.10.2018 07:24Там можно решить без дополнительной памяти, если можно модифицировать список.
faiwer
17.10.2018 07:46можно модифицировать список
без дополнительной памятиА как? Я так понимаю вы предлагаете хранить бит посещения в каждом пройденном звене. Да? Но ведь это никакие не O(1) по памяти.
tamakio
17.10.2018 20:03+1Можно создать свой собственный узел (node) и при прохождении всего списка заменять previous.next на myNode.
Итерироваться пока current.next != null.
Если цикл был — последним элементом будет вашfaiwer
17.10.2018 20:12+1Ух, и правда. Это алгоритм разрушительной мощи. И быстрый и памяти совсем не ест. Правда от списка остаются одни только рожки да ножки :)
a_e_tsvetkov
16.10.2018 13:03Циклы в односвязном списке
За конечное время решить невозможно.
Предположим что это не так и есть алгоритм который завершится за К шагов.
Он сможет просмотреть К первых элементов списка. Что означает что он не сможет обнаружить цикл расположенный на К+1 позиции.TheKnight
16.10.2018 13:24Эм. А как же алгоритм зайца и черепахи?
a_e_tsvetkov
16.10.2018 13:37Это алгоритм предполагает что цикл точно есть. В нашем случае
Мы знаем, что в нём, возможно, есть цикл.
это не так.a_e_tsvetkov
16.10.2018 13:43На самом деле задача то известная, меня поражает что ее редко кто может правильно сформулировать.
JustDont
16.10.2018 13:50Я вот до сих пор не понимаю, где вы видите проблему.
Цикл в однсвязном списке конечного размера ищется за конечное же время.
TheKnight
16.10.2018 13:52Вы про отсутствие упоминания о том, что список конечный? Упоминания про то, что он бесконечный я так же не вижу.
Loriowar Автор
16.10.2018 14:00Добавил уточнение про конечность списка, чтобы всем было удобнее и понятнее.
a_e_tsvetkov
17.10.2018 09:02Возможно вы правы и тут дело в моих предубеждениях. Я почему то всегда думаю об абстрактном в вакууме списке и не люблю
.null
werklop
16.10.2018 13:33-1По поводу последней задачи про шляпы. Как я понял, переговариваться нельзя, порядок цветов может быть произвольным, а значит вероятность выживания — 50%. Максимизировать число выживших, т.е. приблизиться к 50% и ниже можно только увеличением количества шляп. Но как всегда, играет дело случая, к сожалению, теорвер я подзабыл с института.
P.S. сделайте пож-та, вычиткуmk2
16.10.2018 14:05+1У нас есть дополнительная информация — цвета шляп впередистоящих, сказанные стоящими сзади цвета и угадали ли они. Этого хватает, чтобы умер <= 1 человек.
pocifis
16.10.2018 13:52Поиск дырок с помощью SQLSELECT n1.value + 1 FROM num n1 WHERE (SELECT * FROM num n2 WHERE n2.value > n1.value LIMIT 1) != n1.value + 1hatari90
16.10.2018 15:24Без order by в подзапросе порядок не гарантируется, в этом случае ваше решение не отработает.
Paran01d
16.10.2018 18:57molec
16.10.2018 13:55+1Извините, но очень плохой русский. Ладно опечатки даже в заголовках, но сами задачи даны так, чтобы остался максимум вопросов. Плохо сформулированная задача ведет к дорогому решению (как минимум, по времени, которое потребуется на приведение задачи к полной формализации). Это хорошо для устного интервью, чтобы понять, как претендент решает проблемы, но отвратительно для задач для самопроверки.
Loriowar Автор
16.10.2018 14:06Опечатки буду рад исправить, пишите в ЛС. А про письменное решение никто и не говорил. Все эти задачи как раз для устного или полу-письменного совместного решения. Это отличная и нескучная тема для разговора, дающая понимание навыков человека. И да, чтобы их молча дать и оставить человека наедине с задачей нужно много формализации и уточнений. Тут вы абсолютно правы.
vzaguskin
16.10.2018 14:23ШляпыЛюди с нечетным порядковым номером(с конца) называют цвет шляпы впереди стоящего, четным — то, что услышали. Тогда четные(50%) спасутся гарантированно, остальные — с вероятностью 50% при равном количестве черных и белых шляп и случайном их распределении при надевании. Итого 75% выживших.
IgorIlyin
16.10.2018 20:52Предположим последний человек говорит «белое», если цвет шляп двух, стоящих перед ним «игроков» совпадает. Вероятность его выживания — 50%, вероятность выживания следующих двух 100%. Тогда 2/3 людей спасаются гарантированно. Проблема, если всем выдадут чёрные шляпы… Похоже первый человек должен проанализировать распределение цветов и назвать цвет, которые будет означать, совпадение цветов двух стоящих перед ним людей, выбрав тот, что встречается чаще. Тогда наихудшим случаем уже будет равное распределение, в этом случае каждый третий будет гибнуть с вероятностю 50%. Процент выживших будет около 79.
molec
16.10.2018 15:55шляпыЧисто спортивно-тризовское решение.
Первый называет цвет шляпы впереди стоящего. Его шансы равны р — частотность названного цвета.
Второй называет свой цвет. Но. Если впередистоящему нужно назвать тот же цвет, то делает знак голосом — например, чуть растягивает, делает паузу, говорит громче, говорит в левую сторону и т.п. Соответственно, при смене цвета — наоборот.
В принципе, первый даже может тоже сыграть в угадайку, но так же смодулировать свой ответ голосом, чтобы предпоследний его понял.Loriowar Автор
16.10.2018 15:57Вы пытаетесь передать больше одного бита информации за раз. В жизни может и прокатит, но это абсолютно неспортивно и безынтересно.
molec
16.10.2018 16:50абсолютно неспортивно и безынтересно
не согласен. Для Вас неспортивно и Вам безынтересно. А вот в реальных задачах подобные трюки выручают регулярно.
шапки 2Тогда да.
Как рассуждал, решение ниже.
Первый считает число черных шапок впереди него.
Если черных нечетное число — он говорит черный, иначе — белый. Он может и умереть, но героем. Допустим — нечет и он сказал черный.
Каждый последующий запоминает выбор предыдущего. Если он видит перед собой тоже (не)четное число черных шапок, значит на нем белая, иначе — на нем дополнительная черная.
Итого, стратегия второго. Если первый сказал «черный», то если и он видит нечетное число шапок впереди, то на нем белая, иначе на нем черная.
Эта стратегия будет сохраняться, пока кто-нибудь не скажет «черный». Тогда стратегия инвертируется, видишь четное число — говоришь «черный». Инверсия будет каждый раз, когда кто-то говорит «черный».
Если формализовать, то правило такое. Первый говорит «черный», если видит впереди нечерное число черных шапок. Остальные говорят «черный», если [число черных увиденных шапок впереди]-[число черных шапок озвученных позади] нечетное.
paranoya_prod
16.10.2018 17:41Зачем говорить и растягивать слова, делать паузы? Если у человека шапка черная, то стоящий за ним берёт его за правую руку. Если белая, то за левую и так до последнего человека, которому никто не сможет сообщить какого цвета у него шапка, поэтому он погибает первым и последним.
Если можно повернуть голову, тогда предпоследний сообщает последнему цвет его шапки и все живы-здоровы.
Если есть отражающая поверхность типа зеркала или ложки, тогда её наклеивают предпоследнему на затылок и последний видит цвет свой шапки. Так как в поставленной задачи многое не ограничено, то вариантов узнать цвет своей шапки тоже много. Поэтому есть два варианта: никто не умрёт, умрёт один последний.
Но если ужесточить условия до, того, что нельзя говорить, дотрагиваться, вертеть головой, рисовать носком ботинка на земле знаки, то есть коммуникация на абсолютном нуле, то тут ни XORы, ни чётность, ни один бит не поможет.molec
16.10.2018 18:05Ваши расстрельные явно общительнее и запасливее моих :) С касанием с нужной стороны идея красивая, но если почти нельзя вертеться и все стоят достаточно далеко друг от друга, то только вариант по типу моего из второго спойлера. Хотя расписал как попало.
paranoya_prod
17.10.2018 10:20Второй Ваш вариант, при условии, что впередистоящий не закрывает своей головой других :) я не совсем понял, объясните на примере:
Черный — 1
Белый — 0
Очередь на жизнь: 01 11 00 01molec
17.10.2018 13:101 видит впереди 4 черных шапки. Четное. Говорит «белый» и случайно выживает.
Второй слышал, что 1 «сказал черный 0 раз». Т.е. он знает, что 1 увидел четное число черных шапок. Считает черные шапки сам — ага, 3, т.е. нечет. Он понимает, что лишняя черная шапка на нем, говорит «черный».
Третий слышал 1 раз, что говорили «черный». Значит перед предыдущим было нечетное число черных шапок. Пересчитывает — 2, четное. Значит, лишняя шапка на нет. Говорит «черный».
Четвертый слышал четное число раз слово «черный». Значит перед предыдущим было четное число черных шапок. Он видит только одну, Значит лишняя черная на нем. Говорит черный.
Пятый и шестой слышали «черный» нечетное число раз. Пересчитывают черные шапки — 1. Говорят белый.
Последний слышал «черный нечетное число раз, значит на нем черная шапка.
Итого, все выжили.berez
17.10.2018 15:45На практике люди не смогут увидеть всех стоящих впереди — даже если рост у всех одинаковый, ближайший впередистоящий будет закрывать своей башкой весь обзор. Опять же, никто не обещал, что все заключенные обладают орлиным зрением.
С учетом того, что люди переминаются на ногах, шапки две-три впереди еще можно разглядеть. Но посчитать количество черных шапок в очереди из, скажем, двух сотен человек — абсолютно нереально.
И да, вы не учитываете, что люди бывают тупые, шибко умные и просто приезжие из солнечных стран — они могут тупо не понять, что именно им надо делать. Могут не услышать, что там кто сказал. Короче, в реальности нужен какой-то очень простой способ, иначе расстреляют ровно половину. :)paranoya_prod
17.10.2018 17:30Нет, расстрелять могут любое кол-во, тут как повезёт (вариант «орёл или решка»).
:)
dmmax
16.10.2018 20:51Поиск 'дырок' с помощью SQLSELECT n2.position - 1 FROM somenumbers n1 LEFT JOIN somenumbers n2 ON n1.position + 2 = n2.position WHERE n2.position IS NOT NULL
Т.к. в условие сказано, что длина дырки не превышает одного значения, то получается необходимо связывать список не со следующим значением, а через одно.hatari90
16.10.2018 23:05Не сработает, если будут хотя бы 3 значения подряд без пропусков.
dmmax
17.10.2018 05:14Да, после написание поста понял что не хватает условий. Вот переделанный вариант:
Дубль два: Поиск 'дырок' с помощью SQLSELECT n1.position + 1 FROM somenumbers n1 LEFT JOIN somenumbers n2 ON n1.position + 1 = n2.position LEFT JOIN somenumbers n3 ON n1.position + 2 = n3.position WHERE n2.position IS NULL AND n3.position IS NOT NULLuaggster
18.10.2018 16:27В порядке легкого троллинга собеседователей. :-)
На T-SQL:
if OBJECT_ID ('tempdb..#t') is not null drop table #t Create table #t (N int) insert into #t (N) Values (1), (2), (4), (6), (100) ;With s as (Select 1 N Union all Select N+1 from s Where N < any (Select N from #t)) Select * from s except Select * from #t Option (maxrecursion 0)
Можно и что-то более идиотское придумать.
sha4
16.10.2018 23:13Шляпы, XORЕсли группа совсем дауны, я бы им предложил бинарное сложение. Если поумнее, то тернарное. А если есть возможность накидать приложуху на смартфоне (и у каждого он есть), то достаточно всего одного камикадзе в самом начале ряда, чтобы расшифровать эту последовательность. Да, и предполагается, что можно видеть вперёд все шляпы, а не только ближайшего соседа. Выстрел если и будет, то только один (в варианте с приложением).
// чёрная — 1, белая — 0sha4
17.10.2018 04:03Шляпы, XOR, v.2Ладно, мы обойдёмся без приложений и смартфонов.
Последний участник-камикадзе делает XOR для всего ряда (считает [true] чёрные шляпы и если их количество нечётно — говорит [true] чёрная. С вероятностью 50% названный цвет совпадёт с его шляпой, и он выживет).
Предпоследний участник считает все [true] чёрные шляпы перед собой, кроме своей, и если их чётность не изменилась — делает вывод, что его шляпа не повлияла на количество чёрных шляп, следовательно она [false] белая. Если же чётность чёрных шляп изменилась — то именно его шляпа внесла корректив, значит она [true] чёрная.
Пред-предпоследний и далее участники: участник знает (поскольку слышал всю информацию сзади) изначальную чётность чёрных шляп, и он знает сколько чёрных шляп уже было названо (выбыло). На основе этого участник вычисляет текущую чётность чёрных шляп. Затем он считает чёрные шляпы перед собой, если чётность видимых чёрных шляп совпадает — его шляпа [false] белая, если нет — то [true] чёрная.
Итого — камикадзе в начале ряда достаточно передать своим друзьям всего один бит информации — чётность чёрных шляп. И все его друзья будут спасены.paranoya_prod
17.10.2018 17:35+1Это тот случай, когда понимаешь, что не нужно было отлынивать от физкультуры, чтобы успеть сбежать. Или от ОБЖ, чтобы понять, что эта поездка на остров попахивает неприятностями.
:)
SiliconValleyHobo
17.10.2018 03:19Какие-то детские задачки, честно говоря. Кого они смогут отсеять? Что именно показать?
Если кандидат их решает — он считается «годным»? А если не решает, то бракуется?
Мне казалось, что общепринятая практика — это давать задачи и вопросы, на которые иначально в стрессовой ситуации собеседования смогут дать идеально правильный ответ единицы людей во всем мире, если вообще хоть кто-либо. На таких задачах кандидат итеративно шаг за шагом оптимизирует наивное решение при помощи своей головы или наводящих вопросов. И вопрос, скорее не в том, чтобы человек решил. А том, чтобы проследить за его мыслительным процессом при изменении сложности задачи от детской до уровня финалов ACM/ICPC.
Я понимаю, что инженеры и программисты нужны разные. Какие-то — делать сайты-визитки. Какие-то — бизнес-логику на 1С. Какие-то — высоконагруженные веб-сервисы. И на какие-то работы будет достаточно и таких задачек. Но блин, на них все равно же мыслительный процесс толком не проследить.
Вообще интересные задачки, как водится, встречал в обсуждениях гугловых интервью. Они просто эталонны.
Афайк у Яндекса тоже ребята любят дичь поспрашивать. После него можно кучу крутых методов понабрать.Loriowar Автор
17.10.2018 09:50Как говорил товарищ Королёв: "критикуешь — предлагай!" Посему, коли у вас есть необычный опыт собеседований и/или своя подборка задач — пожалуйста, поделитесь. Лично мне будет интересно и в будущем пригодится.
Касаемо "общей практики и нерешаемых задач": там в самом начале статьи написано "Все задачки на логику и/или о программировании. Никакого психологического подтекста и круглых люков." Так что "что на коробке, то и в коробке". А на гугло-яндексовые задачки в комментарии выше была ссылка. Вот там позабористей трава.
a_e_tsvetkov
17.10.2018 09:10По моему опыту такие задачи определяют лишь тот факт что собеседуемый уже с ними встречался (лично меня спрашивали почти все из них).
Ну и конечно честность. Кто-то может сказать что уже знает ответ, а кто-то просто его скажет сделав вид что решил на месте.
Ermit
17.10.2018 17:32Лотереи, экзамены, викторины… удобно для HR, неудобно для соискателя, разорительно для владельца. Небольшая тестовая задача, очень хорошо, если находится в проблемной области компании. Сразу будет видно, на что в реальной работе способен соискатель.
Loriowar Автор
17.10.2018 18:33Из "проблемной области компании" у меня получалось поговорить только про архитектуру. Остальные "живые" задачи либо изоморфны багам и там особо нечего обсуждать, либо тянут за собой мешок бизнес-логики и особенностей системы; то есть, пока расскажешь все вводные начнёт смеркаться и кандидат уснёт. Вы как такие проблемы обходите при подготовке задач?
Ermit
17.10.2018 18:37Ни как, эти проблемы как раз и являются показателем адекватности соискателя. Если человек умеет сделать декомпозию задачи, набросать вариант (пусть плохой) бизнес-логики, выбрать небольшой ключевой модуль (или даже функцию) и определить сигнатуру или сделать кусок логики на псевдокоде — это показатель уровня.
Но я соглашусь с тем, что в больших компаниях вообще идет борьба с любой индивидуальностью. И они правы, для них важнее стандарты, они могут позволить себе неэффективность «в малом»…Loriowar Автор
17.10.2018 18:50Ваш вариант хорош для senior-разработчиков. У них опыта вагон с тележкой и остаётся проверить не врёт ли он и адекватен ли. А как же ребята ниже senior? Как их собесить? Ведь им большую часть означенного ещё предстоит постичь.
Ermit
17.10.2018 18:57Согласен с Вами, у сеньоров имеет смысл смотреть опыт, у джуниоров — эрудицию и интеллект. :-)
Gibboustooth
18.10.2018 09:54+2Про шляпы задача неплохая, но мне больше нравится задача про заключенных и лампочку. Хорошо подходит для программистов)
Формулировка задачиВ тюрьме в одиночных камерах содержится 10 заключенных. В один день начальник тюрьмы собирает их всех вместе и говорит, что хочет с ними сыграть в игру. Если они согласятся, их будут по одному в случайном порядке (в том числе несколько раз одного и того же человека) тайно от остальных водить в специальную комнату. В комнате есть лампочка и выключатель, так что заключенный может включить лампочку, выключить ее или ничего не делать. В любой момент любой из них может сказать: «я уверен, что все заключенные посетили эту комнату хотя бы один раз». Если он прав — всех заключенных отпустят. Если нет — все будут немедленно казнены. Перед началом игры заключенные могут обсудить стратегию поведения. Вопрос: какая стратегия позволяет заключенным гарантированно выиграть в эту игру?hatari90
18.10.2018 12:33Задача имеет решение без условия «1 посещение в день»?
мысльДопустим, для стратегии со счетчиком, первый посетитель не сможет узнать, что он первый. Либо должно быть известно начальное положение выключателя.Gibboustooth
18.10.2018 13:29Да, должно быть условие, что изначально свет в комнате выключен.
molec
18.10.2018 14:43Если кто-то зашел в комнату, сможет ли он об этом сказать остальным? Могут ли они хотя бы перестукиваться? Есть ли возможность делать отметки на стенах/полу/потолке в комнате? Или этого не нужно для решения?
uaggster
18.10.2018 16:38Кстати, я не понял, в чем подвох первой задачи?
Старое доброе сравнение id уже не работает (id левой записи > id правой) в join уже не работает?
Что там имелось ввиду то?
Loriowar Автор
19.10.2018 09:58"Очевидное одному — совсем не очевидно другому". Для вас здесь нет проблемы, а некоторые минут на 5 задумываются.
dskozin
Полагаю что задачи на собеседовании должны даваться, но только на дом. Не у всех (имею ввиду конечно же себя:-) ) прокачан скилл собеседований. Дома я могу весьма сложные вещи взять в работу, сидя перед интервьювером забываю даже базовые. И этот скилл не прокачивается…
Loriowar Автор
Тут тонкий момент: вы дома готовы посидеть и спокойно решить, ибо понимаете свои особенности, а некоторые совсем не хотят своё личное время тратить, даже если это их шанс. И либо надо оговаривать оплату успешных задачек, на что редкая компания согласится. Либо приходится придумывать интересные задачки на 5 строк кода, до которых с наскока не догадаешься и подумать надобно, но реально сделать а 10мин собеседования.
А из личного: давал задачки "на дом" тем, кто почти не впечатлял при устном общении. Прямо говорил: "по общению ты не очень, но, кажется, сильно волновался, поэтому давай дам тебе задачку на 4-8 часов, если сделаешь сам и расскажешь как делал — берём". Суммарно 10-15 соискателей на такое предложение попали. Все били кулаком в грудь, дескать "да, сделаем!" И пропадали в 99% случаев. Только один за всё время сделал.
dskozin
Я домашние задачки иногда просто ради интереса делаю. 4-8 часов это норм, но можно и меньше. Например интересные задачки при найме в csssr.ru. Они опубликованы в вакансии и без решения ты даже на собеседование не попадешь. А решить их задачи можно в пределах часа…
И мотивацию в конце концов показывает…
Loriowar Автор
В таком случае, я недавно наткнулся на старый баян про 123 задачки с IT-собеседований. Он меня как-то стороной обошёл и поэтому я залип там на пару часов. Может и вы там ещё не были :)
TheDaemon
Я часто даю не прошедшим собеседование задачки на дом с codingame.com. В сумме давал раз 30-50, взял так человек 5-7. Так что это норм работает :)