Blog # 40 : Amazon Interview Questions

Following are the questions asked to one of the successful candidates in Amazon Interview :-

Round 1: 
 

     1. A Twin Prime number is a prime number which differs from other prime number by two. eg    (5,7), (11,13), (17,19), (29,31), (41,43), (59,61)........ Prove that number between twin primes is divisible by 6. 

     2. You have a binary tree with non-negative numeric values stored in its nodes, you need to find out the maximum possible sum of all the nodes. Selection of nodes for the sum follows following constraint: 

If you have selected any node for the sum, you can not select its immediate parent and its children for sum.

Hint : Answer does not include level order traversal for obvious reasons.
 

     3. Find all permutations of a string.


 

Round 2:

     1. For a given company, you need to maintain the stock prices (closing price of a day) for last "m" years. [By "m" years he meant, if the year say increases by 1 then database has data of "(m+1)" years, not that the data for "m"th year gets deleted]

Now suggest a data-structure for holding the stock prices of all the companies such that 

(a). The stock price (closing price of the day) of a given company on a given date can be searched easily.   

(b). The stock prices for all the companies can be printed for a given date. 

(By all companies he meant if a company say starts today, its data will also get added to the database and if a company gets closed today its data won't be deleted). 

     2. For compiling a java program you need a list of JARs as libraries but the given JARs have internal dependencies between them: 

eg. JAR1 can only be loaded after loading JAR2 and JAR3. JAR2 is also dependent on JAR3 and JAR4. 

Now write a program to load all the JAR files following their dependency rules.


 

 
Round 3:

     1. You are given an array, infinity on both the sides along with the current position of the pointer [Think of magnetic tape and the head of the reading machine].
Now the data stored in the array can be of length either of 1 byte or 2 bytes.
If the data is of 1 byte, then 1st bit will be 0.
If the data is of 2 bytes, 1st bit of 1st byte the data will be 1 and 1st bit of 2nd byte will be having a Don't Care condition. 
You are given the current position of pointer as the start of a new data. Find the starting position of data, previous to the current data. In other words, find the previous data.

Round 4:

     1. Database Question: 
The main aim was to ask how is a database implemented internally. [Answer : using B and B+ trees]


     2. Synchronization of threads:
You have an account and deposit & withdraw operations should be mutually exclusive, but the ReadAccountValue should not be blocked even if a thread is using deposit or withdraw method.
Account {
       Deposit();
       Withdraw();
        ReadAccountValue(); 
} 
For ReadAccountValue method, do not return an illegal value. (say a thread uses ReadAccountValue while other thread uses Withdraw(), do not return the illegal previous value)

p.s. - For any kind of confusion, don't hesitate in asking.