Google Written Test

Section A

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

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

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

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

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

Question-6

The number of vertices of degree zero in G is:
a) 1
b) n
c) 2n - 1
d) None

Question-7

The number of connected components in G is:
a) 2n
b) n + 2
c) n C 2
d) None

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

Question-9

The enter_CS() and leave_CS() functions to implement critical section of a
process are realized using test-and-set instruction as follows:
void enter_CS(X) {
while(test-and-set(X));
}
void leave_CS(X) {
x=0;
}
In the above solution , X is a memory location associated with the CS and is
initialized to 0. Now consider the following statements:
1. The above solution to CS problem is deadlock free
2. The solution is not starvation free
3. The processes enter CS in FIFO order
4. More than one process can enter CS at the same time
Which of the above statements is TRUE
a) 1
b) 1 and 2
c) 1 and 3
d) 2 and 4

Question-10

The following 'C' code prints:
void f(char *x) {
x++;
*x = ‘a’;
}
int main() {
char *str = "hello";
f(str);
printf("%s", str);
}
a) hello
b) allo
c) hallo
d) empty string

Question-11

An insurance company issues a policy on a small boat under the following
conditions:
The replacement cost of $5000 will be paid for a total loss. If it is not a total loss,
but the damage is more than $2000, then $1500 will be paid. Nothing will be
paid for damage costing $2000 or less and of course nothing is paid out if there
is no damage. The company estimates the probability of the first three events
as .02, .10, and .30 respectively. The amount the company should charge for the
policy if it wishes to make a profit of $50 per policy on average is:
a) $250
b) $201
c) $300
d) $1200

Question-12

We are given an array A with 8 distinct elements. Arrays B and C have 5 and 3
elements respectively and they are populated with elements from A. (The union of
elements in B and C give the elements in A)
In how many ways can the arrays B & C be populated such that both B and C have
elements in sorted (ascending) order.
a) 56
b) 128
c) 256
d) None

Question-13

Increasing the RAM of a computer typically improves performance because:
a. Virtual memory increases
b. Larger RAMs are faster
c. Fewer segmentation faults occur
d. Fewer page faults occur

Question-14

Suppose we want to synchronize two concurrent processes P and Q using binary
semaphores S and T. The code for the processes P and Q is shown below.
Process P:
while (1) {
W:
print '0’;
print '0';
X:
}
Process Q:
while (1) {
Y:
print '1'
print '1'
Z:
}
Synchronization statements can be inserted only at points W, X, Y and Z.
V() increments the semaphore, whereas P() decrements it
Which of the following will always lead to an output staring with '001100110011' ?
a) P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1
b) P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S initially 1, and T initially 0
c) P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S and T initially 1
d) P(S) at W, V(S) at X, p(T) at Y, V(T) at Z, S initially 1, and T initially 0

Question-15

Which of the following statements are true?
I Shortest remaining time first scheduling may cause starvation
II Preemptive scheduling may cause starvation
III Round robin is better than first come first serve in terms of response time
a) I only
b) I and III only
c) II and III only
d) I, II and III

Question-16

A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 ns (nano seconds)
respectively. Registers that are used between the stages have a delay of 5 ns each. Assuming
constant clocking rate, the total time taken to process 1000 data items on this pipeline will
approximately be
a. 120 us (micro seconds)
b. 165 us
c. 180 us
d. 175 us

Question-17

Consider a disk system with 100 cylinders. The requests to access the cylinders occur in
following sequences
4, 34, 10, 7, 19, 73, 2, 15, 6, 20
Assuming that the head is currently at cylinder 50, what is the time taken to satisfy all requests
it it takes 1ms to move from one cylinder to adjacent one and shortest seek time first policy is
used?
a. 95ms
b. 119ms
c. 233ms
d. 276ms

Section B : Code

1. Write the code to find lexicographic minimum in a circular array, e.g. for the array
BCABDADAB, the lexicographic mininum is ABBCABDAD.

explain logic and write code in paper.

All The Best.