Amazon interview question Collection

General Questions and Comments [more]
generic questions on software development


--------------------------------------------------------------------------------

What is the complexity of this algorithm


--------------------------------------------------------------------------------

What is your stronger language (Java or C#)


--------------------------------------------------------------------------------

Lot of design questions and OOAD stuff 2


--------------------------------------------------------------------------------

Programming questions asked were more or less same as the ones listed at this site


--------------------------------------------------------------------------------

more architectural view about solve problem capability. I think the intervier was more realistic than the other two . Not just because he recommend to 2nd interview, since I also have the experience with recuriting other employees in the past. I felt the potenial is more than anything in work. Coding is just one thing , maybe the one who can solve the tricky algorithms is good in some way, but how about the one who has been out of school for several years and I cant remeber anything about mergesort or quicksort or how to find the shortest path blah blah. But I do have the confidence I am very good at work. No matter where I go, I found most people are not that smart and if you are willing to learn, you can be the best. Of course, you must have the potenial first. Like you are willing to learn and you like your job... 5


--------------------------------------------------------------------------------

3rd phone interview


--------------------------------------------------------------------------------

what do you like in a job 2


--------------------------------------------------------------------------------

gave some description about the job and then it is done


--------------------------------------------------------------------------------

I took around 2 hours to do a good job for this becoz he wanted propper OO concepts. Created the util class as a singleton with synchronization for the add and edit methods with exceptions being thrown when employee's arent found etc. He seemed to like it from the reply mail i received


--------------------------------------------------------------------------------

The standard stuff had to be added to the api like synchronization, singleton etc.


--------------------------------------------------------------------------------

its coming up soon, hopefully ill do good :D


--------------------------------------------------------------------------------

How do you resolve a collision in a hash table


Algorithm [more]
Coding: How would you find the nth to last element in a linked list? 27


--------------------------------------------------------------------------------

Algorithm: Explain algorithm to shuffle cards 8


--------------------------------------------------------------------------------

Coding: Jig saw puzzle. What are the data structures? Assume you have some method which can tell you if two pieces fit together. How would you solve the puzzle, minimizing the number of times you have to call that function? 9


--------------------------------------------------------------------------------

Algorithm: 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? 14


--------------------------------------------------------------------------------

Coding: How would you reverse the words in a string? (ie, "the quick brown fox" --> "fox brown quick the" 41


--------------------------------------------------------------------------------

How would you detect a repeated element in an integer array. Discuss various solutions and the order of the algorithm. 37


--------------------------------------------------------------------------------

Write a function to smooth out stock fluctuations. Asked me to layout the mathematical idea for curve smoothing before writing code. 3


--------------------------------------------------------------------------------

Given two sets, Write a function to provide the union of them. STL not allowed to be used.
Optimise for Time and space. 24


--------------------------------------------------------------------------------

Design an algorithm to calculate the most user viewed pages 3


--------------------------------------------------------------------------------

Find missing element in an array of 100 elements. 16


--------------------------------------------------------------------------------

Design an algorithm to find duplicates in an array. Discuss different approaches. 16


--------------------------------------------------------------------------------

Design an algorithm and write code to find nth node from the end in a linked list 3


--------------------------------------------------------------------------------

Design an algorithm and write code to shuffle a standard deck of cards 1


--------------------------------------------------------------------------------

Design an algorithm and write code to serialize a binary tree. Discuss various solutions 18


--------------------------------------------------------------------------------

Design an algorithm and write code to find two numbers in an array whose sum equals a given value 19


--------------------------------------------------------------------------------

Given 2 files, each with names of thousands of customers who bought something from Amazon.com on that particular day. Find the common customers (i.e. common names in file1 and file2) 9


--------------------------------------------------------------------------------

Given 3 files, each with names of thousands of customers who bought something from Amazon.com on that particular day. Find the common customers (i.e. common names in file1 and file2 and file3) 3


--------------------------------------------------------------------------------

count bits in an integer. Solved using mask, did not attempt -1 approach. 6


--------------------------------------------------------------------------------

Given two binary trees, find whether or not they are similar. 12


--------------------------------------------------------------------------------

Determine is a graph is circular. 6


--------------------------------------------------------------------------------

assume your computer is reading characters one by one from a stream (you don't know the length of the stream before ending). Note that you have only one character of storage space (so you cann't save the characters you've read to a something like a strong). When you've finished reading you should return a character out of the stream with equal probability. 11


--------------------------------------------------------------------------------

Algorithm: You have a tree (not Binary) and you want to print the values of all the nodes in this tree level by level. Discussed on phone and asked me to email Java code for my algorithm. 4


--------------------------------------------------------------------------------

Unix: You have 50,000 html files in a UNIX directory structure, some of which contain phone numbers in the format ***-***-****. How would you create a list of all the files which contain phone numbers? (Assume that you already have the regular expression) 5


--------------------------------------------------------------------------------

Given two log files, each with a billion usernames (each username appended to the log file), find the usernames existing in both documents in the most efficient manner? Use pseudo-code or code. If your code calls pre-existing library functions, create each library function from scratch. 8


--------------------------------------------------------------------------------

How could a linked list and a hash table be combined to allow someone to run through the list from item to item while still maintaining the ability to access an individual element in O(1) time? 4


--------------------------------------------------------------------------------

Here is a tree. It's a binary tree but in no particular order. How do you write this tree to a file so that it can be reread in an reconstructed exactly as shown? 33


--------------------------------------------------------------------------------

Here is a graph of distribution centers and the weight to go from one to another. How would you represent this using a data structure? Code an alogrithm that allows me to check if there is a path from one node to another and what the weight of this path is. 1


--------------------------------------------------------------------------------

Given two dates, Design an algorithm to return whether the dates are exactly a month apart, less than a month apart or more than a month apart. 2


--------------------------------------------------------------------------------

Discussed the proof and solution to my card shuffle problem 1


--------------------------------------------------------------------------------

Write a method to shufle the deck. The constraint is it has to be a perfect shuffle - in other words, every 52! permutations of the deck has to be equally like (given a completely random function which is theoretical of course).

I managed to do this with a simple for loop in O(n) time


int[] deck = new int[52];
for(int i=0; i<52; i++)
deck[i] = i;

Random r = new Random();
for(int i=0; i
int ran = r.nextInt(deck.length-i) + i;
int temp = deck[i];
deck[i] = deck[ran];
deck[ran] = temp;
}


--------------------------------------------------------------------------------

int[1000], numbers from 1 to 1000, but one is missed - find it 3


--------------------------------------------------------------------------------

reverse linked list. Why don't you use recursion? 5


--------------------------------------------------------------------------------

If there are two structs, TreeNode and Tree. TreeNode contains 3 elements, data, lChild and rChile. Tree contains 2 elements, int size and TreeNode *root. The tree is a complete tree. So how to find a O(logN) approach to insert a new node. 2


--------------------------------------------------------------------------------

Algorithm and code to detect occurence of a string(patterns) in another string ex: aab, aababa 5


--------------------------------------------------------------------------------

If you are given a set of 1000 integers in a set A , and 10,000,000 integers in a set B, how would you create a set C that would only contain numbers that are both in A and B? 2


--------------------------------------------------------------------------------

In a general tree, how would you find the lowest common ancestor of two nodes that are given to you as parameters? 1


--------------------------------------------------------------------------------

How do you merge n sorted lists with average length K in O(n*log(K)) time? 12


--------------------------------------------------------------------------------

Design an algorithm to find the 100 shortest distances to stars in the universe 1


--------------------------------------------------------------------------------

If you have a draft ransom note and a book, how would you determine if said ransom note can be composed from the book on its own? What if the ransom note is not necessarily in ascii (can be in chinese and such). What if you have no storage save for a few counters?


--------------------------------------------------------------------------------

What is a scripting language? Write a code to output the dot product of two files.


--------------------------------------------------------------------------------

Suggest an algorithm to find the first non-repeating character in a given string. 3


--------------------------------------------------------------------------------

How to find the two numbers whose difference is minimum among the set of numbers 7


--------------------------------------------------------------------------------

a. Findodd - given ana array of numbers return a number which appear odd number of times.
b. isPrime
c. Garbage Collector.
d. OO model for Elevator, grilled a bit but successfully answered.
e. Find if high bit is set in the integer.


--------------------------------------------------------------------------------

Describe the data structures you will use for implementing snake & ladder game 3


Application / UI Design [more]
How would you design a parking garage?


--------------------------------------------------------------------------------

Given an outline for an architectural plan, automate the loading of the design into a computer


Behavioral [more]
Why do you want to work at Amazon? 2


--------------------------------------------------------------------------------

Talk about your favourite project? What part of a Software Project do you enjoy most?


--------------------------------------------------------------------------------

Lunch - QA manager.

1. tell me a situation when u had to face problems and the requirements were not clear. how did u handle the situation?

2. which is the best error you have caught?

3. which is the worst error u've ever caught?

4. asked about a project on my resume


--------------------------------------------------------------------------------

Why do you want to work here?


--------------------------------------------------------------------------------

Favorite feature on Amazon personalization site


--------------------------------------------------------------------------------

How did you hear about Amazon?


--------------------------------------------------------------------------------

what you don't like in a job


--------------------------------------------------------------------------------

what kind og job do you prefer


--------------------------------------------------------------------------------

why amazon


--------------------------------------------------------------------------------

why cs


--------------------------------------------------------------------------------

What is Polymorphism?


--------------------------------------------------------------------------------

If you are already working why are you still looking?


--------------------------------------------------------------------------------

What's the latest book you've read?


--------------------------------------------------------------------------------

If there's a glitch in the system and for some reason, for a very brief moment, the website is inaccessible from your browser. You got back to it a few minutes later and the glitch is gone. Would you report this problem?


Brain Teasers [more]
You have eight balls: seven are the same weight, and one is heavier than the rest. Given a scale that only tells you which side is heavier, how do you find the heavy ball? 9


--------------------------------------------------------------------------------

Given an array of integers where every int has exactly one duplicate except one,
find the number with odd occuring number. 27


--------------------------------------------------------------------------------

assume your computer is reading characters one by one from a stream (you don't know the length of the stream before ending). Note that you have only one character of storage space (so you cann't save the characters you've read to a something like a strong). When you've finished reading you should return a character out of the stream with equal probability. 11


--------------------------------------------------------------------------------

Brainteaser: there is a bar with 25 seats in a line. The people there are anti-social so when they walk in the bar, they always try to find a seat farthest away from others. If one person walks in and find there is no seat are adjecent to nobody, that person will walk away. The bar owner wants as many people as possible. The owner can tell the first customer where to sit. all the other customers will pick the farthest possible seat from others. So where should the first customer sit. 9


--------------------------------------------------------------------------------

If there are a huge array of positive integers, all the integers show up twice except one. Find out that integer. 1


Coding [more]
Coding: Write code to tokenize a string (had to explain code out loud and then follow-up with the actual code in an email 3


--------------------------------------------------------------------------------

Coding: How would you find the nth to last element in a linked list? 27


--------------------------------------------------------------------------------

Coding: You have an array of ints. How would you find the two elements that sum to a particular value? 18


--------------------------------------------------------------------------------

Coding: Implement a binary search in a sorted array 3


--------------------------------------------------------------------------------

Coding: How would you reverse the words in a string? (ie, "the quick brown fox" --> "fox brown quick the" 41


--------------------------------------------------------------------------------

Design a graph class. Write the C++ interface for it. 3


--------------------------------------------------------------------------------

Write a function to smooth out stock fluctuations. Asked me to layout the mathematical idea for curve smoothing before writing code. 3


--------------------------------------------------------------------------------

Write a function to find the no of set bits of an integer. Optimise. Ended up giving two solutions . Could not implement the third one. 10


--------------------------------------------------------------------------------

Given two sets, Write a function to provide the union of them. STL not allowed to be used.
Optimise for Time and space. 24


--------------------------------------------------------------------------------

Given a binary tree, write code to check whether it is a binary search tree or not 9


--------------------------------------------------------------------------------

Do you have unix experience? Have you heard of WC (word count). Code it in c/c++. You can use STL.


--------------------------------------------------------------------------------

Find missing element in an array of 100 elements. 16


--------------------------------------------------------------------------------

write push and pop for stack 1


--------------------------------------------------------------------------------

Design an algorithm and write code to find nth node from the end in a linked list 3


--------------------------------------------------------------------------------

Design an algorithm and write code to shuffle a standard deck of cards 1


--------------------------------------------------------------------------------

Design an algorithm and write code to serialize a binary tree. Discuss various solutions 18


--------------------------------------------------------------------------------

Design an algorithm and write code to find two numbers in an array whose sum equals a given value 19


--------------------------------------------------------------------------------

Print BST level by level 7


--------------------------------------------------------------------------------

Find Nth last element in a linked list 4


--------------------------------------------------------------------------------

Given 2 files, each with names of thousands of customers who bought something from Amazon.com on that particular day. Find the common customers (i.e. common names in file1 and file2) 9


--------------------------------------------------------------------------------

Check if binary representation of an int is a palindrome or not. 21


--------------------------------------------------------------------------------

Write in java a method to parse an integer from a string 2


--------------------------------------------------------------------------------

Count characters in a string, wanted to see a hashtable used. 5


--------------------------------------------------------------------------------

count bits in an integer. Solved using mask, did not attempt -1 approach. 6


--------------------------------------------------------------------------------

Reverse a linked list 10


--------------------------------------------------------------------------------

Given two binary trees, find whether or not they are similar. 12


--------------------------------------------------------------------------------

Determine is a graph is circular. 6


--------------------------------------------------------------------------------

Algorithm: You have a tree (not Binary) and you want to print the values of all the nodes in this tree level by level. Discussed on phone and asked me to email Java code for my algorithm. 4


--------------------------------------------------------------------------------

Given two log files, each with a billion usernames (each username appended to the log file), find the usernames existing in both documents in the most efficient manner? Use pseudo-code or code. If your code calls pre-existing library functions, create each library function from scratch. 8


--------------------------------------------------------------------------------

2nd phone interview: reverse linklist(so stupid, I was too focus on the rule using the exist library much better than build something new(Effctive Java) and when the intervier insisted on asking me to give the non extra memory consuming answer, I was stucked for a while then I told her to move on the next topic. Find the duplicate number from an array. I gave the hash solving method.but I also gave her other answers.


--------------------------------------------------------------------------------

Write code to reverse vowels of string 1


--------------------------------------------------------------------------------

Here is a tree. It's a binary tree but in no particular order. How do you write this tree to a file so that it can be reread in an reconstructed exactly as shown? 33


--------------------------------------------------------------------------------

Multiply a number by 7 without the * operator. 7


--------------------------------------------------------------------------------

I want to see if all the ones in a number appear on the right side of the number and all zeros appear on the left, how can I do this most efficiently? (i.e. 00000111 is true but 100010 is false) 7


--------------------------------------------------------------------------------

no.of 1 bits in a number ---program 3


--------------------------------------------------------------------------------

find dup number for n+1 numbers from 1...n 1


--------------------------------------------------------------------------------

Phone Screen 2: Check whether the bit representation of integer is a palindrome
Multithreading and operating system stuff 1


--------------------------------------------------------------------------------

Given two dates, Design an algorithm to return whether the dates are exactly a month apart, less than a month apart or more than a month apart. 2


--------------------------------------------------------------------------------

Print out a multiplication table, i wasnt told what kind of data structure it is, just that it has 1*1=1, 1*2=2, ...... 200*200=40000, ..... values. 2


--------------------------------------------------------------------------------

Given a deck of nCards unique cards, cut the deck iCut cards from top and perform a perfect shuffle. A perfect shuffle begins by putting down the bottom card from the top portion of the deck followed by the bottom card from the bottom portion of the deck followed by the next card from the top portion, etc., alternating cards until one portion is used up. The remaining cards go on top. The problem is to find the number of perfect shuffles required to return the deck to its original order. Your function should be declared as:

static long shuffles(int nCards,int iCut); 4


--------------------------------------------------------------------------------

The hardest question to date on a phone interview. he asked me to take 2 hours and write the following API.

Create an LRU Cache that caches some key/value pair and kicks out the Least Recently Used when you run out of space. Wanted run times and asked me to comment on how good my implementation is and whether its good for industry level usage.


--------------------------------------------------------------------------------

Asked me to reverse a Linked list without re-creating a new one. I did it recursively going all the way to end and linking it backwards after the recursive call. Had to pass in two nodes though, one previous and one current. He said he likes iteration better becoz its more resource friendly :)


--------------------------------------------------------------------------------

Write a method to shufle the deck. The constraint is it has to be a perfect shuffle - in other words, every 52! permutations of the deck has to be equally like (given a completely random function which is theoretical of course).

I managed to do this with a simple for loop in O(n) time


int[] deck = new int[52];
for(int i=0; i<52; i++)
deck[i] = i;

Random r = new Random();
for(int i=0; i
int ran = r.nextInt(deck.length-i) + i;
int temp = deck[i];
deck[i] = deck[ran];
deck[ran] = temp;
}


--------------------------------------------------------------------------------

Design a data structure for storing sparse arrays. Implement multiplications of such arrays. 2


--------------------------------------------------------------------------------

reverse linked list. Why don't you use recursion? 5


--------------------------------------------------------------------------------

Homework: Reverse all the words in a string.


--------------------------------------------------------------------------------

Algorithm and code to detect occurence of a string(patterns) in another string ex: aab, aababa 5


--------------------------------------------------------------------------------

Asked to code the 'floodFill' method used by graphic products like Paint. 2


--------------------------------------------------------------------------------

Design the classes for Tic Tac Toe. Implement make next move method for the computer player and make sure that the computer wouldn't lose.


--------------------------------------------------------------------------------

Design the game Othello. Write the code to check whether someone has won the game.


--------------------------------------------------------------------------------

Implement class Stack using a linked list.


--------------------------------------------------------------------------------

void removeChars(char *str, char *delete). Remove characters in str that is in delete. 2


--------------------------------------------------------------------------------

Find nth to the last node in a single linked list.


--------------------------------------------------------------------------------

Write a function that would find the one value that occurs an odd number of times in an array. ie; function would return "r" if "ttttjjrll" is passed in. 3


--------------------------------------------------------------------------------

If you are given a number as a parameter, write a function that would put commas after every third digit from the right.


--------------------------------------------------------------------------------

Discuss the code of pre-order traversal of a tree.


--------------------------------------------------------------------------------

Write code to find n-th to last node in a linked list


--------------------------------------------------------------------------------

Write code to delete a node in circular linked list


--------------------------------------------------------------------------------

A phone screen. Write a atoi function for decimal. Expected me to "tell" the code right
from "declare a variable i of type int" to the actual logic. Once this was done generalize it do the atoi for any radix.


--------------------------------------------------------------------------------

How do you determine the size of an object in Java?


--------------------------------------------------------------------------------

Implement the unix command WordCount (wc) using lenguage of your choice. The method takes a string and returns the number of words in the string, number of chars and the number of lines.


Computer Architecture & Low Level [more]
When would a program crash in a buffer overrun case. Gave me,
buff[50];
for( int i=0; i <100; i++ )
buff[i] = 0;

What will happen to first 50 bytes assigned, when would the program crash 5


--------------------------------------------------------------------------------

What is buffer overflow and how do you exploit it? 1


Data structure [more]
What is the difference between arrays and linked lists? What is the advantage of contiguous memory over linked lists?


--------------------------------------------------------------------------------

Given a file containing approx 10 million words, Design a data structure for finding all the anagrams in that set


Database [more]
database question like self joint with tables given by him


--------------------------------------------------------------------------------

Explain how to write a stored procedure in SQL 1


Experience [more]
What sort of commenting standards do you use 1


--------------------------------------------------------------------------------

From 1 - 10, rate c++, c, java, unix, sql skills


--------------------------------------------------------------------------------

Most challenging project 2


--------------------------------------------------------------------------------

How much experience do you have with unix


--------------------------------------------------------------------------------

Talk about your favourite project? What part of a Software Project do you enjoy most?


--------------------------------------------------------------------------------

Tell me about your work experiences in the past?


--------------------------------------------------------------------------------

asked some questions based on my previous job


--------------------------------------------------------------------------------

Lunch - QA manager.

1. tell me a situation when u had to face problems and the requirements were not clear. how did u handle the situation?

2. which is the best error you have caught?

3. which is the worst error u've ever caught?

4. asked about a project on my resume


--------------------------------------------------------------------------------

XML: How have you used XML in your previous projects?


--------------------------------------------------------------------------------

focus on my last project


--------------------------------------------------------------------------------

What was your hardest techincal project?


--------------------------------------------------------------------------------

What was the most interesting thing you have ever done (technical or non technical) ?


--------------------------------------------------------------------------------

Mailed me this code and asked to find the mistakes in the code

class Base {
public:
Base(int numElements) {
m_baseArray = new int[numElements];
}
~Base { //non-virtual
delete [] m_baseArray;
}
private:
int* m_baseArray;
}
class Derived : public Base {
public:
Derived(int numElements) : Base(numElements) {
m_derivedArray = new int[numElements];
}
~Derived() {
delete[] m_derivedArray;
}
private:
int* m_derivedArray;
}
int main(int argc, char** argv) {
Base* base = new Derived(3);
delete base;
return 0;
}

What is wrong with the code ? 5


--------------------------------------------------------------------------------

Projects


Ideas [more]
If you had the entire text to 65 million books in a database, what would you do with it? 9


Java [more]
What is the difference between Inheritance and Interfaces? Under what conditions would you prefer one over the other? 2


--------------------------------------------------------------------------------

What is Garbage Collection in Java. How is it implemented? What kind of algorithms does the garbage collector use? How does it know that references can be collected? What are advantages and disadvantages of garbage collection?


Math & Computation [more]
You have a basket ball hoop and someone says that you can play 1 of 2 games. You get $1000 and one shot to get the hoop. Or, you get three shots and you have to make 2 of 3 shots. Which one do you choose? If p is the probability of making a particular shot, what value of p makes you switch games? 16


--------------------------------------------------------------------------------

Some question about random sampling and buffer read. Don't remember exactly. Had to do with calculating the probabilty and stuff.


--------------------------------------------------------------------------------

When i wasn't certain whether my random function generated with equal probability all permutations, the interviewer asked me to write a formal proof that it works or not and send it to him (really strange).

Proved it with the following and he bought it:
Probabilisticly
card 1 has 52 positions it can fit in
card 2 has 51
card 3 has 50
so on and so forth
card 52 has 1 position to fit in

hence its 52 x 51 x 50 x ... x 1 = 52! can be generated using this shuffle.

Oblivious to me, aparantly this kind of shuffle is used a lot in online card games. Silly me :P


--------------------------------------------------------------------------------

Brainteaser: there is a bar with 25 seats in a line. The people there are anti-social so when they walk in the bar, they always try to find a seat farthest away from others. If one person walks in and find there is no seat are adjecent to nobody, that person will walk away. The bar owner wants as many people as possible. The owner can tell the first customer where to sit. all the other customers will pick the farthest possible seat from others. So where should the first customer sit. 9


--------------------------------------------------------------------------------

Write a program which makes the probablity of getting the even number when a dice is thrown in 72%( some number other than 50%).


Multiple Questions in One [more]
Phone Screen 1: Serialize and deserialize a binary tree/graph
General Unix questions
C++ questions
Design classes to represent a deck of cards


Object Oriented Design [more]
Design the classes and objects for a generic deck of cards that would be used in a poker game 4


--------------------------------------------------------------------------------

Describe the classes and data structures you would use for a file system 23


--------------------------------------------------------------------------------

How would you implement a map (not a map of like a city... just a set of keys which "map" to values")
- Give two data structures you could use
- What is average and worst case insert time, delete time, look up time
- What are pros/cons of each 7


--------------------------------------------------------------------------------

Design a graph class. Write the C++ interface for it. 3


--------------------------------------------------------------------------------

QA engineer -

1. say you have a calculator service running on a server. Automate the process of testing it. i.e. by one click of a buttonu should be able to test it.

2. how would you do the same if you did not have access to the input and expected output. for example. no excel sheet that has the expected values. generate the 2 inputs on the fly. now how would you automate the testing.

3. discuss data structures for NOTEPAD. discuss with reference to bufferer write.


--------------------------------------------------------------------------------

Given two log files, each with a billion usernames (each username appended to the log file), find the usernames existing in both documents in the most efficient manner? Use pseudo-code or code. If your code calls pre-existing library functions, create each library function from scratch. 8


--------------------------------------------------------------------------------

The bigger the ratio between the size of the hash table and the number of data elements, the less chance there is for collision. What is a drawback to making the hash table big enough so the chances of collision is ignorable? 2


--------------------------------------------------------------------------------

Here is a graph of distribution centers and the weight to go from one to another. How would you represent this using a data structure? Code an alogrithm that allows me to check if there is a path from one node to another and what the weight of this path is. 1


--------------------------------------------------------------------------------

Imagine you're implementing the game of chess. Design the classes, objects and heirachies behind it.


--------------------------------------------------------------------------------

Design a deck of cards


--------------------------------------------------------------------------------

Design the data structures and algorithms for a LRU (Least Recently Used) Cache 3


--------------------------------------------------------------------------------

Design a Deck of Cards 1


--------------------------------------------------------------------------------

Asked me to take some time around 1 hour and create an API that could read names,emp ID's,phone numbers, office names in that order from a file and stores them and has the following functionality:

1) getEmployeeById
2) getEmployeeByName
3) getEmployeesByName
4) editEmployeeInfoById
5) editEmployeeInfoByName


--------------------------------------------------------------------------------

Design a data structure for storing sparse arrays. Implement multiplications of such arrays. 2


--------------------------------------------------------------------------------

reverse linked list. Why don't you use recursion? 5


--------------------------------------------------------------------------------

OO design related question? How would you design a class structure for animals in a zoo


--------------------------------------------------------------------------------

Design the classes for Tic Tac Toe. Implement make next move method for the computer player and make sure that the computer wouldn't lose.


--------------------------------------------------------------------------------

Design the game Othello. Write the code to check whether someone has won the game.


--------------------------------------------------------------------------------

Design the classes and data structures for a parking lot


--------------------------------------------------------------------------------

Look within the book. Each person can look at 20% of the book at a time. Only 70% of the book can be served to all users. Design the data structures for this. 4


--------------------------------------------------------------------------------

How would you do a design of a monopoly game (later changed to a chess game)?


--------------------------------------------------------------------------------

How would you design a file system using class diagrams and what data structure would you use?


--------------------------------------------------------------------------------

Discuss the important features of Object Oriented Programming


--------------------------------------------------------------------------------

Model a chess game


System Design [more]
Imagine that there are 7 servers running in parallel. What happens when you need to expand to 20 live? What are issues? What could you do to fix this issue in the future? 6


--------------------------------------------------------------------------------

Algorithm: 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? 14


--------------------------------------------------------------------------------

You have a website which has 5 reads on a database when it is loaded. Each read takes 7 seconds for a total of 35 seconds, discuss how you could improve the performance? 5


--------------------------------------------------------------------------------

Say you have a system. The design is good. But performance is not good. How would you find where the problem is? went on for about half an hour about it. 3


--------------------------------------------------------------------------------

the "logging in" feature of amazon.com has a problem. isolate the problem.


--------------------------------------------------------------------------------

App server+DB server, solve the querying delay problem...


--------------------------------------------------------------------------------

How would you design the software that runs on an ATM machine? The software should support operations such as checking balance, transfer funds from one account to another, deposits and withdrawals.


Terminology & Trivia [more]
Difference between class and object 16


--------------------------------------------------------------------------------

What's the max look up time for a binary tree 21


--------------------------------------------------------------------------------

What's the point of inheritance? 4


--------------------------------------------------------------------------------

What's the max insertion time for a hash table 8


--------------------------------------------------------------------------------

Why would you use an array vs linked-list 14


--------------------------------------------------------------------------------

What is a Pure Function? 3


--------------------------------------------------------------------------------

What is a linked list? What are its advantages over arrays? 7


--------------------------------------------------------------------------------

exception handling, C++ basics, bitwise operations


--------------------------------------------------------------------------------

What is an array? What is a Linked List, Map.


--------------------------------------------------------------------------------

Complexity of insertion and deletion for linked list.


--------------------------------------------------------------------------------

Unix: You want to kill a process that has been running for a long time, how to do that? 2


--------------------------------------------------------------------------------

XML: Differentiate between SAX and DOM. 1


--------------------------------------------------------------------------------

Data Structures: Time complexities for HashTable, Linked List, Binary Search, Array. 1


--------------------------------------------------------------------------------

Java: Differentiate between final, finally and finalize


--------------------------------------------------------------------------------

Java: How does the synchronized keyword work? What happens when you use it on a static method?


--------------------------------------------------------------------------------

Java: Talk to me about the Java Collections API


--------------------------------------------------------------------------------

MultiThread, Garbage Collection. Tomcat distribute request(Java Spaces), http protocal. Socket programming...


--------------------------------------------------------------------------------

to find a telephone number in dir and subdir (find command is the answer)


--------------------------------------------------------------------------------

What is Polymorphism, how do virtual functions work


--------------------------------------------------------------------------------

When would a program crash in a buffer overrun case. Gave me,
buff[50];
for( int i=0; i <100; i++ )
buff[i] = 0;

What will happen to first 50 bytes assigned, when would the program crash 5


--------------------------------------------------------------------------------

Asked me to describe the difference between final, finally and finalize in java. (The last one is tricky coz we rarely use it) 3


--------------------------------------------------------------------------------

Define "class" and "object."


--------------------------------------------------------------------------------

What does the keyword "final" do when put in front of a Collection in Java? 1


--------------------------------------------------------------------------------

Asked me the differnce between using Abstract class vs interface on a real world problem im working on (at one point he settled for an answer where is said "it's just intuitively wrong" - however, he tried to trick me into justifying using the wrong thing, I had to say that there is no justification for using this technique here, took a little bit of guts but he liked it)


--------------------------------------------------------------------------------

array vs list


--------------------------------------------------------------------------------

Java. final, finalize, finally


--------------------------------------------------------------------------------

What are thread, why are they used in programming?


--------------------------------------------------------------------------------

Difference between polmorphism and inheritance?


--------------------------------------------------------------------------------

Difference between class and object?


--------------------------------------------------------------------------------

Questions about C++/Java and Design Patterns.


--------------------------------------------------------------------------------

When would you create an interface class. 2


--------------------------------------------------------------------------------

How would a copy constructor behave if the class had an Object as a member Variable?


--------------------------------------------------------------------------------

Explain the relationship between Equals and Hashcode in Java. 1


--------------------------------------------------------------------------------

What is a tree? How do you traverse a tree? 1


--------------------------------------------------------------------------------

What's the difference between virtual methods in C++ and Java? 1


--------------------------------------------------------------------------------

What's the difference between == and Equals()?


--------------------------------------------------------------------------------

What is Perfect/Universal hashing?


--------------------------------------------------------------------------------

What are the advantages and disadvantages of function lining?


--------------------------------------------------------------------------------

How do you determine the size of an object in Java?


--------------------------------------------------------------------------------

What is Context Free Grammar? What is it used for?


--------------------------------------------------------------------------------

When does the Operating Systems do a Context Switch? 1


Testing [more]
3. What is black box testing?
4. What do you include in a test plan? 1


--------------------------------------------------------------------------------

Say you have a system. The design is good. But performance is not good. How would you find where the problem is? went on for about half an hour about it. 3


--------------------------------------------------------------------------------

Suppose there is a problem with the address change feature on Amazon.com. How would you test it? What data sets would you test it against? How would you decide on such a data set?


--------------------------------------------------------------------------------

say u are in charge of the "login" fature of amazon.com. TEST IT.


--------------------------------------------------------------------------------

the "logging in" feature of amazon.com has a problem. isolate the problem.


--------------------------------------------------------------------------------

QA engineer -

1. say you have a calculator service running on a server. Automate the process of testing it. i.e. by one click of a buttonu should be able to test it.

2. how would you do the same if you did not have access to the input and expected output. for example. no excel sheet that has the expected values. generate the 2 inputs on the fly. now how would you automate the testing.

3. discuss data structures for NOTEPAD. discuss with reference to bufferer write.


--------------------------------------------------------------------------------

say i give you a universal vegetable cutter which claims that it can cut any kind of vegetable. TEST IT.


--------------------------------------------------------------------------------

How would you test an ATM in a distributed banking system.


--------------------------------------------------------------------------------

How would you load test a web page without using any test tools 3


--------------------------------------------------------------------------------

Suppose there is a problem with calculation of taxes on the amazon.com website. How would you isolate the problem. Once isolated and fixed, how would you go ahead and test it?