Amazon Campus Selection

WRITTEN TEST

Aptitude Test : 45 Minutes
Technical          : 45 Minutes

Aptitude Test :

The aptitude was 20 questions general/technical MCQs and 2 coding questions on interviewstreet.com

Subject Covered in Aptitude Test:

-Computer Networks
-Operating System
-Language Processors
-Data Structure and Algorithms

Few questions from previous GATE papers.

The coding questions were quite easy.But do not get carried away if ur code works for the given few test cases. There are probably more cases for which it might fail to work.

Sample Questions :

1. Given the post-order traversal of a Binary Search Tree (BST), choose the correct pre-order traversal.

2. Consider a memory system where only one frame is there and it has the capacity to hold 100 records. In a pure demand paging system, how many page faults will occur for the following record access:
100 200 180 220 340 560 540 600 340

3. In UNIX, what happens to a child process if its parent dies?

4. A DFA was given and in the choices regular expressions were listed. We were supposed to choose those regular expressions that corresponded to the DFA.

5. Four regular expressions were given, and we were supposed to choose those that would accept a palindrome string.

6. What is the value of 'sum' in the following program excerpt?

int sum = 0;
for(int i=0;i<12;i++)
for(int j=i+1;j<10;j++)
for(int k=j+1;k<8;k++)
sum++;

7. A person observes that on a particular road, the probability of a car passing by is 0.85 in 30 minutes. What is the probability of a car passing bye in 10 minutes, provided constant average probability?

Technical :

Time Alloted (in minutes) : 45
No. of Questions : 2
Type of Questions : Programming

Sample Questions :

1. Given a sentence and a word, remove all occurrences of the word in the sentence.
For example, removing "is" from the sentence "This is a boy." becomes "Th a boy."

2. Given two sorted linked lists, merge them.

3. Given an string str and substring subs, if matching substring is found on the str, return the index otherwise return -1;

4. Given top(x,y) and bottom(x,y) of two rectangles, find if two rectangles have some common area return 1 otherwise return 0;

5. Given set of coins {1, 3, 4 ,5 }  find min number of coins required to get sum amount.

6. removeLoop() if loop exists and give the length of the linled list.

7. Given a (decimal - e.g. 21.125) number N that is passed in as a string, print the binary

8. Given an array of N elements, A[0 .. N - 1], Produce an array B such that: B[i] = min (A[i],A[i+1], ..., A[i+K-1]). (The array B will have exactly (N-k+1) elements.

9. http://www.geeksforgeeks.org/sum-of-two-linked-lists/ at nitw 2013

10. http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-sumtree/ at nitw 2013

11. find number of pairs in an array with difference k. Array has unique elements at IITD 2013

12. Second questions was same ashttp://www.geeksforgeeks.org/forums/topic/directi-coding-round-2/ at IITD 2013

Personal Interviews:

There are 4 rounds of interviews held each lasting anywhere from 30 min to an hour. Following were the questions asked.

1. Reverse a linked list using no extra memory or recursion (a very easy one to begin with)

2. Given a linked list, construct a tree whose inorder traversal would be the contents of the linked list.

3. With three files, each containing a day's data on the customers' page visiting pattern on a site, determine all customers that visited the site on exactly 2 days and viewed more that 3 distinct pages. The data was available as key-value pairs of customer IDs and page numbers.

4. Given a string of the form "aaabcc", convert it to the form "a3b1c2" without using any extra memory.

5. Given inorder and postorder traversal of a binary tree, trace the construction of the tree. Comment on the complexity if this construction is performed non-recursively.

6. Given a binary tree, pre-process it to be able to determine any node's inorder successor in constant time.

7. Design your own data structure that implements the following three functions in O(1) time:
a. push()
b. pop()
c. min() - returns the min element


At all times, the interviewer stressed on writing the code that not only handles the general cases but any of the special or edge cases. Lastly and most important of all, the biggest criterion for evaluation was the complexity of the algorithm proposed.