Головоломки для ИТ-собеседований

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

Памятка

👉 Не все ИТ-компании поль­зу­ют­ся голо­во­лом­ка­ми и поло­жи­тель­но к ним отно­сят­ся. Одна­ко если спро­сят — луч­ше быть готовым. 

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

👉 Ход мыс­лей важ­нее пра­виль­но­го отве­та. Поэто­му озву­чи­вай­те вари­ан­ты и не бой­тесь оши­бать­ся — нор­маль­ные интер­вью­е­ры все­гда подсказывают. 

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

Декомпозиция

Суть. Вы чита­е­те голо­во­лом­ку и пере­но­си­те усло­вие в таб­ли­цу из трёх бло­ков: исход­ные дан­ные, дей­ствия и резуль­тат. Таб­ли­ца струк­ту­ри­ру­ет инфор­ма­цию и помо­га­ет понять, с чего начать рас­суж­де­ние и какие дан­ные мож­но игнорировать. 

Когда исполь­зо­вать. В слу­чае длин­но­го или запу­тан­но­го условия. 

При­мер. У фер­ме­ра два­дцать кур, две коро­вы и один щенок. Каж­дые три дня в 5:00 фер­мер доит коро­ву, кор­мит щен­ка и заби­ра­ет три яйца от трёх кур. Посчи­тай­те, сколь­ко яиц сне­сут все куры за девять дней? 

Перед нами зада­ча с раз­ны­ми пере­мен­ны­ми и про­цес­са­ми — это зна­чит, что за мно­же­ством усло­вий скры­та какая-то деталь или они нуж­ны для отвле­че­ния вни­ма­ния. Что­бы быст­ро сори­ен­ти­ро­вать­ся — соста­вим таб­ли­цу: в исход­ные дан­ные запи­шем объ­ек­ты; в дей­ствия — выпол­нен­ные про­цес­сы; в резуль­тат — ответ, кото­рый нуж­но полу­чить. Если усло­вие раз­ло­же­но по полоч­кам, то лег­ко най­ти отправ­ную точ­ку и выде­лить необ­хо­ди­мые дан­ные для расчёта.

Всё крас­ное — лиш­няя инфор­ма­ция. Отправ­ная точ­ка — момент, когда мы рас­счи­ты­ва­ем, сколь­ко яиц кури­ца несёт за три дня 

Исключение

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

Когда исполь­зо­вать. Если нуж­но упо­ря­до­чить данные. 

При­мер. Встре­ти­лись три подру­ги: Ира, Катя и Све­та. У одной девуш­ки были крас­ные туфли, у дру­гой — чёр­ные, у тре­тьей — синие. Пла­тья тоже были крас­но­го, чёр­но­го и сине­го цве­та. Извест­но, что толь­ко у Иры пла­тье и туфли были одно­го цве­та. Све­та была в синих туф­лях. На Кате не было ниче­го чёр­но­го. Опре­де­ли­те, како­го цве­та пла­тья и туфли были у каж­дой из подруг? 

Туфли и пла­тья — это два типа дан­ных, кото­рые мы раз­де­лим на две таб­ли­цы и сгруп­пи­ру­ем. Теперь запол­ня­ем таб­ли­цы и нахо­дим неиз­вест­ные переменные: 

  • Све­та: отме­ча­ем синие туфли; исклю­ча­ем чёр­ные и крас­ные туфли, синее платье. 
  • Катя: исклю­ча­ем чёр­ные туфли и платье.
  • Катя: отме­ча­ем крас­ные туфли; исклю­ча­ем крас­ное пла­тье; отме­ча­ем синее платье. 
  • Ира: отме­ча­ем чёр­ное пла­тье и туфли. 
  • Све­та: отме­ча­ем крас­ное платье. 

Резуль­тат: Ира в чёр­ном пла­тье и чёр­ных туф­лях; Катя в крас­ных туф­лях и синем пла­тье; Све­та в крас­ном пла­тье и синих туфлях.

Зада­чи на исклю­че­ние удоб­но рас­пу­ты­вать с помо­щью таб­лиц — они помо­га­ют не запо­ми­нать гро­мозд­кое усло­вие и посте­пен­но обра­ба­ты­вать данные 

Худший случай 

Суть. Если зада­ча пред­по­ла­га­ет неогра­ни­чен­ное коли­че­ство попы­ток или шагов — счи­та­ем, что нам не пове­зёт, и дела­ем рас­чё­ты для наи­худ­ше­го варианта. 

Когда исполь­зо­вать. Если с раз­ны­ми объ­ек­та­ми совер­ша­ют одно­тип­ные дей­ствия: их взве­ши­ва­ют, счи­та­ют, пере­кла­ды­ва­ют, пере­ли­ва­ют и так далее. 

При­мер. В ящи­ке 100 раз­но­цвет­ных тре­уголь­ни­ков: 30 чёр­ных, 15 синих, 15 крас­ных, 10 зелё­ных, 10 розо­вых, 10 оран­же­вых, 5 фио­ле­то­вых и 5 корич­не­вых. Сколь­ко тре­уголь­ни­ков нуж­но выта­щить, что­бы сре­ди них был один фиолетовый? 

В дан­ном слу­чае худ­ший вари­ант будет таким: мы вытя­нем 95 тре­уголь­ни­ков и сре­ди них не будет ни одно­го фио­ле­то­во­го. Поэто­му если мы выта­щим 96 тре­уголь­ни­ков, то сре­ди них точ­но будет один фиолетовый.

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

Действуем от противного

Суть. Нуж­но пере­вер­нуть исход­ные дан­ные и дока­зать, что они невер­ны. В резуль­та­те мы под­твер­дим своё пред­по­ло­же­ние или най­дём противоречие. 

Когда исполь­зо­вать. Если извест­но суж­де­ние и его нуж­но под­твер­дить или опро­верг­нуть огра­ни­чен­ным коли­че­ством информации.

При­мер. Есть круг из 15 смай­ли­ков зелё­но­го и крас­но­го цве­та. Дока­жи­те, что хотя бы у одной пары сосед­них смай­ли­ков будет один цвет?

Пред­по­ла­га­ем, что опи­сан­ный сце­на­рий невоз­мо­жен и у всех сосед­них смай­ли­ков раз­ные цве­та — долж­но полу­чить­ся семь или восемь пар. Делим пят­на­дцать на два и полу­ча­ем семь с поло­ви­ной — нечёт­ное чис­ло, про­ти­во­ре­ча­щее наше­му утвер­жде­нию. Зна­чит, хотя бы у одной пары будет оди­на­ко­вый цвет. 

Про­ве­ря­ем пред­по­ло­же­ние: рису­ем через один все смай­лы, полу­ча­ем одну пару с общим цве­том и под­твер­жда­ем наше доказательство 

Что дальше

Про­чти­те кни­гу Уилья­ма Пауд­сто­у­на «Най­ти умно­го. Как про­ве­рить логи­че­ское мыш­ле­ние и твор­че­ские спо­соб­но­сти кан­ди­да­та». Она о том, как про­ве­ря­ют логи­че­ское мыш­ле­ние про­грам­ми­стов при собе­се­до­ва­нии в Microsoft. 

Потре­ни­руй­тесь на наших зада­чах из раз­де­ла «Как решить».Посе­ти­те braingames.ru — это сайт, где тре­ни­ру­ет­ся руко­во­ди­тель груп­пы реко­мен­да­тель­ных систем лабо­ра­то­рии ИИ Сбе­ра Алек­сей Васи­льев. На сле­ду­ю­щей неде­ле у нас с ним вый­дет интер­вью, стей тюнед.

Текст и иллю­стра­ции:
Алек­сандр Бабаскин

Редак­тор:
Мак­сим Ильяхов

Заглав­ная иллю­стра­ция:
Даня Бер­ков­ский

Кор­рек­тор:
Ира Михе­е­ва

Вёрст­ка:
Маша Дро­но­ва

Соц­се­ти:
Олег Веш­кур­цев