Рубрики

Amazon Интервью | Набор 57 (вне кампуса для SDE-1)

Привет, гики, я недавно нанял Амазонку. Я просто хочу поделиться своим опытом интервью со всеми вами.

Всего 1 написано + 5 F2F

Письменный тур:
Q1: конвертировать отсортированный целочисленный массив в сбалансированное двоичное дерево поиска . Это очень просто, и я мог бы сделать это за O (n) времени и O (1) дополнительного пространства.

Q2: Напишите программу, которая будет переворачивать каждые k узлов односвязного списка без использования дополнительного пространства. Ограничение: k> = 2

F2F раунд 1:
Q1: Найти самый большой элемент в отсортированном повернутом целочисленном массиве за время o (log n).

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

В3: Найдите свой собственный метод для балансировки несбалансированного двоичного дерева (вы не должны использовать существующие методы, такие как AVL, красный черный или b деревья).
Подсказка: нет ограничений на размещение узлов. Вы можете удалить любой узел из любого места и поместить его в любое место.
Я разработал алгоритм, который будет использовать два списка. Один список содержит узлы, удаленные от корня, и они отсортированы в порядке убывания уровней и слева направо, если узлы находятся на одном уровне. Другой список содержит узлы, которые не полностью заполнены. Это сортируется в порядке возрастания уровней и слева направо, если узлы находятся на одном уровне.
Удалите первый узел (перечисленный в list1) и вставьте в качестве дочернего узла первого узла в list2.dd этот узел также в списке 2. Выполняйте эту операцию, пока высота дерева не станет log (n). Интервьюер был впечатлен этим и закончил интервью.

F2F раунд 2:
Q1: есть файл, который содержит N слов. В этом файле может быть M анаграмм, по K слов в каждой анаграмме. K> = 1, M> = 1, N> = 1. Вам нужно написать алгоритм, который создаст один список для каждой анаграммы с k словами и сгруппирует все M списков с одной структурой данных (это основная область. Нам нужно продумать структуру данных, которая минимизирует пространственную и временную сложность слова Поиск подходящего списка и вставка слова).
Я мог бы сделать вставку за O (1) времени, отслеживая указатель хвоста в каждом списке. Но для поиска соответствующего списка необходимо o (n) в случае связанного списка, o (log (n)) в случае бинарного дерева поиска. Используя хеш-таблицу, вы можете сделать это в o (1), но написание хеш-функции сложно и неэффективно с точки зрения времени. Затем я предложил структуру данных Trie. Благодаря этому мы можем значительно сократить временную сложность. Но космическая сложность будет больше. Я рассказал все идеи интервьюеру. Они были очень довольны этим. И перешел к следующему вопросу (без написания кода J)

Q2: Найти минимальный и максимальный элемент несортированного целочисленного массива.
Очень простой вопрос, вы можете сделать два прохода по массиву и найти его, но количество сравнений будет o (2n). Он попросил меня уменьшить его.
Я дал алгоритм, который будет делать то же самое в O ((n / 2) * 3), который значительно меньше, чем o (2n). Они были впечатлены моим решением и спросили, есть ли у меня вопрос.

F2F раунд 3: (основы CS и системное программирование)
Вопросы касались шаблонов C ++, сетевого программирования, Linux, так как я занимался проектированием сетей, Linux, я мог хорошо выступить в этом раунде.

F2F раунд 4: (Раунд менеджера по найму):
Интервьюер был заинтересован в тестировании культурного соответствия. Почти от 10 до 15 вопросов о моем предыдущем проекте,
Почему амазонка?
Почему вы хотите покинуть предыдущую компанию?
Какую инициативу вы взяли в предыдущей компании?
Как вы будете управлять конфликтом с вашим менеджером?
Как вы будете демонстрировать ваш продукт покупателю?

F2F раунд 5: (рейзер бара)
У этого также были вопросы культурного соответствия и затем вопрос структуры данных.
Qn: Найти расстояние между двумя узлами в двоичном дереве , родительские указатели не указываются. Я мог бы решить это в прохождении после заказа в o (n) сложности времени. Он попросил меня написать код дома и отправить по почте.

Вундеркинды для гиков — моя Википедия для подготовки к интервью. Спасибо гикам за гиков.

Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Все проблемы с практикой для Amazon !

Напишите свой опыт интервью или отправьте его по электронной почте на адрес contrib@geeksforgeeks.org

Рекомендуемые посты:

Amazon Интервью | Набор 57 (вне кампуса для SDE-1)

0.00 (0%) 0 votes