Code Forum

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

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. struct node {    int data;    struct node* left;    struct node* right;    struct node* 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.

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.

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

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 .

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 5   should be changed to 20(4-2+12+6) / \ 4(8-4) 12(7+5) / \ / \ 0 0 0 0

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

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 a i , and the bottom contains number b i , then when the player is playing the card, he gets a i points and also gets the opportunity to play additional b i 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?

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.

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.

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.

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(n 2 ) 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?

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

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

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

You are given a function  printKDistanceNodes   which 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

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}

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?

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

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.