Макдауэлл
Макдауэлл Гейл Лакман
McDowell2013
McDowell2021
McDowell2015
.jpg)
.jpg)
.jpg)
Макдауэлл2023:
Макдауэлл, Гейл Лакман; Баваро, Джеки. Карьера продакт-менеджера. Все, что нужно знать для успешной работы в технологической компании- СПб.: Питер, 2023. - 592 С.: ил. - (Серия «Библиотека программиста»).
Макдауэлл2016:
Макдауэлл, Гейл Лакман: Карьера программиста. Решения и ответы 189 тестовых заданий из собеседований в крупнейших IT-компаниях. - 6-е изд. - СПб: Питер, 2016. - 688с. - Тираж 1500. Доп. глава с подсказками на сайте издательства.
Гейл Лаакманн Макдауэлл//Wikipedia
Задачи для собеседований: всего 10.
Макдауэлл2016:
Макдауэлл, Гейл Лакман: Карьера программиста. Решения и ответы 189 тестовых заданий из собеседований в крупнейших IT-компаниях. - 6-е изд. - СПб: Питер, 2016. - 688с. - Тираж 1500. Доп. глава с подсказками на сайте издательства.
1. Есть 20 баночек с таблетками. В 19 баночках лежат таблетки весом 1 г, а в одной - весом 1.1 г. Даны весы, показывающие точный вес. Как за одно взвешивание найти банку с тяжелыми таблетками?
Подсказки:
- Весы разрешено использовать только один раз. Это означает, что должны использоваться все (или почти все) баночки. При этом с ними необходимо обращаться по-разному, иначе различить их не удастся. [Макдауэлл2016q186]
- А если положить на весы по одной таблетке из каждой баночки? А если по две таблетки? [Макдауэлл2016q252]
- Представьте, что баночек всего три, и одна содержит более тяжелые таблетки. Допустим, вы положили на весы разное количество таблеток из каждой баночки (например, 5 из первой, 2 из второй и 9 из третьей). Что покажут весы? [Макдауэлл2016q319]
- Нужно найти формулу, которая позволит вычислить баночку с тяжелыми таблетками в зависимости от веса. [Макдауэлл2016q387]
Решение этой задачи приводится в: https://tproger.ru/problems/logic-problem-for-weights/
2. Имеется баскетбольное кольцо, и вам предлагается сыграть в одну из двух игр. Игра 1: У вас есть один бросок в кольцо. Игра 2: У вас есть три попытки, но для победы потребуется не менее двух попаданий. Если р - вероятность попадания в кольцо при броске, при каких значениях р следует выбирать ту или иную игру?
Подсказки:
- Вычислите вероятности победы в первой и второй игре, а затем сравните их.[Макдауэлл2016q181]
- Чтобы вычислить вероятность победы во второй игре, начните с вычисления вероятности попадания при первом и втором броске с промахом на третьем. [Макдауэлл2016q239]
- Если два события являются взаимоисключающими (то есть никогда не происходят одновременно), их вероятности складываются. [Макдауэлл2016q284]
- Вероятность двух и более попаданий из трех бросков равна сумме: вероятность (попадание при броске 1, попадание при броске 2, промах при броске 3) + вероятность (попадание при броске 1, промах при броске 2, попадание при броске 3) + вероятность (промах при броске 1, попадание при броске 2, попадание при броске 3) + вероятность(попадание при броске 1, попадание при броске 2, попадание при броске 3). [Макдауэлл2016q323]
Решение приводится в: [Паундстоун2012p252-256]
3. Имеется шахматная доска размером 8×8, из которой были вырезаны два противоположных по диагонали угла, и 31 кость домино; каждая кость домино может закрыть два квадратика на поле. Можно ли вымостить костями всю доску? Обоснуйте ответ (приведите пример или докажите, что это невозможно)
Подсказки:
- Представьте кости домино, разложенные на шахматной доске. Сколько черных квадратов они будут закрывать? Сколько белых квадратов? [Макдауэлл2016q367]
- Сколько черных клеток на доске? Сколько белых? [Макдауэлл2016q397]
Решение приводится в: [Шеллинг2016p70-71],[Паундстоун2012р130]
4. На каждой из трех вершин треугольника сидит муравей. Какова вероятность столкновения (на любой из сторон), если муравьи начнут ползти по сторонам треугольника? Предполагается, что каждый муравей выбирает направление случайным образом, вероятность выбора направлений одинакова, муравьи ползут с одинаковой скоростью. Также определите вероятность столкновения для n муравьев на многоугольнике с n вершинами.
Подсказки:
- При каком условии столкновений не будет? [Макдауэлл2016q157]
- Муравьи не столкнутся только в том случае, если все они идут в одном направлении. Какова вероятность того, что все три муравья идут по часовой стрелке? [Макдауэлл2016q195]
- Ситуацию можно рассматривать так: искомая вероятность равна сумме вероятностей того, что все 3 муравья идут по часовой стрелке, и того, что все 3 муравья идут против часовой стрелки. А можно взглянуть на происходящее иначе: первый муравей выбирает направление. Какова вероятность того, что два других муравья выберут то же направление? [Макдауэлл2016q296]
5. У вас есть пятилитровый и трехлитровый кувшины и неограниченное количество воды. Как отмерить ровно 4 литра воды? Кувшины имеют неправильную форму, поэтому точно отмерить «половину» кувшина невозможно
Подсказки:
- Поэкспериментируйте с сосудами и переливаниями. Удастся ли вам отмерить любой объем, кроме 3 и 5 л? [Макдауэлл2016q149]
- Если заполнить 5-литровый кувшин, а потом из него заполнить 3-литровый кувшин, в 5-литровом кувшине останется 2 литра. Далее можно либо оставить эти два литра, либо опустошить меньший кувшин и перелить два литра в него. [Макдауэлл2016q397]
- После того как будет разработано решение задачи, рассмотрите задачув более широкой перспективе. Если имеются два кувшина объемом X и Y литров, всегда ли с их помощью можно отмерить объем Z? [Макдауэлл2016q400]
6. На остров приезжает гонец со странным приказом: все голубоглазые люди должны как можно скорее покинуть остров. Самолет улетает каждый вечер в 20-00. Каждый человек может видеть цвет глаз других, но не знает цвет собственных (и никто не имеет права сказать человеку, какой у него цвет глаз). Жители острова не знают, сколько на нем живет голубоглазых, известно лишь то, что есть минимум один. Сколько дней потребуется, чтобы все голубоглазые уехали?
Подсказки:
- Задача решается на логическом уровне, а не на уровне хитроумной игры слов. Примените логику/математику/алгоритмы для ее решения.[Макдауэлл2016q218]
- Предположим, на острове ровно один голубоглазый житель. Что он увидит? Когда покинет остров? [Макдауэлл2016q282]
- Теперь предположим, что на острове живут двое голубоглазых. Что они увидят? Какие смогут сделать выводы? Когда покинут остров? Вспомните свой ответ из предыдущей подсказки. Считайте, что этот ответ им известен. [Макдауэлл2016q341]
- Продолжайте развивать эту схему. А если на острове живут трое голубоглазых? Четверо? [Макдауэлл2016q370]
7. Королева нового постапокалиптического мира обеспокоена проблемой рождаемости. Она издает закон, по которому в каждой семье должна рождаться хотя бы одна девочка. Если все семьи повинуются закону, то есть заводят детей, пока не родится девочка, после чего немедленно прекращают, - каково будет соотношение полов в новом поколении? (Предполагается, что вероятности рождения мальчика или девочки равны.) Сначала решите задачу на логическом уровне, а затем напишите компьютерную модель
Подсказки:
- Заметьте, что в каждой семье только одна девочка. [Макдауэлл2016q154]
- Попробуйте записать потомство каждой семьи в виде последовательности символов B (мальчик) и G (девочка). [Макдауэлл2016q160]
- Задачу можно попытаться решить на математическом уровне, хотя вычисления будут довольно трудными. Возможно, вам будет проще дать оценку для семей, включающих, скажем, до 6 детей. Хорошего математического доказательства вы не получите, но зато поймете, в каком направлении следует искать ответ. [Макдауэлл2016q171]
- Логический подход может оказаться проще математического. Представьте, что все рождения записываются в огромную строку из B и G. Обратите внимание: группировка по семьям для данной задачи несущественна. Какова вероятность того, что следующим символом, добавленным в строку, будет B, а не G? [Макдауэлл2016q188]
- Биология не изменилась: изменились только условия, при которых семья перестает заводить детей. При каждой беременности с вероятностью 50% родится мальчик, и с вероятностью 50% родится девочка. [Макдауэлл2016q201]
8. Имеется 100-этажное здание. Если яйцо сбросить с высоты N-го этажа (или с большей высоты), оно разобьется. Если его бросить с меньшего этажа, оно не разобьется. У вас есть два яйца, найдите N за минимальное количество бросков.
Подсказки:
- Это алгоритмическая задача, и к ней следует подходить соответственно. Предложите решение методом «грубой силы», вычислите количество бросков в худшем случае, а затем попытайтесь оптимизировать его. [Макдауэлл2016q156]
- Для начала можно применить некое подобие бинарного поиска: начинаем с 50-го этажа, потом бросаем с 75-го, 88-го и т. д. Проблема в том, что если при броске с 50-го этажа яйцо разобьется, то второе яйцо придется бросать, начиная с 1-го этажа и продвигаясь на 1. В худшем случае потребуется 50 попыток (50-й этаж, 1-й этаж, 2-й этаж и так далее до 49-го). Можно ли улучшить этот результат? еская задача, и к ней следует подходить соответственно. Предложите решение методом «грубой силы», вычислите количество бросков в худшем случае, а затем попытайтесь оптимизировать его. [Макдауэлл2016q233]
- Лучше немного уменьшить высоту первого броска. Например, можно сначала сбросить яйцо с 10-го этажа, потом с 20-го, 30-го и т. д. В худшем случае это потребует 19 бросков (10, 20, ..., 100, 91, 92, ..., 99). Можно ли улучшить это значение? Не пытайтесь изобретать разные решения, думайте глубже. Как определяется худший случай? Как в нем учитывается количество бросков каждого яйца? [Макдауэлл2016q294]
- Если ронять яйцо 1 с фиксированными интервалами (например, через каждые 10 этажей), то худший случай будет равен сумме худших случаев для яйца 1 и яйца 2. Недостаток предыдущих решений заключается в том, что с увеличением объема работы для яйца 1 объем работы яйца 2 не уменьшался. В идеале ситуацию хотелось бы сбалансировать: с увеличением объема работы яйца 1 (которое переживает большее количество бросков) на долю яйца 2 должно оставаться меньше работы. Что это может означать? [Макдауэлл2016q333]
- Попробуйте бросать яйцо 1 с большими интервалами вначале, которые затем постоянно уменьшаются. Идея заключается в том, чтобы сумма бросков яиц 1 и 2 оставалась по возможности постоянной. Для каждого дополнительного броска яйца 1 количество бросков яйца 2 уменьшается на 1. Как выбрать правильный интервал? [Макдауэлл2016q357]
- Пусть X — общее количество бросков. Это означает, что яйцо 2 должно сделать X - 1 бросков, если яйцо 1 разобьется. Сумма бросков яиц 1 и 2 должна быть по возможности постоянной. Если яйцо 1 разобьется со второго броска, то яйцо 2 должно сделать X - 2 броска, и т. д. Чему равно X? [Макдауэлл2016q374]
- У меня в худшем случае получилось 14 бросков. А у вас? [Макдауэлл2016q395]
9. В длинном коридоре расположены 100 закрытых замков. Человек сначала открывает все сто. Затем он закрывает каждый второй замок. Затем он делает еще один проход - "переключает?" каждый третий замок (если замок был открыт, то он его закрывает, и наоборот). Процесс продолжается 100 раз, на і-м проходе изменяется состояние каждого і-го замка. Сколько замков останутся открытыми после 100-го прохода, когда «переключается» только замок N 100?
Подсказки:
- Каким должно быть самое первое значение, присутствующее в каждом массиве? [Макдауэлл2016q39]
- В каком случае дверь останется открытой в конце процесса? [Макдауэлл2016q172]
- Если целое число x делится на a, а b = x / a, то x также делится на b. Означает ли это, что все числа имеют четное количество множителей? [Макдауэлл2016q264]
- Число 3 имеет четное количество множителей (1 и 3). Число 12 имеет четное количество множителей (1, 2, 3, 4, 6, 12). Какие числа не обладают этим свойством? Что это говорит о состоянии дверей? [Макдауэлл2016q306]
10. Имеется 1000 бутылок лимонада, ровно одна из которых отравлена. Также у вас есть 10 тестовых полосок для обнаружения яда. Даже одна капля яда окрашивает полоску и делает ее непригодной для дальнейшего использования. На тестовую полоску можно одновременно нанести любое количество капель, и одна полоска может использоваться сколько угодно раз (при условии, что все пробы были отрицательными). Однако вы можете проводить испытания не чаще одного раза в день, а до получения результата с момента проведения проходит 7 дней. Как найти отравленную бутылку за минимальное количество дней?
Подсказки:
- Сможете ли вы разделить бутылки на группы? Помните, что тестовую полоску нельзя повторно использовать после получения положительного результата, но при отрицательном результате она может использоваться сколько угодно раз. [Макдауэлл2016q146]
- Существует относительно простое решение, которое выполняется за 28 дней в худшем случае. Впрочем, есть и более эффективные решения. [Макдауэлл2016q163]
- Почему между тестированием и получением результатов существует такая задержка? Задача не зря сформулирована именно так, а не «Свести к минимуму количество тестов». [Макдауэлл2016q183]
- Нельзя ли одновременно выполнять несколько тестов? [Макдауэлл2016q191]
- Решение 2: попробуйте вычислить номер бутылки, цифру за цифрой. Как узнать первую цифру номера отравленной бутылки? А как насчет второй цифры? Третьей? [Макдауэлл2016q205]
- Решение 2: будьте очень внимательны с граничными случаями. Что если третья цифра в номере совпадает со второй или первой цифрой. [Макдауэлл2016q221]
- Решение 2: дополнительный день тестирования можно потратить на проверку цифры 3 другим способом. И снова будьте осторожны с граничными случаями. [Макдауэлл2016q230]
- Решение 3: рассматривайте каждую тестовую полоску как бинарный индикатор «яд есть/яда нет». [Макдауэлл2016q241]
- Решение 3: если полоска является бинарным индикатором, нельзя ли связать целочисленные ключи с набором из 10 бинарных индикаторов, чтобы каждый ключ имел уникальное представление? [Макдауэлл2016q249]
Например: 0100000001 - номер бутылки, капаем на вторую полоску и на десятую.
Результат мы увидим через семь дней. Покрасневшие полоски укажут на номер бутылки.
А нежизненное решение потому, что если отравленная бутылка не одна, мы ничего не увидим, а наоборот выкинем хорошую бутылку, а отравленные оставим для дальнейшего употребления. Может быть стоит кодировать бутылки помехоустойчивым кодом?[Макдауэлл2016p117-119]
ГОЛОВОЛОМКИ
У вас две веревки и каждая из них горит ровно один час. Как их можно использовать, чтобы определить, что прошло 15 минут? Более того, плотность веревок не является константой, поэтому необязательно, что половина веревки будет гореть ровно полчаса.
Совет: остановитесь здесь и попытайтесь решить задачу самостоятельно. В крайнем случае, прочитайте этот раздел медленно и вдумчиво. Каждый абзац будет приближать вас к решению.
Из постановки задачи ясно, что у нас есть один час. Можно получить двухчасовой интервал, если поджечь вторую веревку после того, как догорит первая. Таким образом, мы получаем правило.
Правило 1: если одна веревка горит х минут, я другая горит у минут то общее время горения составит х+у.
Что еще мы можем сделать с веревкой? Попытка поджечь веревку в любом другом месте, кроме как с концов, не даст нам дополнительной информации. Огонь будет расходиться в обе стороны, и мы понятия не имеем, сколько времени она будет гореть.
Но мы можем поджечь веревку с двух концов одновременно. Огонь должен будет встретиться через 30 минут.
Правило 2: если веревка горит х минут, мы можем отсчитать интервал времени равный х/2 минут.
Итак, теперь мы знаем, что можем отсчитать 30 минут, используя одну веревку. Это также означает, что мы можем вычесть 30 минут из времени горения второй веревки, если одновременно подожжем первую веревку с двух концов, а вторую только с одного.
Правило 3: если первая веревка горит х минут, а вторая веревка горит у минут, мы можем заставить вторую веревку гореть (у-х) минут или (у-х/2) минут.
Теперь давайте соединим все части воедино. Мы можем превратить вторую веревку в веревку, которая горит 30 минут. Если мы теперь подожжем вторую веревку с другого конца (см. правило 2), то она будет гореть 15 минут.
[Макдауэлл2016p115-116]
У вас есть девять шаров - и семь имеют одинаковый вес, а один более тяжелый. Вы можете воспользоваться весами, позволяющими узнать, какой шар тяжелее. Требуется найти тяжелый шар за два взвешивания.
Разделите шары на две группы (по четыре шара), оставшийся (девятый) шар можете пока отложить в сторону. Если одна из групп тяжелее, значит, шар находится в ней. Если обе группы имеют одинаковый вес, тогда девятый шар - самый тяжелый. Если воспользоваться этим же методом еще раз, то в худшем случае вы получите результат за три взвешивания - одно лишнее! Перед нами типичный пример несбалансированного худшего случая: если девятый шар является самым тяжелым, потребуется одно взвешивание, а во всех остальных случаях - три. Если мы «оштрафуем» девятый шар, выделив для него дополнительные шары, это позволит снизить нагрузку на другие: классический пример балансировки худшего случая.
Если мы разделим шары на группы по три шара в каждой, то достаточно одного взвешивания, чтобы понять, в какой группе находится тяжелый шар. Мы можем даже сформулировать правило: для N шаров, где N кратно трем, за одно взвешивание можно найти группу шаров N/3, в которой находится самый тяжелый шар.
Для оставшейся группы из трех шаров нужно повторить ту же операцию: отложить один шар, а остальные взвесить и выбрать более тяжелый. Если шары весят одинаково, выбирается отложенный шар.
[Макдауэлл2016p115-116]
![[Макдауэлл2023p63]](/File:SCR-20230704-ckah.jpg)
Макдауэлл2023:
Макдауэлл, Гейл Лакман, Баваро Джеки. Карьера продакт-менеджера. Все, что нужно знать для успешной работы в технологической компании- СПб.: Питер, 2023. - 592 С.: ил. - (Серия «Библиотека программиста»).
РАССМОТРИМ ТАКОЙ СЦЕНАРИЙ
Представьте, что вы работаете в Google. Как вы докажете, что ІP-адреса соответствуют местоположению людей, если вы не знаете, где именно они находятся?
Вероятно, существует много ответов на этот вопрос. Я поступила так. Прежде всего, я предположила, что часть пользователей в какой-то момент ввела почтовый индекс (предположительно, свой) для поиска прогноза погоды или расписания сеансов кинотеатра. И я могла быть уверена, что местоположения их ІР-адресов примерно соответствовали местам с указанным индексом. Пока все было хорошо.
Но IP-адреса все равно могли находиться за много миль от местоположения пользователей, даже если почтовый индекс был указан правильно. Как опредлить, что точнее: IP-адрес или почтовый индекс? Опять же, представьте, что вы работаете в Google и решаете эту проблему. Какие данные могут быть вам полезны?
Я подумала, что те же самые пользователи также периодически искали конкретные рестораны или магазины. Теперь вопрос заключался в следующем: когда они искали конкретные адреса, они совпадали с почтовым индексом или с IP-адресом?
Оказалось, что IP-адрес был намного точнее, чем почтовый индекс, а значит, он в принципе был довольно надежным источником информации. Теперь я была готова с уверенностью приступить к эксперименту, потому что знала, что ошибок с определением местоположения практически не будет. Эксперимент оказался успешным, и мы запустили новую функцию.
Все это стало возможным только потому, что я знала, какие данные существуют.
[Макдауэлл2023p63]
