----------------------------------------------------------------------------------------------------------------------------- --
©ittestpapers.com – All rights reserved
GOOGLE PLACEMENT PAPER
Google - Sample Placement Question Papers
1>Google interview
Questions:
interview 1:
1) space complexity of quick sort
2) what are dangling pointers
3) you can take one step or two steps forward from a given step. So find the total number of ways of
reaching Nth step.
4) you are given biased coin. Find unbaised decision out of it.
5) on a empty chessboard, a horse starts from a point( say location x,y) and it starts moving randomly,
but once it moves out of board, it cant come inside. So what is the total probability that it stays within
the board after N steps.
Second Interview:
1) You have 1 to N-1 array and 1 to N numbers, and one number is missing, you need to find the missing
the number. Now you have 1 to N-2 numbers, and two numbers
missing. Find them.
2) You have cycle in linked list. Find it. Prove that time complexity is linear. Also find the node at which
looping takes place.
3) question on my project.
4) how do you search a word in a large database.
5) how do you build address bar in say gmail. i.e. if you press 'r' then you get all email starting from 'r',
and if you press 'ra' then you will get emails starting from 'ra'.
3rd interview:
1) you have an array. Find the maximum and minimum numbers in less number of comparisons.
2) you have an array from 1 to N and numbers also from 1 to N. But more than one number is missing
and some numbers have repeated more than once. Find the algo with running time O(n).
4th interview:
1) 3 strings say A,B,C are given to you. Check weither 3rd string is interleaved from string A and B.
ex: A="abcd" B="xyz" C="axybczd". answer is yes.
2)Given two sorted arrays A and B.
i)Find the intersection of these arrays A and B.
ii)If array A is small and array B is too large. find how are you doing.
ITtestPapers.com – Placement Papers, Interview Questions and Tutorials
----------------------------------------------------------------------------------------------------------------------------- --
©ittestpapers.com – All rights reserved
5th interview:
1) If you get into google, which product are you going to working.
2) what is tcp , udp. what is reliability, unreliablity, give examples of these.
3) what is http protocol.
4) how does google search engine works
5) what is indexing, what is the input and output to it. how google does that.
2>Microsoft interview questions
1. There are two singly linked lists l1 and l2 representing polynomials in X. we have to find difference b/w
lists l1-l2. lists are in orders of descending powers.
constraints:
no extra space i.e., O(1) space
O(m+n) time complexity. m and n and nodes in the lists.
struct node{
int coeff;
int power;
node *next;
};
2. write atoi function with all test cases.
3. output of recursive procedure (anyone could solve it using state space tree)
4. find bugs in the xstrrev function.
char *xstrrev (const char *s1)
{
char s2[20];
for (int i=strlen(s1)-1;i>=0;++i)
s2[strlen(s1)-i-1]=s1[.i];
//here was one bug...the code did not set last char as '\0'.
return s2;//one more bug here..returning local array. we need to allocate in heap and
//make it static
}
5. Design a soln , expalin the DataStructure used and write efficiency class for finding out the top 100
frequently used words in the editor. The words are updated in the DS used for every added or deleted
words and the functions below are called for every updated word.
write the pseudocode for
onWordAdd (const char *word);
onWordDel (const char *word);
ITtestPapers.com – Placement Papers, Interview Questions and Tutorials
----------------------------------------------------------------------------------------------------------------------------- --
©ittestpapers.com – All rights reserved
1. 1) Two linked lists intersect at one node (imagine Y shape)...after intersecting, remaining nodes are
common to both the link lists. how do u find the point of intersection
2) Given a BST, how do u check whether it is a valid BST
3) You have n machines, each having n integers. Now u have to find median of these n^2 numbers, but u
can load only 2n integers at a time in memory
4) Given an array having 16000 unique integers, each lying within the range 1
1. Given a single link list with one info part containing single character and a link. Check whether the link
list is a palindrome or not.
The algo should run in Linear time only. You can't use any array or string to store the string of link-list.
2. Given a sentence ex:"I love Microsoft" reverse the string as "Microsoft love I".
The alog shoudl run in Linear time. You can't use any array or string to store the string.
3. Given an array which contains only 0's or 1's. Now arrange all the O's in the front of the array followed
by all the 1's.
The algo should have better time complexity than O(N).
4. Given a sentence ex: "Mississippi". Remove all the repetations and use the same string to store the
resultant string.
The algo should run in Linear time. You can't use a different string to store the resultant string or the
given string.
5. Given a string ex: "aabccdcb". Find all size palindrome of the given string.
ITtestPapers.com – Placement Papers, Interview Questions and Tutorials
----------------------------------------------------------------------------------------------------------------------------- --
©ittestpapers.com – All rights reserved
OUTPUT:-
aa
aabcc
cc
cdc
....
....
...
The algo should have a time complexity better than O(N^3).
4>MS-Google Problem.
1>This is the question asked by google in telephonic interview
Given two arrays A and B.
A has integers unsorted.
B has the same length as A and its values are in the set {-1,0,1}
you have to return an array C with the following processing on A.
if B has 0 then C must have A
if B has -1 then A must be in C within the sub-array C[0] - C[i-1] ie. left subarray
if B has 1 then A must be in C within the sub array C[i+1] - C[length(A)] ie right subarray.
If no such solution exists then printf("no solution");
2)Consider a binary tree,Policemen is to be placed such that for each edge of the tree, there is a
policemen on atleast one side of each edge.
Tell the minimun no. of policemen and their location.(time-O(N)).
Microsoft Qustions
3)U r given an expression like (a+((b+c)))..... here extra braces r provided on b+c... i mean like (b+c) is
ok... bt ((b+c)) isnt as it contains redundant.. So fr given expression u hav totell
whether expression contains redundant paranthesis or not.....
(a+(b+c) )is ok nd (a+((b+c)) contains redundant one. can we solve by counting no of operands,no
operators and no of braces.
Using stack can we solve this problem?
Sol>Q3
we can use some parsing algorithm for Q3
1)Expression (E)= operand | Expression
ITtestPapers.com – Placement Papers, Interview Questions and Tutorials
----------------------------------------------------------------------------------------------------------------------------- --
©ittestpapers.com – All rights reserved
eg E-->a| E-->E*E |E-->+E|E-->E+B|E-->B+E|E-->B+B|(E);
2)Bracket --> (E)
if condition (bracket) is met ..then it is redunant expression
parse and reduce the string ....finally it must end up with expression(E)
eg:
(a+((b+c)))
convert all operand to E
(E+((E+E)))
reduce E+E to E
(E+((E)))
reduce (E) to B
(E+(B))
(B) arrives redunant
(a+((a+b)+(a+b)))
convert all operand to E
(E+((E+E)+(E+E)))
reduce E+E to E
(E+((E)+(E)))
(E)-->B
(E+(B+B))
B+B to E
(E+(E))
(E) -->B
(E+B)
ITtestPapers.com – Placement Papers, Interview Questions and Tutorials
----------------------------------------------------------------------------------------------------------------------------- --
©ittestpapers.com – All rights reserved
E+B-->E
(E)
(E)-->E
thus it is not an redunant expression
4)Prove that no of prime nos r infinite....
ie thr doesn't exist any upper limit after which prime no doesn't exist.
prove that.....
5)9. See this matrix....
a b c d
e f g h
i j k l
m n o p
here we define a term contiguos.....
(a,b) r contiguos...... (a,e) r contiguos....... (a,f) r contiguos....bt (a,j) r nt contiguos.......
u r given a N X N matrix/array ........ of values all distinct...
u r also given m values....... now u hav to detect in above provided array that whether these m
values r contiguos or not....
like in above matrix..
abcd r contiguos.....
bfjn r contiguos.....
bfkh r contiguos.....
cfjg r contiguos.....
dlpk r nt contiguos.....
ie m values r contiguos if u can reach all m values if u move only thru contiguos elements..........
Read more: http://www.ittestpapers.com/google-and-microsoft-interview-questions.html#ixzz0qTkGsi7n
To Download Placement papers go to http://www.ittestpapers.com/1/placement-papers/viewcategory.
html
For more online Placement Papers of other companies visit: http://www.ittestpapers.com/placement--
papers.html
ITtestPapers.com – Placement Papers, Interview Questions and Tutorials
----------------------------------------------------------------------------------------------------------------------------- --
©ittestpapers.com – All rights reserved
For Interview Questions & Tutorials visit: http://www.ittestpapers.com/interview-questionstutorials.
html
