Amazon Interview Questions
- 3of 3 votes
AnswersGiven a bst and a group of numbers g, check whether all the elements of g occur in the same path.
- thebiker925 September 12, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 3of 3 votes
AnswersThere are N floors and N persons each one is tagged with some random unique number between 1 to N(represents floor number).
- bharat May 31, 2013 in India
We have a lift which can accommodate one person at a time. Every person is in some random floor.
Initially lift is at floor 1 and all floors have single person. Problem here is.. we have to move the persons to their corresponding floor with minimum travelled distance of lift.
Restriction : Lift can have at most one person at a time.
One more thing we have to think of is .. At a time, we can keep more than one person in a floor.. means, we don't necessarily need to take the person out from the floor if we keep another person on the same floor.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 3of 3 votes
AnswersGiven an array, with positive and negative integers, arrange it in such a way that, positive numbers occupy even positions and negative numbers occupy odd position. All the remaining extra positive or negative integers should be stored at the end of the array. Remember, the elements of the array should remain in the same order.
- technical_123 August 11, 2013 in India
EG: Input array {1,-2,3,-4,-5,-6,-7,8,9,4,10,11,12}
output array {1,-2,3,-4,8,-5,9,-6,4,-7,10,11,12}| Report Duplicate | Flag | PURGE
Amazon Software Analyst - 3of 3 votes
AnswersWrite a program to sort an array of strings so that all anagrams are next to each other
- Neo March 07, 2013 in United States for Web Service
ex
input {god, dog, abc, cab, man}
output {abc, cab, dog, god, man}| Report Duplicate | Flag | PURGE
Amazon Intern C++ Java - 3of 3 votes
AnswersPrint the level of friendship.
- AnonD June 24, 2015 in United States
Given a person and list of his friends, print all his friends by level of association.
The text file will be like one below
A: B,C,D
D: B,E,F
E: C,F,G
If the input is A, the out put should be:
Level 1 - B,C,D
Level 2 - E,F
Level 3 - G| Report Duplicate | Flag | PURGE
Amazon Software Engineer Algorithm - 3of 3 votes
AnswersGiven a set of intervals like 5-10, 5-10, 8-12, 9-15
- blackfever April 03, 2014 in India
Find the ith smallest number in these intervals.
for eg:-
Suppose we have intervals like 5-10, 8-12.
Then total numbers in these two intervals would be: {5,6,7,8,8,9,9,10,10,11,12}
So, 1st smallest number: 5
4th smallest number: 8
5th smallest number: 8 (here is the
change since now we have duplicate elements also) and so on.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 3of 3 votes
AnswersSuppose you are supplied with a file containing a list of words like ABC, BCD , CAB ( say each word in new line ). now you have to suggest algorithm for this problem -
- ajitpec November 21, 2013 in India
When a user type some character, we have to suggest him next character and basis of suggestion is that the character you are going to suggest should have maximum occurrence at that position among all these words.
For example , Let's say words are
ABC
BCD
CBA
Now if user types 'A' we have to suggest him 'B' as next character because if you see at second position in all words 'B' is occurring most number of times ( 2 times ).
similarly if he types 'AB' then we need to suggest him third character as 'C' as in third index all words have same occurrence but 'C' comes first.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures - 3of 3 votes
AnswersThere are exactly N advertising boards on the highway. Now a company want to advertise on some of these advertising boards (each advertising board costs some money).
- Naveen Reddy Mandadi May 24, 2013 in United States
Company strategy is that, they want at least 'K' advertisement should be there among M consecutive advertising boards. But at the same time Company want to pay minimum for its advertisement.
Now, what is the total number of ways Company can advertise meeting its minimum cost strategy.
Also 1 <= K <= M <= 50 and M <= N <= 10^9
As for Example: N = 3, M = 2, K = 1 ==> there is only one way for minimum cost, ie. 0C0 , where '0' denotes No company advertisement, and 'C' denotes company advertisement board.
Similarly, for N = 4, M = 2, K = 1 ==> there are 3 possible ways, ie. C0C0, 0C0C, 0CC0.| Report Duplicate | Flag | PURGE
Amazon Developer Program Engineer Algorithm - 3of 3 votes
AnswersTwo sorted array. Find kth smallest element
- pkn May 19, 2012 in India
O(logK)| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 3of 3 votes
AnswersLet's assume that there's an array that has nonzero natural numbers where all the numbers repeat an even number of times, except for one value that repeats an odd number of times. Can you write me a function that takes this array, and returns the value that occurs the odd number of times?
- danny April 17, 2015 in United States for Amazon Music
Ex : - [ 4, 7, 2, 2, 5, 3, 5, 7, 7, 3, 4, 5 ]| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 3of 3 votes
AnswersHow can you design a data structure that can do the following operations in O(1) time:
- Masumbuet December 29, 2014 in United States for International expansion
Insert, Delete, Search, Max which returns the maximum number
I know delete, search and insert can be done O(1) time in a hashmap with a proper hash function. But not sure Max is even possible in O(1) with the presence of delete operation?| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 3of 3 votes
AnswersGiven a binary tree. Modify it in such a way that after modification you can have a preorder traversal of it using only right pointers. During modification you can use right as well as left pointers. Write complete code and dry run it for some test cases
- behinddwalls December 08, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Trees and Graphs - 3of 3 votes
AnswersA program stores total order numbers arrived at different time. For example, at 1.15 pm the program got 15 order, at 1.30 pm, the program got 20 order and so on.Now we need to design the data structure so that we can query the total orders we got in a time range efficiently. For this example, we can query as How many orders we have got between 1 and 2 pm? Ans will be 15+ 20 = 35
- gadha July 21, 2016 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Data Structures Java Object Oriented Design - 3of 3 votes
AnswersCoding:
Public void TransferAccount(AccountID id1, AccountID id2){ Account a1 = id1.GetAccount(); Account a2 = id2.GetAccount(); //Swap amounts. Temp = a1.Balance; a1.Balance = a2.Balance; a2.Balance = Temp; }
Q1: How do you make it thread safe?
I said use “public void synchronized” Good. But terrible performance since the entire method is synchronized.
Q2: Can you not lock on the entire method? I said used nested locks:Synchonized(a1) Synchronized(a2) { //swap }
His q: This will lead to a deadlock if in another thread I call Transfer (id2, id1) and Transfer (id1, id2).
Synchonized(a1) Synchronized(a2) { //swap }
Synchonized(a2) Synchronized(a1) { //swap }
How do you prevent this then? How do you design your code to not to get in to deadlock? (stumbled here)
- xankar March 16, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Java Threads - 3of 3 votes
AnswersImplement a stack with O(1) push, pop, and min
- msito October 14, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Stacks - 3of 3 votes
AnswersRotate a array by N. N can be smaller of greater than the array length.
- someone June 10, 2015 in United States
e.g {0,1,2,4,5,6,7} N =4 should return {5,6,7,4,0,1,2}.
1) I did this using extra array but next I was asked to do without extra array and in o(n) time.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Arrays - 3of 3 votes
AnswersGiven a 2 dimensional matrix where some of the elements are filled with 1 and rest of the elements
- mknarayan1711 August 02, 2014 in India for Media Experience Team
are filled. Here X means you cannot traverse to that particular points. From a cell you can either traverse to left, right, up or down
Given two points in the matrix find the shortest path
between these points
For example if the matrix is
1 1 1 1 1
S 1 X 1 1
1 1 1 1 1
X 1 1 E 1
1 1 1 1 X
Here S is the starting point and E is the Ending point| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 3of 3 votes
AnswersDevelop an algorithm and write code to break a sentence without spaces into a sentence of valid words separated by spaces.
- Murali Mohan July 16, 2013 in India for Bangalore
For ex: thissentenceisseparated needs to be broken into: this sentence is separated
Assume that you have a dictionary to check for valid words. Your algorithm should return false if the sentence cannot be separated into valid words.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 3of 3 votes
AnswersGiven a file (which can be considered as a String with comma delimiter for the complexity of the question) of usernames and a value k, find top k usernames (with number of logins) who logged into the system the most.
- sambenison66 June 05, 2016 in United States
For example -
Input:
User (String) = user1, user4, user2, user1, user3, user1, user2, user3
k (int) = 2
Output:
user1 (3)
user2 (2)
user3 (2)
- Both user2 and user3 should be included since both has same number of logins
Write a java method to find the output with best time and space complexity.| Report Duplicate | Flag | PURGE
Amazon Software Engineer in Test Java - 3of 3 votes
AnswersThere is a clock at the bottom of the hill and a clock at the top of the hill. The clock at the bottom of the hill works fine but the clock at the top doesn’t. How will you synchronize the two clocks. Obviously, you can’t carry either of the clocks up or down the hill! And you have a horse to help you transport yourself. And, the time required for going up the hill is not equal to the time required to go down the hill.
- Nascent July 01, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon - 3of 3 votes
AnswersGiven an array with different numbers and a number of C,so how to find all the combinations which the sum is C..like..array={1,2,3,4},C=3,,return is 2,which contains two combinations{{1,2},{3}}.
- onyasGM May 23, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Java Developer Algorithm - 3of 3 votes
AnswersGiven an array of integers, find Pythagorean triplets.
- goelrinku90 March 29, 2013 in United States
i.e. find a,b and c which satisfies a^2 + b^2 = c^2
Integers could be positive or negative.| Report Duplicate | Flag | PURGE
Amazon Developer Program Engineer - 3of 3 votes
AnswersGive the algorithm and code to get the depth of the deepest odd level leaf node in a binary tree.
- tom March 04, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 3of 3 votes
AnswersGiven two unsorted integer arrays A & B of unequal length.
- vikas.singh.nitj December 05, 2013 in India
Find an element from A(say 'X') and another element from B(say 'Y') such that |X-Y| is minimum.
Note: A & B can contain positive/negative numbers.
How can you find this without sorting both arrays?
How can you find this by sorting both arrays?| Report Duplicate | Flag | PURGE
Amazon Developer Program Engineer Algorithm - 3of 3 votes
AnswersGiven a string, you need to find super string by word match. i.e. all words in the input string has to occure in any order in output string.
- zc51 March 29, 2013 in India
e.g. given data set:
"string search"
"java string search"
"manual c++ string search equals"
"java search code"
"c++ java code search"
...
input: "java search"
output:
1) "java string search"
2) "java search code"
3) "c++ java code search"
input: "c++ search"
output:
1) "manual c++ string search equals"
2) "c++ java code search"
There are millions of records in given data set and you need to process few million as input.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Data Mining - 3of 3 votes
AnswersUsing the mythical Hydra as an example, create a button that is destroyed by clicking it, but two new buttons are created in it's place.
- Kevin.Pheasey April 10, 2013 in United States for AWS| Report Duplicate | Flag | PURGE
Amazon Web Developer JavaScript - 3of 3 votes
AnswersGiven two sorted lists and an integer k, merge the lists up to a maximum of k elements.
- codebrkr September 15, 2016 in United States| Report Duplicate | Flag | PURGE
Amazon SDET - 3of 3 votes
AnswersGiven a matrix containing 0 and 1. Consider 1 as 'Land' and 0 as 'Water'. Find out the number of 'Islands' in the matrix. That is, set of all adjacent 1 will make up for an island.
- prajakta mahamuni July 17, 2015 in India
For example:
[ 0 1 1 0 1 ]
[ 1 1 1 0 0 ]
[ 0 0 0 1 1 ]
[ 1 0 0 1 0 ]
This problem has 4 islands. ( consider set of 1s, vertically, horizontally and diagonally ).| Report Duplicate | Flag | PURGE
Amazon Software Developer Algorithm - 3of 3 votes
AnswersA lot of transistors contains 0.6 percent defectives. Each transistor is subjected to a test that correctly identifies a defective but also misidentifies as defective about two in every 100 good transistors. Given that a randomly chosen transistor is declared defective by the tester, compute the probability that it is actually defective.
- sarora9876 July 29, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Analyst Brain Teasers