Татяна Мелничук, 10 математически илогически задачи

10 математически и логически задачи

Предлагам на читателя 10 математически и логически задачи от интервюта в Apple, Google, Adobe, Microsoft и други IT компании.

Кой не би искал да си намери работа в Google, Intel, Amazon или Apple? Много ИТ компании са известни с това, че дават на кандидатите трудни задачи в областта на математиката, логиката и общата бързина по време на интервюто. Може би един от най-известните примери е въпросът защо шахтите са кръгли. По-долу са най-интересните примери за такива задачи, които изискват познания по математика на училищно ниво или просто изобретателност. Някои от тях се доставят от самите компании, някои се публикуват от потребители, които са отишли на интервюто, някои се събират на популярни сайтове за задачи. Под почти всяка задача е правилният отговор (или поне един от възможните верни отговори) - можете да го видите, като щракнете върху съответната област.

Какво пита Apple

Задача 1. Логическа задача. Шелдън Купър (същият брилянтен физик от популярния сериал) достигна последната граница в мисия на играта в преследване на съкровище. Пред него има две врати, едната водеща към съкровище, другата към смъртоносен лабиринт. На всяка врата има пазач, всеки от тях знае коя врата води до съкровището. Единият от пазачите никога не лъже, другият винаги лъже. Шелдън не знае кой от тях е лъжец и кой не. Преди да изберете врата, можете да зададете само един въпрос и само един пазач.

Въпрос: Какво трябва да попитам Шелдън при пазача, за да стигна до съкровището?

Отговорът е тук

Можете да попитате всеки, като задавате въпроса така: „Коя врата според другия пазач е правилната?“ Ако поискаправдив, ще получи данни коя врата води към лабиринта, защото лъжливият пазач винаги лъже. Ако попита отново лъжливия пазач, той ще разбере коя врата води към лабиринта, защото ще излъже за вратата, която истинският пазач ще посочи.

Проблем 2. Земята е нападната от извънземни. Те планират да унищожат цялата планета, но решават да дадат шанс на човечеството. Те избраха десет от най-умните хора и ги поставиха в напълно тъмна стая, седнали в редица, един по един. Слагат по една шапка на всеки от хората, шапки само в два цвята - 5 розови и 5 зелени. След като всички шапки са на главите им, светлините се включват.

Извънземното започва от последния човек в редицата и пита какъв цвят е шапката на главата му. Други думи, с изключение на цвета на шапката, не могат да бъдат произнесени. Тишината - също. Ако отговори правилно, той е спасен, ако сгреши, той не е спасен.

Не можете да видите какъв цвят е шапката ви, но можете да се споразумеете за определен принцип, по който да отговаряте на всички. Разположението на шапките е произволно, комбинациите могат да бъдат всякакви, можете да видите всички шапки, които са разположени пред вас.

Въпрос: Какво трябва да се отговори, за да оцелеят възможно най-много хора?

Отговорът е тук

Първият отговорил брои броя на зелените шапки пред него, ако това е нечетно число, той нарича "зелено", ако е четно - "розово". Следващият, като види броя и цвета на шапките пред себе си, може по този начин да изчисли какъв цвят е шапката на главата му (например, ако все още има нечетен брой зелени, тогава е очевидно, че той носи розово) и т.н. Така 9 от 10 гарантирано ще оцелеят, а първият отговорил има шанс 1 към 1.

Какво иска Adobe

Проблем 3. Имате 50 мотоциклета с пълен резервоар гориво, коитодостатъчно за 100 км каране.

Въпрос: Използвайки тези 50 мотоциклета, колко далеч можете да стигнете (като се има предвид, че те първоначално са разположени условно в една точка в пространството)?

Отговорът е тук

Най-простият отговор е да ги стартирате всичките едновременно и да карате 100 км. Но има и друго решение. Първо преместете всички мотоциклети на 50 км. След това изсипете горивото от половината мотоциклети в другата половина. Така имате 25 мотоциклета с пълен резервоар. Карайте още 50 км и повторете процедурата. Така можете да изкачите до 350 км (без да вземете предвид горивото, което ще остане от "допълнителния" мотоциклет при разделянето на 25 на две).

Какво пита Microsoft

Задача 4. Имате безкраен запас от вода и две кофи - 5 литра и 3 литра.

Въпрос: Как измервате 4 литра?

Отговорът е тук

Напълнете петлитрова кофа с вода и изсипете част от водата в трилитрова кофа. Вече имате 3 литра в малка кофа и 2 в голяма. Изпразнете малката кофа и изсипете в нея останалите 2 литра от голямата. Напълнете отново голямата кофа и налейте вода от нея в малката. Там вече има 2 литра вода, така че ще трябва да добавите литър, а в голямата ще останат 4 литра.

Задача 5. Имате две парчета въже. Всяка е такава, че ако я запалите от единия край, ще гори точно 60 минути.

Въпрос: Като имате само кутия кибрит, как да измерите 45 минути с две парчета такова въже (не можете да скъсате въжетата)?

Отговорът е тук

Единият сегмент се запалва от двата края, едновременно с това се запалва вторият сегмент, но от единия край. Когато първият сегмент изгори напълно, ще изминат 30 минути, от първия сегмент също ще има 30-минутен сегмент. Подпалвайки го от двата края, получаваме 15 минути.

Какво иска Google

Задача6. Имате 8 топки от същия тип и размер.

Въпрос: Как мога да намеря по-тежка топка с помощта на везна и само две претегляния?

Отговорът е тук

Изберете 6 топки, разделете ги на групи от по 3 топки и ги поставете на везната. Групата с по-тежка топка ще спечели купата. Изберете произволни 2 топки от това трио и ги претеглете. Ако сред тях има тежка топка, ще го познаете, ако тежат еднакво - тежката, която остава. Ако няма по-тежка топка в групи от 3 топки, тя е сред 2-те останали.

Какво иска Qualcomm

Проблем 7. Този проблем е описан от потребител, който е бил интервюиран за позицията на старши системен инженер. Той отбеляза в описанието на задачата, че има свой собствен отговор, за който спори дълго време с интервюиращия.

Да кажем, че имаме 10 трансфера на пакети данни през безжичната мрежа. Каналът не е много добър, така че има 1/10 шанс пакетът данни да не бъде предаден. Предавателят винаги знае дали пакетът данни е бил предаден успешно или неуспешно. Когато предаването е неуспешно, предавателят ще предава пакета, докато успее.

Въпрос: Колко честотна лента получаваме?

Отговорът е тук

Според потребителя отговорът трябваше да бъде 9 пакета в секунда. Но лицето, което проведе интервюто, не се съгласи с него, но не даде отговор, но повтори, че „поради препредаване пропускателната способност трябва да бъде намалена с повече от 1/10″.

Какво се иска в "Yandex"

Играта се състои от еднакви и независими кръгове, всеки от които печели с вероятност p. Когато играчът спечели, той получава $1, а когато загуби, той плаща $1. Веднага щом столицата му достигне Ндолара, той е обявен за победител и отстранен от казиното.

Въпрос: Намерете вероятността играчът да загуби всички пари рано или късно, в зависимост от неговия начален капитал K.

Проблем 9. Този проблем беше даден на разработчиците в интервю и е по-пряко свързан с програмирането от предишните примери.

Има морфологичен речник с обем от около 100 000 статии, в който глаголите от свършен и несвършен вид са поставени в отделни статии (тоест „правя“ и „правя“ се считат за различни речникови статии). Трябва да намерите такива двойки видове в речника и да „залепите“ записите в едно.

Въпрос: Опишете общия сценарий за решаване на такъв проблем и приблизителен алгоритъм за търсене на двойки видове.

На улицата има пет къщи.
Англичанинът живее в червената къща.
Испанецът има куче.
Пият кафе в зелената къща.
Украинецът пие чай.
Зелената къща е непосредствено вдясно от бялата къща.
Този, който яде бонбони Снежна топка, отглежда охлюви.
В жълтата къща ядат сладки "Слънчице".
В централната къща се пие мляко.
Норвежецът живее в първата къща.
Съседът на този, който яде сладките Мишка, държи лисица.
В къщата, съседна на тази, в която се отглежда конят, се ядат сладки "Слънчице".
Всеки, който яде сладки Пинокио, пие портокалов сок.
Японец яде сладки "Пчеличка".
Норвежецът живее до синята къща.
Всяка от къщите е боядисана в различен цвят, във всяка къща живее представител на различна националност, всяка има свой домашен любимец, любимите си бонбони и напитки.

Въпрос: Кой пие вода? Кой държи зебрата?