Loriowar вчера в 09:58

Интересные задачки с технических собеседований

https://medium.com/@loriowar/interesting-tasks-from-technical-interviews-b56d5b6b4ae

Перевод

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

Несколько замечаний

Все задачки на логику и/или о программировании. никакого психологического подтекста и круглых люков.
Решение не приводится умышленно. Однако, я уверяю вас, что почти у всех задач есть простое и красивое решение. Наслаждайтесь!

Задачи

Вот они.

Зеркальные строки в 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). То есть, чтобы потребление памяти не зависело от размера списка.

Подсказка

помните, что так же как масса может превращаться в энергию, так и временнáя сложность, может конвертироваться в потребление памяти и наоборот.

Хранищиде ключ-значение

Ещё одна задачка на совместное написание кода и его обсуждение в ходе написания.

Напишите key-value storage на любом желаемом языке. Добавьте функцию set_all, которая принимает на вход значение и устанавливает его для всех существующих ключей. Оцените затраты времени и памяти для полученной реализации.

А теперь сделайте set_all, работающим за O(1).

А можно сделать так, чтобы сложность методов get и set осталась как в самом начале, а set_all продолжил работать за O(1)? Если да, то реализуйте. Если нет — докажите почему это невозможно.

Спасение людей

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

Представим, что у нас есть группа людей. Количество значения не имеет. Всю группу выстраивают в линию в затылок друг другу и каждому на голову одевают чёрную или белую шляпу. Никто не знает цвета шляпы, которая на него надета. Однако, все видят, что происходит перед ними и слышал, что происходит за ними. После этого, к спине последнего из группы полходит незнакомец с пистолетом. Он спрашивает "какой у тебя цвет шляпы?" Ответом может быть только "черный" или "белый". Никаких других сообщений быть не может. Если человек угадал — его отпускают. Иначе происходит выстрел и, в любом случае, процесс повторяется с "новым" последним членом в очереди.

Важное уточнение: перед началом этого негуманного опыта, все члены группы могут встретиться и продумать свою стратегию выживания.

Вопрос: как максимизировать число выживших и существует ли точная оценка числа выживших в зависимости от размера группы?

Совет

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

Подсказка

может быть чётность/нечётность или оператор XOR смогут вам помочь?

Вот и всё. Теперь ваша очередь решить какую-нибудь из задач и рассказать о своей интересной подборке с/для собеседований.

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

Должны ли дават задачи на собеседованиях?

Обязательно должны. И посложнее.
Обязательно, но гуманные на ~10 строк кода или на совместное размышление.
Не обязательно. Только если есть сомнения в кандидате.
Не должны. И так стресса хватает.
Иное. В комментарии.

Метки:

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

dskozin 16.10.18 в 10:09
+4
Полагаю что задачи на собеседовании должны даваться, но только на дом. Не у всех (имею ввиду конечно же себя:-) ) прокачан скилл собеседований. Дома я могу весьма сложные вещи взять в работу, сидя перед интервьювером забываю даже базовые. И этот скилл не прокачивается…
- Loriowar 16.10.18 в 10:21
  +1
  Тут тонкий момент: вы дома готовы посидеть и спокойно решить, ибо понимаете свои особенности, а некоторые совсем не хотят своё личное время тратить, даже если это их шанс. И либо надо оговаривать оплату успешных задачек, на что редкая компания согласится. Либо приходится придумывать интересные задачки на 5 строк кода, до которых с наскока не догадаешься и подумать надобно, но реально сделать а 10мин собеседования.
  
  А из личного: давал задачки "на дом" тем, кто почти не впечатлял при устном общении. Прямо говорил: "по общению ты не очень, но, кажется, сильно волновался, поэтому давай дам тебе задачку на 4-8 часов, если сделаешь сам и расскажешь как делал — берём". Суммарно 10-15 соискателей на такое предложение попали. Все били кулаком в грудь, дескать "да, сделаем!" И пропадали в 99% случаев. Только один за всё время сделал.
  - dskozin 16.10.18 в 10:30
    
    0
    Я домашние задачки иногда просто ради интереса делаю. 4-8 часов это норм, но можно и меньше. Например интересные задачки при найме в csssr.ru. Они опубликованы в вакансии и без решения ты даже на собеседование не попадешь. А решить их задачи можно в пределах часа…
    
    И мотивацию в конце концов показывает…
    - Loriowar 16.10.18 в 10:34
      
      0
      
      В таком случае, я недавно наткнулся на старый баян про 123 задачки с IT-собеседований. Он меня как-то стороной обошёл и поэтому я залип там на пару часов. Может и вы там ещё не были :)
  - TheDaemon 16.10.18 в 11:34
    
    0
    Я часто даю не прошедшим собеседование задачки на дом с codingame.com. В сумме давал раз 30-50, взял так человек 5-7. Так что это норм работает :)
paranoya_prod 16.10.18 в 10:41
0
В варианте с шапками погибнет только один — последний, при условии, что люди договорились как передать инфу о цвете шапки и количество шапок обоих цветов им неизвестно.
hatari90 16.10.18 в 10:50
0
Вопрос по поводу задачи «Поиск „дырок“ с помощью 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.18 в 10:55
  0
  На самом деле решений у этой задачки масса. Я её упоминал в своей статье "В дцатый раз про собеседования". Мне там десяток или полтора разных вариантов прислали. Было очень интересно обсуждать.
- vassabi 16.10.18 в 20:55
  0
  Помните, что на месте пропусков нет NULL -значений.
  
  хмммм
  
  where tv2.VALUE is null
  
  UPD: а, извините, не заметил что селект по tv1.
stu5002 16.10.18 в 12:28
0
Очень заинтриговала задача про решение циклов в списке со сложностью по памяти O(1). Ответ то будет?)
- Loriowar 16.10.18 в 12:31
  0
  Там никакого космоса, если подумать и взять подсказки, то решается за 5-25мин неспешного размышления. Один из знакомых-фронтендеров после 3мин раздумия воскликнул "этож jQuery-way!" и тут же выдал ответ. Так что наслаждайтесь. Ответ успеете найти.
- JustDont 16.10.18 в 12:58
  0
  Ответ элементарно гуглится. Не хотите сразу ответ — подумайте о разнообразных способах итерации через список.
- berez 16.10.18 в 15:55
  0
  Гуглите алгоритм «заяц и черепаха».
  Хотя нет, это про поиск конкретного места зацикливания.
- faiwer 16.10.18 в 16:04
  +1
  Подсказка: представьте себе самый ужасный, самый не оптимальный, самый отвратительный алгоритм. Да, это он :)
  
  спойлер
  ещё подсказка: кол-во ваших переменных (потребление памяти) не должно зависеть от кол-ва звеньев в цепи. Т.е. по сути у вас может быть ровно 2, или 3, или 5 переменных. Задумайтесь, что вы в них можете указать. Производительность алгоритма при этом не важна, пусть хоть вечность ищет (при условии что найдёт).
a_e_tsvetkov 16.10.18 в 13:03
–1
Циклы в односвязном списке

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

Предположим что это не так и есть алгоритм который завершится за К шагов.
Он сможет просмотреть К первых элементов списка. Что означает что он не сможет обнаружить цикл расположенный на К+1 позиции.
- TheKnight 16.10.18 в 13:24
  0
  Эм. А как же алгоритм зайца и черепахи?
  - a_e_tsvetkov 16.10.18 в 13:37
    
    0
    Это алгоритм предполагает что цикл точно есть. В нашем случае
    Мы знаем, что в нём, возможно, есть цикл.
    это не так.
    - a_e_tsvetkov 16.10.18 в 13:43
      
      0
      
      На самом деле задача то известная, меня поражает что ее редко кто может правильно сформулировать.
      - JustDont 16.10.18 в 13:50
        
        0
        
        Я вот до сих пор не понимаю, где вы видите проблему.
        Цикл в однсвязном списке конечного размера ищется за конечное же время.
      - TheKnight 16.10.18 в 13:52
        
        0
        
        Вы про отсутствие упоминания о том, что список конечный? Упоминания про то, что он бесконечный я так же не вижу.
        
        Loriowar 16.10.18 в 14:00
        
        0
        
        Добавил уточнение про конечность списка, чтобы всем было удобнее и понятнее.
werklop 16.10.18 в 13:33
–1
По поводу последней задачи про шляпы. Как я понял, переговариваться нельзя, порядок цветов может быть произвольным, а значит вероятность выживания — 50%. Максимизировать число выживших, т.е. приблизиться к 50% и ниже можно только увеличением количества шляп. Но как всегда, играет дело случая, к сожалению, теорвер я подзабыл с института.

P.S. сделайте пож-та, вычитку
- mk2 16.10.18 в 14:05
  +1
  У нас есть дополнительная информация — цвета шляп впередистоящих, сказанные стоящими сзади цвета и угадали ли они. Этого хватает, чтобы умер <= 1 человек.
pocifis 16.10.18 в 13:52
0
Поиск дырок с помощью SQL
SELECT n1.value + 1 FROM num n1 WHERE (SELECT * FROM num n2 WHERE n2.value > n1.value LIMIT 1) != n1.value + 1
Правильно?
- hatari90 16.10.18 в 15:24
  0
  Без order by в подзапросе порядок не гарантируется, в этом случае ваше решение не отработает.
- Paran01d 16.10.18 в 18:57
  0
  Судя по подсказке, запрос должен быть таким
  SELECT i+1 FROM t WHERE i+1 NOT IN (SELECT i FROM t)
  - hatari90 16.10.18 в 23:10
    
    0
    Будет возвращать лишнее значение в виде максимального + 1.
    - Paran01d 16.10.18 в 23:21
      
      0
      
      В подсказке к заданию как раз про это и говорится.
      - hatari90 16.10.18 в 23:35
        
        0
        
        Пардон, точно.
molec 16.10.18 в 13:55
+1
Извините, но очень плохой русский. Ладно опечатки даже в заголовках, но сами задачи даны так, чтобы остался максимум вопросов. Плохо сформулированная задача ведет к дорогому решению (как минимум, по времени, которое потребуется на приведение задачи к полной формализации). Это хорошо для устного интервью, чтобы понять, как претендент решает проблемы, но отвратительно для задач для самопроверки.
- Loriowar 16.10.18 в 14:06
  0
  Опечатки буду рад исправить, пишите в ЛС. А про письменное решение никто и не говорил. Все эти задачи как раз для устного или полу-письменного совместного решения. Это отличная и нескучная тема для разговора, дающая понимание навыков человека. И да, чтобы их молча дать и оставить человека наедине с задачей нужно много формализации и уточнений. Тут вы абсолютно правы.
vzaguskin 16.10.18 в 14:23
0
Шляпы
Люди с нечетным порядковым номером(с конца) называют цвет шляпы впереди стоящего, четным — то, что услышали. Тогда четные(50%) спасутся гарантированно, остальные — с вероятностью 50% при равном количестве черных и белых шляп и случайном их распределении при надевании. Итого 75% выживших.
- IgorIlyin 16.10.18 в 20:52
  0
  Предположим последний человек говорит «белое», если цвет шляп двух, стоящих перед ним «игроков» совпадает. Вероятность его выживания — 50%, вероятность выживания следующих двух 100%. Тогда 2/3 людей спасаются гарантированно. Проблема, если всем выдадут чёрные шляпы… Похоже первый человек должен проанализировать распределение цветов и назвать цвет, которые будет означать, совпадение цветов двух стоящих перед ним людей, выбрав тот, что встречается чаще. Тогда наихудшим случаем уже будет равное распределение, в этом случае каждый третий будет гибнуть с вероятностю 50%. Процент выживших будет около 79.
molec 16.10.18 в 15:55
0
шляпы
Чисто спортивно-тризовское решение.
Первый называет цвет шляпы впереди стоящего. Его шансы равны р — частотность названного цвета.
Второй называет свой цвет. Но. Если впередистоящему нужно назвать тот же цвет, то делает знак голосом — например, чуть растягивает, делает паузу, говорит громче, говорит в левую сторону и т.п. Соответственно, при смене цвета — наоборот.
В принципе, первый даже может тоже сыграть в угадайку, но так же смодулировать свой ответ голосом, чтобы предпоследний его понял.
- Loriowar 16.10.18 в 15:57
  0
  Вы пытаетесь передать больше одного бита информации за раз. В жизни может и прокатит, но это абсолютно неспортивно и безынтересно.
  - molec 16.10.18 в 16:50
    
    0
    абсолютно неспортивно и безынтересно
    
    не согласен. Для Вас неспортивно и Вам безынтересно. А вот в реальных задачах подобные трюки выручают регулярно.
    
    шапки 2
    Тогда да.
    Как рассуждал, решение ниже.
    Первый считает число черных шапок впереди него.
    Если черных нечетное число — он говорит черный, иначе — белый. Он может и умереть, но героем. Допустим — нечет и он сказал черный.
    Каждый последующий запоминает выбор предыдущего. Если он видит перед собой тоже (не)четное число черных шапок, значит на нем белая, иначе — на нем дополнительная черная.
    Итого, стратегия второго. Если первый сказал «черный», то если и он видит нечетное число шапок впереди, то на нем белая, иначе на нем черная.
    Эта стратегия будет сохраняться, пока кто-нибудь не скажет «черный». Тогда стратегия инвертируется, видишь четное число — говоришь «черный». Инверсия будет каждый раз, когда кто-то говорит «черный».
    
    Если формализовать, то правило такое. Первый говорит «черный», если видит впереди нечерное число черных шапок. Остальные говорят «черный», если [число черных увиденных шапок впереди]-[число черных шапок озвученных позади] нечетное.
- paranoya_prod 16.10.18 в 17:41
  0
  Зачем говорить и растягивать слова, делать паузы? Если у человека шапка черная, то стоящий за ним берёт его за правую руку. Если белая, то за левую и так до последнего человека, которому никто не сможет сообщить какого цвета у него шапка, поэтому он погибает первым и последним.
  Если можно повернуть голову, тогда предпоследний сообщает последнему цвет его шапки и все живы-здоровы.
  Если есть отражающая поверхность типа зеркала или ложки, тогда её наклеивают предпоследнему на затылок и последний видит цвет свой шапки. Так как в поставленной задачи многое не ограничено, то вариантов узнать цвет своей шапки тоже много. Поэтому есть два варианта: никто не умрёт, умрёт один последний.
  Но если ужесточить условия до, того, что нельзя говорить, дотрагиваться, вертеть головой, рисовать носком ботинка на земле знаки, то есть коммуникация на абсолютном нуле, то тут ни XORы, ни чётность, ни один бит не поможет.
  - molec 16.10.18 в 18:05
    
    0
    Ваши расстрельные явно общительнее и запасливее моих :) С касанием с нужной стороны идея красивая, но если почти нельзя вертеться и все стоят достаточно далеко друг от друга, то только вариант по типу моего из второго спойлера. Хотя расписал как попало.
dmmax 16.10.18 в 20:51
0
Поиск 'дырок' с помощью SQL
SELECT 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.18 в 23:05
  0
  Не сработает, если будут хотя бы 3 значения подряд без пропусков.
sha4 16.10.18 в 23:13
0
Шляпы, XOR
Если группа совсем дауны, я бы им предложил бинарное сложение. Если поумнее, то тернарное. А если есть возможность накидать приложуху на смартфоне (и у каждого он есть), то достаточно всего одного камикадзе в самом начале ряда, чтобы расшифровать эту последовательность. Да, и предполагается, что можно видеть вперёд все шляпы, а не только ближайшего соседа. Выстрел если и будет, то только один (в варианте с приложением).

// чёрная — 1, белая — 0

(Тот самый случай, когда алгебра нужна для выживания. А то слышишь иногда от учеников: «Зачем нам это в жизни пригодится?!»)
- sha4 17.10.18 в 04:03
  0
  Шляпы, XOR, v.2
  Ладно, мы обойдёмся без приложений и смартфонов.
  
  Последний участник-камикадзе делает XOR для всего ряда (считает [true] чёрные шляпы и если их количество нечётно — говорит [true] чёрная. С вероятностью 50% названный цвет совпадёт с его шляпой, и он выживет).
  
  Предпоследний участник считает все [true] чёрные шляпы перед собой, кроме своей, и если их чётность не изменилась — делает вывод, что его шляпа не повлияла на количество чёрных шляп, следовательно она [false] белая. Если же чётность чёрных шляп изменилась — то именно его шляпа внесла корректив, значит она [true] чёрная.
  
  Пред-предпоследний и далее участники: участник знает (поскольку слышал всю информацию сзади) изначальную чётность чёрных шляп, и он знает сколько чёрных шляп уже было названо (выбыло). На основе этого участник вычисляет текущую чётность чёрных шляп. Затем он считает чёрные шляпы перед собой, если чётность видимых чёрных шляп совпадает — его шляпа [false] белая, если нет — то [true] чёрная.
  
  Итого — камикадзе в начале ряда достаточно передать своим друзьям всего один бит информации — чётность чёрных шляп. И все его друзья будут спасены.
  
  Хорошая головоломочка, приятно было вспомнить детство :-) Спасибо автору поста! (спасибо за подсказку на XOR и один бит ;)
SiliconValleyHobo 17.10.18 в 03:19
0
Какие-то детские задачки, честно говоря. Кого они смогут отсеять? Что именно показать?
Если кандидат их решает — он считается «годным»? А если не решает, то бракуется?

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

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

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

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Интересные задачки с технических собеседований

Несколько замечаний

Задачи

Зеркальные строки в SQL

Поиск "дырок" с помощью SQL

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

Продолжение

Хранищиде ключ-значение

Спасение людей

Читают сейчас

Похожие публикации

Что обсуждают

Самое читаемое

Хабр рекомендует

Тест iOS vs Android: извечное противостояние

Магазин и маленькая тележка инноваций для ритейла

Аккаунт

Разделы

Информация

Услуги

Приложения