Google Placement Paper
Company: Google
Latest Google Placement Papers 2010
Institute: IIT Guwahati
Date of test: 24/11/2010
Package: 16Lakh
Paper Type: CSE B Tech/M Tech /PHD
Section A
1. Quick-sort is run on two inputs shown below to sort in ascending order
(i) 1,2,3, ….,n
(ii) n, n – 1, n – 2, …., 2, 1
Let C1 and C2 be the number of comparisons made for the inputs (i) and (ii) respectively. Then,
a) C1 < C2 b) C1 > C2
c) C1 = C2
d) We cannot say anything for arbitrary n
2. Which of the following languages over {0, 1} is regular?
a) 0i1j such that i ≤ j
b) 0iw1j such that w ∈ {0, 1}∗ and i ≥ 0
c) All strings of 0s and 1s such that every pth character is 0 where p is prime
d) None of the above
3. We are given a set X = {x1, x2, …, xn} where xi = 2i. 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) 1 / n
b) 2
c) sqrt(n)
d) n
4. 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
5. For any string s ∈ (0 + 1)*, let d(s) denote the decimal value of s (eg: d(101) = 5, d(011) = 3).
Let L = {s ∈ (0+1)* | d(s) mod 5 = 2 and d(s) mod 7 = 4}. Which of the following statements is
true?
a) L is recursively enumerable, but not recursive
b) L is is recursive, but not context-free
c) L is context-free, but not regular
d) L is regular
Common data for questions 6 and 7
The 2n vertices of a graph G corresponds to all subsets of a set of size n. Two vertices of G are
adjacent if and only if the corresponding sets intersect in exactly 2 elements
6. The number of vertices of degree zero in G is:
a) 1
b) n
c) 2n – 1
d) None
7. The number of connected components in G is:
a) 2n
b) n + 2
c) n C 2
d) None
8. There are 5 nested loops written as follows,
int counter = 0;
for (int loop_1=0; loop_1 < 10; loop_1++) { for (int loop_2=loop_1 + 1; loop_2 < 10; loop_2++) { for (int loop_3=loop_2 + 1; loop_3 < 10; loop_3++) { for (int loop_4=loop_3 + 1; loop_4 < 10; loop_4++) { for (int loop_5=loop_4 + 1; loop_5 < 10; loop_5++) { counter++; } } } } } What will be the value of counter in the end (after all the loops finished running)?
a) 15C5
b) 14C5
c) 10C5
d) 10 * 9 * 8 * 7 * 6 * 5
Google Placement Paper