## Posts

Showing posts from July, 2011

### [facebook]Number as sum of candidate numbers

Given a number, and a series of candidate numbers, print out all combinations, so that the sum of candidate numbers equals to the given number.
Here order is not important, so don’t print the duplicated combination.
e.g. target is 7, candidate is 2,3,6,7
output should be 7 and 3+2+2 (but not print 2+3+2, 2+2+3)

### [MS]GCD using bitwise operation

Suggest an algorithm to find gcd of two numbers faster than Euclidean method.
Note: This works on bitwise operation.

### [MS]Remove multiple spaces

Given a string with multiple delimiters in between words,you have to replace them with single space.
eg:"       hello\t\t   hii    " is changed as " hello hii ".

### Count trees formed of n nodes

If there are n nodes given ,how many structurally different binary trees can be formed.
Note: You don't have to create trees out of n nodes given ,this is a counting problem.

### [MS]Fill the rectangle with squares

Given a rectangle with known width and height, design an algorithm to fill the rectangle using n squares(n is integer given) and make sure in the result the wasting area is minimized. Length of square doesn't have to be integer.
i.e, given width=3,height=2,n=5, one solution is that rectangle can be filled with five 1x1 squares and the wasting area is 1. Another solution could be filled with five 0.9x0.9 squares, but the wasting area is more than first solution.

### [Qualcomm]Generate random number between 1 and 7

Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5. The distribution between each of the numbers must be uniform.

### Equilibrium index of an array

Equilibrium index of an array is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes. For example, in an arrya A: A = -7, A = 1, A = 5, A = 2, A = -4, A = 3, A=0 3 is an equilibrium index, because:
A + A + A = A + A + A 6 is also an equilibrium index, because sum of zero elements is zero, i.e., A + A + A + A + A + A=0

### Delete nodes which have a greater value on right side

Given a singly linked list, remove all the nodes which have a greater value on right side. Examples:
a) The list 12->15->10->11->5->6->2->3->NULL should be changed to 15->11->6->3->NULL. Note that 12, 10, 5 and 2 have been deleted because there is a greater value on the right side.

### Modify linked list into even and odd elements

Given a Linked List of integers, write a function to modify the linked list such that all even numbers appear before all the odd numbers in the modified linked list. Also, keep the order of even and odd numbers same. Examples:
Input: 17->15->8->12->10->5->4->1->7->6->NULL
Output: 8->12->10->4->6->17->15->5->1->7->NULL

Given a fleet of 50 trucks, each with a full fuel tank and a range of 100 miles, how far can you deliver a payload? You can transfer the payload from truck to truck, and you can transfer fuel from truck to truck. Assume all the payload will fit in one truck.

### first odd number in the dictionary

Each number from 1 to 10^10 are written out in english format (eg: "two hundred eleven","one hundred forty two") and then listed down in alphabetical order as in dictionary.Which is the first odd number in the list?

### Divisible by 10

Given a stream of binary digits how can you tell if the number formed is divisible by 10.

### Count number of occurrences of a number

Given a sorted array arr[] and a number x, write a function that counts the occurrences of x in arr[]. Expected time complexity is O(Logn) Examples: Input: arr[] = {1, 1, 2, 2, 2, 2, 3,}, x = 2 Output: 4

### Find the celebrity

You are in a party which has 'n' guests. One of them being a celebrity which meets the following criteria.

1. Celebrity doesn't know anyone
2. All others except the celebrity know atleast one person including the celebrity.

You are allowed to ask any person - DO YOU KNOW X person.
How many questions you need to identify the celebrity

Write a program to print all the LEADERS in the array. An element is leader if it is greater than all the elements to its right side. And the rightmost element is always a leader. For example int the array {16, 17, 4, 3, 5, 2}, leaders are 17, 5 and 2.

### Two elements with minimum sum An Array of integers is given, both +ve and -ve. You need to find the two elements such that their sum is closest to zero. For the below array, program should print -80 and 85.

### Rotation of array by d position Write a function rotate(ar[], d, n) that rotates arr[] of size n by d elements.

Rotation of the above array by 2 will make array

### Tie a rope around the earth

A fool wants to tie a rope around the earth. So he buys a rope of 40,000 KM and ties it around the world. His neighbour, also a fool, wants to do the same only he wants the rope on sticks 1 meter above the ground.
How much more rope does he need?

### Find if number is square

Describe an alogrithm to find out if an integer is a square

### Merging two binary trees

You are given two height balanced binary search trees T and T', storing m and n elements respectively. Every element of tree T is smaller than every element of tree T'. Every node u also stores height of the subtree rooted at it. Using this extra information how can you merge the two trees in time O(log m + log n) (preserving both the height balance and the order)?

### Finding the decimal dominant in an array

You are given n real numbers in an array. A number in the array is called a decimal dominant if it occurs more than n/10 times in the array. Give an O(n) time algorithm to determine if the given array has a decimal dominant.

### Finding the first one

You are given an array of infinite length containing zeros followed by ones. How fast can you locate the the first one in the array?

### Exploring the Binary Heap

Consider a binary heap containing n numbers (the root stores the greatest number). You are given a positive integer k < n and a number x . You have to determine whether the kth largest element of the heap is greater than x or not. Your algorithm must take O(k) time.

### Petrol bunks in a circle

There are n petrol bunks arranged in circle. Each bunk is separated from the rest by a certain distance. You choose some mode of travel which needs 1litre of petrol to cover 1km distance. You can't infinitely draw any amount of petrol from each bunk as each bunk has some limited petrol only. But you know that the sum of litres of petrol in all the bunks is equal to the distance to be covered.
ie let P1, P2, ... Pn be n bunks arranged circularly. d1 is distance between p1 and p2, d2 is distance between p2 and p3. dn is distance between pn and p1.Now find out the bunk from where the travel can be started such that your mode of travel never runs out of fuel.

### set operation str1-str2 on Strings

Set Theory operation on two strings
str1= apple
str2=pie

str1-str2 = (All elements of str1 which are not in str2)

Answer in above case = al

### Merge k sorted array

Given K sorted arrays, How can you get a complete sorted array.

### Minimum distance between two nodes in a binary tree

Given a binary tree, find the minimum distance between  two given nodes given that they exist ?

### maximum contiguous subsequence Where 0 and 1's are equal

You have a array of 0's and 1's. e.g.
0001011101001010100101010101100111
Find the maximum contiguous subsequence of the above sequence so the
number of 0's and 1's in that subsequence are equal

### [Amazon]construct tree with preorder traversal

Leaves are represented with L and non-leaf with N in a tree. Each node has either 0 or 2 children. so if given preorder traversal of this tree, construct the tree.

### find unique number

You are given an array that contains integers. The integers content is such that every integer occurs 3 times in that array leaving one integer that appears only once.
Fastest way to find that single integer
eg:
Input: [2,1,4,5,1,4,2,2,4,1]

### convert spaces to %20

Given a URL, write a function that converts all the spaces to %20.

### Check if one string is rotation of other string

Given a string s1 and a string s2, write a snippet to say whether s2 is a rotation of s1 using only one call to strstr routine?
(eg given s1 = ABCD and s2 = CDAB, return true, given s1 = ABCD, and s2 = ACBD , return false)

### find numbers falling in a range in an infinite stream

You are receiving a continuous stream of numbers, at any point you will be provided a range eg: 5- 15 and the output should be the number of numbers between 5-15.

### Print a node at distance k from root

Given a root of a tree, and an integer k. Print all the nodes which are at k distance from root.
For example, in the below tree, 4, 5 & 8 are at distance 2 from root.

### Inorder successor of a node In Binary Search Tree, Inorder Successor of

### Ancestor of a node in a Binary tree

Given a Binary Tree and a value, write a function that prints all the ancestors of the key in the given binary tree.
For example, if the given tree is following Binary Tree and key is 5, then your function should print  2 and 1.
1 / \ 2 3 / \ 4 5 / 7

### [Solution]Level order traversal

void Levelorder(struct node* p)
{
stack<struct node*> s;
queue<struct node*> q;
struct node* temp;
s.push(p);
do
{
while(!s.empty())
{
temp = s.top();
cout<<temp->data<<endl;
s.pop();
if(temp->left)
q.push(temp->left);
if(temp->right)
q.push(temp->right);

}
while(!q.empty())
{
temp = q.front();
cout<<temp->data<<endl;
q.pop();
if(temp->left)
s.push(temp->left);
if(temp->right)
s.push(temp->right);
}
}while((!s.empty()) || (!q.empty()));
}

### spiral order traversal of tree Write a function to print spiral order traversal of a tree. For below tree, function should print 1, 2, 3, 4, 5, 6, 7.

### Null pointer in c++

#include<iostream>usingnamespacestd;classA{public:voidprint(){cout<<"Hello";}};intmain(){A*a=newA();A*b=NULL; a->print();b->print();}Explain the o/p and reason behind it.

### extern and sizeof

1)
#include
int main()
{
extern int a;
a=20;
printf("%d",sizeof(a));
return 0;

}
2)
#include
int main()
{
extern int a;
printf("%d",sizeof(a));
return 0;

In case 1 we will get linker error and in cae 2 we get 4 a o/p.please explain the behaviour.

### overloaded function with mismatching parameters

class  A
{       public:
void g(int i)
{       cout<<"in a";
}

};
class B:public A
{       public:
void f()
{       cout<<"in b";
}
};
int main()
{       B b;
b.f();   //vl call b::f()
b.g(4);  //vl call a::g()
}
but
class  A
{       public:
void f(int i)
{       cout<<"in a";
}
};
class B:public A
{       public:
void f()
{       cout<<"in b";
}
};
int main()
{       B b;
b.f();   //vl call b::f()
b.f(4);  //bt here errror occurs not a matching protoype...
}
So,can we overload function in inheritance(which vary in
parameters)?

### Empty class in c++

class Empty{};int main(){   Empty a, b;if(&a ==&b)cout<<"impossible: report error to compiler supplier";                   Empty* p1 =new Empty;                 Empty* p2 =new Empty;if(p1 == p2)cout<<"impossible: report error to compiler supplier";return0;}What will be the o/p and why?

### Rotation of an integer array

#includeusingnamespace std;int findRotation(int arr[],int low,int high){int mid;while(arr[low]> arr[high]){      mid = low+(high-low)/2;if(arr[mid]> arr[high])      low = mid+1;else      high = mid;}return low;}int main(){//this is the array rotated by 2 positionsint arr[]={5,6,1,2,3};cout<<"rotation of array is"<<findRotation(arr,0,4);return0;}

### getmin in stack in o(1) time

You need to design a stack which holds an integer value such that getMinimum() function should return the minimum element in the stack.
For example: consider the below example
case #1 5 --> TOP 1 4 6 2 When getMinimum() is called it should return 1, which is the minimum element in the stack. case #2 stack.pop() stack.pop() Note: Both 5 and 1 are poped out of the stack. So after this, the stack looks like, 4 --> TOP 6 2 When getMinimum() is called is should return 2 which is the minimum in the stack.Note: 1. Design it without using another stack,you can change the structure of stack node. 2. Design it using extra stack.

### Find the poisoned Bottle of wine

The King of a small country invites 1000 senators to his annual party. As gifts, each senator brings the King a bottle of wine, for a grand total of 1000 bottles of wine. Each bottle is signed by the senator who gave it.
At the end of the party, the Queen tells the King that one of the senators is trying to assassinate him, and has put deadly poison in the bottle of wine he gave as a gift. Unfortunately, the Queen doesn't know which senator is the traitor (and thus doesn't know which bottle of wine has the poison in it).
The King has 10 servants. He views them as expendable, and does not care if they live or die. He decides to use them to figure out which bottle is poisoned, which will then indicate which senator is trying to assassinate him.
His plan is to make each servant drink from zero or more of the bottles of wine. The King knows that the poison is such that if a servant drinks it, he will feel fine until noon on the next day, at which point he will insta…

### [MG]Generate unique strings

You have to write a function such that every time it is called it should generate some new unique string.There is no restriction on length of string generated but every time it should produce unique strings.
Prototype : char* getnewstring();

### [MG]Collide the robots

Two robots are placed at different points on a straight line of infinite length. When they are first placed down, they each spray out some oil to mark their starting points.
You must program each robot to ensure that the robots will eventually crash into each other. A program can consist of the following four instructions:
Go left one spaceGo right one spaceSkip the next instruction if there is oil in my current spotGo to a label[Note that a "label" is a name that refers to a line of your code. For example, you could label the third line of your program "surveying". Then, the instruction "goto surveying" would jump to line 3 and start executing from there on the next cycle.] Both robots need not have the same program. Note that you won't know ahead of time which robot is on the left and which is on the right.

### fill 2 litres of water in 5 and 4 litre mug

There are two 10 litres mug of waters.You have also one 5 litres and another 4 litres of mug.Now pour from any of the mugs and without throwing out any water fill two other mugs with exactly 2 litres of water.

### Make 120 with five zeroes

Use any mathematical operation between five zeroes to make them 120.

### 4 Switch problem

Four switches can be turned on or off. One is the light switch for the incandescent overhead light in the next room, which is initially off, but you don't know which. The other three switches do nothing. From the room with the switches in it, you can't see whether the light in the next room is turned on or off. You may flip the switches as often and as many times as you like, but once you enter the next room to check on the light, you must be able to say which switch controls the light without flipping the switches any further. (And you can't open the door without entering, either!) How can you determine which switch controls the light?