Sample Questions for Amazon Interview (Part - III)

Check these too

Part - I>>   Part - II>>   Part - IV>>

1. Convert a binary tree to pre-order doubly link list without using extra memory .
(you can only use constant amount of memory)

2. Write a function which checks a given Binary Tree is BST or not.
prototype:-
int isBST(Tree * root)

3. Draw memory-map for C program.

4. Suppose you are a station master and you know the schedule of arrival and departure of trains passing  through  that station for a particular day .You need to find the minimum number of platforms required to fulfill this task.
Eg:-
Trains      arrival    departure
        
T1       9:00        9:30
T2             9:15        10:00
T3             9:45        10:10
(consider time line to be 00:00 hours to 23:55).Here at 9:20  there  will be  two trains at the station , So we  need at least two platform for this schedule.
Ans :- 2
Eg:-
 Trains      arrival    departure
        T1            9:00        9:30
T2            9:15        10:00
        T3            9:20         9:25
(consider )
Here at 9:21  there  will be  three trains at the station , So we  need at least three platform for this schedule.
Ans :- 3
Eg:-
Trains      arrival    departure
 T1            9:00        9:30
 T2            9:10        9:15
 T3            9:20        9:25
 (consider )
At any point of time at max two trains will be at the station.
Ans :- 2
Note :-
     Trains      arrival    departure
        T1            9:00        9:30
        T2            9:30        10:00
     In this case both the trains can use the same platform
     Ans : 1

5. Consider a tree
struct tree{
int data,
struct tree *lchild, *rchild, *parent ;
}Tree;
(Here parent pointer of a node points to it's parent node)
Given two leaf nodes find the least-common-ancestor
of them.
prototype:
Tree* lca(Tree *leaf1, Tree *leaf2

6. Given an array every element is repeating odd number of times
except one number. 
Find the number which is being repeated even
no of times.

7. Given a string remove multiple spaces except one. 
(Similar like html)
Eg. input :- "    hi dost   how   are   you   "
 output:-    "hi dost how are you"

8. A pirate ship captures a treasure of 1000 golden coins.
 The treasure has to be split among the 5 pirates: 1, 2, 3, 4, and 5 in order of rank.
 The pirates have the following important characteristics:

  * Infinitely smart.
  * Bloodthirsty.
  * Greedy.
Starting with pirate 5 they can make a proposal how to split up the treasure.
 This proposal can either be accepted or the pirate is thrown overboard. 
A proposal is accepted if and only if a majority of the pirates agrees on it.
What proposal should pirate 5 make?
Sol:- http://www.puzzlesite.nl/teasers/index_us.html#pirate_treasure

9. There is a link-list having structure
struct LinkList{
struct LinkList *next, *sortedNext;
int data;
}
Initially  sorted Next pointer points to null and next points
to the next pointer as in simple link list.
Manipulate the pointers such that sortedNext pointer of each
node points to the sorted-next node
(It´s the first node in
right side when link-list is sorted).

10. Find all  pythagorean  tripletes in a given array of integers.

11.  Explain  some problems with multi-threading and implement a lock if a section of code is shared by two different processes.