Amazon Interview Question Software Engineer / Developers
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
};
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
}
}
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;
};
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;
}
}
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);
}
}
}
}
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!
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.
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?
why not perform an XOR operation throughout the array and the final result will be the answer.
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)
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
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.
can you elaborate solution to Q3: 3. Data Structures: How will you use a hashtable to find data in a tree?
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.
I think the interviewer is referring to implement TreeMap. where we maintain <key,value> pair and store in RED-BLACK tree.
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"
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";
}
Push half the elements in a stack of bits. Then pop each element while comparing it to the subsequent half of bits.
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);
}
}
Polymorphism : One thing with many forms. Polymorphism possible at function level, at operator level and at class level.
Function with many forms, example is calculateArea(Shape s), based on Shape being Rectangle or Circle, it calls different function with the same signature and calculates area accordingly.
Operator with many forms, example is "+" overloaded to add Rectangle objects to add integers based on operands it takes.
Object with many forms, example is super-class object can person can take form of teacher or student.
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.
Parking lot is supposed to allow parking of the vehicle for the requested type. It should provide the token on successful parking of the vehicle at the parking lot. And, on taking of the vehicle back, it should vacate the parking lot for further use. Parking lot is supposed to maintain all the parking spots.
The possible objects are:
Parking Lot - A system
Parking Spot - A parking place
Vehicle - Car, Jeep, etc..
class ParkingLot
{
List<ParkingSpot> parkingSpots;
Dictionary<int, Vehicle> occupancyMap=new Dictionary<int, Vehicle>();
allocateParkingSpot(int type, Vehicle v)
{
}
freeParkingSpot(int id)
{
}
}
class ParkingSpot
{
int id;
int type;
int row, col;
bool occupied.
}
class Vehicle
{
int type;
}
3. Coding: I have an integer array where every number appears even number of times and only one appears odd times. Find the number.
- Guest August 18, 2009XOR all the numbers together. The final result of XOR is your answer. O(1) space, O(n) time.