Code Forum

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?

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

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

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

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

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?

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.

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

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.

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?

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.

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

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.

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

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

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.

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

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

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?

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

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?

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.

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 .