Google Previous Years Placement Paper Questions and selection Procedure
There were multiple objective questions and a single coding question. The focus of the paper was how quickly you could solve the general ability questions. The time limit was 1 hour.
The written test had 3 objective question sets and 2 coding question. Instead of fixing marks for each question, they had given a weightage estimate by giving suggested time interval for each question.
All objective question were given 1 min each, 1st coding question was 30 minutes and the 2nd question was suggested 45 minutes. All questions were just given estimated time intervals, and the entire paper was given at one go, with a total time of 1 hour 30 minutes.
Although the function prototypes for the coding questions were given with STL containers but you could use any language that suited you. Obviously using C++ STL or a similar construct in other languages such as Java was appreciated.
For each of the coding question an optional space was given for writing the logic. Although the logic was optional, but we seriously recommend you to give your logic. It makes much easier for the checker to understand your answer and increases your chances.
1 Given preorder traversal of a Binary Search Tree. From the given options you have to select which one can possibly be the inorder traversal of the tree.
2 If you could find the (n/4)th element of an array in O(n) time, then what is the worst time complexity of quick sort algo if this algo is used to decide the pivot element.
3 Find the min no of comparisons required to find both the max and min elements of an array containing 20 elements.
4 If an array[0…m-1,0….n-1] is stored in column major format how will u find the (i,j) element ?
5 If an insurance company pays $5000 for complete loss, $1500 in case of a loss of $2000 and more and nothing in case the loss is less that $2000. It obviously pays nothing in case of no loss. If the probability of the first 3 events are 0.02,0.10 and 0.3 , find what should the company charge in order to make a profit of $50 from each customer ?
6 The prob of finding the parking slot occupied is 1/3. You find it empty for 9 consecutive days. Find the prob that it will be empty on the 10th day.
7 Consider a NxN matrix in which the elements are either 0 or 1. Find how many such matrixes are possible that are symmetric in nature(the matrix and its transpose count as 1.
8 1<=i,j,k<=300.
Find (i,j,k) pairs such that their sum is divisible by 3. (2,2,1) and (2,1,2) are counted as different.
9 In the loop given below
int counter=0;
for(i=0;i<10;i++)
for(j=i+1;j<10;j++)
for(k=j+1;k<10;k++)
for(l=k+1;l<10;l++)
f For(m=l+1;m<10;m++)
counter++;
10 Find the value of counter in the end.
11 Consider a set S of the first 10 natural numbers. Find the number of subsets that do not contain consecutive elements.
12 A disk contains 16 partition unit , each unit contains 128 subunits, and each subunit contains 256 sectors of 512 byte each. Find out what is total storage capacity? Also find out the no of bits required to identify each sector?
13 Which of the following is not a Regular Language :
None given
(0^i).(1^j) such that i
(0^i).w.(1^j) such that w belongs to {0,1}* and i >= 0
such that every pth input digit is 0 where p is a prime number.
14 Find the output
void f(char * x)
{
x++;
*x=’a’;
}
int main()
{
char * str=”hello”;
f(str);
cout << str;
system(“pause”);
return 0;
}
hello
hallo
allo
empty string
15 Given an sorted array, what is the complexity of finding weather a number is present n/2 times or not.
O(lgn)
O(n)
O((lgn)2)
O(1)
The weight of a squence a0, a1,a2,… ,an is defined as a0+a1/2+a2/(2^2)+…+an/(2^(n)). A subsequence of a sequence is said to be a sequence with some of the elements deleted from the original sequence but the order of the sequence remaining the same. Now let X be the maximum weight for a subsequence of a sequence a0,a1,a2,a3..,an. And Y be the maximum weight for a subsequence of the sequence a1,a1,a2,a3…..,an. Then X in terms of Y is
max(Y,a0+Y)
max(Y,a0+Y/2)
max(Y,a0+2*Y)
a0+Y/2
16 What is the complexity for finding all the leaders in an array? A leader is defined as an element which is greater than all the elements to its right.
17 For each of the following problems, give the programming paradigm used to solve it.
Travelling Salesman Problem
Dijkstra Shortest Path Algorithm
Euclid GCD Algorithm
Binary search
Kruskal’s Minimum Spanning Tree
Tower of Hanoi
18 For each of the following operations, give the worst case time complexity:
Travelling Salesman Problem
Dijkstra Shortest Path Algorithm
Euclid GCD Algorithm
Binary search
Kruskal’s Minimum Spanning Tree
Tower of Hanoi
19 For each of the following which protocol would you use:
Live video streaming
HTTP
DNS
Subjective Questions
1 Write a program to find the index in an circular array such that the string that is formed starting from that index is first in lexicographic order. For example in the circular array ABCDEABCCDE
2 You are given an array of n elements [1,2,….n]. For example {3,2,1,6,7,4,5}.
3 Now we create a signature of this array by comparing every consecutive pir of elements. If they increase, write I else write D. For example for the above array, the signature would be “DDIIDI”. The signature thus has a length of N-1. Now the question is given a signature, compute the lexicographically smallest permutation of [1,2,….n]. Write the below function in language of your choice.
4 ector* FindPermute(const string& signature);
5 A list of strings is given. Find the number of non-anagramic strings in the list i.e. the number of strings which do not have any anagram int the list.
int FindMaxSubset(const vector & v)