Sample Questions for Amazon Interview (Part - IV)

Check these too

Part - I>>   Part - II>>   Part - III>>

1. Given an array of random integers find the first repeated integer( one with the lowest index).

2. Write the code to find the negative of a given BST.

3. Given an array of random integers such that each integer is repeated even number of times 

except one element x which is repeated odd number of times find x(don't use xor operator).

4. i)  Data structure to store an integer of an undefined length.

   ii) To Add two such integers

5. How will you implement stack & write pop for it.

6. Code for isBST & order analysis(proper mathematical derivation).

7. Write a code to Find the number of words in a string

8. Deadlock prevention technique.

9. Draw state diagram of process.

10. Define tree.

11. int a[10] :

a = (int*)malloc(sizeof(int)*10); Result??

12. Write a code to convert a binary tree to a circular doubly linked list(inorder traversal)

13) Write a code to remove comments from a C code(handle all the cases).

14. Data Structure to implement caching using LRU. (you have the page numbers the corresponding index and the timestamp of last accessed).

Read More...

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.

Read More...

Sample Questions for Amazon Interview (Part - II)

Check these too

Part - I>>   Part - III>>   Part - IV>>

1. There is a postal code scheme with 3 characters:
A0A
A0B
.
.
.
.
A0Z
A1A
A1B
.
.
.
   You will be given 2 postal codes and you have to print all the postal codes in betwwen those 2 codes.

2. Given 2 binary trees checkif they are mirror images of each other.
int isMirror(Tree *BST1, Tree *BST2);

3. Find middlemost element of a linklist(Not in sorted order).
Eg. 1->5->3->4->6->9
Ans: 3.

4. There is an array with all elements repeating odd number of times and only one element
   repeating even numbr of times.
Find the element which repeats even number of times.

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

6. 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).

7.Given A a nxn matrix. Write a function which will multiple A to itself k times (k>0).
int **power(int **,int k);

8. Given 2 sorted arrays of same size, find the median of the combined array
in sorted array without merging
the 2 arrays.
Eg: array1: 1, 3, 4, 5, 10
    array2: 2, 3, 8, 9, 11
Ans:- 4.

9. Given a linked list, remove all elements from the list which occur more than once.
Eg:
3->2->5->2->1->3->7.
Resultant Linked list: 5->1->7.

10. Given an array find the largest sum of any k numbers.

11. There is an array elements of which are in increasing order till some point after which they are decreasing order.
Find the maximum element of this array.
Eg:- 1, 2, 3, 5, 4, 0.
Ans:- 5.

12. Given an array find the first repeating element in the array.
Eg:- 1, 2, 4, 3, 3, 4.
Ans:- 4.

Read More...

Sample Questions for Amazon Interview (Part - I)

Check these too

Part - II>>   Part - III>>   Part - IV>> 

1. Count of internal (non-leaf) nodes of a tree
2. Implement atoi()
3. Convert Binary tree to a Doubly Linked List (in place)
4. Why is Virtual Memory needed
5. Data Structures that can be used in implementation of a dictionary.
6. Difference between threads and processes.
7. What is meant by a "32-bit" architecture
8. From a standard set of 52 playing cards, one card is missing. Algo to find the missing  
    card.
9. From an array of 2n+1 numbers, n numbers repeat once. Algo to find the unique number.
10. An array of integers has a kth element such that elements before k are in ascending   
    order and elements after k are in descending order. Algo to find k.

Read More...