Опыт собеседования с Amazon | Комплект 174 (для SDE)

Недавно я прошел собеседование на должность SDE в Центре разработки Amazon, Ченнаи. Вот мой опыт интервью:

Телефонный раунд:
1) Учитывая массив с длинами, вы должны выбрать 3 длины (a, b и c) для треугольника, чтобы он удовлетворял условию a + b> c, b + c> a, a + c> b. Найдите количество возможных треугольников, которые можно создать из данного массива.
пример: 3 5 6 9 10
(3,9,10), (3 5 6), (5 6 10), (5 9 10), (5 6 9), (6 9 10)
поэтому количество возможных треугольников равно 6

2) Считайте инверсии в массиве
Счетчик инверсий для массива указывает - насколько далеко (или близко) массив от сортировки. Если массив уже отсортирован, счетчик инверсии равен 0. Если массив отсортирован в обратном порядке, счетчик инверсии является максимальным.
Формально говоря, два элемента a [i] и a [j] образуют инверсию, если a [i]> a [j] и i <j. Пример: последовательность 2, 4, 1, 3, 5 имеет три инверсии (2, 1), (4, 1), (4, 3).
Домашнее интервью 1 (F2F):
3) Следующий великий элемент
Учитывая массив, выведите следующий больший элемент (NGE) для каждого элемента. Следующий больший элемент для элемента x - это первый больший элемент справа от x в массиве. Элементы, для которых не существует большего элемента, считают следующий больший элемент как -1.
Примеры:
a) Для любого массива крайний правый элемент всегда имеет следующий больший элемент как -1.
б) Для массива, который отсортирован в порядке убывания, все элементы имеют следующий больший элемент как -1.
c) Для входного массива [4, 5, 2, 25} следующие большие элементы для каждого элемента следующие.

Элемент NGE
   4 -> 5
   5 -> 25
   2 -> 25
   25 -> -1

d) Для входного массива [13, 7, 6, 12} следующие большие элементы для каждого элемента следующие.

  Элемент NGE
   13 -> -1
   7 -> 12
   6 -> 12
   12 -> -1

4) Отсортированный массив для сбалансированного BST
Учитывая отсортированный массив. Напишите функцию, которая создает сбалансированное двоичное дерево поиска с использованием элементов массива.
Примеры:

Вход: массив {1, 2, 3}
Выход: сбалансированный BST
     2
   / 
  1 3

Вход: массив {1, 2, 3, 4}
Выход: сбалансированный BST
      3
    / 
   2 4
 /
1

Внутреннее интервью 2 (F2F):
5) Обнаружение цикла в ориентированном графике
Для данного ориентированного графа проверьте, содержит ли граф цикл или нет. Ваша функция должна возвращать true, если данный график содержит хотя бы один цикл, иначе возвращает false. Например, следующий график содержит три цикла: 0-> 2-> 0, 0-> 1-> 2-> 0 и 3-> 3, поэтому ваша функция должна возвращать истину.

6) Преобразуйте BST в отсортированный круговой двусвязный список на месте.

Телефонный тур с менеджером по найму:
Введение обо мне.
Затем он спросил о моем проекте в колледже. мы обсудили проектно-ориентированный дизайн проекта.
Затем он спросил меня о последнем изобретении моей нынешней компании.
Затем он спросил меня о виртуальной памяти и подробно обсудил это.
Потом он пришел к моему текущему проекту, над которым я работаю
Затем он спросил меня, почему вы уходите из моей нынешней компании ??
Затем он дал вопрос для решения.
7) Учитывая массив A [] и число x, проверьте наличие пары в A [] с суммой как x
Для массива A [] из n чисел и другого числа x определяет, существуют ли в S два элемента, сумма которых в точности равна x.
Он спросил о различных возможных решениях вышеупомянутого.

Подъем штанги круглый (F2F):
8) Для двоичного дерева найдите диаметр дерева.
Диаметр дерева (иногда называемый шириной) - это количество узлов на самом длинном пути между двумя листьями в дереве.

После решения вышеупомянутой задачи он добавил ограничение к указанной выше задаче: (т.е.) найти диаметр дерева не более чем за один оборот.
Примеры поворотов в дереве:
В tree1-> начните с 1, и у корня 2 есть поворот вправо,
В tree2-> начинается с 3 идет влево, а в 1 есть поворот вправо,
В tree3-> начинается с 1 идет направо, а на 3 есть поворот налево,

     2 3 1
    /  / 
   1 3 1 3
                       /
                       2 2

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

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию . Если вы готовы, проверьте свои навыки с помощью серий тестов TCS, Wipro, Amazon и Microsoft.