# Google And MicroSoft Interview Questions

*/ >

### 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.

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;
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);

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<x<20000, how do u sort it. U can load only 1000 numbers at a time in memory.

5) Remove alternate nodes from a link list

6) Write code for removing loop from a link list

7) You have a BST containing integers. now Given any two numbers x and y, how do u find the common ancestor of nodes which have these values in them. You are given pointet to root of the BST.

8) Code for printing all permutations of a string.

9) Code for reversing words of the string

# 3>Microsoft interview

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.

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 - 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 <operator> Expression | <operator> Expression | Expression <operator> Bracket | bracket <operator> Expression |bracket <operator> bracket|(Expression)

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)

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

### Comments (1)

Dhruvesh
Said this on 7-27-2010 At 01:15 pm

Very good post Abhishek......

Post a Comment
* Your Name:
* Your Email:
(not publicly displayed)
Reply Notification:
Approval Notification:
Website:
* Security Image: Generate new
Copy the numbers and letters from the security image:

### Email to Friend

Fill in the form below to send this article to a friend:

Email to Friend
* Your Name:
* Your Email:
* Friend's Name:
* Friend's Email:
* Security Image: Generate new
Copy the numbers and letters from the security image
* Message: