Amazon Interview Questions
- 2of 2 votes
AnswersWrite a function that finds out if any two numbers within that array add up to a target.
- Bheesham March 27, 2013 in United Statesbool addsUp(Array<int> input, int target);
| Report Duplicate | Flag | PURGE
Amazon Intern Algorithm Problem Solving - 2of 2 votes
AnswersGiven a function, take a number and the bit position and return true if that bit is set to 1 and false otherwise.
- An April 04, 2012 in United States
It took me a few minutes to think something like this, pasted code is after he corrected me on 2 silly mistakes.
bool ret_result(int number, int pos) {
int k=1;
for(int i=0;i<pos;i++) {
k=k<<1;
}
if(number&k==1) {
return true;
}
else {
return false;
}
}| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Bit Manipulation - 2of 2 votes
AnswersI have 10 million 10-bit integers to sort, how would you sort them and what's the time complexity?
- chriscareercup November 12, 2012 in United States
Follow-on question: Instead of sorting integers, I now have 10 million pairs to sort. Each pair consists of a 10-bit integer and an object, the sort order is determined by the 10-bit integer. Will your original sort algorithm hold or do you need sort it differently?
(A word of advice: Ask as many questions as you want during the interview, but you MUST be quick. Also, don't mention anything until you've thought it through clearly, otherwise you're just inviting more questions. Time is of essence, you're too slow if this question takes you more than 15 minutes to come up with the optimal solution, because remember, you have to leave time for explanations and other questions)| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Sorting - 2of 2 votes
AnswersGiven an n x n matrix A(i,j) of integers, find maximum value A(c,d) - A(a,b) over all choices of indexes such that both c > a and d > b.
- vik October 07, 2013 in United States
Required complexity: O(n^2)| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm Arrays Data Structures Ideas Matrix - 2of 2 votes
Answers
- Aalekh Neema July 02, 2017 in IndiaLazy Bartender : There are N number of possible drinks.(n1,n2..) Has C number of fixed customers. Every customer has fixed favourite set of drinks. Bartender has to create least possible number of drinks to suffice need of all the customers Example: Cust1: n3,n7,n5,n2,n9 Cust2: n5 Cust3: n2,n3 Cust4: n4 Cust5: n3,n4,n3,n5,n7,n4 Output: 3(n3,n4,n5)
| Report Duplicate | Flag | PURGE
Amazon SDE-2 - 2of 2 votes
AnswersPrint the longest path from root to leaf in a Binary tree (Basically the nodes that lie on the height path).
- abhinavg.stack January 08, 2017 in United States| Report Duplicate | Flag | PURGE
Amazon Backend Developer Data Structures - 2of 2 votes
Answersfind first not-repeating character by iterating through the length of the string only once and by using constant space.
- Raj October 28, 2016 in United States| Report Duplicate | Flag | PURGE
Amazon SDET Algorithm - 2of 2 votes
AnswersSwap the elements in Kth position from the start and end of a link list.
- Aussie July 27, 2016 in United States
ex:
input: list: 1,2,4,5,7,8 & K=2
output: 1,7,4,5,2,8| Report Duplicate | Flag | PURGE
Amazon Senior Software Development Engineer Algorithm - 2of 2 votes
Answers|X XX | | X X | | X | | |
X = land.
- HumbleLearner February 20, 2016 in United States
Empty space = Water.
Find the number of islands present. (Upto you how you want to represent land and water in the array above)
Answer for the above example: 3
I wish I could draw the diagram better!
Explanation: 3 because:
The three islands are:
X
X
X
XX
X| Report Duplicate | Flag | PURGE
Amazon Software Engineer Intern Algorithm - 2of 2 votes
Answersn mice are playing in the desert, when one of them notices some hawks flying in the sky. It alerts the other mice who now realize that the hawks are going to attack them very soon. They are scared and want to get inside holes to ensure their safety.
- chhipababa September 27, 2014 in United States
Mice and holes are placed on a straight line. There are m holes on this line. Each hole can accommodate only 1 mouse. A mouse can either stay at its position, or move one step right from x to x+1, or move one step left from x to x-1. Any of these movements takes 1 minute.
Assign mice to holes so that the time required for all the mice to move inside the holes is minimized.
Input Format
The first line contains an integer T, the number of test cases. This is followed by T blocks of input:
First line contains 2 positive integers n and m separated by a single space.
Next line contains n space separated integers, denoting the positions of the mice.
Next line contains m space separated integers, denoting the positions of the holes.
Note: No two holes have the same position.
Output Format
For each testcase, print the minimum time taken by all the mice to reach inside the holes.
Constraints
1 ≤ T ≤ 17
1 ≤ n ≤ 131072
1 ≤ m ≤ 131072
n ≤ m
-108 ≤ mouse[i] ≤ 108
-108 ≤ hole[j] ≤ 108
Sample Input
1
3 4
2 0 -4
3 1 2 -1
Sample Output
3
Explanation
One possible solution is :
Assign mouse at position x=-4 to hole at position x=-1 -> 3 minutes
Assign mouse at postion x=2 to hole at position x=2 -> 0 minutes
Assign mouse at postion x=0 to hole at postion x=3 -> 3 minutes
So the answer is 3, after 3 minutes all of the mice are in the holes.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 2of 2 votes
Answers{{
- skc25pma February 02, 2015 in India
There are 3 machines M1, M2 and M3. Each machine is 90% full of its capacity with integers. Now you have to sort all the integers combined and then store the first 1/3rd in M1, second 1/3rd in M2 and last 1/3rd in M3.
Your objective is to minimize the number of sort operations and number of data transfer operations.
Each sort operation/data transfer operation is counted as 1 irrespective of the count of values that are being sorted/transferred.
}}| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm Coding Sorting - 2of 2 votes
AnswersGiven a stack.
- BlackMath June 26, 2012 in India for KDK - Kindle Development Kit
Can we find range of numbers in the stack ?
Range is Max value in stack - Min value in stack.
Q > How will we design the stack to get Range in O(1) ?
Ans > I answered this one saying we have max variable and min variable defined in the stack. Whenever we push any number into stack, we compare with the current max and update, if necessary. Same with min.
Q > Then, he asked me what happens when we pop ?
If the element to be popped is the max element, how do we find the second max to be the new max element.
Ans > This, i answered we maintain two different stacks inside a stack called maxStack and minStack for max and min elements. He asked me to code everything. I did.
Then, he asked me if there are duplicates in the stack, can we optimise our solution so that the max element doesn't get inserted into the maxStack more than once and still we get all the above functionalities in optimised way ?
Ans > I answered we maintain a map of integer and it count. When we push into the stack, if the element is already there in the stack, we increase its count and update the maxStack or minStack, if necessary. When we pop, we decrease the count. If count becomes 0, then we update the maxStack and minStack, if necessary.
I coded everything then.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 2of 2 votes
AnswersQuestion on Tree Data Structure: How can we fill all inorder successor pointer of all tree nodes ?
Tree node contains 3 pointers *left, *right and *Successor .Struct node{ int data; struct node *left; struct node *right; struct node *successor; };
A / \ B C / \ / \ D E F G
INORDER Traversal: **DBEAFCG**
**Note:** A inorder successors are F,C and G.
**Function prototype:** void FillSuccessorNodes( struct node *root);
Tree's root node given to us and we need to fill successor pointer for all nodes.case 1) some of the Successor pointers may be **NULL** . This case you have to fill that pointer with immediate Inorder Successor.
Example: if A->Successor == NULL, then fill A->Successor = F
case 2) some of the Successor pointers may already points to correct successors. This case You no need to modify successor pointers.
Example: 1) A->successor = F is valid
2) A->successor = C is valid
3) A-successor = G is valid . All these three cases you no need to modify successor pointer since these already pointing to correct successor nodes.case 3) Some of the successor pointers are **not NULL** but these pointers pointing to INVALID successors i.e it could be inorder successor or some garbage value. This case you have to fill these nodes with immediate successor nodes.
Example:
1) A->successor = B is invalid since B is not successor node , so we have to correct it to A->successor = F.
2) A->successor = 0x23237463478 is invalid since it is pointing to garbage value. So we we have to correct it to A->successor = F.**1) Interviewer asked me time efficient solution in O(n) time complexity. Extra space allowed. 2) she gave some hint i.e we can use HASHing.**
- siva.sai.2020 December 01, 2010**If you know the solution for this problem, please let me know .**
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 2of 2 votes
AnswersQuestion 1 / 3 (Odd even level difference)
- Harjit Singh September 27, 2013 in India for TCS
You are given a function calcDifference which takes in the root pointer of a binary tree as it's input. Complete the function to return the sum of values of nodes at odd height - sum of values of node at even height. Consider the root node is at height 1
Sample Input:
Sample Output
-74
Explanation:
[ (1 + 4 + 5 + 6 + 7 ) ? (2 + 3 + 8 + 9 + 10 + 11 + 12 + 13 + 14 + 15) = -74 ]| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm C++ Trees and Graphs - 2of 2 votes
AnswersIn a string detect the smallest window length with highest number of distinct characters. For eg.
- neer.1304 September 12, 2015 in United States
A = “aabcbcdbca”, then ans would be 4 as of “dbca”| Report Duplicate | Flag | PURGE
Amazon SDE-2 - 2of 2 votes
AnswersI have two arrays A and B(each containing 8 bit integers). Find the common elements between them.
- puneet.sohi April 28, 2014 in United States for AWS
The questions started out as a general discussion with the most inefficient method. Then the interviewer asked me to improve the solution (to give a NlogN and finally a linear time solution)| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 2of 2 votes
Answersimplement division without using division operator in log(n) time.
- !@# April 22, 2014 in India| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 2of 2 votes
AnswersFind the largest substring palindrome in a given string.
- revanthpobala October 01, 2015 in United States
ex: input: abbac output: abba
Solution: Use Hashmap| Report Duplicate | Flag | PURGE
Amazon SDET Algorithm - 2of 2 votes
AnswersYou are given numbers from 1 through 100 in an array, there is one number missing, find that one
- juny January 26, 2014 in United States| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 2of 2 votes
Answers5! = 5 * 4 * 3 * 2 * 1 = 120 (it contains 1 zero).
- pal January 22, 2014 in India
How many zeroes will be contained in 100! then.
Explain with logic.| Report Duplicate | Flag | PURGE
Amazon Quality Assurance Engineer Problem Solving - 2of 2 votes
AnswersWAP to sort prime numbers smaller than given N by digits. If N is 40, the output should be 11, 13, 17, 19, 2, 23, 29, 3, 31, 37, 39, 5, 7.
- lngbrc October 24, 2013 in United States
Follow-up question: limit memory usage.| Report Duplicate | Flag | PURGE
Amazon Senior Software Development Engineer Math & Computation - 2of 2 votes
AnswersIn a BST, I want to replace all nodes with value which is the sum of all the nodes which are greater than equal to the current node.
- Abhishek Shrivastava April 20, 2013 in United States
5
2 10
Output -->
15
17 10| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 2of 2 votes
AnswersYou have 81 balls. 80 balls have the same weight. 1 ball is the lightest one. What would be the minimum possible way to find the lightest ball ?
- AlgoBaba November 23, 2014 in United States
(Use Dynamic Programming)| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Dynamic Programming - 2of 2 votes
Answersinput:
- S.Abakumoff February 25, 2013 in United States
sum - the integer amount
n - the number of coins
d - the array contains the coins denominations
WAP that prints all the possible non-repeated combinations of n coins of denominations from d that sum up to n.
Sample of input:
d={1,5,10,15}
sum = 30
n = 6
The expected output:
1,1,1,1,1,25
5,5,5,5,5,5| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 2of 2 votes
AnswersAlgorithm: You have 50,000 html files, some of which contain phone numbers. How would you create a list of all the files which contain phone numbers?
- Gayle L McDowell April 04, 2005| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer System Design 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 - 2of 2 votes
AnswersGiven N sets of integers, remove some sets so that the remaining all sets are disjoint with one another. Find the optimal solution so that the number of sets remaining at the end is maximum
- Rahul Sharma July 12, 2014 in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 2of 2 votes
Answersgiven a binary tree and a leaf node. holding a leaf node and whole tree falls down such that it is the new root of the tree. return the modified tree.
- Nascent June 07, 2014 in India| Report Duplicate | Flag | PURGE
Amazon - 2of 2 votes
AnswersLink all the level order nodes to makes a linked list with the first node of each level acting as the root of that linklist.
- catlover February 27, 2015 in India
10
/ \
6 17
/ / \
4 14 19
So the Linklist will be
10->null
6->17->null
4->14->19->null| Report Duplicate | Flag | PURGE
Amazon SDE1