Showing posts from March, 2012

[Amazon]Two unsorted array form same BST

Given two unsorted array, check if both will create the same bst. eg: 2, 1, 4, 0 and 2, 1, 0, 4 will both form same BST.
2 / \ 1 4 / 0but,2,1,4,0 and 2,0,1,4 will not.

[AMAZON] Subtree with largest sum

Given a binary tree, every node has a int value, return the root node of subtree with the largest sum up value.

[AMAZON] Vertical sum of nodes

Given a Binary Tree, find vertical sum of the nodes that are in same vertical line. Print all sums through different vertical lines. Examples:
1 / \ 2 3 / \ / \ 4 5 6 7The tree has 5 vertical lines
Vertical-Line-1 has only one node 4 => vertical sum is 4
Vertical-Line-2: has only one node 2=> vertical sum is 2
Vertical-Line-3: has three nodes: 1,5,6 => vertical sum is 1+5+6 = 12
Vertical-Line-4: has only one node 3 => vertical sum is 3
Vertical-Line-5: has only one node 7 => vertical sum is 7
So expected output is 4, 2, 12, 3 and 7

[Amazon]Flatten a Linked-List

You are given a singly link-list such that each node of this list is also a
head of another link list of the same type. So, suggest an algorithm to flatten the
linked-list in single level link-list.

struct node {
void *data; /* could be anything */
struct node *next;
struct node *down;

Implement tail utility

How will you implement tail utility in c/c++ without using inbuilt tail command.
Note: tail -n <filename> will output the last 'n' lines of the file.

Find the Least Length Path Which Sums to S

Given a BST and a number 'N' there can be several paths from root of the bst to leaves such that sum of data of all the nodes will make number 'N'. Suggest an efficient algorithm to find out the path of least length.

[MS]Form Largest Number from given number

Write a function to make the largest number from the digits of a given number.
number: 32441
Output: 44321