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.

I am not an interview expert, but from my experience I found that it is really very helpful to speak up your thoughts. This shows interviewer the direction of your approach. Even if you reject your thought, the interviewer will know that. Speak everything. Also at the end of every round, they will ask if you have any question to ask. Never let this opportunity going waste. Prepare you with some questions like "What are the various teams in the company?" "How are they related?" or questions about working environment etc.. These type of question give you chance to communicate with the interviewer and he will get an impression that this guy wants to know about the company and work. Prepare general questions which can work for all companies.

All the best for your placements. :)

Round 1

1. How will you implement a stack using a priority queue. Push and pop should be in O(1).

2. 3 mislabeled jars problem.

Round 2

1. How does stack look in function calls? Given a recursive function call, how will the stack look like?

2. When does stack(process stack) overflow? What are the remedies?

3. What are balanced BST's. Then he randomly gave me various numbers and asked me to create a BST. And the balance it.

4. Advantages of linked list over arrays. And arrays over linked list.

5. How are vectors implemented internally in the library. This question revolved around dynamic implementation of arrays. Then discussed the amortized time of the operations using dynamic implementation of arrays.

Round 3

1. There was a question in written round that there is a global static variable 'lock' initially set to 0 and there was a code segment given.

while(lock);

lock = 1;

//Critical section

lock = 0;

Does this solve critical section problem. I answered that it will solve in uni processor system but not in multiprocessor system. Then he asked me to explain my answer. After a long discussion we came to a conclusion that this wont even solve in uni processor system. 

Then he asked me the solution to solve this. I did that using testandset instruction. 

2. When a function is called in thread, what variables can be accessed from it. There was a long discussion on this too. I went in the wrong direction but corrected myself later. Stack variables are copied but heap variables are same.

Round 4

1. What data structures will you use to implement a text editor. Size of editor can be changed and you also need to save the styling information for all the text like italic, bold etc.

Round 5

HR Round

Normal HR questions

Written Test (Time): 90 Minutes

20 Objective Questions: Aptitude and basic C objective problems.

2 Subjective Questions:

I.                 To find if there is any root to leaf path with specified sum in a binary tree.

II.               Some question based on sorting.

Interview Round 1(60-70 Minutes):

Technical Interview

Question 1: Check if a character link list is palindrome or not.

Question 2: A sorted array has been rotated r times to the left. Find r in least possible time.

Question 3: Clone a singly link list whose nodes contain, apart from next pointers, an extra pointer to any random node. The random pointer of a node N could be after N, before N or the node N itself.

Interview Round 2(50-60 Minutes):

Technical Interview

Question 1: There is a big file of words which is dynamically changing. We are continuously adding some words into it. How would you keep track of top 10 trending words at each moment?

Question 2: Write code for minHeapify() operation.

Question 3: Design a data structure for the following operations:

I.                 Enqueue

II.               Dequeue

III.              Delete a given number(if it is present in the queue, else do nothing)

IV.              isNumberPresent

All these operations should take O(1) time.

Question 4: Write a function that returns the length of the longest leaf-to-leaf path in a binary tree.

Interview Round 3(60-70 Minutes):

Technical Interview

Question 1: There is a binary tree of size N. All nodes are numbered between 1-N(inclusive). There is a N*N integer matrix Arr[N][N], all elements are initialized to zero. So for all the nodes A and B, put Arr[A][B] = 1 if A is an ancestor of B (NOT just the immediate ancestor).

Question 2: Find an element in a sorted rotated integer array.

Question 3: There is a N*N integer matrix Arr[N][N]. From the row r and column c, we can go to any of the following three indices:

I.                 Arr[r+1][c-1] (valid only if c-1>=0)

II.               Arr[r+1][c]

III.              Arr[r+1][c+1] (valid only if c+1<=N-1)

So if we start at any column index on row 0, what is the largest sum of any of the paths till row N-1.

Interview Round 4(40-50 Minutes):

Bar Raiser Round

Interviewer asked HR Questions Initially, then a sort of puzzle.

Two robots land with their parachutes on an infinite one-dimensional number line. They both release their parachutes as soon as they land and start moving. They are allowed only to make use of the following functions.

I.                 moveLeft() // robot moves to left by 1 unit in 1 unit time

II.               moveRight() // robot moves to right by 1 unit in 1 unit time

III.              noOperation() // robot does not move and takes 1 unit time

IV.              onTopOfParachute() // returns true if the robot is standing on top of either of the parachute, else false

V.               didWeMeet() // returns true if the robot meets to the other robot, else false

Write a function in order to make the robots meet each other. Robots will be executing the same copy of this function.

Tips / Advice:

I.                 Each time you write a code, check for the edge cases.

II.               Do not assume anything. Keep asking questions if there are any doubts.

Courtesy: A selected sincere candidate

Five coworkers want to know what the average of all their salaries is, but refuse to reveal ANY information about their own salaries to their coworkers. How can they calculate the average ? courtesy: Vibhaj Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Remarks: What you'd do if such thing happens in your life? Hit again for hints. Hints: No Hints. Hit again for solution. Solution: One of them may choose any random number (not to be known any other) and add his salary to it and tell the sum to the second person, then he will add his salary to the sum and tell the result to the third person and so on. The fifth person after adding his salary to the sum will tell it to the first person. He will subtract the random number he choose from the final sum giving them the sum of their salaries and the average.

There is a big file containing 10^8 integers, one per line. Devise an algorithm to find the largest 100 integers among them. Remember you cannot read all of them into memory at once. courtesy: Vibhaj Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Remarks: No remarks. Hit again for hints. Hints: Value stored in any element of the Array reaches a maxima at certain index. Solution: We simply use Min-Heap data structure to keep list of top 100 numbers replacing next with lowest if greater. Complexity: 1. Time: O(N*logN) 2. Space: O(1) /** * Assume standard heap ADT operations : heap_min(), heap_remove() and heap_insert() **/ void top_100(FILE *fp, int output[]){ int num, count=0; while(fscanf(fp, "%d\n", &num)){ if(++count > 100 && num > heap_min(output)){ heap_remove(output); } heap_insert(output, num); } }

A truck stops at a weigh station at the entrance to a bridge and is shown to weigh exactly 2000 lbs. The operator of the weigh station notes that the bridge can hold exactly 2000 lbs, but would crumble if it were subjected to even a fraction of an ounce more. But he says that no other vehicles ever cross over the bridge and so it's fine if the truck crosses. The truck continues on. Once the truck is halfway across the 10-mile long bridge, a sparrow flies over to the truck and lands on the hood. The truck driver sees the bird lands and his heart drops as he realizes the bridge is about to collapse, but even after the bird lands, the bridge doesn't crumble. How was the bridge able to hold up despite the extra weight from the bird ? courtesy: Vibhaj Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Remarks: Observe. Hit again for hints. Hints: An intelligent question. Just compare the states of the truck. Solution: The weight of bird was compensated by the fuel burnt during 5 mile drive.

Given an array of N distinct integers with the property that there exists an index K (0 <= K <= N-1) such that input[0], ..., input[K] is and increasing sequence and input[K], ..., input[N-1] is a decreasing sequence. Devise and algorithm to find K. Ex [1 2 4 7 10 15 13 11 5 0 -5] Answer: K=5 (input[K]=15)  courtesy: Vibhaj Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Remarks: No remarks. Hit again for hints. Hints: Value stored in any element of the Array reaches a maxima at certain index. Solution: Use binary search with the following conditions : input[mid-1] < input[mid] > input[mid+1] for mid != 0 and mid != N-1 input[mid] > input[mid+1] for mid == 0 input[mid-1] < input[mid] for mid == N-1 with initial low = 0, high = N-1, mid = (high + low)/2 int bitonic_pivot(int input[], int N) { int low=0, high=N-1, mid; while(low < high) { mid=(low+high)/2; if((!mid || (input[mid-1] < input[mid])) && (mid != N-1 || (input[mid] > input[mid+1]))) return mid; else if((!mid || (input[mid-1] < input[mid])) && (mid != N-1 || (input[mid] < input[mid+1]))) low=mid+1; else if((!mid || (input[mid-1] > input[mid])) && (mid != N-1 || (input[mid] > input[mid+1]))) high=mid; } return -1; }

What is the least number of people that need to be in a room such that there is greater than a 50 % chance that at least two of the people have the same birthday ? Click here to see the solution. Courtesy: Vibhaj Rajan p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Remarks: No remarks. Hit again for hints. Hints: Probability, think how will it be not possible? Hit again for solution. Solution: At least 23 people should be there. To find N such that probability of two people sharing the same birthday be more than 50%, we find N such that probability of no two people sharing same birthday be less than 50%. Thus probability would be 364/365 * 363/365 * 362/365.... (N-1 terms)... (365 - (N-1) )/365 < 0.5 So, N = 23 For more information : http://en.wikipedia.org/wiki/Birthday_problem

Written Round:

1st Paper was completely a speed test.

2nd Paper had 20 question, 10 from general computer science and 10 from algorithm and data structure, few from paper 2 are below:

1. For every number that has 3 in its units place has one number which has all one's i.e. 111 that can be divided by it completely and 13 has a multiple 111111. Write a program to find such multiple for any number that has 3 at its units place.

2. write a program for checking the given number is a palindrome.

3. write a recursive program for reversing the linked list.

4. what are the maximum no of edges that can be connected in a graph of n vertices and 0 edges such that after adding edges given graph is still disconnected.

5. A question of OS on critical section.

6. write a program to return the row number which has max no of one's in an array of NxN matrix where all 1's occur before any 0's starts.

for example:

1110

1111

1000

1100

7. 1 question on deadlock and starvation

8. Given two arrays A[], B[]. Given a no. 'sum'. Find a and b such that a+b=sum ['a' from A and 'b' from B]

Technical Round 1:

1. For every number that has 3 in its units place has one number which has all one's i.e. 111 that can be divided by it completely and 13 has a multiple 111111. Write a program to find such multiple for any number that has 3 at its units place. [As I could not solve it in written round]. 

[proposed 3 different methods and their complexity]

Technical Round 2:

1. Virtual Function

2. Copy Constructor

3. Inheritance

4. Virtual Destructor

5. Suppose a Date in the format DD/MM/YYYY is palindrome, find the next palindrome date.

6. "He is a good boy" -> "boy good a is He" [He kept on adding constraints.]

7. 10 Red and 10 Blue balls are given. You have 2 jars, now a person will be picking 1 ball out of any of them. How will you maximize probability of picking Red Ball.

Technical Round 3:

1. How T9 dictionary is implemented?

2. How do Touch Phones know in which area they are touched?

3. Project info.

Technical Round 4:

1. 2 arrays A & B of numbers are given. Find combination such that a+b=c+d. [a,b from A and c,d from B] [Kept on adding constraint to minimize time and space complexity]

2. How to design a stack using 2 queues.

HR Round:

1. Tell me about yourself.

2. Why do you want to join Adobe?

Placed!

-All the very best!

Will post more as I recall them.  :)

What would be the output of the following code ? int main(int argc, char **argv){ printf("%d", 012345 + 123450); return 0; } courtesy: Mahesh Gondi Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Remarks: No remarks. Hit again for hints. Hints: Think of different number system representations. Hit again for solution. Solution: The number 012345 shall be considered an octal literal and thus its value will be 5349 and addition with 123450 shall result in 128799.

You have two Indian coins that add up to 6 rupees. However, one of them is not a 5 rupee coin. What are the two coins ? courtesy: Vibhaj Rajan Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Remarks: No remarks. Hit again for hints. Hints: Read the question loud. Hit again for solution. Solution: There are 2 coins. If one of them is not 5, the other one will be. LOL

Interview questions asked by Google Recruitment team after qualifying the first on-campus round comprising a written exam:


Round 1:
1) Given a database, a query returns correct output 99% of the time, however 1% of the time, it returns wrong output. What could be the possible reasons?
2) On a 2-D grid, the positions (x,y) of 3 persons are given. Find the meeting point such that sum of distances of each person from meeting point is minimized.
Now generalize this to N persons and solve.
3) A very long question related to hashing. I don't remember it.


Round 2:
1) Given a string of parantheses, check if the string is valid. ex: [[]] is valid, ][][ is not valid. How would you solve if the parantheses could be of different types like {,[,(
2) Given a layout like
a b c d e
f g h i j
k l m n o
p q r s t
u v w x y
z
Your initial point is a. You want to form a string like "movie". WAP to find the sequence of moves consisting of letters 'U','D','L','R'
( normal conventions) that would form the movie. for example: for string "afg" sequence would be DR.


Round 3:
1) Given a number N, form all possible paranthesizations. like for N=3, there would be 5 possible parathesizations ( catalan numbers ).
Kept on asking to optimize time and space.
2) Given a 8X8 chess-board, there is a bishop placed on a square (i,j). You have to move to any square (x,y). In how many moves you could do it ?
Find the intemediate point.
3) Given an array of integers, where each element of array represents height of a building. Width of each building is 1. [ Think of it as histogram].
It starts raining, so water will get accumulated between some buildings. Find the amount of water that will be accumulated.


Round 4:
1) Given a rod of length L, there are some positions marked on rod at which the rod can be cut. The cost of cutting at any position is the current length of rod you are cutting. Like if the rod length is 10 and you can cut it at 4,9, cost of cutting at any position would be 10.
Find the minimum cost of cutting the rod.


2) What features would you suggest that should be added in Google+ to attract more users.
What signals would you use to determine any particular interest of a user.
More on similar topics, like suppose you have to design a page where top 100 posts by random users on Google+. What signals would you use to determine that. How would you rank the posts on that page.


Round 5:
1) Questions on final year project.
2) Design an interface on cache. Then I was asked incremental questions of the code that I have written. Pointed some issues and I was asked to correct them.