Written Round (1 hour 30 minutes):

20 MCQs (mostly from latest GATE paper)

2 Programming questions:

1) An operation "swap" means removing an element from the array and appending it at the back of the same array. Find the minimum number of "swaps" needed to sort that array.
Eg 3124
output: 2 (3124->1243->1234)

2) find if there exists a path from root to leaf in binary tree with sum K.



Interview:

Round 1 (1 hour 15 minutes):


write programs on paper keeping in mind all the boundary cases and complexity of the code. Following were  the programs:

1) Find if the given linked list is a palindrome or not (including inplace reversal of linked list)

2) We have a right rotated sorted array.Eg
   4  5  1  2  3
You need to find where this rotation had occured.

3) There exists a linked list such that each node has two pointers next and random. Random pointers points to any other node in the same linked list or to 
itself or NULL. Clone this linked list.


Round 2 (1 hour 15 minutes):

First part was mainly concerned with questions related to OOPs, second part included OS and lastly algorithms and miscellaneous.

OOPs

1) interviewer turned the laptop towards me and then asked me to write an "interface" for this laptop. Then he asked me to implement this interface.
2) Event handler. Asked how will you tell whether a key on the laptop has been pressed or not. Write a function (whose signature I had written in interface).
3) Difference between interface, abstract class, instance.

OS

He asked me back to back questions which covered topics:
1) Processes and threads (Asked example, desing a software which will be having three components-file copy, data transfer, user input efficiently)
2) Multi-threading
3) Scheduling Algorithms (both Process and thread)
4) Synchronization (many questions from mutex and semaphore)
5) Deadlock (deadlock prevention, avoidance, etc)
6) context switching

Algo and misc

1) Scenario: In gmail if somebody wants to sort mails according to name, date, size, etc which sorting algorithm is most accurate one for this puropse.
2) quicksort and heapsort.
3) what are shared library.
4) Other type of libraries.


Round 3 (1 hour):

Write the programs for following:
1) COunt the total number of parenthesis pattern for a given number n. 
Eg 
n=1
()
count=1
n=2
()() (())
count=2
n=3
()()() ()(()) (())() ((())) (()())
count=3

2) If the given graph is bipartite or not.
3) (not code only ds) Scenario: There is a huge database of telephone numbers. Each telephone number is unique and information (name, address, etc) of the user is attached to this telephone number. Design a data structure to store this.

Round 4 (1 hour):

HR plus techincal
1) Tell me about yourself.
2) What is your educational background.
3) Why Amazon

tech:
1) delete nth element from the end in a linked list.
2) find the maximum sum subarray in an array A of size n which may also contain negative numbers.

Selected!

Whenever u write a program be sure to cover all the corner cases and write it in a proper indented way. As interviewers ask to write testcases for the program u have written and then check if ur program covers all the test cases.

All the best fellas !!!

Written Round 1 :  50 multiple choice questions in 60 mins time. Had 2 sections – Aptitude and

Programming Ability.

Written Round 2 : 3 coding questions in 1 hour.

1.   Swap every consecutive odd and even positioned bit in a number.

Ex:- 10101011010101 =  01010111101010

2.   Given a binary search tree . Convert it into a doubly linked list in place (no extra space) such that prev points to left child and next points to right child.

3.   Given a linked list that contains 0,1 and 2 . Sort this linked such that it contains 0s first,then

1s and then 2s in O(n) time.

Ex:- 2->2->1->0->0->2->1->1->0 = 0->0->0->1->1->1-2->2->2

PI round 1 (Technical):

1.   About urself, most challenging project of all you have done and about ur internship.

2.   Remove from string s1, all the characters that are present in string s2.

S1=”abcde” s2=”xyazbx”   Ans. S1= ”cde”

3.   Reverse alternate k nodes in an linked list.

Ex:- 1->2->3->4->5->6->7->8  if k=2; then return 2->1->3->4->6->5->7->8

4.   Always ask some questions to the interviewer at the end. That’s a good gesture.

5.   Write test cases for the programs above and see if ur program covers all the test cases or not.

PI round 2 (Program manager)

1.   Design a tic-tac-toe game for multiplayer on a smartphone.

2.   Design a vending machine for blind and deaf.

PI round 3 (Technical)

1.   Add numbers from 1 to n2  into a n X n matrix spirally.

1	2	3	4	5
16	17	18	19	6
15	24	25	20	7
14	23	22	21	8
13	12	11	10	9

2.   Remove duplicates from a string in place.

Ex-microsoft -> microsft

3.   Some question on recursive functions using memorization technique for optimization.

PI round 4 (Testing)

1.   Given a func ::    int *strcmp(char *s1,char *s2);

Write test cases to check functionality and security issues and even automate the generation of test cases.

2.   Given a func ::    int typeOfTriangle(int side1,int side2,int side3); (func gives a number for the type of triangle)

Write test cases to check functionality and security issues and even automate the generation of test cases.

3.   WAP to reverse words in a sentence.

I am a good boy -> boy good a am i

4.   WAP to get the next higher palindrome of a given number.

123 -> 131                1232 -> 1331

PS -  Functional issues are test cases that check the functionality of the program and Security issues are the ones where the program may crash.

PI round 5 (Technical)

1.   WAP to check if a binary tree is a BST or not.

2.   WAP to find Least Common Ancestor of two nodes in a BST.

3.   Reverse every two nodes in a linked iteratively and recursively.

Round 1

Write a code to check if a tree is BST or not.

Modify this code to find the maximum subtree in tree which is a BST. Maximum subtree means subtree goes upto its leaves from any node.

Modify the code again to find the maximum tree which is a BST. BST can lie anywhere and it may or may not go upto its leaves.

Round 2

1. There is code like

var i;

{

  ..

  var j;

  ..

}

var k;

..

var a;

{

  ..

  var c;

  {

    var i;

  }

  ..

  var d;

  ..

}

For simplicity you may assume that there is only one variable declaration on 1 line. Now given a line number, you have to tell what all variables are valid on that line. Propose an algorithm for this.

2. Implement LRU cache. Write a code for this. LRU cache supports 3 operations,

put(key, value)

get(key)

remove(key)

P.S. This is very important and actually good question. Even if you know the answer, dont rush with it. Take your time to frame the algorithm. Always speak your thoughts. Interviewers like to know the way you are thinking in.

Round 3

1. Implement next_permutation function (similar to what is in algorithm.h).

2. Given n sequences, and starting and stopping point of every sequence with its score. For eg.

no of sequences = 5

start stop score

0      4    4

3      10  11

6      8    8

7      15  10

11    15  4

All scores are positive. You have to find the maximum subset of non overlapping sequences having maximum total sum of scores. I proposed a n^2 approach first and then modified it to nlgn.

3. Normal discussion on work culture, teams etc.