Задачи с собеседований для разработчиков в IBM, Amazon и Microsoft

Собрали отзывы о собеседованиях на должности разработчиков ПО в IBM, Amazon и Microsoft с сайта Coding Ninjas.

Соискатели рассказали, как готовились к интервью, какие задачи решали на первых раундах и на какие вопросы отвечали перед HR.

Собеседование в Amazon

Автор этого отчета последовательно готовился к собеседованию в “большую пятерку” FAANG еще с обучения в бакалавриате. Также он писал свой диплом так, чтобы он казался более значимым в глазах собеседующих. На подготовку к собеседованиям у автора ушло 3 года, и его взяли на работу.

Советы

1. Решайте все задачи по теме “Конкурентное программирование”. Также стоит регулярно решать задачки с сайтов как Leetcode, Interviewbit и Codeforces.
2. Регулярно занимайтесь конкурсным программированием.
3. Постоянно обновляйте свое резюме. В нем должны быть хотя бы 2-3 проекта хорошего уровня, чтобы впечатлить интервьюера.
4. Не врите в резюме.

Раунд 1

1. Рассчитать объем воды

Дан массив ‘arr’ типа long размера ‘n’. При этом ‘arr[i]’ обозначает высоту столбца ‘i’.

Рассчитайте объем воды, который можно было бы собрать, если бы из столбцов массива можно было собрать фигуру. Ширина каждого столбца одинакова и равна 1.

Например, ‘n’ = 6, ‘arr’ = [3, 0, 0, 2, 0, 4]. Тогда ответом будет 10.

Нам нужно реализовать функцию, которая высчитывала бы:

1. В первой строке целое число ‘n’, обозначающее размер массива/списка.
2. Во второй строке ‘n’ целых чисел, разделенных пробелами, представляющих высоту столбиков.

Вывод должен содержать целое число, обозначающее количество воды, которое может быть собрано.

2. Реализация LRU-кеша

Разработать и реализовать структуру данных для LRU-кеша для поддержки следующих операций:

1. get(key) – Возвращает значение кэша, если он есть в памяти. В противном случае, функция должна вернуть -1.
2. put(key, value) – Вставить значение в кэш, если ключа еще не существует, или обновить значение ключа, если ключ уже существует. Перед обновлением элемента кэш должен удалить последнее использованное значение.

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

Первая строка ввода должна содержать два разделенных пробелом целых числа ‘C’ и ‘Q’, обозначающих емкость кэш-памяти и количество выполняемых операций соответственно.

Следующие ‘Q’ строк содержат операции, по одной на строку. Каждая операция начинается с целого числа, обозначающего тип операции.

Если число равно 0, то операция относится к первому типу, и за ней следует один целочисленный ключ.

Если число равно 1, то операция относится ко второму типу, и за ней следуют два целых числа key и value (в таком порядке), разделенные пробелами.

Для каждой операции типа 0 выведите целое число в одной строке, которое обозначало бы значение ключа, если ключ существует, или -1.

Значение Q не меньше 1 и не больше 10^4. Значение C не меньше 1 и не больше 10^5. В выводе не может быть значения меньше 1 и больше 10^9. Время выполнения операции не должно превышать секунды.

Раунд 2

На этом раунде присутствовал HR, разговор происходил наедине в Google Meet. Вопросы от HR:

1. Кто является для вас примером для подражания?
2. Что вы ожидаете от этой работы?

Собеседование в IBM

Автор этого отзыва готовился к интервью 4 месяца.

Советы

1. Отработайте не менее 250 вопросов по программированию и разберитесь с концепциями ОС, сетей и баз данных.
2. В резюме должно быть не менее двух хороших проектов.
3. Изучите нюансы конкретной компании перед тем, как прийти на интервью.
4. Не врите в резюме.

Раунд 1

1. Сортировка массива

Вам дан массив ‘arr’, состоящий из ‘n’ элементов. Каждый элемент массива равен 0, 1 или 2. Отсортируйте элементы массива в порядке возрастания. Не создавайте новый массив, просто внесите изменения в существующий.

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

Сперва автор использовал метод сортировки, но интервьюер попросил его не делать этого. Тогда автор просто написал функцию, которая запоминает количество 0, 1 и 2 в массиве.

2. Задача об отрезании веревки

Дана веревка длиной ‘N’ единиц. Она может быть разрезана на части различной длины, и каждый отрезок имеет свою стоимость. Определите максимальное количество вариантов, на которые можно разрезать веревку, вместе с ценами на каждый отрезок.

Размеры отрезков могут варьироваться от 1 до N. При этом сумма отрезков должна равняться N.

Первая строка ввода должна содержать целое число ‘N’, обозначающее длину веревки.

Вторая строка должна содержать вектор ‘A’ размера ‘N’, который показывает стоимость получившихся отрезков, где каждый индекс массива – это поддлина, а элемент с этим индексом – стоимость для этой поддлины.

Поскольку длина отрезка не может равняться 0, то нулевой индекс вектора будет представлять первую поддлину отрезка. Следовательно, индекс N-1 будет представлять стоимость для длины ‘N’.

Раунд 2

Интервьюер спрашивал о проектах, и автор рассказал о них. Затем интервьюер задал несколько вопросов по концепциям ОС.

Вопросы HR:

1. Какие ваши сильные и слабые стороны?
2. Кем вы видите себя через 5 лет?

Собеседование в Microsoft

Автор готовился к собеседованию в течение полугода. В частности, автор решил сделать упор на СУБД и объектно ориентированное программирование.

Советы

1. Практикуйтесь в вопросах по структурам данных и алгоритмам. Можете тренироваться на InterviewBit и выполнять все задания по структурам данных и алгоритмам, которые задают на последних интервью.
2. Решайте задачи на Leetcode. Также стоит участвовать в еженедельных конкурсах, чтобы знать, какие ваши слабые места нужно улучшить.
3. Также стоит изучить основные понятия операционных систем и баз данных.
4. Проведите исследование целей компании и будьте готовы задать некоторые вопросы, связанные с компанией, которые покажут ваш интерес к компании.
5. Ваше резюме должно состоять в основном из навыков, проектов и достижений.
6. Никогда не лгите в своем резюме.

Раунд 1

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

1. Ближайшее число, кратное 10

Вам дано целое число N. Найдите ближайшее к нему число, кратное 10. Если расстояние до чисел равное, выберите меньшее из них. К примеру, если дано число 3, то правильными ответами будут и 30, и 40. В этом случае стоит вывести 30.

2. Вычислить день недели

Напишите функцию, которая вычисляет день недели для любой даты в прошлом или будущем. К примеру, 28 августа 2020 года приходится на пятницу. Следовательно, ответ должен быть “Пятница”.

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

Вывод должен содержать значения из списка {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}.

Также есть ограничения по вводу: число дней не должно превышать 31, число месяцев не должно превышать 12, а год не должен превышать 2,000,000. Кроме того, все эти значения не могут быть меньше 1.

3. Удалить N значений после M значений

У вас есть список и два целых числа «N» и «M». Нужно удалить «N» узлов в списке после количества узлов «M». Иными словами, нужно отсчитать M узлов, после чего удалить N узлов, и так до конца списка.

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

Вторая строка должна содержать два целых числа ‘N’ и ‘M’, разделенных одним пробелом.

Вывод должен содержать итоговый список.

Раунд 2

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

1. Найти элемент последовательности

Есть последовательность: 1, 11, 21, 1211, 111221, 312211, 13112221,...

Она строится так. Первое число читается как “один один”, точнее, как “one One”. Значит, и второе число будет “one one”, то есть 11. Число 11 читается как “two One”, то есть третье число будет равно 21. Число 21 читается как “one Two one One”, то есть четвертое число будет равно 1211. И так далее.

Нужно написать код, который позволял бы найти N элемент последовательности. При этом N должно быть не меньше 1 и не больше 40.

2. Составить самое большое число из элементов массива

Вам дан массив ‘ARR’ длины N, состоящий из неотрицательных целых чисел. Используя только эти заданные числа, переставьте их так, чтобы из них составлялось максимально возможное число.

К примеру, задан массив с элементами ’32’, ‘8’, ’29’. Вы должны расположить числа в порядке ‘8’, ’32’, ’29’. Тогда из них можно будет составить максимальное число 83229. Порядок цифр внутри элементов массива изменить нельзя.

Раунд 3

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

1. Упростить путь к файлу

Вам дан путь к файлу/каталогу в стиле Unix длиной N. В файловой системе в стиле Unix точка (.) относится к текущему каталогу. Двойная точка (..) относится к предыдущему каталогу относительно текущего каталога. Если между двумя каталогами имеется несколько косых черт, вы должны превратить их в одну косую черту.

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

Упрощенный путь всегда должен начинаться с косой черты (/), а между именами двух каталогов должна быть одна косая черта. На конце пути не должно быть косой черты.

Ввод должен содержать число Т, которое указывает, сколько каталогов на пути к файлу нужно отобразить. Кроме того, Т не может быть меньше 1 и больше 100.

2. Упростить полином

В странах бывшего СССР полином называют многочленом. Вам дается полином. К примеру, это будет 5x^3 + 2x^3 + 6x^4 + 2. Нужно упростить его.

Количество элементов полинома не должно быть равно нулю и превышать 10, а степени чисел и коэффициенты не должны превышать 10^5.

Раунд 4

На этом этапе интервьюер спрашивал соискателя о его проектах. Вопросы интервьюера:

1. Расскажите обо всех своих проектах.
2. Какая структура у ваших проектов?
3. Как вы проходили летнюю стажировку?
4. Что такое линейная регрессия?

Раунд 5

Этап собеседования с HR. Вопросы:

1. Что такое СУБД?
2. Объясните ACID.
3. Объясните двухуровневую и трехуровневую архитектуру СУБД.
4. Что такое независимость от схемы в СУБД?

Заключение

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

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