Рубрики

Amazon Интервью | Набор 53 (для SDE-1)

В каждом раунде меня спрашивают, почему я хочу присоединиться к Amazon, почему я покидаю свою предыдущую компанию с таким небольшим промежутком (около 2,5 месяцев) и проектами.
Интервьюеры были довольно дружелюбны. Они объяснят вам до того момента, пока вы полностью не поймете. И даже при обсуждении подхода и решения, они бы очистили ваши сомнения, если таковые имеются.

Онлайн тест на InterviewStreet
1. Учитывая 2 строки, найдите, является ли 2nd подстрокой 1st или нет . (было бы здорово, если вы решите с KMP)
2. Учитывая 2 прямоугольника, определите, перекрываются они или нет.
3. По заданному списку монет с различными значениями (неограниченное количество монет каждого типа), найдите, сколько способов вы можете сделать данное значение. (Ожидалось DP.) Поскольку не было гарантии, что монета достоинством 1 будет присутствовать, мы должны вернуть -1, если данное значение невозможно.

Все раунды в один и тот же день.

1й f2f:
Сначала меня попросили представиться и дать краткое описание моих проектов. Позже он попросил меня объяснить любой из моих проектов и самую сложную задачу, которую я выполнил.
Мы использовали infix для публикации оценки ix и postfix для оценки нашего общего поискового выражения. Здесь у нас было много дискуссий о том, зачем нужен разговор от инфикса до пост-исправления и все такое.

1. Если заданы String s и int r, сначала заполните каждую строку символов и напечатайте столбец.
например, String s = «abcdefgh» и r = 3
поэтому заполнение колонки мудро даст:
ADG
бех
сравни

и последний ответ будет adgbehcf.
он просто хотел точный вывод. Внутренне то, как мы работаем со строкой, не было проблемой.

2. с заданной строкой или, скажем, номером … например, теперь 134 с каждым номером, согласно клавиатуре мобильного телефона, некоторые буквы будут связаны.
здесь 1 -> abc, 3-> ghi, 4 -> jkl. Таким образом, мы должны напечатать всю перестановку так, чтобы мы взяли 1 символ из каждого числа.
вводимое число может быть любой произвольной длины.
скажем, с каждой цифрой связано m чисел, тогда для ввода длины n нам нужно сгенерировать n ^ m возможных строк.

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

2й f2f
1. Найти целую часть sqrt заданного числа. Изначально я дал о (root (n)) решение. Позже решена с помощью бинарного поиска (O (logn)).

2. Дан массив целых чисел. замените каждое число на следующее более высокое число на его правой стороне, которая ближе. (если нет, то оставьте все как есть.)
например, для ввода -> 3 4 6 1
выход-> 4 6 6 1

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

if (a[i] 

Since we needed extra space to store indexes, he asked that the input is array of a structure which has number and higher Index, 2 fields. So that we don't need extra space and extra traversal.

class Node {
   int val;
   int higher;
}

Ему было очень интересно посмотреть, как я отслеживаю индексы и как я пересекаю их. Это o (n) с o (1) пространственной сложностью. (когда у нас есть [i]> a [i + 1], мы не выполняем линейный поиск, но мы прыгаем по индексам, так что это не o (n ^ 2)) Было сложно убедить его в сложности.

3. дано двоичное дерево. подключить все узлы на одном уровне. каждый узел имел бы указатели left, right и nextSibling. нам нужно заполнить nextSibling.
решено с обходом порядка уровня. Аналогично BFS на дереве с очередью. Нужен был только подход, никакого кода для этого.

3-й f2f (менеджер по найму)
1. Это был вопрос дизайна. Вы должны разработать игру. у него разные типы монстров и разное оружие. герой стреляет в монстра. у каждого монстра будет какое-то начальное здоровье. Каждое оружие будет наносить некоторый заранее определенный урон монстру. когда его здоровье становится равным 0, монстр умрет / исчезнет. и было бы несколько уровней. в зависимости от уровня, монстр и их поведение будут меняться.

2. При наличии связанного списка только для чтения со следующим и случайным указателем клонируйте список. Я сказал ему, что знаю решение, и объяснил ему подход. Это было с использованием hashmap и занимает o (N) дополнительного места. Затем он спрашивает меня, знаю ли я (1) космическое решение, так как я не знал, мне сказали решить это. При этом он сказал, что я могу изменить список ссылок.
Изначально я боролся, но с его помощью в итоге придумал рабочий код. Он хорошо выглядел с реализацией.

Здесь я спрашиваю о рабочей культуре и процессе, которому следуют в Amazon. Я задаю много вопросов, касающихся инструментов и технологий, которые они используют. Так как у меня была работа над scrum-моделью, это было довольно интересно. Он, казалось, был впечатлен здесь.

4-й f2f (Dev Manager)
1. Учитывая 2 отсортированных связанных списка, объединить их в один отсортированный список. Измените указатели, не копируйте данные. (так же, как часть слияния mergesort на SLL)

2. Для данного двоичного дерева соедините все узлы, которые находятся в одном столбце. 1 оговорка была о том, что один и тот же узел может иметь 2 родителей. Здесь, как в примере, на узел 7 указывают 2 и 6.
Решил это, используя обход уровня порядка. Использовал карту: columNo, Node. он будет хранить последний посещенный узел этого столбца. Поэтому всякий раз, когда мы посещаем узел, сначала мы проверяем, присутствует ли соответствующий ему столбец в hashmap. если нет, это означает, что это первый узел столбца, помещенный в карту. если столбец присутствует, то мы получим узел, сохраненный на карте, и текущим узлом будет его nextVerticleSibling. и мы обновляем карту.
Он продемонстрировал пример и код, и он был в порядке с окончательным подходом.

        1
       /   \
      2     6
     /  \   / \
   3      7    8
   /           /  
  4         12 
 / \           \     
5  9           13
    \             \
     10           14
      \
       11 

Наконец через два дня мне позвонили из HR, что меня выбрали selected

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

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

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

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

Amazon Интервью | Набор 53 (для SDE-1)

0.00 (0%) 0 votes