Мы отобрали задачи и вопросы на логику, которые могут задать соискателям на должность разработчика в Microsoft. Задачи имеют разный уровень сложности (даже все если кажутся на первый взгляд очень простыми :).
Цель подборки — подготовить соискателя к успешному прохождению собеседования, посредством тренировки умения находить оптимальные для решения алгоритмы и строить логические цепочки, а не банальным заучиванием ответов.
Надеемся, что мы достигли этой цели.
Вопросы
- Утка в пруду
A duck that is being chased by a fox saves itself by sitting at the center of circular pond of radius r. The duck can fly from land but cannot fly from the water. Furthermore, the fox cannot swim. The fox is four times faster than the duck. Assuming that the duck and fox are perfectly smart, is it possible for the duck to ever reach the edge of the pond and fly away to its escape from the ground?
ПереводУтка, преследуемая лисой, спасается в центре круглого пруда радиусом r. Утка может взлететь с земли, но не с воды. Лиса же не умеет плавать. Также, лиса в 4 раза быстрее утки. Предположив, что утка и лиса абсолютно разумны, возможно ли для утки достичь берега и улететь?
- Ящики с фруктами (и ярлыками)
In front of you are three boxes. One contains only apples, one contains only oranges and one contains a mix of apples and oranges. Each box is incorrectly labeled, like this:
Box 1: “apples”
Box 2: “oranges”
Box 3: “apples & oranges”
Question: You get to choose one, and only one, box. I will remove a randomly selected piece of fruit from your chosen box and show it to you (so you can tell if it’s an apple or an orange). After that, you will be able to accurately and definitively relabel all three boxes
ПереводПеред Вами 3 ящика. Один содержит только яблоки, второй — только апельсины, а третий — и яблоки и апельсины. На каждом ящике неправильно повешенный ярлык, вроде:
Ящик 1: «яблоки»
Ящик 2: «апельсины»
Ящик 3: «яблоки и апельсины»
Вопрос: Вам нужно выбрать только один ящик, после чего я вытащу один фрукт из выбранного ящика и покажу Вам (так, что Вы сможете определить, яблоко это или апельсин). Вам требуется безошибочно перевесить ярлыки на ящиках.
Задачи
- Умножить без оператора умножения
Write a function that takes the produce of two given integers without using the multiplication operation. Try to do this as fast as you can (O(log(n) or better)
ПереводНаписать функцию, которая возвращает произведение 2-х целых числе без использования оператора умножения. Постарайтесь реализовать с максимальной производительностью (O(log(n) или лучше).
Я видел также вариацию этой задачи, где требовалось реализовать умножение без операторов умножения, деления, циклов и побитовых операторов.
- N-е простое число
Write a function that returns the nth prime number. For example, nthPrime(1) should return 2 since 2 is the first prime number, nthPrime(2) should return 3, and so on.
ПереводНапишите функцию, возвращающую n-ое простое число. Например:
nthPrime(1) => 2 (поскольку 2 является первым простым числом),
nthPrime(2) => 3
и т.д.
- Найти следующее число с теми же цифрами
Given a number N, find the next number that has same set of digits as n and is greater than N. If N is the greatest possible number with its set of digits, then print “not possible”.
Ex:
N = «218765» => «251678»
N = «1234» => «1243»
N = «4321» => «Not Possible»
N = «534976» => «536479»
ПереводДано число N, нужно найти следующее число, имеющее тот же набор цифр и большее чем N. Если N — самое большое из возможных комбинаций, вывести «not possible».
Пример:
N = «218765» => «251678»
N = «1234» => «1243»
N = «4321» => «Not Possible»
N = «534976» => «536479»
Ответы, как обычно, будут даны в течение следующей недели — успейте решить. Удачи!
Комментарии (37)
Roman_Kh
11.01.2018 13:47+1Многовато ошибок в формулировках.
"Вопрос 2" неразрешим без важнейшего условия — в начальный момент ВСЕ ящики помечены неправильно.
В "задаче 1" также отсутствует важное условие — нужно умножить не какие-то произвольные inputs, а именно integers.
alexeykuzmin0
11.01.2018 16:43+1Задача 1 явно недостаточно сформулирована. Какие операции можно использовать? Учитываем ли мы, что операции (сложение, скажем) могут работать разное время в зависимости от входных данных? Что такое n? Если n — это длина наших чисел, то быстрее, чем за O(n log n) мы ничего не умножим, а за эту сложность — есть БПФ.
А если нет ограничений на операции и выполняются они все за O(1), я могу и exp(log(a) + log(b)) написать. Сомневаюсь, что это то решение, которое имелось в виду.
Videoman
11.01.2018 18:24Если n — это длина наших чисел, то быстрее, чем за O(n log n) мы ничего не умножим, а за эту сложность — есть БПФ.
Да ну ладно вам… N — длина числа в битах. Скорее всего, они имеют ввиду алгоритм по мотивам того как это делается аппаратно:
uint_t a = 5; uint_t b = 1000; uint_t mask = 1; uint_t result = 0; for (uint_t n = 0; n < sizeof(uint_t) * 8; ++n) { if ((a & mask) != 0) res += b; mask <<= 1; b <<= 1; }
вполне за O(N) делается. Правда, совсем аппаратно можно и за O(1), но это не интересно.
Дальше из этого классического алгоритма можно сделать log(N), рекурсивно складывая вершины дерева состоящего из результатов попарных сложений.kardan2
11.01.2018 18:30А я думаю, что n — это само число. Соответственно его длинна в битах — это log(n). Кстати, в вашем примере есть оператор умножения. Но в целом решение правильное.
На аппаратном уровне есть ОПЕРАЦИЯ УМНОЖЕНИЯ, поэтому задача в такой постановке скорее абсурдна.
alexeykuzmin0
11.01.2018 19:12И где здесь быстрее, чем за O(n)? У вас в цикле битовый сдвиг и сложение, которые сами за O(N) делаются.
kardan2
11.01.2018 19:25А почему битовый сдвиг и сложение делается не за O(1)? Это же 1 операция. Тут что 1+1 сложить, что 10000+10000.
alexeykuzmin0
11.01.2018 19:47Потому, что у нас длина числа — не константа, а N. Оно может не уместиться в int32_t.
А если число короткое, то ваш код работает за O(1), ведь его время работы ограничено сверху константой.
Videoman
11.01.2018 20:06Это просто базовая идея алгоритма — умножение в столбик. Дальше я описал словами, так как нужно развернуть цикл руками и получится слишком много кода. Но идея такая — в базовом варианте N — сложений и каждое не зависит от результата, а только от «своего» бита. Следовательно мы может разложить эти слагаемые:
(1-е + 2-е) +
(3-е + 4-е) +
(5-е + 6-е) +
(6-е + 7-е) +
…
будет N/2 сложений. Дальше к результатам рекурсивно применяет тот же алгоритм. В итоге получится log(N) сложений и сдвигов.alexeykuzmin0
12.01.2018 13:34Если
будет N/2 сложений
то ваш алгоритм за O(n) работать ну никак не может. Потому что для одного сложения двух чисел длины n нам нужно O(n) времени.
А насчет дерева не понял, что вы имеете в виду. В записи(1-е + 2-е) +
Ровно 7 знаков сложения, столько же, сколько и при отсутствии скобок. Или вы каким-то образом бесплатно считаете суммы в скобках?
(3-е + 4-е) +
(5-е + 6-е) +
(6-е + 7-е)Videoman
12.01.2018 13:52Все зависит от того, что считать элементарной операцией. Так как в изначальных условиях это не оговорено, то я считаю сложение двух N-разрядных чисел элементарной операцией, вы — нет. В рамках моей постановки, я правильно оцениваю сложность.
Ровно 7 знаков сложения, столько же, сколько и при отсутствии скобок. Или вы каким-то образом бесплатно считаете суммы в скобках?
Я имею ввиду, что эти суммы, на практике, можно считать параллельно, так как они не зависят друг от друга. Без конкретики, что является элементарной операцией, спор бессмыслен. Условия слишком размыты. Например, мне никто не мешает рассматривать N как константу, и тогда в железе ваши 7 сложений будут иметь сложность O(1), если есть аналог SIMD. Собственно, так и есть на практике в железе — умножение выполняется примерно как O(1).alexeykuzmin0
12.01.2018 14:08За О(1) можно сложить только числа не более, чем константной длины. А если у нас числа константной длины, то мы можем хоть перебором искать их произведение, все равно сложность будет O(1), ибо ограничена константой. Такая постановка задачи особого смысла не имеет. Именно поэтому я предполагаю, что длина чисел произвольна (разумеется, на реальном собеседовании я бы уточнил это у интервьювера, но здесь такой возможности, увы, нет, и поэтому приходится довольствоваться наиболее вероятным объяснением).
А учитывая, что число ядер у нас константно (не растет с увеличением длины числа), оно может дать рост производительности не более, чем в константу раз. То есть, асимптотическую оценку не меняет.
Итого:- Если числа длиной O(1), сделать за О(1) не представляет труда — например, ваш алгоритм будет за О(1) работать.
- Если числа произвольной длины, то их сложение займет O(N) времени, поэтому умножение быстрее, чем за O(N) сделать вообще нельзя. Наиболее быстрый алгоритм, известный Википедии, работает за O(n log n 2^(log* n)). Кроме того, количество ядер всегда константа, и поэтому не влияет на асимптотику решения.
- Если числа у нас произвольной длины, то мы можем их умножать за O(N) операций сложения. Но зачем кому-то в здравом уме оценивать производительность умножения, используя за единицу измерения именно операцию сложения? Это какая-то странная величина, ее полезность непонятна.
Videoman
12.01.2018 15:15Согласен с вами.
Если числа у нас произвольной длины, то мы можем их умножать за O(N) операций сложения. Но зачем кому-то в здравом уме оценивать производительность умножения, используя за единицу измерения именно операцию сложения? Это какая-то странная величина, ее полезность непонятна.
Я могу лишь предположить, что все эти «тесты», когда-то раньше, имели под собой практическую основу и выросли из реальных практических задач.
Вот, ситуация когда сложение занимает O(N) у меня была лишь один раз — когда я реализовывал библиотеку «длинной» арифметики, и там ваш подход полностью оправдан. Во всех остальных задачах, всегда были разумные ограничения на битность числа и сложение всегда было O(1). А вот умножения, совсем еще недавно, каких-то 20 лет назад, могло вообще не быть. Я сам начинал программировать с ассемблера и именно с такой архитектуры, где не было умножения. В случае умножения констант, умножение, почти всегда, можно было заменить на сдвиги или/и сложения. Но иногда, приходилось умножать честно — вот тут и нужны все эти алгоритмы и выкрутасы.alexeykuzmin0
12.01.2018 15:39Как задача на ассемблер или просто на умение выпутаться из сильно ограниченной ситуации — согласен, интересная. И, по-хорошему, интервьюверу стоит давать ее именно такой, «сделать быстро и красиво», а не «минимизировать асимптотическую сложность».
kardan2
11.01.2018 18:05Мои решения
Заголовок спойлера1) Просто так утке на берег не выбраться, так как у Пи<4. Но утка может двигаться по кольцу с четвертью радиуса с тойже угловой скоростью, что и лиса. Поэтому Утка переходит на колицо, радиуса чуть меньше четверти (r/4-q), по нему плывет, пока не окажется с другой стороны озера (диаметрально), а потом резко плывет к берегу. У лисы на бег уйдет времени Пи/4, а у утки (3/4+q)/1. Можно взять q очень малым (0,000001) и показать, что первое значение больше второго.
2) Задача баян баянный.
3) Писать долго, поэтому достаточно просто мыслей. Делаем побитовую обработку в цикле первое слово, начиная со старших разрядов. Если видим, что бит =0, переходим к следующей итерации, если =1, то прибавляем второй слово. После каждой итерации умножаем полученную сумму на 2 раза путем сложение с ней же.
Я видел также вариацию этой задачи, где требовалось реализовать умножение без операторов умножения, деления, циклов и побитовых операторов.
Умножения нет, деления нет, цикл можно заменить рекурсивным вызовом, а вот отказ от побитовой проверки как сделать — не знаю пока. Сложность — логарифм (двоичный).
4) Решение в лоб. Начинаем с 2-ки проходим все числа последовательно, проверяем каждое число на простоту. Если оно просто, то увеличиваем счетчик. Как только он достигает нужного значения возвращает текущее число. Вся фишка в том, как проверять число на простоту. До этого момента сохраняем все найденные ПРОСТЫЕ числа в списке. Последовательно проверяем дает ли деление текущего числа по модулю на одно из чисел списке 0. Если да, то число не простое. Но можно проверять не все делители, а только те, чей квадрат меньше или равен самому числу.
5) Очень простая задача. Разбиваем число на разряды (десятичные). Идем с конца, ищем ситуацию, когда предыдущий разряд больше следующего (т.е. когда 34, а не 43). Если разряды упорядоченны монотонно возврастающи, то решения нет. Если мы нашли такой разряд (например в числе 97154 мы нашли что «1»<«5»). То что идет до этих разрядов (97) оставляем на месте, далее находим число, следующее из уже пройденных которое больше предыдущего разряда (здесь из чисел 5 и 7 следующее после 1 идет 5). Ставим это число, а из оставшихся строим число в порядке возрастания разрядов. Т.е. 97-5-17.kardan2
13.01.2018 12:11Вариант на Java без деления, циклов и побитовых операций
Заголовок спойлераpublic class Multy { private int sub =0; public int doOperation(int a, int b){ sub =0; return iteration(a, b, 1); } private int iteration(int a, int b, int c){ if(c>a){ return 0; } int d = iteration(a, b, c+c); if(a-sub>=c){ sub+=c; return d+d+b; }else{ return d+d; } } }
Слабое место данного алгоритма — это ситуация, когда первое число является наибольшим положительным из int, а второе равно 0 или 1. Но предварительно можно сравнить входные числа, и поменять их местами в случае необходимости. Алгоритм работает только с положительными числами.kardan2
13.01.2018 12:29А вот пример кода для поиска простых чисел
Заголовок спойлераpublic class SimpleValue { public static long nthPrime(int number){ if(number==1){ return 2; } ArrayList<Long> array = new ArrayList<>(); array.add(new Long(2)); long n=2; while(true){ n++; if(checkSimple(n, array)){ array.add(n); if(array.size()==number){ return n; } } } } private static boolean checkSimple(long n, ArrayList<Long> array) { for(long l : array){ if(n%l==0){ return false; } if(l*l>n){return true;} } return true; } }
xi-tauw
11.01.2018 21:03Задача 2.
4 варианта на плюсах1. Если можно использовать битовые операции и деления
int foo(int a, int b) { if (a == 1) return b; if (b == 1) return a; if ((a%2==0) && (b%2==0)) return foo(a>>1,b>>1)<<2; if (a%2 == 0) return foo(a>>1,b)<<1; if (b%2 == 0) return foo(a,b>>1)<<1; return (foo(a>>1,b>>1)<<2) + a + b - 1; }
Теперь менее практичные, но более забавные варианты.
2. Если нельзя деление и битовые операции
int foo(int a, int b) { return PRECALCULATED_A_MULT_B[a][b]; }
Где PRECALCULATED_A_MULT_B — думерный массив размером чтобы любые индексы a,b были корректны. Содержимое подсчитано заранее.
Сама функция работает за O(1).
3. Если надо ближе к вычислимым реалиям крутить, но все еще без умножения
int foo(int a, int b) { char t[a][b]; return sizeof(t); }
4. Еще немного с побочными эффектами
int foo(int a, int b) { FILE* f = fopen("tmp", "wb"); void* t = calloc(a, b); fwrite(t, a, b, f); int r = ftell(f); fclose(f); remove("tmp"); free(t); return r; }
el777
13.01.2018 02:31Утка
УткаУтка сдвигается в сторону противоположную лисе. Теперь лиса должна начать двигаться, иначе она гарантированно проиграет. Поскольку картинка симметрична, то лисе все равно в какую сторону двигаться. Предположим, что она решила двигаться против часовой стрелки. Как только лиса сдвигается, утка поворачивается, так чтобы быть всегда хвостом к лисе и тем самым двигаться от нее с максимальной скоростью. Лиса продолжает движение по окружности, Утка все время поворачивается от нее. В итоге — Лиса проходит дугу окружности, Утка движется по спирали из центра к окружности.
Ключевой вопрос, на который надо ответить — действительно ли длина дуги Лисы более чем в 4 раза превышает длину спирали Утки.
Лиса движется с постоянной максимальной скоростью вокруг озера. Длина дуги = 4ut, где u — скорость Утки, t — прошедшее время. Угол в радианах, на который она сместилась = lambda=4ut/pi. Получается треугольник со сторонами r (радиус пруда), ut (смещение утки) и углом pi-lambda. Угол alpha (между вертикальной линией и направлением от Утки к Лисе) = arcsos[(ut+rcos lambda) / sqrt (r^2 + u^2t^2+2utcos lambda)]. Отсюда можно подсчитать радиальную скорость Утки по направлению к краю пруда
ur=(ut+r cos (4t/pi)) / sqrt (r^2+u^2t^2 + 2t cos (4t/pi))
Понятно, что радиально Утка должна проплыть расстояние r, таким образом интеграл по t от ur = r. Дальше берем свежий математический мозг )))sergey_grachev_spb
13.01.2018 10:54Задача с уткой и лисой интересная. И решение с движением утки по окружности в 1/4 r до момента максимального удаления от лисы кажется логичным. Отсюда время движения лисы t1 = 3.14/4, а время утки t2 = от 3 до 3.14/4 в зависимости от расстояния от утки до 1/4 r (но не больше чем 1/7 r; большее расстояние чем (3/4 r + 1/7 r) утке не одолеть быстрее лисы).
Но в условиях задачи стоял пункт про разумность утки и лисы...
Кто-нибудь пробовал подсчитать количество длин окружностей, кот. пройдут лиса (и утка тоже) перед тем, как между ними будет 180° учитывая, что их скорость движения по своим окружностям практически не отличается? =)
P.S. Утка может нырять и незаметно плавать под водой.
el777
13.01.2018 12:18Кто-нибудь пробовал подсчитать количество длин окружностей, кот. пройдут лиса (и утка тоже) перед тем, как между ними будет 180° учитывая, что их скорость движения по своим окружностям практически не отличается? =)
Там не совсем окружность — там лучше двигаться по спирали. А подсчитать несложно — нужно взять добрый интегральчик :)
https://habrahabr.ru/company/spice/blog/346424/#comment_10614030kardan2
13.01.2018 12:54А смысл в спирали? За пределами четверти радиуса утка двигается с меньшей угловой скорость, чем лиса. Если сравнивать прямой отрезок и спираль, то отрезок выигрывает по длине (он короче), а заканчиваются они оба в одной точке. Лисе в обоих случаях бежать одинаково. Рассуждения о спирали здесь совершенно избыточны. Другое дело, что лиса может поменять направление движения, но в этом случае утке просто придется сменить направление, и опять же двигаться по отрезку.
el777
13.01.2018 13:28Задача утки двигаться не только с угловой скоростью, но и приближаться к краю. При движении по прямой утка проигрывает. Мне видится, что спираль за счет отдаления точки пересечения с окружностью дает утке больший выигрыш.
Но это все надо хорошо просчитать математически.kardan2
13.01.2018 13:44Ничего тут математически считать не надо. Кратчайший путь между 2-мя точками — это отрезок, спираль будет длиннее. Нарисуйте на бумаге спираль (между окружностями разного радиуса), например в 1/6 оборота, а потом проведите отрезок через те же концы. Что короче? Движение по отрезку — гарантированный выигрыш утки, а вот спираль может сделать лису сытой.
Оптимальный путь для утки на участке до четверти радиуса действительно будет похож на спираль, а дальше только прямая-ломанная.
KonstantinSpb
Утка не жилец, т.к. (Pi*R/4) < R
Almet
Утка может никуда не лететь, и ждать (плавать) в центре озера, пока лиса обессилит, соответственно ее скорость может снизиться :)
KonstantinSpb
точно, и вообще лисе надоест, она скажет: «Да, нафиг мне сдалась эта утка» и пойдет отжимать дом у зайца.
ainu
Утка как раз жилец, задача не была бы такой простой. Решение — сдвинуться от лисы на небольшое расстояние (например, 1/100r) и затем повернуть на 90 градусов.
утка пройдёт. От лисы до утки в момент касания берега будет 1,2r минус маленькое число в зависимости от того, это было. 1/100 или 1/100.
если лиса передумала бежать и сменила направление назад, то утка тоже меняет направление на 180 градусов. Итого утка не в центре, а лиса на прежнем месте. Повторяем процесс.
KonstantinSpb
Я исхожу из того, что никуда утка сдвинуться не может, т.к. она находится не на острове в середине пруда, а на бесконечно малой точке в середине, такой, что любое движение на бесконечно малое расстояние из этой точки и она оказывается в воде. Т.к. в задаче не сказано, может ли она двигаться в середине острова и на какое растояние, то либо надо уточнить у интервьюера, либо рассчитывать на худший вариант, ибо в лучшем никто никуда не полетит, а лисе надоест и она уйдет.
ainu
Ок, решение попроще (не моё). Утка двигается от центра на кольцевую линию окружности на расстоянии четверти радиуса от центра. После этого она делает круг по этому кольцу чтобы встать напротив лисы (по угловой скорости она быстрее).
Далее плывёт к берегу.
KonstantinSpb
Да, тоже нашел решение в сети, так что утка сможет выжить.
ainu
Ну как «тоже»… Это коллега решил со вторым кругом.
webkumo
Что-то у меня не сходится…
На четверти радиуса получаем длину 1/2 Pi R
длина окружности озера — 2 Pi R
Лиса в 4 раза быстрее => скорость утки на этом радиусе и лисы одинакова. Вопрос — как утке встать в противофазу?
xi-tauw
Если утка проплывет хотя бы миллиметр к центру озера, то по новой окружности (радиус R/4 — 1) она будет быстрее, а значит может выбрать свою позицию. Поскольку это справедливо и для миллиметра и 0,1 миллиметра и даже нанометра, для краткости решения указывают просто четверть радиуса.