## Posts

Showing posts from June, 2011

### Probability of observing a car

If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)?

### [Google puzzle]Find the 25th fastest car

There are 49 race cars and no two car have the same speed. Now  you are given  7 tracks with equal length,each can occupy maximum of 7 cars.You have to find the 25th fastest car. At least how many races are needed.(no time recorder).please share your solution along with explanation.

### Give a BST find two numbers that sum upto a given value

Given a BST, is it possible to find two numbers that add up to a given value, in O(n) time and little additional memory. By little additional memory, it is implied that you can't copy the entire BST into an array/list.

### Destructor in c++

What is the output of c++ program given below :

#include iostream.h class Base { public: Base(){ cout<<"Constructing Base";} // this is a destructor: ~Base(){ cout<<"Destroying Base";} }; class Derive: public Base { public: Derive(){ cout<<"Constructing Derive";} ~Derive(){ cout<<"Destroying Derive";} }; void main() { Base *basePtr = new Derive(); delete basePtr; }

### print a binary tree level wise from leaves to root

Write an algorithm to print a binary tree level wise and that too from leaves to root. Also only one queue and one stack can be used for the purpose.

### Regular numbers

you have a sequence where each number is a multiple of 2 or 5 (so: 2^i * 5^j). Given the beginning of the sequence as 1,2,4,5,8,10,16... and find a algorithm to calculate the next number in the sequence?

### count number of bits set in constant time

Count No of Set bits in Number in O(1).

### Fill the number matrix

There is a 2X4 matrix, in this you are supposed to arrange the numbers from 1-8, so that no consecutive numbers are adjacent(vertically, horizontally and diagonally) to each other. It is possible to do if one keeps on trying it randomly but it can be done with an intelligent approach too. What would that be?

There is a circle enclosed in a square,such that it is touching all the four sides of the square. In the top left space between square and the circle, there is a rectangle with length 14 and breadth 7, such that top left corner of the rect is the top-left corner of square and bottom right corner lies on the circumference of the circle. What is the radius of the circle?

### Frog and River

A frog has to cross a river. There are n rocks in the river, using which the frog can leap across the river. On its way across the river the frog can chose to skip a rock, but it cannot skip two consecutive rocks because that would be two far a distance for the frog to hop, also the from would not skip the first rock and the last rock. E.g. if there are 3 rocks, 1,2,3 and 4, there could be three following routes it could take:
1,2,3,4
1,2,3,4
1,3,4
1,2,4 Write a recursive algorithm, that takes a number of rocks' and prints all the feasible paths.

### [Carnegie Mellon]Pancakes with a problem

The chef at our place is sloppy: when he prepares pancakes, they come out all different sizes.
When the waiter delivers them to a customer, he rearranges them (so that smallest is on top,and so on, down to the largest at the bottom)
He does this by grabbing several from the top and flipping them over, repeating this (varying the number he flips) as many times as necessary.
eg : Assume pancakes are represented through numbers as :
5 2 3 4 1
Now you have to sort it as 1 2 3 4 5 using only flip operations.How many optimal flip operations required in worst case.

### Find the equilibrium point

Find a point in an array where sum of left side array members(wrt to that point) and right side(wrt to that point) are equal..in other words equilibrium point.

### Check if a point is vertex of convex polygon

You are given a convex polygon and an additional point. You know the x and y co-ordinates of all vertices of the polygon and the point. Find if the point is one of the vertices of the polygon in O(log N) time..

### Circus arrangment

A circus is designing an act consisting of a tower of people standing atop one another’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below her. Given the heights and weights of each person in the circus, what is the largest possible number of people in such a tower?

Input(ht wt) : (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)

Output: The longest tower is length 6 and includes from top to bottom: (56,90) (60,95) (65,100) (68,110) (70,150) (75,190)

### Check whether point lies inside polygon

You are given a convex polygon and an additional point. You know the x and y co-ordinates of all vertices of the polygon and the point. Find if the point is one of the vertices of the polygon in O(log N) time.

### Boys and Girls Ratio

In a country in which people only want boys, every family continues to have children until they have a boy. if they have a girl, they have another child. if they have a boy, they stop. what is the proportion of boys to girls in the country?

### Heaven and Hell again

A person dies, and arrives at the gate to heaven. there are three doors. one of them leads to heaven. another one leads to a 1-day stay at hell, and then back to the gate, and the other leads to a 2-day stay at hell, and then back to the gate. every time the person is back at the gate, the three doors are reshuffled. how long will it take the person to reach heaven?

### sort LL efficiently

The LL is in alternating ascending and descendin orders. Sort the list efficiently
egs: 1->2->3->12->11->2->10->6->NULL

### Generate all subsets of a given set

Generate all subsets of a given set. In another words generate super set of a given set. Example- Given set {1,2,3}. Output- {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}

### find 2nd smallest element among n elements

Show that second smallest of n elements can be found with n + logn -2 in worst case.

### Loop in a DLL

Can there exist a loop in a doubly linked list? if so how will you remove it?

### place 10 trees in 5 rows of 4 each

There are 10 Apple trees. A Farmer has placed these trees in 5 rows of 4 each... Can you tell me how to do it?

### Data structure for large mathematical operations

Design the data structure to provide the mathematical operations +, - ,/ , * etc for the very very large numbers.
Also implement the + function for two such very very large numbers.

### n largest pairs from two sorted array

Given two sorted positive integer arrays A(n) and B(n), we define a set S = {(a,b) | a in A and b in B}.
Obviously there are n^2 elements in S. The value of such a pair is defined as Val(a,b) = a +b.
Now we want to get the n pairs from S with largest values.

### find if one tree is subset of the other

How do you find if one tree is subset of the other?
consider below two tree
A
B C
D E
in order is DBEAC
for tree as
E
B A
in order is BEA
You can say that it is a sub-tree .

### Imlement stack using queue

Given two queues with their standard operations (enqueue, dequeue, isempty, size), implement a stack with its standard operations (pop, push, isempty, size).

### assign the grandparent node for all the nodes in the tree.

you have given a node of a tree. that node is defined as below:
node(
int value,
node left;
node right;
node grandparent)
at the starting the grand parent node is null in the tree. you have to assign the grandparent node for all the nodes in the tree.

### Swap every consecutive elements in Linked list

You have single linkedlist.Swap every consecutive two elements without using value stored in the node of linkedlist. for eg. 1->2->3->4->5 then output should be 2->1->4->3->5

### find rotation of integer array

Implement the following function, FindSortedArrayRotation, which takes as its input an array of unique integers that has been sorted in ascending order, then rotated by an unknown amount X where 0 <= X <= (arrayLength – 1). An array rotation by amount X moves every element array[i] to array[(i + X) % arrayLength]. FindSortedArrayRotation discovers and returns X by examining the array.

### frequency of each words in a dictionary

There is a document containing lots of information. You have a function char * getNextWord() which returns the next word from the document.
a) which data structure should be used for maintaining the information about the frequency of words.
b) Write an effective algo for maintaining the information about the frequency of each word in the document.
c) what is the complexity of algorithm.

### find an element in an rotated integer array

Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). How do you find an element in the rotated array efficiently?

### print tree anticlockwise

Print all edge nodes of a complete binary tree anti-clockwise.
That is all the left most nodes starting at root, then the leaves left to right and finally all the rightmost nodes.
In other words, print the boundary of the tree.
Variant: Print the same for a tree that is not complete.
Assume we have a binary tree below:
_30_    /   \     1020  /     /  \ 50    45  35The correct solution should print 30, 10, 50, 45, 35, 20.

You are given an IPV4 address.Write a code to validate the address.

### Arrange positive and negative numbers

you are given a set of positive and negative integers ,group all the positive integers on one side and negative integers on other side.Order of numbers must be maintained after rearrangement.

### Create tree from inorder and postorder traversal

Given inorder and postorder traversals construct a binary tree.
Let us consider the below traversals
Inorder sequence: D B E A F C
Postorder sequence: D E B F C A
tree should be:
A / \ / \ B C / \ / / \ / D E F

### Binary tree is sum tree or not

Write a function that returns true if the given Binary Tree is SumTree else false. A SumTree is a Binary Tree where the value of a node is equal to sum of the nodes present in its left subtree and right subtree. An empty tree is SumTree and sum of an empty tree can be considered as 0. A leaf node is also considered as SumTree.

Following is an example of SumTree.

26
/ \
10 3
/ \ \
4 6 3

### modifying const in c++

void fun( const int & k)
{
cout << k;
}

int main()
{
const int i=10;

int *p=(int*)&i;
*p=15;
cout<< i;
cout<<*(&i);
cout<<*p;
fun(i);
}
What will be the output and reason for the same.

### implement two stack in an array

Implement two stacks in a single array. Please note that you should not report stack full until all the elements are full.

### square root of a number

How will you calculate square root of a number?

### missing cards from deck

You are given a deck of cards of which one card is missing .How will you find which card is missing.

### lowest common ancestor

Given the values of two nodes in a *binary search tree*, write a c program to find the lowest common ancestor. You may assume that both values already exist in the tree.
The function prototype is as follows:
int FindLowestCommonAncestor(node* root, int value1, int value)
I/P : 4 and 14 O/P : 8 (Here the common ancestors of 4 and 14, are {8,20}. Of {8,20}, the lowest one is 8).

### Pythagorean triplet in an integer array

suggest an algorithm that finds all Pythagorean triplets among numbers in a given array. Pythagorean triplet is a set {a,b,c} such that a2 = b2 + c2. Example: for array [9, 2, 3, 4, 8, 5, 6, 10] the output of the algorithm should be {3, 4, 5} and {6, 8, 10}.

### print the integer array randomly

Given an array arr of size M containing distinct integers, randomly select N distinct integers and output them. You are given the rand() function and N < M.

### Rearrange array into sorted even and odd groups

Rearrange an array of integers such that on one side you have all even numbers and the other side you have all odd numbers.
now among the even numbers, they should be sorted and among the odd numbers they should be sorted.You can use c++ STL.

### output the integers in sorted order using constant storage

Given a stream of N integers which has the property that no integer is more than 1000 positions away from its sorted location, how would you output the integers in sorted order while using constant storage?

### [Microsoft]:Lucky Number

Take the set of integers
1,2,3,4,5,6,7,8,9,10,11,12,14,15,16,17,18,19,……
First, delete every second number, we get following reduced set.
1,3,5,7,9,11,13,15,17,19,…………
Now, delete every third number, we get
1,3,7,9,13,15,19,….….
Continue this process indefinitely……
Any number that does NOT get deleted due to above process is called “lucky”.
Therefore, set of lucky numbers is 1,3,7,13,25,………
Now, given an integer ‘n’, write a function to say whether this number is lucky or not.

### iterative traversal of a BST

Write the iterative version of inorder,preorder and postorder traversal of a binary search tree.

### find k numbers such that minimum difference of all the possible pairs of k numbers is maximum

Given an array of 'n' random integers. Find the k numbers such that the minimum difference of all the possible pairs of k numbers is maximum .

eg:Suppose the given elements are 11, 5, 6, 20, 30, 31, 60. then for k =4, answer should be 5 20 30 60 as minimum difference is maximum for this set.

### new and free

Can I free the memory using free instead of delete in c++? i have allocated memory with new operator and want to free it with free?

### longest substring with equal number of 0 and 1

We are given a string of 0s and 1s.
We have to find the maximum length of the substring in which no. of 0s and 1s is equal.

### nim game strategy

The game of nim is played as follows:Some numbers of sticks are placed in a pile.Two players alternate in removing either one or two sticks from the pile.The player to remove the last stick is the loser.what will be your move if you start the game.

### the game of 21

The game "21" is played as a  game with any number of players who take turns saying a number. The first player says "1" and each player in turn increases the number by 1, 2, or 3, but may not exceed 21; the player forced to say "21" loses.Here we will play this game with two players ,if you are given chance to start what will be your strategy?

### keep first m nodes and delete next n nodes

Given a singly link list, you have to keep first M nodes and then delete next N nodes, again keep M nodes and delete next N nodes and so on.Write a algo for this.

### sets all cells of row i and column j to 0

Given a matrix of 1s and 0s. Implement an algorithm that sets all cells of row i and column j to 0 if the original matrix has a 0 in cell (i,j). Would the algo change if you have to set it to 1 instead of 0?

### merge two sorted arrays without redundancy

Merge two sorted arrays and sort them in order as specified at runtime. The two arrays may share common entries between them, but the resultant array must not have duplicates.
Please define this with space and time complexity.

### print a matrix in spiral form

Given a m*n matrix ,print it in spiral form. eg: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20print it in spiral form

### minimum distance between two characters

Given a character array with a set of characters, there might be repetitions as well, given two characters, you should give the minimum distance between these two characters in the whole array.

### count number of ways from (0,0) to (m,n)

You are given a m*n chess board.you are at lower-most vertex,and you can move one step right or one step above your current co-ordinate.Find out the number of ways to reach point(m,n).

### static variable storage class

foo.c:                         bar.c:staticint foo =1;staticint foo =10;void fooTest(){void barTest(){staticint bar =2;staticint bar =20;   foo++;                         foo++;   bar++;                         bar++;   printf("%d,%d", foo, bar);     printf("%d, %d", foo, bar);}}If I compile both files and link it to a main that calls fooTest() and barTest repeatedly, the printf statements increment independently. Makes sense since the foo and bar variables are local to the translation unit.
But where is the storage allocated?

### intersection of two integer array

Given two sorted arrays: A and B. The size of array A is La and the size of array B is Lb. How to find the intersection of A and B? If La is much bigger than Lb, then will there be any difference for the intersection finding algorithm?

### Concept of fork

How many processes are created in this snippet?
main()
{
Fork();
Fork() && fork () || fork ();
Fork ();
}

### first triangle number to have over five hundred divisors

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... Let us list the factors of the first seven triangle numbers:
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?

### largest palindrome made from the product of two 3-digit numbers

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.
Find the largest palindrome made from the product of two 3-digit numbers.

### Pythagorean triplet for which their sum is 1000

A Pythagorean triplet is a set of three natural numbers, abc, for which,
a2 + b2 = c2 For example, 32 + 42 = 9 + 16 = 25 = 52.
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.