Third party conducted test on behalf of Google @IIT Rajasthan.
This is effort of my colleagues and B.tech guys. I have not included answers of questions, also i can't claim that my answers are 100% accurate :) though we can discuss.
Questions asked in Google written test (21st Sept, 2012 of 70 minutes)
(30 minutes for objective questions and 40 minutes for programming questions)
Objective questions (18 questions in 30 minutes):
1. How many distinct BSTs are possible for 6 distinct numbers?
(A) 128
(B) 132
© 720
(D) 120
2. Inorder and Preorder Traversals of a tree were given. Find the Postorder Traversal.
3. Which one of the given grammars is regular?
a. (wwr)
b. (wawr)
c.
d.
4. 2 or 3 scheduling questions. (LRU), optimal page replacement policy
5. Find the time complexity of a recursive algorithm.
6. We are given a set X = {x1, x2, ..., xn} where xi = 2^i. A sample S (which is a subset of X) is drawn by selecting each xi independently with probability pi = 1 / 2. The expected value of the smallest number in sample S is
(A) log n
(B) 2
© n
(D) √n
7. Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?
a) R is NP-complete
b) R is NP-hard
c) Q is NP-complete
d) Q is NP-hard
8.
if(fork() && fork())
fork();
if(fork() || fork())
fork();
printf(“hello\n”);
how many times hello will be printed?
9. which of the following languages can be solved using DFA
(a^n)(b^n)\
(a^n)x(b^n)
(a^n)(b^n)x
x(a^n)(b^n)
10. 1 question from computer architecture.
11. Three processes with process ids 0,1 and 2 with their CPU burst times 2,4 and 8 time units respectively arrive at the CPU at t=0. If the Longest Remaining Time First (LRTF) algorithm is followed, what will be the average turnaround time for these 3 processes. In case of a tie for 2 or more processes, the process with smaller process id is given the priority of executing first.
(A) 11 units
(B) 12 units
© 13 units
(D) 14 units
12. What the following code does:
bool SomeFunction(unsigned int v)
{
return (v!=0) && ! (v & (v-1));
}
a) odd number
b) power of 2
c) number contains a 0 digit
d) multiple of 2
13. A simple graph is one in which no two vertices are connected by more than 1 edge and neither does it contain any cycle. Given a simple undirected graph with 6 vertices which of the following can be the only possible set of degrees corresponding to the vertices of the graph?
(A) {4,4,2,1,1,1}
(B) {4,4,2,2,1,1}
© {4,4,2,2,2,1}
(D) {4,4,1,1,1,1}
14. An array A has 7 distinct numbers. It has to be splitted into two arrays B and C such that B contains 3 numbers and C contains 4 and atleast one of the arrays should be sorted in increasing sequence. How many possible combinations of B and C are possible?
(A) 30*(7C4)
(B) 29*(7C4)
© 28*(7C3)
(D) 32*(7C4)
15. Two numbers are chosen at random from the set {1,2,3}. What is the expected value of sum of these numbers?
(A) 4
(B) 5
© 4.5
(D) 3
16. What is the time complexity for finding the GCD of nth and (n+1)th Fibonacci Number using Euclid’s Algorithm?
(A) log(log(n))
(B) log(n)
© n
(D) n^2
17. How many minimum states do you need to draw a DFA of strings which include a’s that are divisible by 6 and the number of b’s divisible by 8?
(A) 8
(B) 14
© 24
(D) 48
18. There are n stations in a slotted LAN. Each station attempts to transmit with a probability p in each time slot. What is the probability that only one station transmits in a given time slot?
(A) (1-p)^(n-1)
(B) np(1-p)^(n-1)
(C) p(1-p)^(n-1)
(D) 1-(1-p)^(n-1)
40 minutes for this programming question given below-
----------------------------------------------------------------
Programming question: (Language could be C,C++,Java. An optional component of logic presentation was also there)
There are n dice each with m faces numbered from 1 to m. Given a number x, find out the probability that the sum of all numbers obtained from the n dice in a trial is greater than x. All dice are fair. A function double winningProbability(int n, int m,int x) was to be written.
This question can be divided into two cases, n<=m and n>m.
Case 1: When n<=m,
Probability=(1-xCn/k), where k=m^n.
Case 2: When n>m,
This is effort of my colleagues and B.tech guys. I have not included answers of questions, also i can't claim that my answers are 100% accurate :) though we can discuss.
Questions asked in Google written test (21st Sept, 2012 of 70 minutes)
(30 minutes for objective questions and 40 minutes for programming questions)
Objective questions (18 questions in 30 minutes):
1. How many distinct BSTs are possible for 6 distinct numbers?
(A) 128
(B) 132
© 720
(D) 120
2. Inorder and Preorder Traversals of a tree were given. Find the Postorder Traversal.
3. Which one of the given grammars is regular?
a. (wwr)
b. (wawr)
c.
d.
4. 2 or 3 scheduling questions. (LRU), optimal page replacement policy
5. Find the time complexity of a recursive algorithm.
6. We are given a set X = {x1, x2, ..., xn} where xi = 2^i. A sample S (which is a subset of X) is drawn by selecting each xi independently with probability pi = 1 / 2. The expected value of the smallest number in sample S is
(A) log n
(B) 2
© n
(D) √n
7. Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?
a) R is NP-complete
b) R is NP-hard
c) Q is NP-complete
d) Q is NP-hard
8.
if(fork() && fork())
fork();
if(fork() || fork())
fork();
printf(“hello\n”);
how many times hello will be printed?
9. which of the following languages can be solved using DFA
(a^n)(b^n)\
(a^n)x(b^n)
(a^n)(b^n)x
x(a^n)(b^n)
10. 1 question from computer architecture.
11. Three processes with process ids 0,1 and 2 with their CPU burst times 2,4 and 8 time units respectively arrive at the CPU at t=0. If the Longest Remaining Time First (LRTF) algorithm is followed, what will be the average turnaround time for these 3 processes. In case of a tie for 2 or more processes, the process with smaller process id is given the priority of executing first.
(A) 11 units
(B) 12 units
© 13 units
(D) 14 units
12. What the following code does:
bool SomeFunction(unsigned int v)
{
return (v!=0) && ! (v & (v-1));
}
a) odd number
b) power of 2
c) number contains a 0 digit
d) multiple of 2
13. A simple graph is one in which no two vertices are connected by more than 1 edge and neither does it contain any cycle. Given a simple undirected graph with 6 vertices which of the following can be the only possible set of degrees corresponding to the vertices of the graph?
(A) {4,4,2,1,1,1}
(B) {4,4,2,2,1,1}
© {4,4,2,2,2,1}
(D) {4,4,1,1,1,1}
14. An array A has 7 distinct numbers. It has to be splitted into two arrays B and C such that B contains 3 numbers and C contains 4 and atleast one of the arrays should be sorted in increasing sequence. How many possible combinations of B and C are possible?
(A) 30*(7C4)
(B) 29*(7C4)
© 28*(7C3)
(D) 32*(7C4)
15. Two numbers are chosen at random from the set {1,2,3}. What is the expected value of sum of these numbers?
(A) 4
(B) 5
© 4.5
(D) 3
16. What is the time complexity for finding the GCD of nth and (n+1)th Fibonacci Number using Euclid’s Algorithm?
(A) log(log(n))
(B) log(n)
© n
(D) n^2
17. How many minimum states do you need to draw a DFA of strings which include a’s that are divisible by 6 and the number of b’s divisible by 8?
(A) 8
(B) 14
© 24
(D) 48
18. There are n stations in a slotted LAN. Each station attempts to transmit with a probability p in each time slot. What is the probability that only one station transmits in a given time slot?
(A) (1-p)^(n-1)
(B) np(1-p)^(n-1)
(C) p(1-p)^(n-1)
(D) 1-(1-p)^(n-1)
40 minutes for this programming question given below-
----------------------------------------------------------------
Programming question: (Language could be C,C++,Java. An optional component of logic presentation was also there)
There are n dice each with m faces numbered from 1 to m. Given a number x, find out the probability that the sum of all numbers obtained from the n dice in a trial is greater than x. All dice are fair. A function double winningProbability(int n, int m,int x) was to be written.
This question can be divided into two cases, n<=m and n>m.
Case 1: When n<=m,
Probability=(1-xCn/k), where k=m^n.
Case 2: When n>m,
No comments:
Post a Comment