GrabDuck

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

:

20.01.2016 | Автор: tproger.ru  

Коллеги (проект «Типичный программист») собрали в своей  рубрике c задачами уже более 80 вопросов с подробным разбором решений. Они решили собрать их всех в единый список, чтобы вам было удобнее готовиться и прорешивать их.

 

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

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

Показать ответ

Свернуть

 

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

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

Показать ответ

Свернуть

 

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

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

  • Уменьшится?
  • Увеличится?
  • Не изменится?

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

Обычно после прочтения задачи возникает желание заявить, что влиянее ветра в целом нулевое. Встречный ветер замедлит движение в одном направлении, но в обратном пути он будет дуть вам в спину, что позволит преодолеть путь быстрее. В целом это так, но будет ли при этом время полёта таким же?

Показать ответ

Свернуть

 

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

operator int() const {
    return *this;
}

 

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

Вот один из возможных ответов на эту задачу. Последовательности сопоставлены буквы алфавита, закодированные в набор «П» и «К» — некоторых характеристик. Нужно найти что-то, чего в букве А три, в Б — две и т.д.

Показать ответ

Свернуть

 

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

Приведём один из вариантов возможных рассуждений. Любой инженер знает, что 210 = 1024. Будем считать, что это приблизительно 1000. Умножим 210 на себя шесть раз и получим 260.

Показать ответ

Свернуть

 

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

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

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

Показать ответ

Свернуть

 

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

Те, кто столкнулись с этой ошибкой в живом проекте и не знали про неё ранее, наверняка потратили немало времени на отлов этого бага. Разберём его по полочкам.

Показать ответ

Свернуть

 

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

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

Показать ответ

Свернуть

 

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

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

Показать ответ

Свернуть

 

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

Ответ на самом деле очень прост: string — это просто псевдоним (alias) для System.String т.е. технически, никакой разницы нет.

Показать ответ

Свернуть

 

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

 

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

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

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

Показать ответ

Свернуть

 

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

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

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

 

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

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

Показать ответ

Свернуть

 

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

unsigned int i;
for (i = 100; i >= 0; --i)
    printf("%d\n", i);

 

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

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

Вернемся к «истокам».

Что означает A & B == 0?

Это означает, что А и B не содержат на одних и тех же позициях единичных битов.

Свернуть

Показать ответ

 

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

Обратите внимание, что независимо от того, с какого этажа мы бросаем яйцо №1, бросая яйцо №2, необходимого использовать линейный поиск (от самого низкого до самого высокого этажа) между этажом «повреждения» и следующим наивысшим этажом, при броске с которого яйцо останется целым.

Показать ответ

Свернуть

 

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

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

Показать ответ

Свернуть

 

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

Чтобы найти нужный элемент, можно воспользоваться бинарным поиском по каждой строке. Алгоритм потребует O(M log(N)) времени, так как необходимо обработать М столбцов, на каждый из которых тратится O(log(N)) времени. Также можно обойтись и без сложного бинарного поиска. Мы разберем два метода.

Показать ответ

Свернуть

 

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

Самый распространенный вариант реализации функции max — проверка знака выражения a - b. В этом случае мы не можем использовать оператор сравнения, но можем использовать умножение.

Показать ответ

Свернуть

 

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

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

Показать ответ

Свернуть

 

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

Первое, что приходит в голову, — обработка битов. Почему? У нас нет выбора — нельзя использовать оператор «+». Так что будем суммировать числа так, как это делают компьютеры!

Показать ответ

Свернуть

 

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

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

Топлива хватит, чтобы отправить каждый из 50-ти  грузовиков на расстояние 100 км, то есть  на расстояние 50*100 = 5000 км. Но возможно ли считать 5000 км ответом? Нет, если только у вас нет способа, позволяющего телепортировать топливо из бака одного грузовика в другой. Вспомните, что каждый грузовик полностью заправлен и пока топливо не израсходовано, добавить его нельзя.

Показать ответ

Свернуть

 

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

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

Показать ответ

Свернуть

 

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

 

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

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

Исаак Ньютон и Христиан Гюйгенс обсуждали этот вопрос в 1600-е годы, но так и не дали на него исчерпывающий ответ. Три столетия спустя два химика из Университета Миннесоты, Брайан Геттельфингер и Эдвард Касслер проделали эксперимент для сравнения сиропа и воды. Может быть, не стоит удивляться, что его проведение заняло много времени. Касслер рассказал, что ему потребовалось получить 22 согласования, в том числе и разрешение на то, чтобы затем вылить большой объем сиропа в канализационную систему.

Показать ответ

Свернуть

 

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

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

Показать ответ

Свернуть

 

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

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

void produce() {
    // создаем задачу и кладем в очередь
}

void consume() {
    // читаем данные из очереди и обрабатываем
}

int main(int , char **) {
    std::thread thr(consume); // порождаем поток
    produce(); // создаем данные для обработки
    thr.join(); // ждем завершения работы функции consume()
    return 0;
}

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

Показать ответ

Свернуть

 

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

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

Показать ответ

Свернуть

 

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

С первого взгляда кажется, что это возможно. Доска 8×8, следовательно, есть 64 клетки, две мы исключаем, значит остается 62. Вроде бы 31 кость должна поместиться, правильно?

Показать ответ

Свернуть

 

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

В нашем распоряжении 232 (или 4 миллиарда) целых чисел. У нас есть 1 Гбайт памяти, или 8 млрд бит.
8 млрд бит — вполне достаточный объем, чтобы отобразить все целые числа. Что нужно сделать?

Показать ответ

Свернуть

 

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

Первая мысль — использовать рекурсивный подход, который строит решение для f(n), добавляя пары круглых скобок в f(n-1). Это, конечно, правильная мысль.

Показать ответ

Свернуть

 

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

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

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

Показать ответ

Свернуть

 

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

 

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

Это классическая задача, которую любят предлагать на собеседованиях, и она достаточно проста. Пусть a0 — это исходное значение a, а b0 — исходное значениеb. Обозначим diff разницу а0 - b0.

Показать ответ

Свернуть

 

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

Данный алгоритм можно реализовать рекурсивным и нерекурсивным способом. Рекурсивные решения обычно более понятны, но менее оптимальны. Например, рекурсивная реализация этой задачи почти в два раза короче нерекурсивной, но занимает O(n) пространства, где n – количество элементов связного списка.

Показать ответ

Свернуть

 

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

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

На первый взгляд кажется, что задача сложная, но фактически она очень проста. Чтобы решить ее, задайте себе вопрос: “Как узнать, какие биты в двух числах различаются?”. Ответ прост...

Показать ответ

Свернуть

 

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

У каждого числа, обозначающего страницу, имеется цифра на месте единиц. При N страниц имеется N цифр, стоящих на месте единиц.

У всех, за исключением первых 9 страниц, числа являются как минимум двухзначными. Поэтому добавим еще N-9 цифр.

Показать ответ

Свернуть

 

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

В хэш-таблицу значение попадает при вызове хэш-функции с ключом. Сами значения хранятся в неотсортированном порядке. Так как хэш-таблица использует ключ для индексации элементов, вставка или поиск данных занимает O(1) времени (с учетом минимального количества коллизий в хэш-таблицах).

Показать ответ

Свернуть

 

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

Существует несколько общих способов предотвратить мертвые блокировки. Один из самых популярных — обязать процесс явно объявлять, в какой блокировке он нуждается.

Показать ответ

Свернуть

 

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

Можно действовать прямо — подсчитать количество строк (N) и вывести строки с N-Kдо N. Для этого понадобится дважды прочитать файл, что очень неэффективно. Давайте найдем решение, которое потребует прочитать файл только один раз и выведет последние K строк.

Показать ответ

Свернуть

 

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

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

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

Показать ответ

Свернуть

 

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

Для начала нужно уточнить детали. Следует разобраться, является ли сравнение анаграмм чувствительным к регистру. То есть является ли строка «God» анаграммой «dog»? Также нужно выяснить, учитываются ли пробелы.

Показать ответ

Свернуть

 

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

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

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

Показать ответ

Свернуть

 

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

Итак, оценка времени работы функция push, pop и min — O(1).

Экстремумы изменяются не часто. Фактически минимум может поменяться только при добавлении нового элемента.

Показать ответ

Свернуть

 

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

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

Показать ответ

Свернуть

 

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

Сложность задачи заключается в том, что адресов дано 10 миллиардов. Сколько пространства понадобится для хранения 10 миллиардов URL-адресов? Если в среднем URL-адрес занимает 100 символов, а каждый символ представляется 4 байтами, то для хранения списка из 10 миллиардов URL понадобится около 4 Тбайт.

Показать ответ

Свернуть

 

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

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

Показать ответ

Свернуть

 

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

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

 

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

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

Итак, нам нужно сравнить две фразы. Для начала нам нужно их «обработать»: выбрать только буквы и перевести их в нижний регистр. Также, на этом шаге мы можем преобразовать строку в массив.

Показать ответ

Свернуть

 

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

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

Показать ответ

Свернуть

 

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

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

Показать ответ

Свернуть

 

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

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

Хороший способ решить эту задачу — устранить ограничения и сначала разобраться с упрощенной версией.

Показать ответ

Свернуть

 

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

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

Эта задача является разновидностью классической задачи, задаваемой на собеседованиях, – определить, содержит ли связный список петлю. Давайте используем подход «Сопоставление с образцом».

Показать ответ

Свернуть

 

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

Давайте используем подходы «базовый случай» и «сборка». Предположим, что на острове находится n людей и c из них — голубоглазые. Таким образом, мы знаем, что c > 0.

Показать ответ

Свернуть

 

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

Doubly_linked_list-870x295

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

Показать ответ

Свернуть

 

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

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

Давайте будем решать задачу «в лоб».

Показать ответ

Свернуть

 

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

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

Показать ответ

Свернуть

 

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

Число шариков становится все меньше и меньше с каждым ходом, и, в конце концов, их станет как-то совсем мало. Вот тут-то стратегия становится совершенно понятной.

Показать ответ

Свернуть

 

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

При правильном толковании термина «слияние» две компании отказываются от своей прежней индивидуальности и сливаются в новое образование, имеющее новый бренд. 

Показать ответ

Свернуть

 

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

Есть два способа интерпретации этого вопроса. Они приводят к разным ответам, и поэтому вам лучше спросить интервьюера, что он имеет в виду (или подготовить оба варианта ответов).

Показать ответ

Свернуть

 

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

Вы можете начать свой ответ с уточнения: спросите интервьюера, следует ли считать «самой быстрой лошадью» ту, которая выигрывает конкретную скачку. 

Показать ответ

Свернуть

 

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

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

Показать ответ

Свернуть

 

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

Факториал одной сотни записывается как 100! Это произведение всех натуральных чисел до ста включительно.

Показать ответ

Свернуть

 

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

Это довольно сложная, но очень популярная задача. Давайте решим ее на примере массива:

2 3 -8 -1 2 4 -2 3

Показать ответ

Свернуть

 

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

Одно из возможных решений — использовать две кучи разных приоритетов: максимальная куча (maxHeap) для значений выше среднего и минимальная куча(minHeap) для значений ниже среднего.

Показать ответ

Свернуть

 

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

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

Показать ответ

Свернуть

 

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

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

Эту задачу также можно решить двумя способами: простым и сложным. Давайте рассмотрим оба решения.

Показать ответ

Свернуть

 

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

Самый плотный из возможных вариантов — чередование клиентов и пустых мест, при котором оба крайних места заняты.

Показать ответ

Свернуть

 

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

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

Показать ответ

Свернуть

 

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

Это рекурсивная задача, поэтому давайте разберемся, как рассчитать makeChange(n), основываясь на предыдущих решениях (подзадачах).

Показать ответ

Свернуть

 

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

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

Давайте считать, что порядок появления слов word1 и word2 не важен. Этот вопрос нужно согласовать с интервьюером. Если порядок слов имеет значение, нужно будет модифицировать приведенный далее код.

Показать ответ

Свернуть

 

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

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

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

Показать ответ

Свернуть

 

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

Если бы мы работали с массивом, то было бы много сложностей, связанных со смещением элементов.

Со связным списком задача намного проще. 

Показать ответ

Свернуть

 

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

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

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

Показать ответ

Свернуть

 

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

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

Нам нужно подсчитать количество вариантов прохождения дистанции с Х шагов вправо и Y шагов вниз (X + Y шагов).

Показать ответ

Свернуть

 

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

public String compressBad(String str) {
    String mystr = "";
    char last = str.charAt(0);
    int count = 1;
    for (int i = 1; i < str.length(); i++) {
        if (str.charAt(i) == last) { // Находим повторяющийся символ
            count++;
        } else {    // Вставляем счетчик символа и обновляем последний символ
            mystr += last + count;
            last = str.charAt(i);
            count = 1;
        }
    }
    return mystr + last + count;
}

Этот код не отслеживает случай, когда сжатая строка получается длиннее исходной. Но эффективен ли этот алгоритм?

Показать ответ

Свернуть

 

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

car

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

  • Переместится назад, против движения
  • Останется на месте
  • Переместится вперёд, по движению

Интуиция подсказывает нам (практически всем), что при ускорении шарик будет отбрасываться назад. Однако интуиция в данном случае ошибается. 

Показать ответ

Свернуть

 

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

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

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

При использовании RSA генерируется два ключа: общественный и частный. Общественный ключ похож на адрес электронной почты. Он позволяет любому человеку отправить вам сообщение.

Показать ответ

Свернуть