Amazon Interview Question Software Engineer / Developers

  • amazon-interview-questions
    3
    of 3 votes
    34
    Answers

    Had 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.
    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.

    - S on July 01, 2008 Report Duplicate | Flag
    Amazon Software Engineer / Developer Java Data Structures Object Oriented Design Coding



Comment hidden because of low score. Click to expand.
9
of 9 vote

3. Coding: I have an integer array where every number appears even number of times and only one appears odd times. Find the number.

XOR all the numbers together. The final result of XOR is your answer. O(1) space, O(n) time.

- Guest on August 18, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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
----------------------------
ANS:
Relation:
1 game -- 2 player , 1 deck ( atleast )
1 deck - 52 cards.
so entities are

Cards , Deck , Player , Game:
class cards
{
int rank;
int suits;
int type;
int name;
};

Class Deck
{
Cards *deck;
fill();
shuffle();
};

class Player
{
int number_of_cards;
string name;
Cards play_card();
void collect_card(Cards C);
string get_name();

};

Class Game
{
void play();
Player getWinner();
bool enough_cards
};

- Deepak Garg on October 03, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

What about below solution:

class Vehicle
{
}

class Slot
{
	Type: regular, handicapped, compact
	int index
}

class Parking
{
	Slot arrSlots[]

	Status: full, empty
	GetStatus()

	//Lets assume regular slots are from 0 to 99, handicapped from 100 to 199 and compact 200 to 299
	int iIndexRegular=0, iIndexHandicapped=100, iIndexCompact=200

	int iRegularFilledUpto=-1, iHandicappedFilledUpto=-1, iCompactFilledUpto=-1

	//Below Lists will maintain the list of slots which were filled once and then emptied
	List EmptiedRegular, EmptiedHandicapped, EmptiedCompact

	Map VehicleToSlot<Vehicle vehicle, Slot slot>

	ParkVehicle(Vehicle vehicle, Slot.Type slotType) throw NotEmpty
	{
		switch (slotType)
		{
			case regular:
			{
				if (!EmptiedRegular.isEmpty)
				{
					Slot freeSlot = EmptiedRegular[0];
					EmptiedRegular.Remove(freeSlot);
					VehicleToSlot.Add(vehicle, freeSlot);
					return;
				}

				if (iRegularFilledUpto + 1 <= 99)
				{
					iRegularFilledUpto++;
					VehicleToSlot.Add(vehicle, arrSlots[iRegularFilledUpto]);
					return;
				}
				throw NotEmpty
			}
			...//Same for other slot-types
		}
	}
	DeparkVehicle(Vehicle vehicle) throw NotFound
	{
		Slot slot = VehicleToSlot[vehicle];
		if (null == slot)
		{
			throw NotFound;
		}
		VehicleToSlot.Remove(vehicle);
		switch (slotType)
		{
			case regular:
			{
				EmptiedRegular.Add(slot)
			}
		}
		...//Same for other slot-types
	}
}

- AseemSharma on April 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.
-------------------------------------------------------------
Idea was number of parking car allotment can depend on parking type.
User can put diff -2 algo to find the spot for diff parking type,
-------------------------------------------------------------
class parking
{
virtual bool full() =0;
virtual bool empty()= 0;
virtual bool spot_position()=0;
};

class RegularParking:public Parking
{
static int number_of_cars;
bool full() ;
bool empty()= 0;
int spot_position()=0;
};
class HandicapedParking:public Parking
{
static int number_of_cars;
bool full() ;
bool empty()= 0;
int spot_position()=0;
};
class CompactParking:public Parking
{
static int number_of_cars;
bool full() ;
bool empty()= 0;
int spot_position()=0;
};

- Deepak Garg on October 03, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is much more flexible solution. I think parking spot finding logic should be there.

class ParkingSpot{
	private ArrayList<Parking> pList;
	public ParkingSpot(){
		pList=new ArrayList<Parking>();
	}
	public void add(Parking p){
		pList.add(p);
	}
	public int spot(String type){
		for(int i=0; i<pList.size(); i++)
			if(pList.get(i).getType()==type)
				return pList.get(i).spot_position();
		return -1;
	}
	public boolean vacate(String type, int num){
		for(int i=0; i<pList.size(); i++)
			if(pList.get(i).getType()==type)
				return pList.get(i).free(num);
		return True;
	}
}

- spiderman on August 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Answer to Interview Qs # 3

package com.badal.HashTable;

import java.util.Hashtable;

public class HashTable3 {

public static void main(String [] args){
Hashtable<Integer,Integer>hashtable=new Hashtable<Integer, Integer>();

for(int i=0;i<args.length;i++){
if(hashtable.containsKey(Integer.parseInt(args[i]))){
hashtable.put(Integer.parseInt(args[i]), hashtable.get(Integer.parseInt(args[i]))+1);
}else{
hashtable.put(Integer.parseInt(args[i]), 1);
}

}

System.out.println("Start printing the hash table");
for(int key:hashtable.keySet()){
System.out.println(key+" = "+hashtable.get(key));
}
System.out.println("End printing the hash table");

for(int key:hashtable.keySet()){
if(hashtable.get(key)%2==1){
System.out.println("Odd occurence number is: "+key);
}

}


}

}

- badalrocks on January 08, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This can be done in linear time too without using extra memory i.e. HashTables.

- shuby.gupta on March 26, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Exactly, it can be done by merely going through the array of integers and keeping track of how many times each int appears by storing the count in the array 'count[]'.

Here count[i]=no. of times the i'th unique integer appears in the array. On each occurrence of i, count[i] should be increased by 1.

I don't understand the need to make it extra complicated by introducing a Hashtable!

- Anonymous on June 24, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Say the array was

{1,3,5,1,5} where a[0] = 1 and a[3] = 1.


Now when you get to index 3 (thus looking at the second occurence of 1), how do you know that you need to update count[0] (or which ever element of count)?

At least the hashtable solution works with O(n) average runtime.

There is a better solution, though: just XOR all the integers and you are done.

- LOLer on June 24, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

isnt .. instead of hashtable & array ... cant we sort the given integer array and then find whether the integer appears odd or even number of times. Also, you can break the loop as soon as find the odd number of appearance integer.

Sorting - O(log n)
iteration - O(n)

so even though its O(n) on the whole, we are saving extra memory. What you guys think?

- Spawn_hmmm on September 07, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Correction: Sorting O(nlogn)

so on the whole it is O(nlogn)

- Spawn_hmmm on September 07, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

why not perform an XOR operation throughout the array and the final result will be the answer.

- Prem on September 09, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Its not a bad idea. The complexity is stiall O(n)

- Anonymous on January 17, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can Somebody explain how XOR idea works?

- Shri on February 18, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

if you know whats property of XOR then this question is simple enough.

1 XOR 0 = 1
0 XOR 1 = 1
1 XOR 1 = 0
0 XOR 0 - 0

so even numbers will be eliminated where ever they are in array and odd number will left (since A XOR A XOR A = A)

- reall on March 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why Hashtable? why not HashMap?

- Hrushi on January 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

XORing is the best solution:

import java.lang.StringBuilder;
import java.util.Arrays;

public class XorInts {
	int[] ints;

	public XorInts(int[] ints) {
		this.ints = ints;
	}

	public int findOddInt() {
		int val = ints[0];
		for (int i=1; i<ints.length; ++i) {
			val ^= ints[i];
		}
		return val;
	}

	public String toString() {
		StringBuilder sb = new StringBuilder();
		for (int i=0; i<ints.length; ++i) {
			sb.append(ints[i]+" ");
		}
		return sb.toString();
	}

	public static void main(String[] args) {
		int[] ints = new int[99];
		for (int i=0; i<ints.length; i+=2) {
			int val = (int)(Math.random()*100);
			ints[i+0] = val;
			if (i+2 <= ints.length) {
				ints[i+1] = val;
			}
		}
		XorInts xorints = new XorInts(ints);
		System.out.println("Before sort: "+xorints.toString());
		System.out.println("Xor value  : "+xorints.findOddInt());
		Arrays.sort(ints);
		xorints = new XorInts(ints);
		System.out.println("After sort : "+xorints.toString());
		System.out.println("Xor value  : "+xorints.findOddInt());
	}
}

Output from the above:

Before sort: 22 22 60 60 79 79 6 6 17 17 87 87 34 34 30 30 86 86 78 78 70 70 63 63 73 73 45 45 23 23 39 39 83 83 47 47 39 39 15 15 80 80 81 81 56 56 5
 5 23 23 28 28 64 64 68 68 39 39 37 37 42 42 68 68 67 67 72 72 31 31 3 3 96 96 16 16 18 18 14 14 87 87 24 24 1 1 6 6 30 30 54 54 92 92 95 95 16 16 5
Xor value  : 5
After sort : 1 1 3 3 5 5 5 6 6 6 6 14 14 15 15 16 16 16 16 17 17 18 18 22 22 23 23 23 23 24 24 28 28 30 30 30 30 31 31 34 34 37 37 39 39 39 39 39 39 4
2 42 45 45 47 47 54 54 56 56 60 60 63 63 64 64 67 67 68 68 68 68 70 70 72 72 73 73 78 78 79 79 80 80 81 81 83 83 86 86 87 87 87 87 92 92 95 95 96 96
Xor value  : 5

- Kory on July 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.
------------------
Ans: Is it a binary search tree? In that case, it will take O(logN) where N is the isze of the bucket.

5.
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.
---------------

We can use Hashing for this. Hash the phone numbers of the first file. Then take the 2nd file phone number and try to hash, if the element already exists in the Hash table, then print that phone number.

- Sadineni.Venkat on February 14, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you elaborate solution to Q3: 3. Data Structures: How will you use a hashtable to find data in a tree?

- Anonymous on October 29, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i think the question is to locate data in tree with the help of hashtable. So, when data is inserted in tree, its node address is to be stored as value for the key data in hashtable.

- spiderman on August 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Mr Badal,
What exactly are you trying to do ?

- Anonymous on May 22, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Solution: reverse the bits of the given integer and store it in another variable. Now check both the numbers whether they are equal or not. If equal the given number is palindrome otherwise not.

The code as follows:
int input; // given input number - find palindrome or not
int reverse_input = 0; // this will contain the no in which the bits are reverse order of the given input

while(input)
{
int remainder = input % 2;
reverse_input = (reverse_input << 1) | remainder;
input = input / 2;
}

// Now check if they are equal or not
if(input == reverse_input)
print "Is Palindrome"
else
print "Not Palindrome"

- Sreenivas on August 20, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can check they are equal or not by using XOR operation.

- Anonymous on September 19, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

lovely solution

- spiderman on August 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void reverseBits(int n)
{
int rev = 0;
int o = n;
while(n)
{
rev = (n & 1) | rev;
n = n >> 1;
if(n)
rev = rev << 1;
}
decimal_to_anybase(o,2);
decimal_to_anybase(rev, 2);
if(o == rev)
cout<<"Palindrome\n";
else
cout<<"Not palindrome\n";
}

- M on August 14, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ignore decimal_to_anybase calls above

- M on August 14, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Push half the elements in a stack of bits. Then pop each element while comparing it to the subsequent half of bits.

- Venkat on July 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Reversing bits is pretty simple, enjoy this quick example:

public class ReverseBits {
	public static int reverseBits(int i) {
		int val = 0;
		int n = 0;
		while (n<32) {
			int bit = (i >> n) & 1;
			val = (bit << (31-n)) | val;
			++n;
		}
		return val;
	}

	public static String toBinaryString(int i) {
		String binaryString = String.format("%32s", Integer.toBinaryString(i)).replace(' ', '0');
		StringBuilder sb = new StringBuilder();
		for (int j=0; j<binaryString.length()/4; ++j) {
			sb.append(binaryString.substring(4*j,4*(j+1)));
			sb.append(" ");
		}
		return sb.toString();
	}

	public static void reverse(int i) {
		String binarystr = ReverseBits.toBinaryString(i);
		System.out.println(String.format("%10d = %32s",i,binarystr));
		int reverse = ReverseBits.reverseBits(i);
		String binarystrRev = ReverseBits.toBinaryString(reverse);
		System.out.println(String.format("%10d = %32s",reverse,binarystrRev));
	}

	public static void main(String[] args) {
		int i = 1114;
		reverse(i);
		i = (int)(Math.random()*Integer.MAX_VALUE);
		reverse(i);
	}
}

- Kory on July 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Output from above code:

1114 = 0000 0000 0000 0000 0000 0100 0101 1010
1512046592 = 0101 1010 0010 0000 0000 0000 0000 0000
 848272352 = 0011 0010 1000 1111 1001 1011 1110 0000
 131723596 = 0000 0111 1101 1001 1111 0001 0100 1100

- Kory on July 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

hi S... I dont ur name .bt I would like to discuss some about design problem.If u have no problem .can u give me a call as soon as possible..just send me the acknowledgement on my email Id on jigu4paint@yahoo.com.I will send my number.

I really need ur help..
Thanks

- Jigs on July 05, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This Should help us a lot! Thanks for posting al the questions

- BSR on July 18, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

thanks a lot for sharing this!! it gave me a clear picture of how amazon photo interview looks like, very very helpful!

- Anonymous on October 22, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

ya photo

- Anonymous on July 24, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think he meant photon

- Anonymous on June 12, 2013 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More