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

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