Комментарии 78
Тут тонкий момент: вы дома готовы посидеть и спокойно решить, ибо понимаете свои особенности, а некоторые совсем не хотят своё личное время тратить, даже если это их шанс. И либо надо оговаривать оплату успешных задачек, на что редкая компания согласится. Либо приходится придумывать интересные задачки на 5 строк кода, до которых с наскока не догадаешься и подумать надобно, но реально сделать а 10мин собеседования.
А из личного: давал задачки "на дом" тем, кто почти не впечатлял при устном общении. Прямо говорил: "по общению ты не очень, но, кажется, сильно волновался, поэтому давай дам тебе задачку на 4-8 часов, если сделаешь сам и расскажешь как делал — берём". Суммарно 10-15 соискателей на такое предложение попали. Все били кулаком в грудь, дескать "да, сделаем!" И пропадали в 99% случаев. Только один за всё время сделал.
И мотивацию в конце концов показывает…
В таком случае, я недавно наткнулся на старый баян про 123 задачки с IT-собеседований. Он меня как-то стороной обошёл и поэтому я залип там на пару часов. Может и вы там ещё не были :)
Вариант этой задачи от Михаила на порядок интереснее, где количество заключенных алеф-0 и нужна бесконечная память: habr.com/post/54824
Мы ничего не знаем о минимуме/максимуме значений в ней.
Но использовать 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.
Там никакого космоса, если подумать и взять подсказки, то решается за 5-25мин неспешного размышления. Один из знакомых-фронтендеров после 3мин раздумия воскликнул "этож jQuery-way!" и тут же выдал ответ. Так что наслаждайтесь. Ответ успеете найти.
Хотя нет, это про поиск конкретного места зацикливания.
Подсказка: представьте себе самый ужасный, самый не оптимальный, самый отвратительный алгоритм. Да, это он :)
ещё подсказка: кол-во ваших переменных (потребление памяти) не должно зависеть от кол-ва звеньев в цепи. Т.е. по сути у вас может быть ровно 2, или 3, или 5 переменных. Задумайтесь, что вы в них можете указать. Производительность алгоритма при этом не важна, пусть хоть вечность ищет (при условии что найдёт).
Там можно решить без дополнительной памяти, если можно модифицировать список.
Это если надо O(1) по памяти и О(n) по
можно модифицировать список
без дополнительной памяти
А как? Я так понимаю вы предлагаете хранить бит посещения в каждом пройденном звене. Да? Но ведь это никакие не O(1) по памяти.
Можно создать свой собственный узел (node) и при прохождении всего списка заменять previous.next на myNode.
Итерироваться пока current.next != null.
Если цикл был — последним элементом будет ваш
Циклы в односвязном списке
За конечное время решить невозможно.
Предположим что это не так и есть алгоритм который завершится за К шагов.
Он сможет просмотреть К первых элементов списка. Что означает что он не сможет обнаружить цикл расположенный на К+1 позиции.
Мы знаем, что в нём, возможно, есть цикл.это не так.
Цикл в однсвязном списке конечного размера ищется за конечное же время.
P.S. сделайте пож-та, вычитку
SELECT n1.value + 1 FROM num n1 WHERE (SELECT * FROM num n2 WHERE n2.value > n1.value LIMIT 1) != n1.value + 1
Правильно?
Опечатки буду рад исправить, пишите в ЛС. А про письменное решение никто и не говорил. Все эти задачи как раз для устного или полу-письменного совместного решения. Это отличная и нескучная тема для разговора, дающая понимание навыков человека. И да, чтобы их молча дать и оставить человека наедине с задачей нужно много формализации и уточнений. Тут вы абсолютно правы.
Первый называет цвет шляпы впереди стоящего. Его шансы равны р — частотность названного цвета.
Второй называет свой цвет. Но. Если впередистоящему нужно назвать тот же цвет, то делает знак голосом — например, чуть растягивает, делает паузу, говорит громче, говорит в левую сторону и т.п. Соответственно, при смене цвета — наоборот.
В принципе, первый даже может тоже сыграть в угадайку, но так же смодулировать свой ответ голосом, чтобы предпоследний его понял.
Вы пытаетесь передать больше одного бита информации за раз. В жизни может и прокатит, но это абсолютно неспортивно и безынтересно.
абсолютно неспортивно и безынтересно
не согласен. Для Вас неспортивно и Вам безынтересно. А вот в реальных задачах подобные трюки выручают регулярно.
Как рассуждал, решение ниже.
Первый считает число черных шапок впереди него.
Если черных нечетное число — он говорит черный, иначе — белый. Он может и умереть, но героем. Допустим — нечет и он сказал черный.
Каждый последующий запоминает выбор предыдущего. Если он видит перед собой тоже (не)четное число черных шапок, значит на нем белая, иначе — на нем дополнительная черная.
Итого, стратегия второго. Если первый сказал «черный», то если и он видит нечетное число шапок впереди, то на нем белая, иначе на нем черная.
Эта стратегия будет сохраняться, пока кто-нибудь не скажет «черный». Тогда стратегия инвертируется, видишь четное число — говоришь «черный». Инверсия будет каждый раз, когда кто-то говорит «черный».
Если формализовать, то правило такое. Первый говорит «черный», если видит впереди нечерное число черных шапок. Остальные говорят «черный», если [число черных увиденных шапок впереди]-[число черных шапок озвученных позади] нечетное.
Если можно повернуть голову, тогда предпоследний сообщает последнему цвет его шапки и все живы-здоровы.
Если есть отражающая поверхность типа зеркала или ложки, тогда её наклеивают предпоследнему на затылок и последний видит цвет свой шапки. Так как в поставленной задачи многое не ограничено, то вариантов узнать цвет своей шапки тоже много. Поэтому есть два варианта: никто не умрёт, умрёт один последний.
Но если ужесточить условия до, того, что нельзя говорить, дотрагиваться, вертеть головой, рисовать носком ботинка на земле знаки, то есть коммуникация на абсолютном нуле, то тут ни XORы, ни чётность, ни один бит не поможет.
Черный — 1
Белый — 0
Очередь на жизнь: 01 11 00 01
Второй слышал, что 1 «сказал черный 0 раз». Т.е. он знает, что 1 увидел четное число черных шапок. Считает черные шапки сам — ага, 3, т.е. нечет. Он понимает, что лишняя черная шапка на нем, говорит «черный».
Третий слышал 1 раз, что говорили «черный». Значит перед предыдущим было нечетное число черных шапок. Пересчитывает — 2, четное. Значит, лишняя шапка на нет. Говорит «черный».
Четвертый слышал четное число раз слово «черный». Значит перед предыдущим было четное число черных шапок. Он видит только одну, Значит лишняя черная на нем. Говорит черный.
Пятый и шестой слышали «черный» нечетное число раз. Пересчитывают черные шапки — 1. Говорят белый.
Последний слышал «черный нечетное число раз, значит на нем черная шапка.
Итого, все выжили.
С учетом того, что люди переминаются на ногах, шапки две-три впереди еще можно разглядеть. Но посчитать количество черных шапок в очереди из, скажем, двух сотен человек — абсолютно нереально.
И да, вы не учитываете, что люди бывают тупые, шибко умные и просто приезжие из солнечных стран — они могут тупо не понять, что именно им надо делать. Могут не услышать, что там кто сказал. Короче, в реальности нужен какой-то очень простой способ, иначе расстреляют ровно половину. :)
SELECT n2.position - 1
FROM somenumbers n1
LEFT JOIN somenumbers n2 ON n1.position + 2 = n2.position
WHERE n2.position IS NOT NULL
Т.к. в условие сказано, что длина дырки не превышает одного значения, то получается необходимо связывать список не со следующим значением, а через одно.
Раньше только читал подобные посты, в первый раз решил попробовать, получилось занимательно =)
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)
Можно и что-то более идиотское придумать.
Если кандидат их решает — он считается «годным»? А если не решает, то бракуется?
Мне казалось, что общепринятая практика — это давать задачи и вопросы, на которые иначально в стрессовой ситуации собеседования смогут дать идеально правильный ответ единицы людей во всем мире, если вообще хоть кто-либо. На таких задачах кандидат итеративно шаг за шагом оптимизирует наивное решение при помощи своей головы или наводящих вопросов. И вопрос, скорее не в том, чтобы человек решил. А том, чтобы проследить за его мыслительным процессом при изменении сложности задачи от детской до уровня финалов ACM/ICPC.
Я понимаю, что инженеры и программисты нужны разные. Какие-то — делать сайты-визитки. Какие-то — бизнес-логику на 1С. Какие-то — высоконагруженные веб-сервисы. И на какие-то работы будет достаточно и таких задачек. Но блин, на них все равно же мыслительный процесс толком не проследить.
Вообще интересные задачки, как водится, встречал в обсуждениях гугловых интервью. Они просто эталонны.
Афайк у Яндекса тоже ребята любят дичь поспрашивать. После него можно кучу крутых методов понабрать.
Как говорил товарищ Королёв: "критикуешь — предлагай!" Посему, коли у вас есть необычный опыт собеседований и/или своя подборка задач — пожалуйста, поделитесь. Лично мне будет интересно и в будущем пригодится.
Касаемо "общей практики и нерешаемых задач": там в самом начале статьи написано "Все задачки на логику и/или о программировании. Никакого психологического подтекста и круглых люков." Так что "что на коробке, то и в коробке". А на гугло-яндексовые задачки в комментарии выше была ссылка. Вот там позабористей трава.
Ну и конечно честность. Кто-то может сказать что уже знает ответ, а кто-то просто его скажет сделав вид что решил на месте.
Из "проблемной области компании" у меня получалось поговорить только про архитектуру. Остальные "живые" задачи либо изоморфны багам и там особо нечего обсуждать, либо тянут за собой мешок бизнес-логики и особенностей системы; то есть, пока расскажешь все вводные начнёт смеркаться и кандидат уснёт. Вы как такие проблемы обходите при подготовке задач?
Но я соглашусь с тем, что в больших компаниях вообще идет борьба с любой индивидуальностью. И они правы, для них важнее стандарты, они могут позволить себе неэффективность «в малом»…
Ваш вариант хорош для senior-разработчиков. У них опыта вагон с тележкой и остаётся проверить не врёт ли он и адекватен ли. А как же ребята ниже senior? Как их собесить? Ведь им большую часть означенного ещё предстоит постичь.
Старое доброе сравнение id уже не работает (id левой записи > id правой) в join уже не работает?
Что там имелось ввиду то?
Как sql-запросом извлечь из базы данных информацию, которой там нет
Там решения под MySQL, Oracle, MSSQL
Тестируем запросы здесь
sqlfiddle.com
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
Можно будет изучить на сколько были большие интервалы между дырками, запрос можно с таким же успехом выполнить для дат, где задача ещё интереснее.
Интересные задачки с технических собеседований