Amazon Interview Questions
- 1of 1 vote
Answersfinds a domino pattern for a "double-N" domino set that forms a loop / a ring using all available tiles.
- czuu December 02, 2014 in United States
for example,In a double-two domino set, with six tiles, (0 , 0) (0 , 1) (1 , 1) (1 , 2) (2 , 2) (2 , 0). So if parameter is 2, the function should return true. if no loop found, should return false.
Dominoes are small rectangular game tiles divided into two squares and embossed with dots on the top surface of the tile. You can think of dots as integers. A double-N domino set consists of (N+1)(N+2)/2 tiles, e.g. a standard double-six domino set has 28 tiles (T): one for each possible pair of values from (0.0) to (6.6) - no pair of numbers occurs more than once.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersWe have a class as follows:
public class People{ String name; String position; String sex; ... ... public String getAttribute(String attrName){ /** * This is a generic getter method that will give you * any attribute value based on the passed attribute * Name; * for eg: getAttribute("name") => will return the * attriute(Name) value of the current object. */ } }
I now give you two List:
- Arya December 01, 2014 in United States
list1<People> friends;
list2<String> attributes;
Using the generic getter method, we have to group "friends" on "attributes". Think of this as an implementation of GROUP BY function to be implemented on objects in list1 and to be grouped on entries in list2.
eg: list2 = {sex, occupation}
So objects in list1 will be grouped such that all Male-doctors together, Female-cops together, male-cops together, etc.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 2of 2 votes
AnswersGiven a large array of unsigned ints, quickly find two who's sum is 10
- JSDUDE November 22, 2014 in United States for Software Developer, Infrastructure Planning, Analysis and Optimization
Then the interviewer asked me to write test cases.
Followed by how to implement this on a distributed system, where multiple systems can read/write simultaneously on a shared cache (HINT: It is ok if you do not return the first instance)| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm Arrays - 1of 1 vote
AnswersMinesweeper question: Given an n x m grid holding individual mine co-ordinates, identify all of the mine clusters. A mine cluster is the largest collection of neighboring mines.
- wyu277 November 17, 2014 in United States
Example input:
0 1 2 3
---------
0|0|1|0|1
1|0|0|1|1
2|0|0|0|0
3|1|1|0|0
Expected output:
[cluster 1] (0,1),(1,2),(1,3),(0,3)
[cluster 2] (3,0),(3,1)| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 1of 1 vote
Answersgiven a range of number 1 through N, where N >=3. you have to take an array of length 2N and place each number ( from the range 1 to N) twice. such a that the distance between two indexes of a number is equal to the number. example
- vikaskupushkar November 15, 2014 in India
N=3
( 3, 1, 2, 1, 3, 2 )
I know we can Use Backtracking but is there any other solution.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersWrite an algorithm to convert the given input string to the expected output string. The input string shall be the length of few million characters. So the output has to be updated in the same string...
- smartdiwa November 14, 2014 in India
Input String = "ABBCDEFGGGGGGGGHHXX..<20 more X>..XYY..."
Expected output = "A1B2C1D1E1F1G8H2X23Y2..."
Note: The count of each character has to be appended with the same character in the output string| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
Answerscalculate the summary statistics for a fleet of hosts. Each host has a fixed number of slots in which virtual instances can run. Each host can only run instances of a particular type, e.g. M1, M2, or M3. You are provided with the file “FleetState.txt” that contains the state of the fleet. Each line in the file represents a single host in the following comma-separated format:
- Algo October 31, 2014 in -
<HostID>,<InstanceType>,<N>,<Slot1State>,<Slot2State>,…,<SlotNState>
where
<HostID> is an integer
<InstanceType> can be M1, M2, or M3
<N> is the total number of slots on the machine
<SlotjState> is 0 if slot j is empty and 1 if it is occupied by an instance
Write a program that loads the state of the fleet from the input file “FleetState.txt” and then computes and writes out the following summary statistics to the output file “Statistics.txt”:
For each instance type, the count of empty hosts (all slots empty)
For each instance type, the count of full hosts (all slots filled)
For each instance type, the count of the most filled hosts (having the smallest number of empty slots > 0). Both the host count and number of empty slots must be written out in that order.
The output file must have the following format:
EMPTY: M1=<count>; M2=<count>; M3=<count>;
FULL: M1=<count>; M2=<count>; M3=<count>;
MOST FILLED: M1=<count>,<empty slots>; M2=<count>,<empty slots>; M3=<count>,<empty slots>;
What is the best way to solve this problem?| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 0 votes
Answerscalculate the summary statistics for a fleet of hosts. Each host has a fixed number of slots in which virtual instances can run. Each host can only run instances of a particular type, e.g. M1, M2, or M3. You are provided with the file “FleetState.txt” that contains the state of the fleet. Each line in the file represents a single host in the following comma-separated format:
- Algo October 31, 2014 in -
<HostID>,<InstanceType>,<N>,<Slot1State>,<Slot2State>,…,<SlotNState>
where
<HostID> is an integer
<InstanceType> can be M1, M2, or M3
<N> is the total number of slots on the machine
<SlotjState> is 0 if slot j is empty and 1 if it is occupied by an instance
Write a program that loads the state of the fleet from the input file “FleetState.txt” and then computes and writes out the following summary statistics to the output file “Statistics.txt”:
For each instance type, the count of empty hosts (all slots empty)
For each instance type, the count of full hosts (all slots filled)
For each instance type, the count of the most filled hosts (having the smallest number of empty slots > 0). Both the host count and number of empty slots must be written out in that order.
The output file must have the following format:
EMPTY: M1=<count>; M2=<count>; M3=<count>;
FULL: M1=<count>; M2=<count>; M3=<count>;
MOST FILLED: M1=<count>,<empty slots>; M2=<count>,<empty slots>; M3=<count>,<empty slots>;
what is the best way to solve it?| Report Duplicate | Flag | PURGE
Amazon SDE1 - 1of 1 vote
Answers
- Aspire October 11, 2014 in United StatesGiven a String s and a hashmap containing certain decodings for all the characters of alphabet. Find all possible passwords that can be generated by replacing decodings in the string s. Note that decodings of a charachter can only be single charachters Eg: String s="abcde" decodings given a-{1,2,p,o,q} b-{2,y} c-{p} d-{4,a,m,n} e-{9,z,x} h-{1} ' ' ' x-{0} y-{4,k,l} z-{r,5} So possible set passwords will be abcde,1bcde,2bcde,pbcde,obcde,qbcde, //replace a with all possible decodings a2cde,12cde,22cde,p2cde,o2cde,q2cde,aycde,1ycde,2ycde,pycde,oycde,qycde //replace b will all possible decodings a2pde,12pde,22pde,p2pde,o2pde,q2pde,aypde,1ypde,2ypde,pypde,oypde,qypde.....//replace c will all possible decodings
| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
Answersnon recursive method to calculate height of the binary tree.
- NEO September 27, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
Answersyou have a dictionary which will return true if the word is present in it otherwise false. You have a string "ABC", check if anagram of "ABC" is present or not. the condition was not to generate the all the anagram of ABC. (Assumption: you can store the dictionary in trie or hashmap (any data structure) and no need to implement the dictionary)
- NEO September 27, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersMerge two sorted linked list
- LCHammer September 25, 2014 in United States for Advertising| Report Duplicate | Flag | PURGE
Amazon SDE1 Linked Lists - 0of 0 votes
AnswersDesign a stack using queue(s)
- LCHammer September 25, 2014 in United States for Advertising| Report Duplicate | Flag | PURGE
Amazon SDE1 Stacks - 1of 1 vote
AnswersDesign a valet parking system. Requirements of the valet parking system should be:
- LCHammer September 25, 2014 in United States for Advertising
1. Customer are given a ticket that they can use to redeem to get their vehicle back
2. Parking spots come in three sizes, small, med, large
3. Thee types of vehicles, small, med, large
-a small vehicle can park in a small, medium, and large spot
-a medium vehicle can park in a medium and large spot
-a large vehicle can park in a large spot| Report Duplicate | Flag | PURGE
Amazon SDE1 Object Oriented Design - 0of 0 votes
AnswersSuppose you want improve the performance of search queries, using a cache. Each search queries is in form of a string and returns a list of ad id's in the form of longs.
- LCHammer September 25, 2014 in United States for Advertising
Design a class with the appropriate data structure(s) that can manage a cache of search queries.| Report Duplicate | Flag | PURGE
Amazon SDE1 Coding - 0of 0 votes
AnswersSay you have a string:
- LCHammer September 25, 2014 in United States for Advertising
"Thisisasentence"
How would you separate the string into separate words, return either the sentence with spaces or as a list/array where each entry is a word| Report Duplicate | Flag | PURGE
Amazon SDE1 String Manipulation - 1of 1 vote
AnswersWrite a program to find the smallest number that can be formed by 0 and 9 which is divisible by a given number.
- Shaziya Syeda September 22, 2014 in India
For example, if given number is 3 output should be 9,
if given number is 2 output is 90,
if given number is 10 output is 90,| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - -2of 2 votes
AnswersWrite a program to find the smallest number that can be formed by 0 and 9 which is divisible by a given number.
- Shaziya Syeda September 22, 2014 in India
For example, if given number is 3 output should be 9,
if given number is 2 output is 90,
if given number is 10 output is 90,
if given number is 7 output is 10^23.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 2 votes
AnswersGiven ten million numbers, each having 11 bits, find the most time efficient way to sort the numbers.
- alregith September 20, 2014 in United States for Marketplace Team| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersGiven an array and a number, find two integers that sums to the given number.
- alregith September 20, 2014 in United States for Marketplace Team| Report Duplicate | Flag | PURGE
Amazon SDE1 Arrays - 0of 0 votes
AnswersMice and holes are placed in a straight line. There are n holes on this line. Each hole can accomodate only 1 mouse. A mouse can stay at his position, move one step right from x to x+1, or move one step left from x to x−1. Any of these moves consumes 1 minute.
- Selfies September 13, 2014 in -
Assign mice to holes so that the time when the last mouse gets inside a hole is minimized.
for example if there are 3 mice positions of mice are:
4 -4 2
positions of holes are:
4 0 5
the answer should be 4
because:
Assign mouse at position x=4 to hole at position x=4 : Time taken is 0 minutes
Assign mouse at postion x=-4 to hole at position x=0 : Time taken is 4 minutes
Assign mouse at postion x=2 to hole at postion x=5 : Time taken is 3 minutes
After 4 minutes all of the mice are in the holes.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersRecursively implement a function that returns boolean value by checking if a binary tree is binary search tree or not.
- mohanraj1311 September 03, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 - -6of 6 votes
AnswersTraveling Salesman Problem
- blessedmanisha86 August 31, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersOn a very large rotated sorted array with one or more duplicates, find the index of a particular number: 20,30,30,45,60,60,5,17,17,19
- Digi Digi August 27, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 0 votes
AnswersHow would you architect a client based recommendation feature(based on customer history) on product detail page?
- Digi Digi August 27, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 0 votes
AnswersDesign Customers who viewed this also viewed that for an online shopping portal
- Digi Digi August 27, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 0 votes
AnswersConsider a regular polygon with N vertices labelled 1..N. In how many ways can you draw K diagonals such that no two diagonals intersect at a point strictly inside the polygon? A diagonal is a line segment joining two non adjacent vertices of the polygon.
- Rahul Sharma August 24, 2014 in India
Input:
The first line contains the number of test cases T. Each of the next T lines contain two integers N and K.
Output:
Output T lines, one corresponding to each test case. Since the answer can be really huge, output it modulo 1000003.
Constraints:
1 <= T <= 10000
4 <= N <= 10^9
1 <= K <= N
Sample Input:
3
4 1
5 2
5 3
Sample Output:
2
5
0
Explanation:
For the first case, there are clearly 2 ways to draw 1 diagonal - 1 to 3, or 2 to 4. (Assuming the vertices are labelled 1..N in cyclic order).
For the third case, at most 2 non-intersecting diagonals can be drawn in a 5-gon, and so the answer is 0.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersThere are 8 statues 0,1,2,3,4,5,6,7 . Each statue is pointing in one of the following four direction North, South, East or West.
- viksolanram4 August 18, 2014 in United States
John would like to arrange the statues so that they all point in same direction. However John is restricted to the following 8 moves which correspond to rotation each statue listed 90 degrees clockwise. (N to E, E to S, S to W, W to N)
Move A: 0,1
B: 0,1,2
C: 1,4,5,6
D: 2,5
E: 3,5
F: 3,7
G: 5,7
H: 6,7
Help John figure out fewest number of moves to help point all statues in one direction.
Input : A string initialpos consisting of 8 chars. Each char is either 'N,'S,'E,'W'
Output: An integer which represents fewest no. of moves needed to arrange statues in same direction. If no sequence possible then return -1.
Sample test cases:
input: SSSSSSSS
Output: 0
Explanation: All statues point in same direction. So it takes 0 moves
Test case 1:
Input : WWNNNNNN
Output: 1
Exp: John can use Move A which will make all statues point to North
Test Case 3:
input: NNSEWSWN
Output: 6
Exp: John uses Move A twice, B once, F twice, G once. This will result in all statues facing W.
Note: Read input from stdin and output from stdout| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersHow to remove file named "~" ?
- Pinky August 09, 2014 in India for ECOX| Report Duplicate | Flag | PURGE
Amazon SDE1 Unix - 2of 2 votes
AnswersGiven a file containing a list of ip addresses that have lost their dots(.'s), write a program to find the ip addresses, assume ipv4. input: 11111 output. 1.1.1.11, 11.1.1.1, etc
- rk August 09, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1