Amazon Interview Questions
- 0of 0 votes
AnswersThere are n persons and k different type of dishes. Each person has some preference for each dish. Either he likes it or not. We need to feed all people. Every person should get atleast one dish of his chioce. What is the minimum number of different type of dishes we can order?
- prashant2006ster July 28, 2015 in India
Input is n x k matrix boolean matrix.For each person a row represent his likes or not likes each row.
n = 6 k = 7
1 0 0 0 1 0 0
1 0 0 0 0 1 0
1 0 0 0 0 0 1
0 1 0 0 1 0 0
0 0 1 0 0 1 0
0 0 0 1 0 0 1
Output
3
Explanation
Take dish number 5,6,7.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersGiven set of job schedules with start and end time, write a function that returns indexes of overlapping sets.
- Tom Walker May 13, 2015 in United States
for ex :-
input -> [1,2][5,6][1,5][7,8][1,6]
return -> [0,1,2,4]| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 0 votes
AnswersGiven a array of positive integers, you have to find the smallest positive integer that can not be formed from the sum of numbers from array.
- hacker123 December 07, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Arrays - 0of 4 votes
Answers2.Given an integer linked list of which both first half and second half are sorted independently. Write a function to merge the two parts to create one single sorted linked list in place [do not use any extra space].
- Harjit Singh September 27, 2013 in India for TCS
Sample test case:
Input: List 1:1->2->3->4->5->1->2; Output: 1->1->2->2->3->4->5
Input 2: 1->5->7->9->11->2->4->6; Output 2: 1->2->4->5->6->7->9->11
C/C++/Java/C#
struct node
{
int val;
node *next;
}
node* sortList(node* list1) {
}
Java
class Node
{
int val;
Node next;
}
Node sortList(Node list1) {
}| Report Duplicate | Flag | PURGE
Amazon SDE1 Linked Lists - 0of 0 votes
AnswersYou have a web server's log that records for each user the URL that he accessed.
Example format:Time-stamp User-id URL
How to find the maximum common (sub)sequence of visited URLs from all users? Write code in java
Log entries are ordered based on timestamp.
Example log (omitting timestamp for clarity):
John URL1
John URL2
Jim URL2
Mary URL1
John URL4
etc
Update:
Example:User-id URL 186 A 187 B 186 C 188 B 186 C 187 A 186 B 188 A 188 C 189 A 189 D 187 C 189 B 186 A 187 C 189 A 189 C
So the max common URL sequence is A,C,C (URL A followed by URL C, followed by URL C)
- Jim January 20, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Java - 0of 0 votes
AnswersPrint a binary tree in vertical.
- kaushikdev9 October 11, 2012 in India
e.g.,
1
/ \
2 3
/ /
4 5
\
6
o/p: 4 2 1 5 3 6| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Trees and Graphs - 0of 0 votes
AnswersA n*n matrix is given which is containing elements in which each row alone is sorted. column is not sorted. I have to convert it into a single dimensional array which will hold all the elements of the array in a sorted manner
- firefox October 01, 2012 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 1of 1 vote
AnswersGiven an array which contains the parent of the ith element in the n-ary tree.Parent[i] = -1 for root.
- grave July 07, 2012 in India
Find the height of the tree.
Gave O(n2) ,space O(1).
Expected Complexity- Linear
You can use extra space if you want.
Example-
{-1 0 1 6 6 0 0 2 7}
0 1 2 3 4 5 6 7 8
0 is the root here.
0 is the parent of 1 5 6
1 is parnt of 2
6 is parent of 3 4
2 is of 7 which is parent of 8.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Data Structures Hash Table Trees and Graphs - 0of 0 votes
AnswersFind the nth most frequent number in array
- mdfirozansari June 09, 2012 in India for MP3 mobile team| Report Duplicate | Flag | PURGE
Amazon Quality Assurance Engineer Arrays - 0of 0 votes
AnswersYou are getting a stream of characters and at any time you can be asked to find out if the string received yet is palindrome or not.
- Ajax May 21, 2012 in India
There can be multiple queries.He insisted to do it in better than O(n) and No extra space.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a Binary tree where nodes may have positive or negative value, store the sum of the left and right subtree in the nodes.
Eg-10 -2 6 8 -4 7 5
Output:
- Puzzle November 19, 2011 in India20(-2+6+4+12) 4(8-4) 12(7+5) 0 0 0 0
| Report Duplicate | Flag | PURGE
Amazon Software Engineer in Test Trees and Graphs Data Structures - 0of 0 votes
AnswersGiven a set of numbers eg:{2,3,6,7,8} . any one who is playing the game can score points only from this set using the numbers in that set. given a number, print all the possible ways of scoring that many points. Repetition of combinations are not allowed.
- putta.sreenivas May 09, 2011
eg:
1. 6 points can be scored as
6
3+3
2+2+2
2. 7 can be scored as
7
2+2+3
but 2+3+2 and 3+2+2 is not allowed as they are repetitions of 2+2+3| Report Duplicate | Flag | PURGE
Amazon Developer Program Engineer Algorithm - 0of 0 votes
Answers<round 3>
- siva.sai.2020 February 08, 2011
9. Array A[n] it contains numbers from 1 to n but 1 number repeated. Find out missing number.
----------------------
I have not answered this question and manager not happy with my performance. THIS THE END OF THE BATTLE.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 1of 1 vote
AnswersThere is very long array of ints, and you are given pointer to base addr of this array.. each int is 16bit representation... you need to return the pointer to tht "bit" inside array where longest sequence of "1"s start
- gradStudent June 16, 2010| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Arrays Bit Manipulation Computer Architecture & Low Level - 0of 0 votes
AnswersGiven a two integer n and d. Print the value of n/d. When n/d may or may not have decimal digits. In case of numbers n=1 and d=3, n/d=0.3333333.... So when there is a repeating pattern the output should be 0.(3), In case of a n/d = 3.12454545454545.... the output should be 3.12(45), for n/d = 4.123982 the output should be 4.123982. Give a solution and write code for the same.
- Raju April 21, 2010| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven a singly linked list, swap every two elements (e.g. a->b->c->d->e->f->null should become b->a->d->c->f->e->null). Code it such that memory position is swapped and not the node value.
- AnonymousUser March 28, 2010| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Linked Lists - 0of 0 votes
AnswersFind the K'th Maximum Element in a Binary Search Tree . Do it in O(log N).
- Amar August 31, 2009
Please dont do a in order tree traversal and return the K'th element from the end. I told that but interviewer did not wanted me to traverse the entire tree. Any suggestions ?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 5of 5 votes
AnswersHad my first and second phone interview with Amazon. I was dropped. This site has been a great help towards my preparation and most questions are based on what you find here.
- S July 01, 2008
Posting my Questions is a small way of saying Thanks!
Interview 1:
1. What is polymorphism.
2. Design an OO parking lot. What classes and functions will it have. It should say, full, empty and also be able to find spot for Valet parking. The lot has 3 different types of parking: regular, handicapped and compact.
3. Coding: I have an integer array where every number appears even number of times and only one appears odd times. Find the number.
(I said hashtable and he asked me to write code with Hashtable)
4. What data structure would you use to look up phone numbers for customer names.
(I said Hashtable. Asked why hashtable, why not a tree. I said HT has O(1). Asked is order always 1, when more than O(1) in HT.
Second Interview:
1. Starter: Describe your college projects.
2. OO Design: Design a deck of cards. What classes, data structures will you use? How will you shuffle the cards? How will you divide (deck) among players. What class/function do you need to denote players and where will you add them? What class/function do you need to deck? What if I need to add 2 jokers to the deck of 52 cards.
3. Data Structures: How will you use a hashtable to find data in a tree. (Then he rephrased) suppose I have a hashtable, I want to store the data in a tree instead of a bucket. How will I do it. What complexity to find an element.
4. Bits & Bytes: Find if a binary representation of a number is palindrome. The function should work irrespective of number of bytes for an integer. Suppose if our machine is 4 bytes for an int, how will you use the program for 8 byte machine.
5. Unix: Suppose I have 100's of html files in many directories. I want to find the files having phone numbers.
b) Suppose I have 2 files having phone numbers, find the repeating phone numbers. (I said sort and grep). Then he asked what if the lines cannot be sorted.
All the best guys. I think the second interview was challenging since the interviewer was prodding until he heard a leave me alone. So it means that though they are based on questions in cc, be prepared for extensions. I think this site is all you need to prepare for Amazon interview.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Java Data Structures Object Oriented Design Coding - 0of 0 votes
AnswersDesign an algorithm to find duplicates in an array. Discuss different approaches.
- divya November 19, 2005| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 2of 2 votes
AnswersWrite a method to count the number of 2s between 0 and n.*
- xankar May 12, 2016 in United States| Report Duplicate | Flag | PURGE
Amazon Software Developer Coding - 3of 5 votes
AnswersThere is a village in which parent prefer to have at least 1 boy. So they keep doing child until they get their first boy and then they stop doing children. What is ratio of girl/boy in such town after infinite years.
- shivam.s.kalra March 13, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Automata - 0of 2 votes
AnswersYou are given an array in which you’ve to find a subarray such that the sum of elements in it is equal to zero.
- ninja October 02, 2013 in -| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 4 votes
AnswersWrite a function to search for the existence of a string (target) in another string (str). The function takes two strings as the input and returns the index where the second string is found. If the target string cannot be found, then return -1
- Rahul June 18, 2013 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer String Manipulation - 0of 0 votes
Answers[Question asked during online Test.]
- Rahul June 18, 2013 in India
Given a list of 'N' coins, their values being in an array A[], return the minimum number of coins required to sum to 'S' (you can use as many coins you want). If it's not possible to sum to 'S', return -1
Sample Test Cases:
Input :
Coin denominations: { 1,3,5 }
Required sum (S): 11
Output :
3| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 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 - 2of 2 votes
AnswersAssume I have a log file with list of people with their arrival and departure time at an event that happened in the past.
- Bevan March 02, 2013 in United States
My task is to find out the maximum number of people present at any time during the entire event? I am not given query time.
ai = Arrival time of person i
di = Departure time of person i
I have a list of pairs like (a1,d1), (a2,d2), (a3,d3).... (an,dn)... It's not in a database.
I apologize as I cannot edit my previous question. I think it had a incomplete description.
Please let me know if you guys still need clarification. Thanks| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersYou have a two dimensional array of size m*n. The
- charan January 08, 2013 in United States
elements in the rows are sorted and every row has
unique elements means( in a row no two elements are same) but
the elements can repeat across the rows.
For example:
you have following 2-D array:
{
2 5 7 9 14 16
3 6 8 10 15 21
4 7 9 15 22 35
7 8 9 22 40 58
}
You are supposed to write an efficient function which
will take upper 2-D array as input and will return a
one-dimensional array with following properties:
a) the 1-D array must contain all the elements of above
2-D array.
b) the 1-D array should not have any repeated elements.
c) all the elements should be in sorted order.
For example:
for the above 2-D array, the output should be:
A [ ] = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 14, 15, 16, 21, 22, 35,
40, 58 }
Function Prototype should be :
int [ ] MergeAndSort( int[ ][ ] inputArray )| Report Duplicate | Flag | PURGE
Amazon