Latest CTS Aptitude Interview Papers

11.A man sells apples. First he gives half of the total apples what he has and a half apple.

Then he gives half of the remaining and a half apple. He gives it in the same manner. After 7 times all are over. How many apples did he initially have.

ans: 127 apples.

12.In a club there are male and female members. If 15 female quit then the number of females will become double the number of males. If 45 males quit no. of female becomes five times the number of males. Find the number of females.

ans: females:175,males:80

13.When I was married 10 years back my wife was the sixth member of my family. Now I have a baby. Today my father was dead and I had a new baby.now the average age of my family is the same as that when I was married. Find the age of my father when I was married.

ans:50

14.I and two of my friends were palying a game. For each win I get Rs 3. totally I had three wins. Player 2 got Rs9 and player 3 got Rs 12. how many games had been played.

15.A person gives a secret to two other persons in 5 minutes. How long will he take to tell the secret to 768 people.

16.There are 40 seats in a bus. People agree to share the money for the number of seats. The total money comes to 70.37. how many seats were free.

9 seats.Rs.2.27

17.I had Rs100 and I play. If I win I will hav Rs110 and if I lose I will hav Rs90. at the end I hav 2 wins and 2 loses. How much do I hav.

18.There were sums related to diagrams. They asked to calculate the areas of the circle, rectangle that were enclosed in other objects. They were simple.

20. In a village, there is flood. In one village causalities were less than the other. Why?

Ans : There were better health care centres(HCC).

21. A question on Pythagoras Theorem. Ans. 20

23. The distance between Mumbai & Calcutta is 25000 Km. Train goes from Mumbai to Culcutta for which Speed & Time are given. From C->M Speed alone is give. Of the above conditions which is not required. (Not Complete)

ans: The distance 25,000Km is not required. Because, Speed * Time = Distance. So only two conditions are required.

24. m < n & x>y Which is false?

Ans: x-m < y-n

25. A person has Rs.100. If he wins he gains 10%. If he loses the game, he loses 10%. He wins twice and loses twice. How much he has at the end?

Ans: Always less than 100.

26. Area of Shaded portion is ?

Ans : 115.5

Verbal

27. In A tribal group two groups live in different climatic conditions. Ear Sensitivity is tested and found that one has more when compared to other. What is the reason.

Ans. Depends on the physical place and condition he is living.

There were many questions on logical reasoning.

Eg:

There are two identical islands. Same tribe live in the islands. But their receptiveness varies.

This is the question.

There were four choices and we have to select the most appropriate one.

For the above one the answer is ----- because of climatic changes

There was a question in which they gave a polygon with all the external angles. we have to calculate the asked interior angle

Latest Google Top Interview Puzzles

There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].

Solve it without division operator and in O(n).

There is a linked list of numbers of length N. N is very large and you don't know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.

Hint:

1. Use random function rand() (returns a number between 0 and 1) and irand()
(return either 0 or 1)
2. It should be done in O(n).

Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M >> N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm.

You are given a game of Tic Tac Toe. You have to write a function in which you pass the whole game and name of a player. The function will return whether the player has won the game or not. First you to decide which data structure you will use for the game.You need to tell the algorithm first and then need to write the code.

Note: Some position may be blank in the game। So your data structure should
consider this condition also.

You are given an array [a1 To an] and we have to construct another array [b1 To bn] where bi = a1*a2*...*an/ai. you are allowed to use only constant space and the time complexity is O(n). No divisions are allowed.

How do you put a Binary Search Tree in an array in a efficient manner.


Hint :: If the node is stored at the ith position and its children are at
2i and 2i+1(I mean level order wise)Its not the most efficient way.

How do you find out the fifth maximum element in an Binary Search Tree in efficient manner.

Note :: You should not use use any extra space. i.e sorting Binary Search Tree
and storing the results in an array and listing out the fifth element.

Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 ... iN c1 c2 c3 ... cN.Write an in-place algorithm to rearrange the elements of the array ass A = i1 c1 i2 c2 ... in cn

Given two sequences of items, find the items whose absolute number increases or decreases the most when comparing one sequence with the other by reading the sequence only once.

Given That One of the strings is very very long , and the other one could be of various sizes. Windowing will result in O(N+M) solution but could it be better? May be NlogM or even better?

How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points ?

Lets say you have to construct Google maps from scratch and guide a person standing on Gateway of India (Mumbai) to India Gate(Delhi).How do you do the same ?

Given that you have one string of length N and M small strings of length L . How do you efficiently find the occurrence of each small string in the larger one ?

Given a Binary Tree, Programmatically you need to Prove it is a Binary Search Tree
Hint: Some kind of pointer handling with In Order Traversal - anybody in for
writing some code

You are given a small sorted list of numbers, and a very very long sorted list of numbers - so long that it had to be put on a disk in different blocks. How would you find those short list numbers in the bigger one?

Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are theres to merge?

Given a file of 4 billion 32-bit integers, how to find one that appears at least twice?

Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures.

Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time.

Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.

Given an array,

i) find the longest continuous increasing subsequence.

ii) find the longest increasing subsequence.

Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?

Write a function to find the middle node of a single link list.

Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure.

Implement put/get methods of a fixed size cache with LRU replacement algorithm.

You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum.

Distance is defined like this :

If a[i], b[j] and c[k] are three elements then

distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))"

Please give a solution in O(n) time complexity

Classic - Egg Problem

You are given 2 eggs.You have access to a 100-storey building.

Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.

Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.

You can discuss these puzzles in comments.if you have any more Google puzzles which are interesting and frequently asking in interviews comment it, i will add to the above 27 puzzles.

Recent Google Interview Questions Papers

Total there are five Technical Interviews followed by Management round.

So here are the questions.

Google Interview Round 1 ::

What is the Space complexity of quick sort algorithm? how do find it?

What are dangling pointers?

Given that you can take one step or two steps forward from a given step. So find the total number of ways of reaching Nth step.

You are given biased coin. Find unbiased decision out of it?

On a empty chessboard, a horse starts from a point( say location x,y) and it starts moving randomly, but once it moves out of board, it cant come inside. So what is the total probability that it stays within the board after N steps.



Google Interview Round 2 ::

You have 1 to N-1 array and 1 to N numbers, and one number is missing, you need to find the missing the number. Now you have 1 to N-2 numbers, and two numbers missing. Find them.

You have cycle in linked list. Find it. Prove that time complexity is linear. Also find the node at which looping takes place.

Questions on my project please be prepare well about your project

How do you search for a word in a large database.

How do you build address bar in say gmail. i.e. if you press 'r' then you get all email starting from 'r', and if you press 'ra' then you will get emails starting from 'ra'.


Google Interview Round 3 ::

You have given an array. Find the maximum and minimum numbers in less number of comparisons.

You have given an array from 1 to N and numbers also from 1 to N. But more than one number is missing and some numbers have repeated more than once. Find the algo with running time O(n).


Google Interview Round 4 ::

Three strings say A,B,C are given to you. Check weather 3rd string is interleaved from string A and B.

Ex: A="abcd" B="xyz" C="axybczd". answer is yes.

Given two sorted arrays A and B.

Find the intersection of these arrays A and B.

If array A is small and array B is too large. how will you proceed for getting intersection of those two arrays?


Google Interview Round 5 ::

If you get into Google, which products are you going to work on?

What is TCP, UDP. what is reliability, unreliability, give examples of these?

What is http protocol?

How does Google search engine works?

What is indexing, what is the input and output to it. how Google does that?

Aptitude Recursion algorithms

Recursion algorithms can be analysed by 3 methods : Substitution method,recursion tree method and master method.

1)Show that the solution of T(n)=T(n/2) + 1 is O(lg n).

2)Show that the solution to T(n)=2*T((n/2)+17) is O(n*(lg n)).

3)Solve the recurrence T(n)=2*T(sqrt(n)) + 1.

4)Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n)=3*T(n/2) + n.

5)Use a recursion tree to give an asymptotically tight solution to the recurrence T(n)=T(n-a) + T(a) +cn,where a >=1 and c>0 are constants.

6)Draw the recursion tree for t(n)=4T(n/2)+cn,where c is a constant,and provide a tight asymptotic bound on its solution.

7)Use a recursion tree to give an asymptotically tight solution to the recurrence T(n)=T(an)+T((1-a)n)+cn,where a is a constant in the range 0<>0 is also a constant.

8)Use master method to give tight asymptotic bounds for the following recurrences.
a.T(n)=4T(n/2)+n.
b.T(n)=4T(n/2)+n^3

9)The recurrence T(n)=7T(n/2)+n^2 describes the running time of an algorithm A.A completing algorithm A' has a running time of T'(n)=aT'(n/4)+n^2.What is the largest integer value for a such that A' is asymptotically faster than A?

10)Can the master method be applied to the recurrence T(n)=4T(n/2)+n^2(lg n)? Why or why not? Give an asymptotic upper bound for this recurrence.

11)Use the master method to show that the solution to the binary-search recurrence T(n)=T(n/2)+ Theta(1) is T(n)=Theta(lg n).

Click here for the solutions

Find some problems on recursion here

Aptitude Basic Questions on Sorting

1 .In a selectionsort of n elements, how many times is the swap function called in the complete execution of the algorithm?

A. 1
B. n - 1
C. n log n
D. n^2

2 .Selectionsort and quicksort both fall into the same category of sorting algorithms. What is this category?

* A. O(n log n) sorts
* B. Divide-and-conquer sorts
* C. Interchange sorts
* D. Average time is quadratic.

3 . Suppose that a selectionsort of 100 items has completed 42 iterations of the main loop. How many items are now guaranteed to be in their final spot (never to be moved again)?

* A. 21
* B. 41
* C. 42
* D. 43

4 .Suppose we are sorting an array of ten integers using a some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here:

1 2 3 4 5 0 6 7 8 9

Which statement is correct? (Note: Our selectionsort picks largest items first.)

* A. The algorithm might be either selectionsort or insertionsort.
* B. The algorithm might be selectionsort, but could not be insertionsort.
* C. The algorithm might be insertionsort, but could not be selectionsort.
* D. The algorithm is neither selectionsort nor insertionsort.

5 .Suppose we are sorting an array of eight integers using a some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here:

2 4 5 7 8 1 3 6

Which statement is correct? (Note: Our selectionsort picks largest items first.)

* A. The algorithm might be either selectionsort or insertionsort.
* B. The algorithm might be selectionsort, but it is not insertionsort.
* C. The algorithm is not selectionsort, but it might be insertionsort.
* D. The algorithm is neither selectionsort nor insertionsort.

6 .When is insertionsort a good choice for sorting an array?

* A. Each component of the array requires a large amount of memory.
* B. Each component of the array requires a small amount of memory.
* C. The array has only a few items out of place.
* D. The processor speed is fast.

7 What is the worst-case time for mergesort to sort an array of n elements?

* A. O(log n)
* B. O(n)
* C. O(n log n)
* D. O(n^2)

8 What is the worst-case time for quicksort to sort an array of n elements?

* A. O(log n)
* B. O(n)
* C. O(n log n)
* D. O(n^2)

9 .Mergesort makes two recursive calls. Which statement is true after these recursive calls finish, but before the merge step?

* A. The array elements form a heap.
* B. Elements in each half of the array are sorted amongst themselves.
* C. Elements in the first half of the array are less than or equal to elements in the second half of the array.
* D. None of the above.

10 .Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this:

2 5 1 7 9 12 11 10

Which statement is correct?

* A. The pivot could be either the 7 or the 9.
* B. The pivot could be the 7, but it is not the 9.
* C. The pivot is not the 7, but it could be the 9.
* D. Neither the 7 nor the 9 is the pivot.

11 .What is the worst-case time for heapsort to sort an array of n elements?

* A. O(log n)
* B. O(n)
* C. O(n log n)
* D. O(n^2)

12.Suppose you are given a sorted list of N elements followed by f(N) randomly ordered elements.How would you sort the entire list if
* A. f(N)=O(1)
* B. f(N)=O(logN)
* C. f(N)=O(N^1/2)
* D. How large can f(N) be for the entire list still to be sortable in O(N) time?

13.Prove that any algorithm that find an element X in a sorted list of N elements requires Omega(log N) comparisons.

14.Prove that sorting N elements with integer keys in the range 1 < Key < M
takes O(M + N) time using bucket sort.

15.Suppose you have an array of N elements,containing only 2 distinct keys, true and false.Give an O(N) algorithm to sort the array.

16.Prove that any comparison based algorithm to sort 4 elements requires atleast 5 comparisons

17. In how many ways can 2 sorted arrays of combined size N be merged?

18.Show that binary insertion may reasonably be expected to be an O(n log n) sort.

19.You are given two sets of numbers Xi and Yj , where i and j run from 1 to N.
Devise an algorithm to find the M largest values of Xi −Yj . This algorithm should
not be quadratic in N, though it is permitted to be quadratic in M.
You should regard N as being of the order of 20,000 and M as being of the order
of 1,000.


20.If 1024 numbers are drawn randomly in the range 0–127 and sorted by binary
insertion, about how many compares would you expect?

Fresher Interview questions on Sorting - Quick Sort

QuickSort

Here are some of the commonly asked and good questions on quick sort.

1.
Determine the running time of QuickSort for

a.Sorted input
b.reverse -ordered input
c.random input
d. When all the elements are equal


2.
The ones who are familiar with QuickSort as also well aware of the important phase of the algorithm-the pivot selection.Suppose we always choose the middle element as the pivot .Does this make it unlikely that QuickSort will require quadratic time?

3.
What is the worst-case behavior (number of comparisons) for quick sort?
link to solution
In selecting the pivot for QuickSort, which is the best choice for optimal partitioning:
a.The first element of the array
b.The last element of the array
c.The middle element of the array
d.The largest element of the array
e.The median of the array
f.Any of the above
link to solution

4.
In its worst case QuickSort behaves like:
a.Bubble sort
b.Selection sort
c.Insertion sort
d.Bin sort
link to solution


5.
Describe an efficient algorithm based on Quicksort that will find the element of a set that would be at position k if the elements were sorted.


6.
Recall that the linked-list version of quicksort() puts all items whose keys are equal to the pivot's key into a third queue, which doesn't need to be sorted. This can save much time if there are many repeated keys.

The array-based version of quicksort() does not treat items with equal keys specially, so those items are sorted in the recursive calls.

Is it possible to modify array-based quicksort() so that the array is partitioned into three parts (keys less than pivot, keys equal to pivot, keys greater than pivot) while still being in-place? (The only memory you may use is the array plus a constant amount of additional memory.)

C programming questions/puzzles

What do you think would be the output of the following program and why? (If you are about to say "f is 1.0", I would say check it out again)

#include




int
main()

{


float
f=0.0f;


int
i;





for(i=0;i<10;i++)


f
=
f
+
0.1f;





if(f
==
1.0f)


printf("f is 1.0 \n");


else


printf("f is NOT 1.0\n");





return
0;

}




I thought the following C program is perfectly valid (after reading about the comma operator in C). But there is a mistake in the following program, can you identify it?

#include




int
main()

{


int
a
=
1,2;


printf("a : %d\n",a);


return
0;

}




What would be the output of the following C program? (Is it a valid C program?)

#include

int
main()

{


int
i=43;


printf("%d\n",printf("%d",printf("%d",i)));


return
0;

}





void
duff(register
char
*to, register
char
*from, register
int
count)
{

register
int
n=(count+7)/8;

switch(count%8){

case
0: do{ *to++
=
*from++;

case
7: *to++
=
*from++;

case
6: *to++
=
*from++;

case
5: *to++
=
*from++;

case
4: *to++
=
*from++;

case
3: *to++
=
*from++;

case
2: *to++
=
*from++;

case
1: *to++
=
*from++;
}while( --n
>0);
}
}

Is the above valid C code? If so, what is it trying to acheive and why would anyone do something like the above?




Here is yet another implementation of CountBits. Verify whether it is correct (how do you that???). If so, find out the logic used.


int
CountBits(unsigned
int
x)
{

int
count=0;

while(x)
{

count++;

x
=
x&(x-1);
}

return
count;
}




Are the following two function prototypes same?


int
foobar(void);

int
foobar();

The following programs should be of some help in finding the answer: (Compile and run both the programs and see what happens)
Program 1:


#include


void
foobar1(void)
{

printf("In foobar1\n");
}


void
foobar2()
{

printf("In foobar2\n");
}


int
main()
{

char
ch
=
'a';

foobar1();

foobar2(33, ch);

return
0;
}

Program 2:


#include


void
foobar1(void)
{

printf("In foobar1\n");
}


void
foobar2()
{

printf("In foobar2\n");
}


int
main()
{

char
ch
=
'a';

foobar1(33, ch);

foobar2();

return
0;
}




What's the output of the following program and why?


#include


int
main()
{

float
a
=
12.5;

printf("%d\n", a);

printf("%d\n", *(int
*)&a);

return
0;
}




The following is a small C program split across files. What do you expect the output to be, when both of them compiled together and run?
File1.c


int
arr[80];

File2.c


extern
int
*arr;

int
main()
{

arr[1] =
100;

return
0;
}




Explain the output of the following C program (No, the output is not 20).


#include


int
main()
{

int
a=1;

switch(a)
{ int
b=20;

case
1: printf("b is %d\n",b);

break;

default:printf("b is %d\n",b);

break;
}

return
0;
}




What is the output of the following program? (Again, it is not 40, (if the size of integer is 4)).


#define SIZE
10


void
size(int
arr[SIZE])
{

printf("size of array is:%d\n",sizeof(arr));
}


int
main()
{

int
arr[SIZE];

size(arr);

return
0;
}




The following is a simple c program, in which there is a function called Error to display errors. Can you see a potential problem with the way Error is defined?


#include


#include


void
Error(char*
s)
{

printf(s);

return;
}


int
main()
{

int
*p;

p
=
malloc(sizeof(int));

if(p
==
NULL)
{

Error("Could not allocate the memory\n");

Error("Quitting....\n");

exit(1);
}

else

{

/*some stuff to use p*/

}

return
0;
}




What is the differnce between the following function calls to scanf?(Please notice the space carefully in the second call. Try removing it and observe the behaviour of the program)


#include


int
main()
{

char
c;

scanf("%c",&c);

printf("%c\n",c);


scanf(" %c",&c);

printf("%c\n",c);


return
0;
}