Amazon Interview Questions
- 0of 0 votes
Answersreverse a single linked link - recursive and iterative. tell the O(n) for each.
- vickykansal December 19, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersQ: Pretend I'm a Dog breeder and you are an SDE. Design a solution for tracking my dog's pedigrees.
- vickykansal December 19, 2013 in United States
Followup - pedigree may also be hybrid. need a data structure which can lookup by pedigree to see if dog exists. also should be able to search by pedigree and some characters of dog.| Report Duplicate | Flag | PURGE
Amazon SDE1 Data Structures - 1of 1 vote
Answersgiven a N x N matrix find the no. of times a word is present in that matrix. constraints you can move in 3 directions from one cell 1. forward (x+1,y), 2. down (x, y+1) 3. diagonal(x+1,y+1) . Find all the occurance of all the word
- GOOGLE_SDE December 16, 2013 in India
solution approach --> BFS or DFS
eg:-
forward means right (x+1,y)
down mean (x,y+1)
diagonal means (x+1,y+1)
it can be done with BFS. {search the no. of occurance of a given word example "sachin" in the whole NxN matrix}
w | s | r | t | g | g|
a | a | c | h | i | n |
k | c | h | u | j | j |
o | h | i | n | y | q |
in this sachin can be found out 3 times.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersWe have a fictitious multi-level marketing scheme where a member can recruit one or more other members. At the end of the month, member’s payout is calculated at 10% of his direct sales (items the members sells
themselves) and 4% of sales generated by his recruits and their recruits.
Write a function that calculates the monthly compensation for all members given the original member. You can assume a member can only be recruited by a single existing member.
Given the following interface, please implement the MemberPayoutUtil.calculatePayout function.
- Albert1981 December 15, 2013 in United Statespublic interface Member { public double getMonthlySales(); private Collection<Member> getRecruitedMembers(); } public class MemberPayoutUtil { public static double calculatePayout(Member member) { // Implement me! } }
| Report Duplicate | Flag | PURGE
Amazon SDE1 Java - 1of 1 vote
Answersgiven a N x N matrix find the no. of times a word is present in that matrix. constraints you can move in 3 directions from one cell 1. forward , 2. down 3. diagonal . Find all teh occurance of all the word
- GOOGLE_SDE December 14, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - -1of 1 vote
Answers/*
- Anonymous December 08, 2013 in India
Question 2 / 36 (FizzBuzz)
Write a program which prints the numbers from 1 to N, each on a new line. But for multiples of three print “Fizz” instead of the number 3 and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”. Read in the input number from STDIN.
Sample Input #00:
15
Sample Output #00 :
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
Explanation:
Position 3,6,9,12 have the word "Fizz" because they are multiples of 3.
Positions 5 and 10 have the word "Buzz" because they are multiples of 5.
Position 15 has the word FizzBuzz because it is a multiple of both 3 and 5.
*/
import java.io.*;
class Solution {
public static void main(String args[] ) throws Exception {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter the value of N");
int N=Integer.parseInt(br.readLine());
Solution objSolution=new Solution();
objSolution.fizzBuzz(N);
}
public static void fizzBuzz(int N) throws IOException
{
for(int i=0;i<=N;i++)
{
if((i%5==0)&&(i%3==0))
{
System.out.println("fizzBuzz");
}
else
{
if((i%3)==0)
{
System.out.println("Fizz");
}
if((i%5)==0)
{
System.out.println("Buzz");
}
if((i%3!=0)&&(i%5!=0))
{
System.out.println(i);
}
}
}
}
}
----------------------------------------
What is the complexity of this algorithm ?
Is there any solution with better efficiency ?| Report Duplicate | Flag | PURGE
Amazon SDE1 - 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 - 0of 0 votes
AnswersFind cousins of a given node in a Binary tree and BST.
My Approach:
- behinddwalls December 07, 2013 in United StatesSteps:(Using level order Traversal) 1. Create a queue q and en-queue root element and take variable qSize and a flag=true 2. Start a loop and check queue is empty or not { if qSize==0 then qSize=q.size(); if not flag then print the current queue (q) Start one more loop and check for qSize>0 { qSize-- x=deque(); if((x.left != null && x.left== key) || (x.right!= null && x.right== key)) { flag=false continue } enqueue(x.left) enqueue(x.right) } }
| Report Duplicate | Flag | PURGE
Amazon SDE1 Trees and Graphs - 1of 1 vote
AnswersFind the longest path in a binary tree
- rahul23111988 December 04, 2013 in India
with one bend.
One bend means like SAY I HAVE
1
2 44
3
With one bend means all the nodes means if we start connecting nodes then connect as much as possible in a single line and u can take maximun one bend.Say left left left than right right right.That is maximum one turn..It is not same as diameter say ia have
1
/
2
\
3
Diameter of above is 3 but if we take all the nodes then we will have 2 bends..
So we will two nodes to get nodes with one bend..hope m clear| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 0 votes
AnswersDesign a OO system for furniture where there are wooden chairs and tables, metal chairs and tables. There are stress and fire tests for each products.
- samotgun November 18, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 Object Oriented Design - 1of 1 vote
AnswersFind the first non-repeating character in a stream of characters?
- samotgun November 18, 2013 in United States| Report Duplicate | Flag | PURGE
Amazon SDE1 Hash Table Software Engineer / Developer Algorithm - 0of 0 votes
AnswersWhat language are you most comfortable with? (I answered C/C++)
- ootah November 14, 2013 in United States
What's an unordered map, and how is it implemented?| Report Duplicate | Flag | PURGE
Amazon SDE1 Knowledge Based - 2of 2 votes
Answers"Given an array of strings, find the string which is made up of maximum number of other strings contained in the same array.
- mail.kshitij.jain October 10, 2013 in India
e.g. “rat”, ”cat”, “abc”, “xyz”, “abcxyz”, “ratcatabc”, “xyzcatratabc”
Answer: “xyzcatratabc”
“abcxyz” contains 2 other strings,
“ratcatabc” contains 3 other strings,
“xyzcatratabc” contains 4 other strings"| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 1of 1 vote
AnswersImplement Cache in Java.
- niraj.nijju October 10, 2013 in United States for kindle
function should support
Object get(key)
void put(key, value)| Report Duplicate | Flag | PURGE
Amazon SDE1 - 1of 1 vote
AnswersGiven a class with n people,where each people plays a game with all other people. Results are with you. You have to arrange them in a queue with a condition that, a[i] should have won a[i-1], for all I, you don’t need to care about a[i-2] . (a[i] may win or lose a[i-2]).
- mail.kshitij.jain October 09, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 1of 1 vote
AnswersPrint all pairs(sets) of prime numbers (p,q) such that p*q <= n, where n is given number
- mail.kshitij.jain October 09, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 0of 0 votes
AnswersGiven a chess board of finite length (NxN), start position of a knight(x, y) and an end position (p, q). 1) Find number of minimum hops required to reach end position.
- Vin October 08, 2013 in India
2) Check your solution extendable to infinite length chess board ??| Report Duplicate | Flag | PURGE
Amazon SDE1 - 1of 1 vote
AnswersDesign a DS to perform
- Vin October 08, 2013 in India
1. Insert
2. Search
3. Delete
4. Get Random
All in O(1).| Report Duplicate | Flag | PURGE
Amazon SDE1 - -2of 2 votes
Answersn1 pairs of “{} ” brackets
- Vin October 08, 2013 in India
n2 pairs of “[] ” brackets
n3 pairs of “() ” brackets
Print all valid combinations of all the pairs| Report Duplicate | Flag | PURGE
Amazon SDE1 - -4of 4 votes
AnswersA student needs to implement a BST structure to solve a problem, but instead he used a linked list. New value will always be added at beginning of a linked list. So basically at each step after insertion , root of BST and head of link list should point to same node. Then give an example of input sequence, in which his implementation works…
- Vin October 08, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 - 0of 2 votes
AnswersGiven an array consisting of both positive and negative numbers, 0 is considered as positive, rearrange the elements such that positive and negative numbers are placed alternatively, constraints are that it should be in-place and order of elements should not change.
- Vin October 08, 2013 in India| Report Duplicate | Flag | PURGE
Amazon SDE1 - 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
AnswersYou are given an array whose each element represents the height of the tower. The width of every tower is 1. It starts raining. How much water is collected between the towers?
- mail.kshitij.jain October 06, 2013 in India
Eg. [1,5,3,7,2] – then answer is 2 units between towers 5 and 7.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - 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
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
AnswersQuestion 3 / 3 (Find first unique character)
- Harjit Singh September 27, 2013 in India for TCS
Find the first unique character in a Stream. Please note that you are being provided a stream as a source for these characters.
The stream is guaranteed to eventually terminate (i.e. return false from a call to the hasNext() method), though it could be very long. You will access this stream through the provided interface methods.
A call to hasNext() will return whether the stream contains any more characters to process.
A call to getNext() will return the next character to be processed in the stream.
It is not possible to restart the stream.
If there is no unique character, then return the character '#'. # won't be any character in the character stream.
You just have to complete the function getUniqueCharacter() using the functions hasNext() and getNext() which are already defined.
Example:
Input:
aAbBABac
Output:
b
Input:
aBBa
Output:
#| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm C++ Data Structures - 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 - -5of 7 votes
AnswersGiven a matrix of size M X N containing all 0's, and a co-ordinate (i, j) in the matrix.
You have to fill the matrix with L shape block (made by 3 blocks, each block is having 1) except the given co-ordinate.1 1 1 1 1 1 1 1 1 1 1 1
Note - L shaped block can be rotated, so finally there will be 4 orientation for L shape block.
- Nitin Gupta September 27, 2013 in United States for AppStore
You can assume that solution always exists.
Later on he changed matrix to N X N where N = 2^n.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm - -1of 1 vote
AnswersGiven 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
- pirate September 14, 2013 in India
Input #01:
Coin denominations: { 5,5,5,5,5 }
Required sum (S): 11
Output #01:
-1| Report Duplicate | Flag | PURGE
Amazon SDE1 - 2of 2 votes
AnswersGiven a n (large number) lists of customers who visited n webpages on n (large number) days, design a data structure to get customers who have visited the website on exactly “k” days and should have visited at least “m” distinct pages altogether.
- blackfever September 03, 2013 in India
Was then asked to improvise the solution as much as possible| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm