Code Forum

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

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" 

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.

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.

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.

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:          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

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

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 ?

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.

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?

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.

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.

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 )

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

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 ".

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.

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.

  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 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

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.

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.

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?

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

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

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.

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.

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

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?

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

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)?

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.

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?

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.

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 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

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

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

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

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.

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

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

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)

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.

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.

In Binary Search Tree, Inorder Successor of

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

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)           ...

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

#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.

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.

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;  ...

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?

#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 ; }

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.

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...

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();

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.

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.

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

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?

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)?  

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.

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.

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; }

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.

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 No of Set bits in Number in O(1).

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?

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.

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 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.

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..

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)

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.

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?

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?

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. 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}

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

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

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?

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.

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.

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 .

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

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.

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

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.

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.

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 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 .

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

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.

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

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

 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 stacks in a single array. Please note that you should not report stack full until all the elements are full.

How will you calculate square root of a number?