## Posts

Showing posts from February, 2012

### Convert a Binary Tree To hold Children Sum Property

Given an arbitrary binary tree, convert it to a binary tree that holds Children Sum Property. You can only increment data values in any node.
For example, the below tree doesn’t hold the children sum property, convert it to a tree that holds the property.
50 / \ / \ 7 2 / \ /\ / \ / \ 3 5 1 30

### Connect nodes of a binery tree at same Level

Write a function to connect all the adjacent nodes at the same level in a binary tree. Structure of the given Binary Tree node is like following.structnode { intdata; structnode* left; structnode* right; structnode* nextRight; } Initially, all the nextRight pointers point to garbage values. Your function should set these pointers to point next right for each node. You can use only constant extra space.
Consider this example for your solution:
1 / \ 2 3 / \ / \ 4 5 6 7 / \ / \ 8 9 10 11 nextRight for node with value 9 will be 10 and not NULL.

### perfect cubes

It is possible, to find integers greater than 1 that satisfy the "perfect cube" equation a^3 = b^3 + c^3 + d^3 (e.g. a quick calculation will show that the equation 12^3 = 6^3 + 8^3 + 10^3 is indeed true). This problem requires that you write a program to find all sets of numbers {a,b,c,d} which satisfy this equation for a <= N.

### Euclidean Distance

You are given a multiset of points on the plane with integer coordinates. Find the maximum distance between two points from this multiset.

### Pair of Numbers

Let's assume that we have a pair of numbers (a, b). We can get a new pair (a + b, b) or (a, a + b) from the given pair in a single step.
Let the initial pair of numbers be (1,1). Your task is to find number k, that is, the least number of steps needed to transform (1,1) into the pair where at least one number equals n.

### Convert to Sum Tree

Given a Binary Tree where each node has positive and negative values. Convert this to a tree where each node contains the sum of the left and right sub trees in the original tree. The values of leaf nodes are changed to 0.
For example, the following tree

10 / \ -2 6 / \ / \ 8 -4 7 5should be changed to

20(4-2+12+6) / \ 4(8-4) 12(7+5) / \ / \ 0 0 0 0

### [AMAZON]All combination of balanced parenthesis

Write a function to generate all possible n pairs of balanced parentheses.
For example, if n=1
{}
for n=2
{}{}
{{}}

### Playing Card Game

A player has several cards. Each card contains two non-negative integers inscribed, one at the top of the card and one at the bottom. At the beginning of the round the player chooses one of his cards to play it. If the top of the card contains number ai, and the bottom contains number bi, then when the player is playing the card, he gets ai points and also gets the opportunity to play additional bi cards. After the playing the card is discarded.The round ends when the counter reaches zero or the player runs out of cards.
We want him to get as many points as possible. Can you determine the maximum number of points he can score provided that you know his cards?

### [AMAZON]Find two nodes which sums equal to 'K'

Given a binary search tree of n nodes, find two nodes whose sum is equal to a given number k in O(n) time and constant space.

### Number of distinct decoding

Two people want to send coded messages to each other. One possible encoding scheme is to simply replace each letter with its numerical value in the alphabet and then string all the digits together without spaces. Determine the number of possible ways to decode a message encoded this way.
eg: the message encoded as 25114 can be decoded as BEAAD, BEAN, YAD, YAN, ‘YKD’ and ‘BEKD’, so there are 6 different decoding of given string value.

### [Inmobi]Maximum sum of increasing sequence

Variation of LIS:
Given an integer array, how will you find out the increasing subsequence which gives the largest sum. For example,
50,23,1,67,30 in this subsequence a few possible increasing subsequences are
1)    23,30
2)    23,67
2)    50,67
3)    1,67
4)    1,30
5)    67
6)    30

but 50, 67 gives the maximum sum. How to find it
Note: In the above scenario however if we have 128 at index 0 then it will have the max sum although it is not forming longest LIS.

### [AMAZON] Stock purchase problem

Suppose we are given an array of n integers where each index represent stock prices on a single day. We want to find a pair (buyDay, sellDay), with buyDay ≤ sellDay, such that if we bought the stock on buyDay and sold it on sellDay, we would maximize our profit.
Clearly there is an O(n2) solution to the algorithm by trying out all possible (buyDay, sellDay) pairs and taking the best out of all of them. However, is there a better algorithm, perhaps one that runs in O(n) time?

### [AMAZON]Longest palindrome substring

Given a string S, find the longest palindromic substring in S.

### [DP]Coin Counting Problem

Given 1, 2, 5, and 10 paise coins, how many ways can you make a rupee?
Hint: Order doesn't matter.

### Getminimum steps

On a positive integer, you can perform any one of the following 3 operations.
1.) Subtract 1 from it. ( n = n - 1 )  2.) If its divisible by 2, divide by 2. ( if n % 2 == 0 , then n = n / 2)
3.) If its divisible by 3, divide by 3. ( if n % 3 == 0 , then n = n / 3  ). Now given a positive integer n, find the minimum number of steps that takes n to 1

### [AMAZON]printKDistanceNodes You are given a function printKDistanceNodeswhich takes in a root node of a binary tree, a start node and an integer K.  Complete the function to print the value of all the nodes (one-per-line) which are a K distance from the given start node in sorted order. Distance can be upwards or downwards.
Example:

Sample Input:

Root node: 5
Given start node: 8
Distance (K): 1
Sample Output:
5
6
9

### [AMAZON]Arrange Array elements

In given array of elements like [a1,a2,a3,..an,b1,b2,b3,..bn,c1,c2,c3,...cn] Write a program to merge them like[a1,b1,c1,a2,b2,c2,...an,bn,cn].

PS: Do it without using extra memory
Sample Testcases:
Input #00:
{1,2,3,4,5,6,7,8,9,10,11,12}
Output #00:
{1,5,9,2,6,10,3,7,11,4,8,12}
Explanation:
Here as you can notice, the array is of the form
{a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4}

### Sum of 15

Two players are playing a game and take alternating turns. Initially, there are 9 cards with numbers from 1 to 9 on the table. On each turn, a player takes one of the cards. The first player to have exactly 3 cards with numbers that sum to 15 wins. If no one can after all cards are distributed, then it's a draw.

Can you tell who wins and how to play this game without using a computer to analyze all possible positions?

### [c++]vector insert method

Suppose I'd like to copy an array of ints into the front of a vector. (The
data might be in an array instead of a vector in the first place, because the data came from a legacy C API. )
What is the performance wise difference in the two method:

int data[numValues];
vector<int>::iterator insertLoc(v.begin());
for (int i = 0; i < numValues; ++i) {
insertLoc = v.insert(insertLoc, data[i]);
}

### Find the two repeating elements in a given array

You are given an array of n+2 elements. All elements of the array are in range 1 to n. And all elements occur once except two numbers which occur twice. Find the two repeating numbers.
For example, array = {4, 2, 4, 5, 2, 3, 1} and n = 5
The above array has n + 2 = 7 elements with all elements occurring once except 2 and 4 which occur twice. So the output should be 4 2.