14 самых популярных вопросов на собеседовании по программированию на Amazon

Практикуйте эти вопросы по кодированию, чтобы отличиться от других!

Будучи крупнейшим в мире онлайн-рынком и поставщиком облачных услуг, Amazon — работодатель мечты. Устроиться на работу в Amazon — мечта многих разработчиков программного обеспечения.

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

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

В этом посте будут рассмотрены наиболее распространенные вопросы по программированию на Amazon. Я собрал эти данные из GlassDoor, LeetCode и CareerCup. Ответы на эти вопросы вы можете посмотреть в Grokking the Coding Interview или LeetCode.

1. Самый большой остров (легко)

Учитывая двумерный массив (то есть матрицу), содержащий только 1s (суша) и 0s (вода), найдите в нем самый большой остров. Напишите функцию, которая возвращает площадь самого большого острова.

Остров — это связанный набор 1s (суши), окруженный либо краем, либо 0s (водой). Каждая ячейка считается соединенной с другими ячейками по горизонтали или вертикали (не по диагонали).

Example 1
Input: matrix =

Output: 5
Explanation: The matrix has three islands. The biggest island has 5 cells.

2. «K» ближайших точек к началу координат (легко)

Учитывая массив точек на 2D-плоскости, найдите «K» ближайших точек к началу координат.

Example 1:
Input: points = [[1,2],[1,3]], K = 1
Output: [[1,2]]
Explanation: The Euclidean distance between (1, 2) and the origin is sqrt(5). The Euclidean distance between (1, 3) and the origin is sqrt(10). Since sqrt(5) < sqrt(10), therefore (1, 2) is closer to the origin.

Example 2:
Input: point = [[1, 3], [3, 4], [2, -1]], K = 2
Output: [[1, 3], [2, -1]]

3. Правильное представление бинарного дерева (легко)

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

4. Количество островов (среднее)

Дан двумерный массив (т. е. матрица), содержащий только единицы (суша) и нули (вода), подсчитайте количество островов в нем.

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

Example 1
Input: matrix =

Output: 1
Explanation: The matrix has only one island. See the highlighted cells below.

Example 2
Input: matrix =

Output: 3
Explanation: The matrix has three islands. See the highlighted cells below.

5. Объединить отсортированные списки «К» (средний уровень)

Учитывая массив связанных списков, отсортированных по «K», объедините их в один отсортированный список.

Example 1:
Input: L1=[2, 6, 8], L2=[3, 6, 7], L3=[1, 3, 4]
Output: [1, 2, 3, 3, 4, 6, 6, 7, 8]
Example 2:
Input: L1=[5, 8, 9], L2=[1, 7]
Output: [1, 5, 7, 8, 9]

6. Планирование задач (средний)

Есть «N» задач, помеченных от «0» до «N-1». Каждая задача может иметь некоторые предварительные задачи, которые необходимо выполнить, прежде чем ее можно будет запланировать. Учитывая количество задач и список обязательных пар, выясните, возможно ли запланировать все задачи.

Example 1:
Input: Tasks=3, Prerequisites=[0, 1], [1, 2]
Output: true
Explanation: To execute task '1', task '0' needs to finish first. Similarly, task '1' needs to finish before '2' can be scheduled. One possible scheduling of tasks is: [0, 1, 2]
Example 2:
Input: Tasks=3, Prerequisites=[0, 1], [1, 2], [2, 0]
Output: false
Explanation: The tasks have a cyclic dependency, therefore they cannot be scheduled.
Example 3:
Input: Tasks=6, Prerequisites=[2, 5], [0, 5], [0, 4], [1, 4], [3, 2], [1, 3]
Output: true
Explanation: A possible scheduling of tasks is: [0 1 4 3 2 5]

7. Медиана числового потока (средняя)

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

1. insertNum(int num): сохраняет число в классе
2. findMedian(): возвращает медиану всех чисел, вставленных в класс.

Если количество чисел, вставленных в класс, четное, медиана будет средним значением двух средних чисел.

Example:
 1. insertNum(3)
 2. insertNum(1)
 3. findMedian() -> output: 2
 4. insertNum(5)
 5. findMedian() -> output: 3
 6. insertNum(4)
 7. findMedian() -> output: 3.5

8. Интервалы слияния (средние)

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

Example:
Intervals: [[1,4], [2,5], [7,9]]
Output: [[1,5], [7,9]]
Explanation: Since the first two intervals [1,4] and [2,5] overlap, we merged them into one [1,5].

9. Зигзагообразный обход (средний)

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

Пример 1:

Пример 2:

10. Лучшие «K» частые номера (средние)

Учитывая несортированный массив чисел, найдите в нем первые «K» часто встречающихся чисел.

Example 1:
Input: [1, 3, 5, 12, 11, 12, 11], K = 2
Output: [12, 11]
Explanation: Both ‘11’ and ‘12’ appeared twice.
Example 2:
Input: [5, 12, 11, 3, 11], K = 2
Output: [11, 5] or [11, 12] or [11, 3]
Explanation: Only ‘11’ appeared twice, all other numbers appeared once.

11. Минимум конференц-залов (жесткий)

Имея список интервалов, представляющих время начала и окончания N встреч, найдите минимальное количество комнат, необходимое для проведения всех встреч.

Example 1:
Meetings: [[1,4], [2,5], [7,9]]
Output: 2
Explanation: Since [1,4] and [2,5] overlap, we need two rooms to hold these two meetings. [7,9] can occur in any of the two rooms later.
Example 2:
Meetings: [[4,5], [2,3], [2,4], [3,5]]
Output: 2
Explanation: We will need one room for [2,3] and [3,5], and another room for [2,4] and [4,5].
 
Here is a visual representation of Example 2:

12. Сбалансированные скобки (жесткие)

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

Example 1:
Input: N = 2
Output: (()), ()()
Example 2:
Input: N = 3
Output: ((())), (()()), (())(), ()(()), ()()()

13. Самая длинная подстрока с различными символами (сложно)

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

Example 1:
Input: String="aabccbb"
Output: 3
Explanation: The longest substring with distinct characters is "abc".
Example 2:
Input: String="abbbb"
Output: 2
Explanation: The longest substring with distinct characters is "ab".
Example 3:
Input: String="abccde"
Output: 3
Explanation: Longest substrings with distinct characters are "abc" & "cde".

14. Инопланетный словарь (сложный)

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

Example 1:
Input: Words: [“ba”, “bc”, “ac”, “cab”]
Output: bac
Explanation: Given that the words are sorted lexicographically by the rules of the alien language, so from the given words we can conclude the following ordering among its characters:
 
 1. From “ba” and “bc”, we can conclude that ‘a’ comes before ‘c’.
 2. From “bc” and “ac”, we can conclude that ‘b’ comes before ‘a’
 
From the above two points, we can conclude that the correct character order is: “bac”
Example 2:
Input: Words: [“cab”, “aaa”, “aab”]
Output: cab
Explanation: From the given words we can conclude the following ordering among its characters:
 
 1. From “cab” and “aaa”, we can conclude that ‘c’ comes before ‘a’.
 2. From “aaa” and “aab”, we can conclude that ‘a’ comes before ‘b’
 
From the above two points, we can conclude that the correct character order is: “cab”
Example 3:
Input: Words: [“ywx”, “wz”, “xww”, “xz”, “zyy”, “zwz”]
Output: ywxz
Explanation: From the given words we can conclude the following ordering among its characters:
 
 1. From “ywx” and “wz”, we can conclude that ‘y’ comes before ‘w’.
 2. From “wz” and “xww”, we can conclude that ‘w’ comes before ‘x’.
 3. From “xww” and “xz”, we can conclude that ‘w’ comes before ‘z’
 4. From “xz” and “zyy”, we can conclude that ‘x’ comes before ‘z’
 5. From “zyy” and “zwz”, we can conclude that ‘y’ comes before ‘w’
 
From the above five points, we can conclude that the correct character order is: “ywxz”

Заключение

Интервью по программированию Amazon включают вопросы типа LeetCode. Подготовьтесь с умом и сосредоточьтесь на вышеупомянутых проблемах кодирования, чтобы увеличить свои шансы на успех. Вы можете узнать больше об этих вопросах в Grokking the Coding Interview.

➡ Подпишитесь на меня в Linkedin, чтобы получать советы по проектированию системы и интервью по программированию.

Подробнее об интервью по кодированию:

Спасибо за прочтение

• 👏 Пожалуйста, хлопайте в историю и подписывайтесь на меня 👉
• 📰 Посмотреть больше материалов на Интервью по кодированию и проектированию систем
• 🔔 Подпишитесь на меня: LinkedIn| Твиттер| "Новостная рассылка"