Posts

Showing posts from 2011

[Amazon]Data structure for Car Parking

Design a data structure which can be used efficiently for simulating car parking.It can have three different operations... 1 car_in 2 car_leave 3 Reset all

[MS]All combination of a string

Write a code to find r-combination of a String of length n. Ex: for String "abcd"  Combinations are:  ""      "a"  "b"   "ab"  "c"   "ac"   "bc"   "abc"   "d"  "ad"  "bd"    "abd"   "cd"   "acd"   "bcd"   "abcd" 

Insertion in cyclic linked list

Given a node from a cyclic linked list which has been sorted, write a function to insert a value into the list such that it remains a cyclic sorted list. The given node can be any single node in the list.

[MS]Serialize and Deserialize a string

There are  multiple api's for serializing and de-serializing strings while communicating from one process to another.Json is one of the most famous.Write your own api which will serialize a list of string and deserialize the list into individual string.

[inmobi]Handshake at the party

If there are  n  number of people invited in a party, who can shake hands with one another (where  n  > 1 ). After sometime host says that there is always a pair of people who has shake hands with the same number of people.How he came to know.

second largest number in minimum comparison

You have an array of numbers, you need to find the second largest number in the array in minimum number of comparisons.

Solve the Equation

Solve the equation:          p *e - x + q *sin( x ) + r *cos( x ) + s *tan( x ) + t * x 2 + u = 0         where 0 <= x <= 1 . p,q,r,s,t,u are variables.(where 0 <= p , r <= 20 and -20 <= q , s , t <= 0 ). For each set of input, there should be a line containing the value of x , correct upto 4 decimal places, or the string " No solution ", whichever is applicable. eg: Input 0 0 0 0 -2 1 1 0 0 0 -1 2 Output: 0.7071 No Solution

cycle length of n

Image
consider the following algorithm : if n = 1 then STOP if n is odd then else Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Given an input n , it is possible to determine the number of numbers printed (including the 1). For a given n this is called the cycle-length of n . In the example above, the cycle length of 22 is 16. For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j . Sample Input (1<n<1000000) 1 10 100 200 201 210 900 1000 Sample Output 1 10 20 100 200 125 201 210 89 900 1000 174

Exception while deleting an object

void g ( ) { throw "Exception" ; } void f ( ) { int * i = new int ( 0 ) ; g ( ) ; delete i ; } int main ( ) { f ( ) ; return 0 ; }   In the above code what can be the problem ?

[Amazon]clone a linked list with random pointer

Image
You are given a Double Link List with one pointer of each node pointing to the next node just like in a single link list. The second pointer however can point to any node in the list and not just the previous node. Now write a program in O(n) time to duplicate this list. That is, write a program which will create a copy of this list.

copy constructor

class Cents { private:     int m_nCents; public:     Cents(int nCents=0)     {         m_nCents = nCents;     }     // Copy constructor     Cents(const Cents &cSource)     {         m_nCents = cSource.m_nCents;     } }; In above c++ code  why parameter cSource (const Cents &cSource) is passed as reference?

Sizeof operator again

char * p = "Hello World" ; int a ; char b ; printf ( "%d\n" , sizeof ( p ++)); printf ( "%c\n" ,* p ); printf ( "%d" , sizeof ( a , b )); printf ( "%d" , sizeof ( b , a ));   Explain why p didn't get incremented and  what is the use of comma operator here.

[Adobe]Job scheduling problem

You are given N jobs with their start and end time mentioned.These jobs may have their timings overlapped.You have to suggest an algorithm such that maximum number of jobs can be performed in that given time interval.

[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[0] = -7, A[1] = 1, A[2] = 5, A[3] = 2, A[4] = -4, A[5] = 3, A[6]=0 3 is an equilibrium index, because: A[0] + A[1] + A[2] = A[4] + A[5] + A[6] 6 is also an equilibrium index, because sum of zero elements is zero, i.e., A[0] + A[1] + A[2] + A[3] + A[4] + A[5]=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

trucks with payloads

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

Leaders in an array

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

Image
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

Image
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 k th 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] Answer: 5

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

Image
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

Image
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> using namespace std ; class A { public : void print () { cout << "Hello" ; } }; int main () { A * a = new A (); 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" ;       return 0 ; } What will be the o/p and why?

Rotation of an integer array

#include using namespace 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 positions   int arr [ ] = { 5 , 6 , 1 , 2 , 3 } ;   cout << "rotation of array is" << findRotation ( arr, 0 , 4 ) ;   return 0 ; }

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 instan

[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 space Go right one space Skip the next instruction if there is oil in my current spot Go 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?

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?

radius of the circle

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 _    /   \     10     20  /     /  \ 50    45  35 The correct solution should print 30 , 10 , 50 , 45 , 35 , 20 .

validate an ipv4 address

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

Image
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 a 2  = b 2  + c 2 . 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 20 print 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 : static int foo = 1 ;             static int foo = 10 ; void fooTest () {               void barTest () {   static int bar = 2 ;             static int 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 7 th 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,28 We 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

Image
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

Image
A Pythagorean triplet is a set of three natural numbers, a b c , for which, a 2 + b 2 = c 2 For example, 3 2 + 4 2 = 9 + 16 = 25 = 5 2 . There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc .

sum of digits in 100!

Image
n ! means n ( n 1) ... 3 2 1 For example, 10! = 10 9 ... 3 2 1 = 3628800, and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27. Find the sum of the digits in the number 100!

Numbers are co-prime

Check whether two numbers are co-prime without finding their factors.

The typeof operator

The  typeof  operator returns the type of its argument, which can be an expression or a type. The language feature provides a way to derive the type from an expression. The alternate spelling of the keyword,  __typeof__ , is recommended. Given an expression  e ,  __typeof__(e)  can be used anywhere a type name is needed, for example in a declaration or in a cast. A  typeof  construct itself is not an expression, but the name of a type. A  typeof  construct behaves like a type name defined using  typedef , although the syntax resembles that of  sizeof . The following examples illustrate its basic syntax. For an expression  e : int e; __typeof__(e + 1) j; /* the same as declaring int j; */ e = (__typeof__(e)) f; /* the same as casting e = (int) f; */ Using a  typeof  construct is equivalent to declaring a  typedef  name. Given int T[2]; int i[2]; you can write __typeof__(i) a; /* all three constructs have the same meaning */ __typeof__(int[2]) a; __typeof__(T) a; The be

type of a variable at run time

Given a variable in c,how can you know the type of the variable at run time .If you don't have to use type_of operator .

number as square of two integers

Given an integer n decide if it is possible to represent it as a sum of two squares of integers.

Rotate by n bit positions

Write a function that rotates ( NOT shifts ) to the right by n bit positions the bits of an unsigned char x.ie no bits are lost in this process. Your answer should print out the result in binary form  Your output should be like this: x = 10100111 (binary) x rotated by 3 = 11110100 (binary)

invert function in c

Write a function invert(x,p,n) that returns x with the n bits that begin at position p inverted (i.e., 1 changed into 0 and vice versa), leaving the others unchanged.

nth prime number

Suggest an efficient algorithm to find nth prime number,where n is run time option.

#if defined in c

The special operator  defined  is used in ` #if ' and ` #elif ' expressions to test whether a certain name is defined as a macro.  defined  name  and  defined ( name )  are both expressions whose value is 1 if  name  is defined as a macro at the current point in the program, and 0 otherwise. Thus,  #if defined MACRO  is precisely equivalent to  #ifdef MACRO . defined  is useful when you wish to test more than one macro for existence at once. For example, #if defined (__vax__) || defined (__ns16000__) would succeed if either of the names  __vax__  or  __ns16000__  is defined as a macro. Conditionals written like this: #if defined BUFSIZE && BUFSIZE >= 1024 can generally be simplified to just  #if BUFSIZE >= 1024 , since if  BUFSIZE  is not defined, it will be interpreted as having the value zero. If the  defined  operator appears as a result of a macro expansion, the C standard says the behavior is undefined. GNU cpp treats it as a genuine  defined  operator an

find total subset sums to s

given an array of elements (all elements are unique ) , given a sum s find all the subsets having sum s. for ex array {5,9,1,3,4,2,6,7,11,10} sum is 10 possible subsets are {10}, {6,4}, {7,3}, {5,3,2}, {6,3,1} etc. there can be many more. also find the total number of these subsets.

Understanding endianess

Introduction To understand the concept of endianness ,you need to be familiar, at a highly abstract level, with memory. All you need to know about memory is that it's one large array. The array contains bytes. In the computer world, people use address to refer to the array locations. Endianness The attribute of a system that indicates whether integers are represented with the most significant byte stored at the lowest address (big endian) or at the highest address (little endian). Each address stores one element of the memory array. Each element is typically one byte. In some memory configurations, each address stores something besides a byte. However, those are extremely rare so, for now, let's make the broad assumption that all memory addresses store bytes. Storing bytes in memory I refer to 32 bits, which is the same as four bytes. Integers or single-precision floating point numbers are all 32-bits long. But since each memory address can store a single byte and not fo