Amazon SDE Interview Questions, Process, and Tips

Round: Telephonic round
Experience: 1. An array is given with element name and their respective pH values. Print the combination of 2 elements which make a neutral compound.

A discussion started and best solution was O(n) time complexity and O(1) space complexity.

Then I got call for F2F interviews and here are those-

Round: Technical Interview
Experience: 1. Print Matrix in spiral form.

2. A store have n customers and any 1 can visit them any time through out the year.Data is stored in a file.Design a data structure to find given person visited on so n so date or not.

Round: Technical Interview
Experience: 1.There are N packages P1, P2…Pn. A package may depend on another or many other for its compilation. Given a matrix of dependency, find a sequence of package compilation.

2.A 2D matrix is given, with each elements representing number of gold coin at that position. I have to travel from (0,0) to last element of matrix collecting maximum no. of coins.I can travel either right of an element or down of it.

3.In Galaxy there are trillions of stars. I am provide distance of every star from earth. Tell me nearest 1Million stars to earth, provided with best time and space complexity.

Round: Technical Interview
Experience: 1. Implement LRU.

2.In Android phones we have 3X3 grid for making a pattern. Given a length, find number of combinations for that length in that grid.

Round: HR Interview
Experience: 1. Project deep discussion.
2. Few given scenarios and how you will tackle.
3. Strengths and weaknesses.
4. Given a file with many statements. Print all the strings with their anagrams through the file.Logic to check anagrams and to store them

Round: Technical Interview
Experience: 1. Behavioral Questions like
>Why you want to leave your organization?
>What is most challenging work you have done till date?
>Why you want to join Amazon?
etc.
2. Which data structure you know?
3.Say I have few words and their meaning, and I want to store them which DS will you use and why.
I started with Hashmap and we kept on discussing about pros and cons.Finally ended up with trie.He asked me to write code for it, for adding new word and for fetching meaning from Trie.The whole process started in 1st week and yesterday got a call from HR for I am invited to be part of Amazon.

College Name: NA

Round: Test
Experience: They had an online aptitude test on day 1. It was 90 minutes: 20 MCQs + 2 coding questions (choice between C/C++/Java for coding). MCQs were based on DSA, OS, and Math. They were apparently difficult.

Round: Test
Experience: 1. Keypad problem ( -----/ )– Little difficult problem on backtracking.2. Given an array, find the count of impossible triangle ( -----/ )

Round: Test
Experience: Questions involved DSA and strongly based on optimising the code:



1. Given a linked list, reverse K nodes in it eg :- 1->2->3->4->5->NULL , k = 3 3->2->1->5->4 2. Search for an element in an array which has elements who’s values are first increasing and then decreasing. (Use modified binary search)
Duration: 60 minutes
Total Questions: 2

College Name: NA

Round: Test
Experience: Online Round :(Duration – 90 minutes)20 MCQs to solve and 2 coding questions. 20MCQs were on Algorithms,Data Structures, C Output, Quantitative Aptitude, etc.

Coding questions were of 10 marks each.

MCQ’s had negative marking.

Correct : +1

Wrong : -0.25Q1– Given an array of numbers, arrange them in an alternate fashion such that every number is followed by a number of opposite sign. Also the order was to be maintained. If the count of negative numbers is more keep the extra at last in array and same for positive numbers.Example :

Input: -3 -2 6 0 7 -1 -8

Output: -3 6 -2 0 -1 7 -8Q2– String of characters as arranged in a cellphone i.e.

1- NULL

2-a,b,c

3-d,e,f

4-g,h,i

.

.

.

9-w,x,y,z

0-NULLPrint all combinations for given number of digits(k) in lexicographical order .

Constraint : 1<=k<4

For Example : Input = 234

Output : adg adh adi aeg aeh aei afg afh afi bdg bdh bdi beg beh bei bfg bfh bfi cdg cdh cdi ceg che dei cfg cfh cfi

Round: TECHNICAL INTERVIEW
Experience: Q1– Design a shuffle function which would play songs randomly in your device (unique song_id) and code it.

After i gave him a solution with hash function , he asked me to improve the algorithm such that once a song is played it should be played only when all the other songs are played,

Solution’s Complexity : Space – O(n) , Time – O(1) ; n—> number of songs

After that he asked me to improve my solution and do it without using extra space.

Solution’s Complexity : Space – O(1) , Time – O(n) ; n—>number of songs

Hint : Maintain indices and once a song is played shift it in range of played songs index.

After that i was asked about each part of the hash function and how i came up with that.Q2– Add two linked lists. And code it.Input : 1->2->3->4->NULL

8->2->NULL

Output : 1->3->1->6->NULLFirst he asked to do it without recursion and then with recursion.We also talked about theproblem we face if we store the value of the linked list in an integer or long if the number of digits were above certain limits in the non-recursive function.

Round: TECHNICAL INTERVIEW
Experience: Q1 – Find the largest sub tree which is binary search tree in a given Binary Tree. Then to optimize it and then asked me to code it.
Q2 – Given a linked list with a next pointer and an arbitrary pointer pointing to any node in the list , copy the linked list.After i gave him a solution which changed the links of the initial linked list, he asked me to do without changing the links.So i gave him a O(n^2) solution . He asked me to give another way or optimize my solution.He helped me to figure out the solution.Hint – Hash map.The interviewers were really helping and supporting and were more interested in seeing the efforts you make and the way you get to the logic.They help throughout by giving hints.

College Name: NA

Round: Test
Experience: Online Round: (Duration – 90 minutes)

20 MCQs and 2 coding questions. MCQs were on Algorithms, Time Complexity, Quantitative Aptitude, Probability, Operating Systems, Graphs, Data Structures, Recursion outputs etc.

Coding Questions:

1. In one of Amazon fulfillment centers, there are a no. of empty boxes kept in increasing order in a row. Kiva robots are designed to put a product in a box. The product size is given. Design a program to find the best fit box for given product size. First line contains no. of empty boxes and next line contains size of boxes with space. The next line contains size of given product. The output shows the best fit box size and -1 otherwise.For example, Input: 6

2 7 9 11 13 16

12

Output: 13 2. You have to find a string in two-dimensional array. The input contains 2-D array of characters and given string. You can move in one of eight directions . The output contains location of first letter of string if string found completely, otherwise return -1. Any one out of multiple answers is accepted, if possible.

For example, Input:

b t g

p a d

r k jString: rat

Output: (2,0)

Round: TECHNICAL INTERVIEW
Experience: Brief introduction about myself and my project.

1. Given an array of positive and negative integers, rearrange positive and negative numbers in 0(n) time .

First, I solved it using 2 arrays,each for positive and negative integers and place elements of array in these 2 arrays and them combine them back by taking one element from each array. Then he told me to do without extra space. I then segregated positive and negative elements using quicksort .Below is the link:

-----. Program to check whether strings are rotation of each other or not. I approached as below:

-----/

He then told to solve without using strstr. I used naive searching method.

Round: HR INTERVIEW
Experience: Brief introduction and some behavioral questions.

Given a BST and a key sum, design an algorithm to find all pairs of integers whose sum equal to key.

I first approached using an array and placing elements into it in inorder fashion and then find pairs. He told to do in-place and I solved with 2 traversals (inorder and reverse- inorder

Round: Technical Interview
Experience: Based on CS Fundamentals and also had 15 minutes discussion on my internship project.
Q.Given a Binary tree, full_path_sum is sum of all nodes from root to leaf in a path. Given a min_sum value, delete nodes if path has full_path_sum less than min_sum . Delete all such nodes . For example,Given min_sum =8 1
2 3
4 5 6 7

College Name: NA

Round: Test
Experience: 1. Convert Binary tree to linked list.

2. Rotate a matrix by 90 degree.

There were 2 more questions. But I forgot what were they?

Round: TECHNICAL INTERVIEW
Experience: Overview of current job responsibilities and internship project.

1. Convert a tree to a sum tree.Example :

1 27

/ /

2 3 -------> 9 13

/ / / /

4 5 6 7 0 0 0 0 Always take care of all the corner cases

2. Print a pascal tree .

3. Given a 2D matrix sorted row wise and column wise . Print the matrix in sorted way. (Can be done using Min Heap).

For all the questions, complexity of the program was asked and was being asked to improve both time and space complexity.

Round: TECHNICAL INTERVIEW
Experience: Many questions regarding my current project, tools and technology I am working on.

1. Convert a binary tree to a sum tree . Here he had a new meaning of sum tree.

Example :Example :

1 1

/ /

2 3 -------> 2 5

/ / / /

4 5 6 7 4 9 15 22 (I did it with Level Order Traversal) (Complete working code was required)

2. Given an array of integers. Find the largest 3 element. (Can be done using Max Heap in less time complexity)

College Name: NA

Round: Test
Experience: Q1. Given a string you need to print all possible strings that can be made by placing spaces (zero or one) in between them. For example : ABC -> A BC, AB C, ABC, A B CQ2. Given a tree where there are three pointers (left_pointer, right_pointer and a next_right_pointer). Left and right pointers are set like that of any general binary tree. We were asked to set the next_right_pointer to the next node in the level order traversal for the same level. This implies means for the last node in every level it will be null for rest it will be pointer to the next node in level order traversal.
Duration: 60 minutes
Total Questions: 2

General Tips: TIPS:1. Don’t jump into solutions&#44; ask about the type of input that is given and output that is expected.2. The interviewer always tries to take you to the most optimal solution so listen to what all he says. Many a times they are big hints !!!3.Be honest.4. Keep believing that you will get the job .
College Name: NA