108 задач с IT-собеседований с разбором решений

job-interview3

В нашей рубрике c задачами уже больше 100 вопросов с подробным разбором решений. Решили собрать их всех в единый список, чтобы вам было удобнее готовиться и прорешивать их.

Есть однонаправленный список из структур. В нём random указывает на какой-то еще элемент этого же списка. Требуется написать функцию, которая копирует этот список с сохранением структуры (т.е. если в старом списке random первой ноды указывал на 4-ю, в новом списке должно быть то же самое – рандом первой ноды указывает на 4-ю ноду нового списка). O(n), константная дополнительная память + память под элементы нового списка. Нельзя сразу выделить память под все данные одник куском т.е. список должен быть честным, разбросанным по частям, а не единым блоком, как массив.

Ответ Вариант реализации

Классическая задачка с собеседований в Google. На доске записаны числа, вам нужно ответить на вопрос: какое число идёт дальше?
YkkjpXHI5bo

Ответ

Допустим, вы летите из Москвы во Владивосток, а затем обратно, при полном безветрии. Затем вы совершаете точно такой же перелёт, но на этот раз на протяжении всего перелёта дует постоянный западный ветер: в одну сторону попутный, в обратную — лобовой.

Как изменится суммарное время перелёта туда-обратно?

или посмотреть результаты

Loading ... Loading ...

Ответ

Что не так в этом отрывке кода на С++?

Ответ

Задача, которая была популярна в своё время на собеседованиях в Amazon. Мы русифицировали её, но смысл остался тот же. Вам нужно продолжить последовательность.

7BG1Rq0GTdg

Ответ автора с обзором вариантов ответов подписчиков

Как это вычислить, не пользуясь калькулятором? Можете дать приблизительный ответ?

XXeiJs71psg

Ответ

«Вас уменьшили до размеров 5-центовой монеты и бросили в блендер. Ваш вес уменьшился так, что плотность вашего тела осталась прежней. Лезвия начнут вращаться через 60 секунд. Ваши действия?»

Это классическая google-задачка, хороший разбор которой в рунете не так-то просто найти. Мы подготовили его для вас. Абсолютного правильного ответа нет, но есть те, которые явно лучше остальных.

Разбор вариантов ответа

Вопрос по С++. Что за ошибка «pure virtual function call»? В какой ситуации она может быть сгенерирована? Предоставьте минимальный код, приводящий к ней.

Ответ

В вашем распоряжении 10 тысяч серверов в дата-центре с возможностью удалённого управления и один день, чтобы получить миллион долларов. Что вы для этого сделаете?

Ответ

У вас есть аналоговые часы с секундной стрелкой. Сколько раз в день все три стрелки часов накладываются друг на друга?

vkpXkPgrCQM

Ответ

В чём разница между string и String в C#?

yG1wPwEobQ0

Ответ

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

Ответ

Cколько мячей для гольфа войдет в школьный автобус?

Для справки: в Национальных стандартах транспотрных средств для школ в США на 1995 год указаны максимальные размеры школьного автобуса и равны 40 футам в длину и 8.5 футам в ширину. Стандартный диаметр мяча для гольфа — 1.69 дюйма с допуском 0.005 дюймов.

Ответ

Представьте себе вращающийся диск, например DVD. У вас есть в распоряжении черная (Ч) и белая (Б) краски. На краю диска установлен небольшой датчик, который определяет цвет под ним и выдает результат в виде сигнала. Как бы вы раскрасили диск, чтобы было возможно определить направление вращения по показаниям датчика?

A6Y4czusetc

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

Датчик фиксирует цвет точки в непосредственном месте установки в последовательные моменты времени. Показания представляются в виде «ЧЧЧББ…». Задача сводится к такой раскраске диска, где последовательность показаний отличается при вращении в прямую и в противоположную стороны.

Ответ

У вас есть исходный код приложения на языке С, которое аварийно завершается после запуска. После десяти запусков в отладчике вы обнаруживаете, что каждый раз программа падает в разных местах. Приложение однопоточное и использует только стандартную библиотеку С. Какие ошибки могут вызвать падение приложения? Как вы проверите каждую?

Ответ

Найдите ошибки в следующем коде.

Ответ

Объясните, что делает этот код.

((n & (n – 1)) == 0)

Ответ

Дано 100-этажное здание. Если яйцо сбросить с высоты N-го этажа (или с большей высоты), оно разобьется. Если его бросить с любого меньшего этажа, оно не разобьется. У вас есть два яйца. Найдите N за минимальное количество бросков.

Ответ

Продолжаем задачки по С/С++. Что означает ключевое слово volatile и в каких ситуация оно может быть применено? Если даже помните формальное значение, попробуйте привести пример ситуации, где volatile на самом деле будет полезно.

Ответ

У вас есть отсортированная матрица размера MxN. Предложите алгоритм поиска в ней произвольного элемента. Под отсортированной матрицей будем понимать такую матрицу, строки и столбцы которой отсортированы (см. пример).

Re15WLGNZSU

Ответ

Напишите метод, находящий максимальное из двух чисел, не используя операторы if-else или любые другие операторы сравнения.

Ответ

На пустынном шоссе вероятность появления автомобиля за 30-минутный период составляет 0.95. Какова вероятность его появления за 10 минут?

Ответ

Напишите функцию суммирования двух целых чисел без использования «+» и других арифметических операторов.

Ответ

У вас есть парк из 50 грузовиков. Каждый из них полностью заправлен и может проехать 100 км. Как далеко с их помощью вы можете доставить определенный груз? Что будет, если в вашем распоряжении N грузовиков?

Не все понимают сразу о чем речь: территориально это место, где нет никаких заправочных станций. Единственное место, где можно здесь найти горючее – это топливные баки грузовиков. Пересесть из грузовика в гибридный легковой автомобиль Prius нельзя. Бросить грузовик без топлива, где бы это ни случилось, и без водителя – в порядке вещей. И единственное, что здесь важно, – доставить как можно дальше ценный груз.

Ответ

Опишите алгоритм для нахождения миллиона наименьших чисел в наборе из миллиарда чисел. Память компьютера позволяет хранить весь миллиард чисел. Если придумали какое-либо решение, то оцените его эффективность по времени. Есть ли более эффективное решение?

Ответ

Напишите метод, который будет подсчитывать количество цифр «2», используемых в десятичной записи целых чисел от 0 до n (включительно). Картинка дана в качестве подсказки к одному из возможных решений.

89AF2ZU2dT0

Ответ

Где вы будете плыть быстрее — в воде или сиропе?

Это классическая задача с долгой историей, которую обсуждал в своё время еще Исаак Ньютон. Когда-то она использовалась и на IT-собеседованиях в Google (сейчас — нет). Тем не менее предлагаем вам порассуждать над решением.

Ответ

Напишите методы для умножения, вычитания и деления целых чисел, используя из арифметических операций только оператор суммирования. Язык реализации не важен, об оптимизации скорости работы и использования памяти также можете не особо беспокоиться. Главное, что можно использовать только сложение. В подобных задачах полезно вспомнить суть математических операций.

Ответ

Допустим, вы пишете конвейер, в котором 2 потока, используя общий буфер, обрабатывают данные. Поток-producer эти данные создает, а поток-consumer их обрабатывает (Producer–consumer problem). Следующий код представляет собой самую простую модель: с помощью std::thread мы порождаем поток-consumer, a создавать данные мы будем в главном потоке.

Опустим механизмы синхронизации двух потоков, и обратим внимание на функцию main(). Попробуйте догадаться, что с этим кодом не так, и как его исправить?

Ответ

Дано 20 баночек с таблетками. В 19 из них лежат таблетки весом 1 г, а в одной – весом 1.1 г. Даны весы, показывающие точный вес. Как за одно взвешивание найти банку с тяжелыми таблетками?

Ответ

Дана шахматная доска размером 8×8, из которой были вырезаны два противоположных по диагонали угла, и 31 кость домино; каждая кость домино может закрыть два квадратика на поле. Можно ли вымостить костями всю доску? Дайте обоснование своему ответу.

2Ujg18t9ZCY

Ответ

Дан входной файл, содержащий четыре миллиарда целых 32-битных чисел. Предложите алгоритм, генерирующий число, отсутствующее в файле. Имеется 1 Гбайт памяти для этой задачи. Дополнительно: а что если у вас всего 10 Мбайт? Количество проходов по файлу должно быть минимальным.

Ответ

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

Ответ

Вы поставили стакан воды на диск проигрывателя виниловых пластинок и медленно увеличиваете скорость вращения. Что произойдет раньше: стакан сползет в сторону, стакан опрокинется, вода расплескается?

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

Ответ

Короткая задачка по С++ в виде вопроса для новичков. Почему деструктор полиморфного базового класса должен объявляться виртуальным? Полиморфным считаем класс, в котором есть хотя бы одна виртуальная функция.

Ответ

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

Ответ

Предложите алгоритм поиска в односвязном списке k-го элемента с конца. Список реализован вручную, есть только операция получения следующего элемента и указатель на первый элемент. Алгоритм, по возможности, должен быть оптимален по времени и памяти.

Ответ

Напишите функцию, определяющую количество битов, которые необходимо изменить, чтобы из целого числа А получить целое число B. Числа, допустим, 32-битные, язык любой.

Это одна из типичных задач на работу с битами, которые любят давать на собеседовании. Если вы никогда с ними не сталкивались, вам будет сложно сразу решить задачу с учётом стрессовой ситуации, поэтому запомните использованные при решении трюки.

Ответ

В книге N страниц, пронумерованных как обычно от 1 до N. Если сложить количество цифр, содержащихся в каждом номере страницы, будет 1095. Сколько страниц в книге?

Ответ

Задачка по С++, которая, тем не менее, будет полезна и для других языков. Сопоставьте хэш-таблицу и mар из стандартной библиотеки шаблонов (STL). Как организована хэш-таблица? Какая структура данных будет оптимальной для небольших объемов данных?

Ответ

Разработайте класс, обеспечивающий блокировку так, чтобы предотвратить возникновение мертвой блокировки.

Ответ

Напишите функцию на С++, выводящую в стандартный поток вывода K последних строк файла. При этом файл очень большой, допустим 50 ГБ, длина каждой строки не превышает 256 символов, а число K < 1000.

Ответ

Дан кусок сыра в форме куба и нож. Какое минимальное количество разрезов потребуется сделать, чтобы разделить этот кусок на 27 одинаковых кубиков? А на 64 кубика? После каждого разреза части можно компоновать как угодно.

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

Ответ

Реализуйте метод, определяющий, является ли одна строка перестановкой другой. Под перестановкой понимаем любое изменение порядка символов. Регистр учитывается, пробелы являются существенными.

Ответ

В тёмной комнате вам вручают колоду карт, в которой известное количество карт N лежат рубашкой вверх, а остальные — вниз. Вы не можете видеть карты, но можете их переворачивать. Как вы разделите колоду на две стопки, чтобы в каждой из них было одинаковое число карт, лежащих рубашкой вверх?

Эта головоломка в своё время была популярна в JP Morgan Chase. Понятное дело, оказавшись в темноте, вы просто достанете сотовый телефон и воспользуетесь экраном как фонариком. Однако эта задачка появилась до эпохи сотовых телефонов, и её можно решить, даже не видя карт.

Ответ

Реализуйте вручную стек со стандартными функциями push/pop и дополнительной функцией min, возвращающей минимальный элемент стека. Все эти функции должны работать за O(1). Решение оптимизируйте по использованию памяти.

push-pop2

Ответ

У скольких целых чисел, лежащих в диапазоне от 1 до 1000, есть цифра 3? Посчитать нужно без использования компьютера, приведя свои рассуждения в комментариях.

Ответ

У вас есть много URL-адресов, порядка 10 миллиардов. Как бы вы организовали эффективный поиск дубликатов, учитывая, что все они, конечно же, не поместятся в памяти?

Ответ

Вы должны выбрать одну из двух ставок. При первом варианте вы должны забросить баскетбольный мяч в корзину за один бросок. Если попадёте, то получите 50 тыс. рублей. Во втором варианте вам надо попасть два раза из трёх бросков, и тогда вы также получите те же 50 тыс. рублей. Какой из этих вариантов вы предпочтёте? Будет ли ваше умение забрасывать мячи влиять на выбор?

Ответ

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

Какой алгоритм вы предложите? Какая у него будет сложность и можно ли предложить лучший вариант?

golden-pyramid-example

Ответ

Даны два слова или фразы, и ваша задача — проверить, являются ли они анаграммами.

Анаграмма — это игра со словами, когда в результате перестановки букв слова или фразы получаем другое слово или фразу. Два слова являются анаграммами, если мы можем получить одно из другого переставляя буквы местами.

anagramm

Ответ

Предложите алгоритм, который обнуляет столбец N и строку M матрицы, если элемент в ячейке (N, M) нулевой. Конечно же, нужно минимизировать затраты памяти и время работы.

Ответ

Разработайте алгоритм, обнаруживающий в массиве все пары целых чисел, сумма которых равна заданному значению.

Ответ

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

Под большой базой подразумевается порядка миллиарда зарегистрированных пользователей и не менее 100 миллиардов «дружеских» связей между ними.

Ответ

Допустим, у вас есть однонаправленный список с петлёй. Его «последний» элемент содержит указатель на один из элементов этого же списка, причём не обязательно на первый. Ваша задача — найти начальный узел петли.

Элементы списка менять нельзя, память можно использовать только константную.

Ответ

На острове существует правило — голубоглазые люди не могут там находиться. Самолет улетает с острова каждый вечер в 20:00. Все жители собираются за круглым столом ежедневно, каждый человек может видеть цвет глаз других людей, но не знает цвет собственных. Никто не имеет права сказать человеку, какой у его цвет глаз. На острове находится не менее одного голубоглазого человека. Сколько дней потребуется, чтобы все голубоглазые уехали?

Ответ

Напишите код, удаляющий дубликаты из несортированного связного списка. Можно использовать только константную память.

Doubly_linked_list-870x295

Ответ

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

Ответ

Допустим, вам поручили задачу по разработке поискового робота — программы, которая, грубо говоря, посещает страницы в Интернете, индексирует, выделяет из них ссылки, переходит по ним и повторяет процесс. Вопрос: как избежать зацикливания?

Ответ

У вас есть стеклянный кувшин, в котором лежат небольшие шарики, и вы в любое время можете определить их количество. Вы со своим другом играете в следующую игру: каждый из вас по очереди забирает из кувшина 1 или 2 шарика. Игрок, который забирает последний шарик, выигрывает. Какая самая лучшая стратегия в этой игре? Можете ли вы в самом начале предсказать, кто выиграет?

Ответ

Имеется N компаний, и вы хотите, чтобы они слились и образовали одну крупную компанию. Сколько разных способов вы можете использовать для этого? Поглощение можно считать частным случаем слияния, когда А поглощает Б и Б полгощает А — два разных способа. Равнозначные слияния тоже возможны.

Ответ

Какой минимальный комплект монет необходим для того, чтобы выдать любую сдачу от 1 до 99 центов? Доступные номиналы монет: 1, 5, 10, 25, 50 центов и 1 доллар.

Ответ

У вас есть 25 лошадей. Сколько забегов вам нужно устроить, чтобы определить трех самых быстрых из них? Вы не можете пользоваться секундомером. В каждом заезде могут участвовать только пять лошадей.

Ответ

Короткая задачка на сообразительность. По результатам исследования известно, что 70% людей любят кофе, в то же время 80% любят чай. Каковы верхние и нижние границы доли людей, которые одновременно любят кофе и чай?

Ответ

Задачка, которую нужно решать без калькулятора и компьютера, имея под рукой только карандаш и бумагу. Сколько нулей в конце факториала 100?

Ответ

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

Ответ

Напишите программу расчета значения медианы в потоке чисел, динамически отслеживающую новые поступающие числа, получаемые рандомом.

Ответ

Идет дождь, а вам надо добраться до вашей машины, которая стоит в самом дальнем конце парковки. Побежите ли вы к ней или нет, если ваша цель — как можно меньше промокнуть? Как вы будете себя вести, если у вас есть зонтик?

Ответ

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

Разбор двух вариантов решения за O(N^4) и O(N^3). Можете ли вы найти другие варианты?

Ответ

Предположим, в некоторый бар ходят только необщительные посетители. Вдоль барной стойки расположены 25 мест. Всякий раз, когда входит новый посетитель, он обязательно садится на самое дальнее, насколько это возможно, место от остальных гостей. Ни один не сядет рядом с кем-то другим: если посетитель входит и видит, что «свободных» мест нет, он тут же разворачивается и уходит из бара. Бармену, естественно, хочется, чтобы за стойкой сидело как можно больше клиентов. Если ему разрешено усадить первого посетителя на любое место, куда выгоднее его посадить с точки зрения бармена?

Ответ

Опишите, как можно использовать один одномерный массив для реализации трех стеков.

Ответ

У вас есть неограниченное количество монет достоинством 25, 10, 5 и 1 цент. Напишите код, определяющий количество способов представления n центов.

Ответ

Напишите код, который позволяет найти минимальное расстояние (выражаемое количеством слов) между любыми двумя словами в файле. Порядок не важен.

PJ24s9zjzZw

Достаточно ли будет линейного времени?
Сколько памяти понадобится для решения?

Ответ

Смоделируйте использование игральной кости с семью гранями, если в вашем распоряжении имеется только кость с пятью гранями.

Иными словами, как получить случайное число в диапазоне от 1 до 7, используя генератор случайных целых чисел от 1 до 5?

Ответ

Напишите код, разбивающий связный список вокруг некоторого значения так, чтобы все меньшие узлы оказались перед узлами, большими или равными этому значению.

Ответ

Напишите метод, генерирующий случайную последовательность m целых чисел из массива размером n. Все элементы выбираются с одинаковой вероятностью.

Первое, что приходит в голову, — выбрать случайные элементы из массива и поместить их в новый массив. Но что если мы выберем один и тот же элемент дважды?

Ответ

Представьте себе робота, находящегося в левом верхнем углу сетки с координатами (X, Y). Робот может перемещаться в двух направлениях: вправо и вниз. Сколько существует маршрутов, проходящих от точки (0, 0) до точки (X, Y)?

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

Ответ

Реализуйте метод сжатия строки на основе счетчика повторяющихся символов. Например, строка aabcccccaaa должна превратиться в а2b1с5аЗ. Если «сжатая» строка оказывается длиннее исходной, метод должен вернуть исходную строку.

Ответ

Вы находитесь в автомобиле, где к полу веревочкой привязан шар, наполненный гелием. Окна закрыты. Вы нажимаете на педаль газа. Что произойдет с шаром: переместится он вперед, назад или останется в прежнем положении?

car

Что произойдет с шаром?

или посмотреть результаты

Loading ... Loading ...

Ответ

Задачка, на примере который можно кратко ознакомиться с основами RSA-криптографии.

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

Даже не зная ничего про RSA можно попробовать придумать ответ.

Ответ

Задача на знание конкретных языков. Объясните разницу между шаблонами в C++ и дженериками в Java.

Многие программисты полагают, что шаблоны C++ и дженерики (например в Java) — это одно и то же, ведь их синтаксис похож: в обоих случаях можно написать что-то вроде List<T>.  Но различия на самом деле есть.

Ответ

Реализуйте вручную «умный» указатель с автоматическим управлением памятью на C++.

Умный (интеллектуальный) указатель — это тот же обычный указатель, обеспечивающий безопасность благодаря автоматическому управлению памятью. Такой указатель помогает избежать множества проблем: «висячие» указатели, «утечки» памяти и отказы в выделении памяти. Интеллектуальный указатель должен подсчитывать количество ссылок на указанный объект.

На первый взгляд эта задача кажется довольно сложной, особенно если вы не эксперт в C++.

Ответ

Эта головоломка, в которой вас пытаются запутать, предложив поменять свое решение, известна также под именем «Парадокс Монти Холла». Монти Холл был первым ведущим телевизионной игры-шоу «Давайте заключим сделку»

Перед вами три коробки, в одной из которых находится ценный груз, в двух других ничего нет. Вы можете выбрать любую коробку, но вам по-прежнему неизвестно, в какой именно приз. Одну из двух не выбранных вами коробок открывают и показывают, что она пустая. Теперь вы можете или оставить коробку, которую вы первоначально выбрали (оставить), или поменять ее на другую, неоткрытую (заменить). Что вы предпочтете сделать (оставить или заменить)?

Ответ

У вас есть пустое помещение и группа людей снаружи. За один ход вы можете либо позволить одному человеку войти в помещение, либо выпустить из него одного человека. Можете ли вы предложить серию ходов, при которой каждая возможная комбинация людей находится в помещении только один раз?

Нужно время, чтобы понять, чего именно хочет от вас интервьюер. Разобраться в этом помогает простой пример. Скажем, за порогом находятся два человека, Ларри и Сергей. Возможны четыре комбинации их присутствия в комнате, учитывая тот случай, когда в комнате вообще никого нет.

Вот они:

  • В помещении никого нет.
  • В помещении только Ларри.
  • В помещении только Сергей.
  • В помещении Ларри и Сергей.

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

Иными словами, как сгенерировать неповторяющиеся комбинации, меняя только один элемент за раз?

Ответ

Напишите код поиска субматрицы с максимально возможной суммой в матрице N*N, содержащей положительные и отрицательные числа.

Ответ

Сложная задача, требующая умения придумывать алгоритмы.

По условию требуется разработать алгоритм, позволяющий найти k-e число из упорядоченного числового ряда, в разложении элементов которого на простые множители присутствуют только 3, 5 и 7.

Решение с примерами кода на Java есть у нас на сайте.

Решение с примерами кода

Дан список из миллиона слов. Разработайте алгоритм, создающий максимально возможный прямоугольник из букв так, чтобы каждая строка и каждый столбец образовывали слово (при чтении слева направо и сверху вниз). Слова могут выбираться в любом порядке, строки должны быть одинаковой длины, а столбцы — одинаковой высоты.

Ответ

Дан массив с числами типа Integer. Вам нужно написать функцию, которая на входе получит исходный массив, а на выходе вернет массив, в котором каждое значение получено путем произведения всех значений исходного массива с отличным от текущего индексом.

Для ясности приведем пример. Допустим, исходный массив имеет вид:

Тогда функция должна вернуть:

Расчет значений происходит следующим образом:

Дополнительные условия:

  • Нельзя использовать деление.
  • Функция должна быть с наименьшими затратами памяти и времени выполнения.

Ответ

Задача на умение рассуждать. Конкретный ответ не важен, важно показать как вы мыслите. Представьте, что вам необходимо добраться из точки A в точку B, но вы не знаете, как. Как вы будете действовать?

Ответ

Представьте, что вам дали задание разработать план эвакуации большого города (в классическом варианте — Сан-Франциско). С чего вы начнете?

Ответ

Задача, которую предлагали на собеседованиях в Apple: у вас есть массив с целыми числами, в том числе и отрицательными, вам нужно найти самое большое произведение 3 чисел из этого массива.

Например: у вас есть массив list_of_ints, содержащий числа -10, -10, 1, 3, 2. Функция, которая обрабатывает этот массив, должна вернуть 300, так как -10 * -10 * 3 = 300. Задание нужно выполнить максимально эффективно, не забывая учесть отрицательные числа.

Ответ

Представьте страну, где все родители хотят иметь мальчика. Каждая семья продолжает рожать детей до тех пор, пока у них не появляется мальчик, а затем останавливается. Каково соотношение мальчиков и девочек в этой стране?

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

Как обычно, предлагаем порассуждать над решением в комментариях. Проверить свой ответ можно на сайте по прикреплённой ссылке, там мы даём наш вариант решения.

Ответ

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

Сколько флаконов шампуня производится в мире за год? Ответ

Сколько насечек на ребре четвертака — монеты в 25 центов? Ответ

Сколько насечек на ребре четвертака — монеты в 25 центов? Ответ

Сколько будет 2 в 64 степени? Ответ

Сколько туалетной бумаги потребуется, чтобы покрыть ею весь штат? Ответ

Сколько атомов резины стираются с шины автомобильного колеса при каждом его обороте? Ответ

Также смотрите примеры других задач для самостоятельного решения.

Задача, которую давали на собеседованиях в Apple. От вас требуется написать функцию, которая возвращает максимальную прибыль от одной сделки с одной акцией (сначала покупка, потом продажа). Исходные данные — массив вчерашних котировок stock_prices_yesterday с ценами акций Apple.
Информация о массиве:

  • Индекс равен количеству минут с начала торговой сессии (9:30 утра).
  • Значение в массиве равно стоимости акции в это время.

Например: если акция в 10:00 утра стоила 20 долларов, то
stock_prices_yesterday[30] = 20.

Допустим, имеем некоторые условия:

Массив может быть любым, хоть за весь день. Нужно написать функцию get_max_profit как можно эффективнее — с наименьшими затратами времени выполнения и памяти.

Ответ

Задача про слияние промежутков в календаре.

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

Те периоды, когда команда занята, на календаре отмечены как диапазоны времени, например, с 10:00 до 12:30 или с 12:30 до 13:00. В разрабатываемой программе промежуток времени представлен в виде кортежей из двух целых чисел. Число означает номер 30-минутного блока, который идет после 9:00 утра. Например, кортеж (2, 4) означает диапазон с 10:00 до 11:00, а (0, 1) — это промежуток 9:00-9:30.

Вам нужно написать функцию, которая должна упростить вывод информации таким образом, что если команда занята в промежутках с 10:00 до 12:30 и с 12:30 до 13:00, то это отображалось как 10:00‒13:00. Например: на входе вашей функции неупорядоченный массив из кортежей [(0, 1), (3, 5), (4, 8), (10, 12), (9, 10)], а на выходе вы должны получить упорядоченный массив [(0, 1), (3, 8), (9, 12)].

В будущем планируется внести изменения в программу, где вместо 30-минутных блоков будут минутные, как это реализовано в представлении Unix-времени. С учетом этого изменения нужно, чтобы ваша функция уже сейчас могла работать с большими числами. Еще не забудьте, что кортеж — это такой тип данных, в котором содержимое переменной невозможно изменять после ее создания.

Ответ

Задача, которую давали на собеседованиях в Apple. Представьте, что вы получили работу кассира в магазине. Ваш босс случайно выяснил, что вы обладаете навыками программиста, и захотел, чтобы вы помогли ему написать программу.

Входные данные:

  1. Указанная сумма денег.
  2. Массив со всеми доступными номиналами монет.

Нужно написать функцию, которая на выходе выдаст количество всех возможных способов получить указанную сумму денег при помощи различных доступных номиналов монет. Например, если вам нужно получить 4 цента из монет номиналами 1, 2 и 3 цента, то функция вернет 4 — именно столько есть возможных комбинаций из чисел 1, 2 и 3, чтобы получить в сумме 4:

  1. 1, 1, 1, 1.
  2. 1, 1, 2.
  3. 1, 3.
  4. 2, 2.

Ответ

Эту задачу когда-то давали в Google.

Вам нужно подняться по лестнице. За один раз можно подняться на одну или две ступеньки. Сколько существует способов добраться до N-й ступеньки?

Ответ

Эту задачу задавали на собеседовании в Twitter.
Рассмотрим следующую картинку:

1-9BE6dgt1cTDOHZSON7mlzQ

На этой картинке изображены стены различной высоты в некотором плоском мире. Картинка представлена массивом целых чисел, где индекс — это точка на оси X, а значение каждого индекса — это высота стены (значение по оси Y). Картинке выше соответствует массив [2, 5, 1, 2, 3, 4, 7, 7, 6].

Теперь представьте, что начался дождь, который не прекращается и поливает стены сверху равномерным потоком. Сколько воды соберется в «лужах» между стенами?

1-MKQZbWOdLPK-DD10Y48fkQ

Единицей объема воды считаем квадратный блок 1×1. На картинке выше всё, что расположено слева от точки 1, выплескивается. Вода справа от точки 7 также прольется. У нас остается лужа между 1 и 6 — таким образом, получившийся объем воды равен 10.

Ответ

Задача про бесконечный поезд.

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

Все вагоны внутри выглядят строго одинаково, окна закрыты так, что невозможно посмотреть наружу, движение поезда равномерное. Помечать вагоны как-либо, кроме включения или выключения света, нельзя. Количество вагонов конечно (не верьте названию задачи).

Ответ

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

Расположение переключателей случайное, порядок подключения заранее неизвестен. Зайдя в комнату, можно делать с лампочками всё, что угодно, но уже нельзя вернуться к переключателям. Изначально все лампы выключены.

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

У лампочек при начальных условиях есть только два состояния: горит или не горит. Понятно, что этого недостаточно, чтобы разделить их на три группы. Вам нужно придумать какие-то ещё состояния лампочек и способ их добиться переключателями.

Или смотрите сразу ответ

Классическая задача. Найдите в данной вам строке максимальную по длине подстроку, которая является палиндромом (то есть читается слева направо и справа налево одинаково). Предложите как можно более эффективный алгоритм.

Ответ

Реализуйте функцию извлечения квадратного корня, не пользуясь встроенными в язык средствами нахождения корня и возведения в степень.

Ответ

В этой задаче вам необходимо реализовать функцию, которая бы проверяла число на четность, используя только битовые операции AND, OR, NOT.

Ответ

На прямой даны N отрезков (в реальной жизни это могут быть промежутки времени, например), которые заданы координатами их левого и правого конца. Для каждого данного отрезка необходимо узнать, сколько из данных отрезков полностью находятся в нем. Один отрезок полностью содержится во втором, если левый конец первого отрезка находится правее левого конца второго отрезка, а правый конец первого находится левее правого конца второго. Предложите как можно более эффективный способ решения этой задачи. Гарантируется, что все концы данных отрезков различны.

Если вы придумали решение, то написать и проверить его вы можете здесь, на codeforces.

Сможете ли вы решить эффективно данную задачу в случае, если концы отрезков могут совпадать?

Ответ

Также рекомендуем по теме: