Как стать автором
Обновить

Комментарии 78

Полагаю что задачи на собеседовании должны даваться, но только на дом. Не у всех (имею ввиду конечно же себя:-) ) прокачан скилл собеседований. Дома я могу весьма сложные вещи взять в работу, сидя перед интервьювером забываю даже базовые. И этот скилл не прокачивается…

Тут тонкий момент: вы дома готовы посидеть и спокойно решить, ибо понимаете свои особенности, а некоторые совсем не хотят своё личное время тратить, даже если это их шанс. И либо надо оговаривать оплату успешных задачек, на что редкая компания согласится. Либо приходится придумывать интересные задачки на 5 строк кода, до которых с наскока не догадаешься и подумать надобно, но реально сделать а 10мин собеседования.


А из личного: давал задачки "на дом" тем, кто почти не впечатлял при устном общении. Прямо говорил: "по общению ты не очень, но, кажется, сильно волновался, поэтому давай дам тебе задачку на 4-8 часов, если сделаешь сам и расскажешь как делал — берём". Суммарно 10-15 соискателей на такое предложение попали. Все били кулаком в грудь, дескать "да, сделаем!" И пропадали в 99% случаев. Только один за всё время сделал.

Я домашние задачки иногда просто ради интереса делаю. 4-8 часов это норм, но можно и меньше. Например интересные задачки при найме в csssr.ru. Они опубликованы в вакансии и без решения ты даже на собеседование не попадешь. А решить их задачи можно в пределах часа…

И мотивацию в конце концов показывает…

В таком случае, я недавно наткнулся на старый баян про 123 задачки с IT-собеседований. Он меня как-то стороной обошёл и поэтому я залип там на пару часов. Может и вы там ещё не были :)

Я часто даю не прошедшим собеседование задачки на дом с codingame.com. В сумме давал раз 30-50, взял так человек 5-7. Так что это норм работает :)
В варианте с шапками погибнет только один — последний, при условии, что люди договорились как передать инфу о цвете шапки и количество шапок обоих цветов им неизвестно.
С шапками очень популярная, легкая и из разряда не рекомендованных к собеседованиям. Но такого рода задачи интересно просто решать в свободное от работы время.

Вариант этой задачи от Михаила на порядок интереснее, где количество заключенных алеф-0 и нужна бесконечная память: habr.com/post/54824
Вопрос по поводу задачи «Поиск „дырок“ с помощью 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 у меня так себе.

На самом деле решений у этой задачки масса. Я её упоминал в своей статье "В дцатый раз про собеседования". Мне там десяток или полтора разных вариантов прислали. Было очень интересно обсуждать.

Помните, что на месте пропусков нет NULL -значений.

хмммм
where tv2.VALUE is null


UPD: а, извините, не заметил что селект по tv1.
Можно короче: select nn+1 from #t where nn+1 not in (select nn from #t)
Очень заинтриговала задача про решение циклов в списке со сложностью по памяти O(1). Ответ то будет?)

Там никакого космоса, если подумать и взять подсказки, то решается за 5-25мин неспешного размышления. Один из знакомых-фронтендеров после 3мин раздумия воскликнул "этож jQuery-way!" и тут же выдал ответ. Так что наслаждайтесь. Ответ успеете найти.

Ответ элементарно гуглится. Не хотите сразу ответ — подумайте о разнообразных способах итерации через список.
Гуглите алгоритм «заяц и черепаха».
Хотя нет, это про поиск конкретного места зацикливания.

Подсказка: представьте себе самый ужасный, самый не оптимальный, самый отвратительный алгоритм. Да, это он :)


спойлер

ещё подсказка: кол-во ваших переменных (потребление памяти) не должно зависеть от кол-ва звеньев в цепи. Т.е. по сути у вас может быть ровно 2, или 3, или 5 переменных. Задумайтесь, что вы в них можете указать. Производительность алгоритма при этом не важна, пусть хоть вечность ищет (при условии что найдёт).

Там можно решить без дополнительной памяти, если можно модифицировать список.

Это если надо O(1) по памяти и О(n) по

можно модифицировать список
без дополнительной памяти

А как? Я так понимаю вы предлагаете хранить бит посещения в каждом пройденном звене. Да? Но ведь это никакие не O(1) по памяти.

Можно создать свой собственный узел (node) и при прохождении всего списка заменять previous.next на myNode.
Итерироваться пока current.next != null.
Если цикл был — последним элементом будет ваш

Ух, и правда. Это алгоритм разрушительной мощи. И быстрый и памяти совсем не ест. Правда от списка остаются одни только рожки да ножки :)

Циклы в односвязном списке

За конечное время решить невозможно.

Предположим что это не так и есть алгоритм который завершится за К шагов.
Он сможет просмотреть К первых элементов списка. Что означает что он не сможет обнаружить цикл расположенный на К+1 позиции.
Эм. А как же алгоритм зайца и черепахи?
Это алгоритм предполагает что цикл точно есть. В нашем случае
Мы знаем, что в нём, возможно, есть цикл.
это не так.
На самом деле задача то известная, меня поражает что ее редко кто может правильно сформулировать.
Я вот до сих пор не понимаю, где вы видите проблему.
Цикл в однсвязном списке конечного размера ищется за конечное же время.
Вы про отсутствие упоминания о том, что список конечный? Упоминания про то, что он бесконечный я так же не вижу.

Добавил уточнение про конечность списка, чтобы всем было удобнее и понятнее.

Возможно вы правы и тут дело в моих предубеждениях. Я почему то всегда думаю об абстрактном в вакууме списке и не люблю
null
.
По поводу последней задачи про шляпы. Как я понял, переговариваться нельзя, порядок цветов может быть произвольным, а значит вероятность выживания — 50%. Максимизировать число выживших, т.е. приблизиться к 50% и ниже можно только увеличением количества шляп. Но как всегда, играет дело случая, к сожалению, теорвер я подзабыл с института.

P.S. сделайте пож-та, вычитку
У нас есть дополнительная информация — цвета шляп впередистоящих, сказанные стоящими сзади цвета и угадали ли они. Этого хватает, чтобы умер <= 1 человек.
Поиск дырок с помощью SQL
SELECT n1.value + 1 FROM num n1 WHERE (SELECT * FROM num n2 WHERE n2.value > n1.value LIMIT 1) != n1.value + 1


Правильно?
Без order by в подзапросе порядок не гарантируется, в этом случае ваше решение не отработает.
Будет возвращать лишнее значение в виде максимального + 1.

В подсказке к заданию как раз про это и говорится.

Пардон, точно.
Извините, но очень плохой русский. Ладно опечатки даже в заголовках, но сами задачи даны так, чтобы остался максимум вопросов. Плохо сформулированная задача ведет к дорогому решению (как минимум, по времени, которое потребуется на приведение задачи к полной формализации). Это хорошо для устного интервью, чтобы понять, как претендент решает проблемы, но отвратительно для задач для самопроверки.

Опечатки буду рад исправить, пишите в ЛС. А про письменное решение никто и не говорил. Все эти задачи как раз для устного или полу-письменного совместного решения. Это отличная и нескучная тема для разговора, дающая понимание навыков человека. И да, чтобы их молча дать и оставить человека наедине с задачей нужно много формализации и уточнений. Тут вы абсолютно правы.

Шляпы
Люди с нечетным порядковым номером(с конца) называют цвет шляпы впереди стоящего, четным — то, что услышали. Тогда четные(50%) спасутся гарантированно, остальные — с вероятностью 50% при равном количестве черных и белых шляп и случайном их распределении при надевании. Итого 75% выживших.
Предположим последний человек говорит «белое», если цвет шляп двух, стоящих перед ним «игроков» совпадает. Вероятность его выживания — 50%, вероятность выживания следующих двух 100%. Тогда 2/3 людей спасаются гарантированно. Проблема, если всем выдадут чёрные шляпы… Похоже первый человек должен проанализировать распределение цветов и назвать цвет, которые будет означать, совпадение цветов двух стоящих перед ним людей, выбрав тот, что встречается чаще. Тогда наихудшим случаем уже будет равное распределение, в этом случае каждый третий будет гибнуть с вероятностю 50%. Процент выживших будет около 79.
шляпы
Чисто спортивно-тризовское решение.
Первый называет цвет шляпы впереди стоящего. Его шансы равны р — частотность названного цвета.
Второй называет свой цвет. Но. Если впередистоящему нужно назвать тот же цвет, то делает знак голосом — например, чуть растягивает, делает паузу, говорит громче, говорит в левую сторону и т.п. Соответственно, при смене цвета — наоборот.
В принципе, первый даже может тоже сыграть в угадайку, но так же смодулировать свой ответ голосом, чтобы предпоследний его понял.

Вы пытаетесь передать больше одного бита информации за раз. В жизни может и прокатит, но это абсолютно неспортивно и безынтересно.

абсолютно неспортивно и безынтересно

не согласен. Для Вас неспортивно и Вам безынтересно. А вот в реальных задачах подобные трюки выручают регулярно.
шапки 2
Тогда да.
Как рассуждал, решение ниже.
Первый считает число черных шапок впереди него.
Если черных нечетное число — он говорит черный, иначе — белый. Он может и умереть, но героем. Допустим — нечет и он сказал черный.
Каждый последующий запоминает выбор предыдущего. Если он видит перед собой тоже (не)четное число черных шапок, значит на нем белая, иначе — на нем дополнительная черная.
Итого, стратегия второго. Если первый сказал «черный», то если и он видит нечетное число шапок впереди, то на нем белая, иначе на нем черная.
Эта стратегия будет сохраняться, пока кто-нибудь не скажет «черный». Тогда стратегия инвертируется, видишь четное число — говоришь «черный». Инверсия будет каждый раз, когда кто-то говорит «черный».

Если формализовать, то правило такое. Первый говорит «черный», если видит впереди нечерное число черных шапок. Остальные говорят «черный», если [число черных увиденных шапок впереди]-[число черных шапок озвученных позади] нечетное.

Зачем говорить и растягивать слова, делать паузы? Если у человека шапка черная, то стоящий за ним берёт его за правую руку. Если белая, то за левую и так до последнего человека, которому никто не сможет сообщить какого цвета у него шапка, поэтому он погибает первым и последним.
Если можно повернуть голову, тогда предпоследний сообщает последнему цвет его шапки и все живы-здоровы.
Если есть отражающая поверхность типа зеркала или ложки, тогда её наклеивают предпоследнему на затылок и последний видит цвет свой шапки. Так как в поставленной задачи многое не ограничено, то вариантов узнать цвет своей шапки тоже много. Поэтому есть два варианта: никто не умрёт, умрёт один последний.
Но если ужесточить условия до, того, что нельзя говорить, дотрагиваться, вертеть головой, рисовать носком ботинка на земле знаки, то есть коммуникация на абсолютном нуле, то тут ни XORы, ни чётность, ни один бит не поможет.
Ваши расстрельные явно общительнее и запасливее моих :) С касанием с нужной стороны идея красивая, но если почти нельзя вертеться и все стоят достаточно далеко друг от друга, то только вариант по типу моего из второго спойлера. Хотя расписал как попало.
Второй Ваш вариант, при условии, что впередистоящий не закрывает своей головой других :) я не совсем понял, объясните на примере:

Черный — 1
Белый — 0
Очередь на жизнь: 01 11 00 01
1 видит впереди 4 черных шапки. Четное. Говорит «белый» и случайно выживает.
Второй слышал, что 1 «сказал черный 0 раз». Т.е. он знает, что 1 увидел четное число черных шапок. Считает черные шапки сам — ага, 3, т.е. нечет. Он понимает, что лишняя черная шапка на нем, говорит «черный».
Третий слышал 1 раз, что говорили «черный». Значит перед предыдущим было нечетное число черных шапок. Пересчитывает — 2, четное. Значит, лишняя шапка на нет. Говорит «черный».
Четвертый слышал четное число раз слово «черный». Значит перед предыдущим было четное число черных шапок. Он видит только одну, Значит лишняя черная на нем. Говорит черный.
Пятый и шестой слышали «черный» нечетное число раз. Пересчитывают черные шапки — 1. Говорят белый.
Последний слышал «черный нечетное число раз, значит на нем черная шапка.

Итого, все выжили.
На практике люди не смогут увидеть всех стоящих впереди — даже если рост у всех одинаковый, ближайший впередистоящий будет закрывать своей башкой весь обзор. Опять же, никто не обещал, что все заключенные обладают орлиным зрением.

С учетом того, что люди переминаются на ногах, шапки две-три впереди еще можно разглядеть. Но посчитать количество черных шапок в очереди из, скажем, двух сотен человек — абсолютно нереально.

И да, вы не учитываете, что люди бывают тупые, шибко умные и просто приезжие из солнечных стран — они могут тупо не понять, что именно им надо делать. Могут не услышать, что там кто сказал. Короче, в реальности нужен какой-то очень простой способ, иначе расстреляют ровно половину. :)
Нет, расстрелять могут любое кол-во, тут как повезёт (вариант «орёл или решка»).
:)
Поиск 'дырок' с помощью SQL
SELECT n2.position - 1
FROM somenumbers n1
  LEFT JOIN somenumbers n2 ON n1.position + 2 = n2.position
WHERE n2.position IS NOT NULL

Т.к. в условие сказано, что длина дырки не превышает одного значения, то получается необходимо связывать список не со следующим значением, а через одно.

Раньше только читал подобные посты, в первый раз решил попробовать, получилось занимательно =)
Не сработает, если будут хотя бы 3 значения подряд без пропусков.
Да, после написание поста понял что не хватает условий. Вот переделанный вариант:
Дубль два: Поиск 'дырок' с помощью SQL
SELECT 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 NULL

В порядке легкого троллинга собеседователей. :-)
На 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)


Можно и что-то более идиотское придумать.
Под условие конкретной задачи не подходит ;-)
Почему не подходит? Дырка в 1 запись — частный случай дырки в N записей :-)
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Это тот случай, когда понимаешь, что не нужно было отлынивать от физкультуры, чтобы успеть сбежать. Или от ОБЖ, чтобы понять, что эта поездка на остров попахивает неприятностями.
:)
Какие-то детские задачки, честно говоря. Кого они смогут отсеять? Что именно показать?
Если кандидат их решает — он считается «годным»? А если не решает, то бракуется?

Мне казалось, что общепринятая практика — это давать задачи и вопросы, на которые иначально в стрессовой ситуации собеседования смогут дать идеально правильный ответ единицы людей во всем мире, если вообще хоть кто-либо. На таких задачах кандидат итеративно шаг за шагом оптимизирует наивное решение при помощи своей головы или наводящих вопросов. И вопрос, скорее не в том, чтобы человек решил. А том, чтобы проследить за его мыслительным процессом при изменении сложности задачи от детской до уровня финалов ACM/ICPC.

Я понимаю, что инженеры и программисты нужны разные. Какие-то — делать сайты-визитки. Какие-то — бизнес-логику на 1С. Какие-то — высоконагруженные веб-сервисы. И на какие-то работы будет достаточно и таких задачек. Но блин, на них все равно же мыслительный процесс толком не проследить.

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

Как говорил товарищ Королёв: "критикуешь — предлагай!" Посему, коли у вас есть необычный опыт собеседований и/или своя подборка задач — пожалуйста, поделитесь. Лично мне будет интересно и в будущем пригодится.


Касаемо "общей практики и нерешаемых задач": там в самом начале статьи написано "Все задачки на логику и/или о программировании. Никакого психологического подтекста и круглых люков." Так что "что на коробке, то и в коробке". А на гугло-яндексовые задачки в комментарии выше была ссылка. Вот там позабористей трава.

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

Ну и конечно честность. Кто-то может сказать что уже знает ответ, а кто-то просто его скажет сделав вид что решил на месте.
Лотереи, экзамены, викторины… удобно для HR, неудобно для соискателя, разорительно для владельца. Небольшая тестовая задача, очень хорошо, если находится в проблемной области компании. Сразу будет видно, на что в реальной работе способен соискатель.

Из "проблемной области компании" у меня получалось поговорить только про архитектуру. Остальные "живые" задачи либо изоморфны багам и там особо нечего обсуждать, либо тянут за собой мешок бизнес-логики и особенностей системы; то есть, пока расскажешь все вводные начнёт смеркаться и кандидат уснёт. Вы как такие проблемы обходите при подготовке задач?

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

Но я соглашусь с тем, что в больших компаниях вообще идет борьба с любой индивидуальностью. И они правы, для них важнее стандарты, они могут позволить себе неэффективность «в малом»…

Ваш вариант хорош для senior-разработчиков. У них опыта вагон с тележкой и остаётся проверить не врёт ли он и адекватен ли. А как же ребята ниже senior? Как их собесить? Ведь им большую часть означенного ещё предстоит постичь.

Согласен с Вами, у сеньоров имеет смысл смотреть опыт, у джуниоров — эрудицию и интеллект. :-)
Про шляпы задача неплохая, но мне больше нравится задача про заключенных и лампочку. Хорошо подходит для программистов)

Формулировка задачи
В тюрьме в одиночных камерах содержится 10 заключенных. В один день начальник тюрьмы собирает их всех вместе и говорит, что хочет с ними сыграть в игру. Если они согласятся, их будут по одному в случайном порядке (в том числе несколько раз одного и того же человека) тайно от остальных водить в специальную комнату. В комнате есть лампочка и выключатель, так что заключенный может включить лампочку, выключить ее или ничего не делать. В любой момент любой из них может сказать: «я уверен, что все заключенные посетили эту комнату хотя бы один раз». Если он прав — всех заключенных отпустят. Если нет — все будут немедленно казнены. Перед началом игры заключенные могут обсудить стратегию поведения. Вопрос: какая стратегия позволяет заключенным гарантированно выиграть в эту игру?
Задача имеет решение без условия «1 посещение в день»?
мысль
Допустим, для стратегии со счетчиком, первый посетитель не сможет узнать, что он первый. Либо должно быть известно начальное положение выключателя.
Если кто-то зашел в комнату, сможет ли он об этом сказать остальным? Могут ли они хотя бы перестукиваться? Есть ли возможность делать отметки на стенах/полу/потолке в комнате? Или этого не нужно для решения?
Этого всего не нужно для решения.
Кстати, я не понял, в чем подвох первой задачи?
Старое доброе сравнение id уже не работает (id левой записи > id правой) в join уже не работает?
Что там имелось ввиду то?

"Очевидное одному — совсем не очевидно другому". Для вас здесь нет проблемы, а некоторые минут на 5 задумываются.

А как на счет искать дырки так:

  select min([idRow]) [start],MAX(idrow) [end],COUNT(grp)-1 [length] from (
  select  
      [idRow] -ROW_NUMBER()  OVER (ORDER BY [idRow] )  AS grp,
      [idRow]
  FROM table
  )  x
  group by grp
  order by 1

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

Можете диалект уточнить? Это MSSQL? А то у меня сходу не распарсилось в голове.

да, чистый MS SQL(+оконные функции). Вся соль в том, что отнимая роу нумбер у подряд идущих по IDROW записей, должно быть одинаковое значение :)
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории