Sunday, August 26, 2012

Given an array all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array.

Example 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).

Given an expression remove the unnecessary brackets in it with out creating an ambiguity in its execution. input output

 ex1: (a+(b)+c) a+b+c ex2: (a*b)+c a*b+c

Given Preorder can you make BST from it then print the sorted output from BST


#include<iostream>
#include<stdlib.h>
using namespace std;
 
typedef struct tree{
int val;
struct tree *left;
struct tree *right;
}tree;
 
tree* insert(tree* root, int val)
{
if(root == NULL)
{
tree* temp = (tree*) malloc(sizeof(tree));
temp->val = val;
temp->left = NULL;
temp->right = NULL;
return temp;
}
 
tree* node = (tree*) malloc(sizeof(tree));
if(root->val < val)
root->right = insert(root->right, val);
else
root->left = insert(root->left, val);
return root;
}
 
tree* buildBST(int preOrder[], int length)
{
tree* root;
if(length != 0)
{
root = (tree*) malloc(sizeof(tree));
root->val = preOrder[0];
root->left = NULL;
root->right = NULL;
}
else
return NULL;
 
for(int i = 1; i < length; i++)
{
root = insert(root, preOrder[i]);
}
 
return root;
}
 
void printInOrder(tree* BST)
{
if(BST == NULL) return;
printInOrder(BST->left);
cout << BST->val << " ";
printInOrder(BST->right);
}
 
void printPreOrder(tree* BST)
{
if(BST == NULL) return;
cout << BST->val << " ";
printPreOrder(BST->left);
printPreOrder(BST->right);
}
 
int main(void)
{
int preOrder[] = {10, 5, 3, 4, 6, 11, 13, 12};
tree* BST = buildBST(preOrder, sizeof(preOrder) / sizeof(int));
printInOrder(BST);
cout << endl;
printPreOrder(BST);
cout << endl;
}



 Time Complexity O(N^2) in Case of Skewed Tree
 Space Complexity O(1)
Run Here http://ideone.com/KVDrB

Given a array of intervals, check if that have any gape efficiently


u will be given pairs.. u need to see whether they have any gaps..
u can think pairs are like intervals..
ex1: max no:20 pairs: 11-15, 0-5, 18-20, 14-19, 6-13 
 
the above has no gaps..because 0-5,6-13,11-15,18-20 have all numbers from 0 (min) to 20(max)
 
ex2: 11-15, 0-5, 18-20, 14-16, 6-13 this have gap as the intervals miss a number from 0 to 20 i.e.,17

Find Maximum length palindrome in a from a ascii text file


Given an array of length n, print all sub arrays of length r


Saturday, August 25, 2012

Given n find all possible representations of n in Fibonacci binary number system.

Consider the Fibonacci Seies 1, 2, 3, 5, 8, 13.....
Now consider a Fibonacci binary number system of numbers where numbers are considered as sum of Fibonacci numbers
Ex. 10 can be written as 8+2=>10010 and 17 can be written as 13+3+1 => 100101. This representation is similar to binary representation. Instead of powers of 2, Fibonacci numbers are used.
The question was, given n find all possible representations of n in Fibonacci binary number system.
as 10=8+2=>10010
also 10=5+3+2=>1110 

#include <stdio.h>
#include <string.h>
 
void printSol(int* sol, int size)
{
        int i;
 
        for( i = 0; i <= size; ++i )
                printf("%d",sol[i]);
        printf("\n");
}
 
void binaryFiboUtil(int* sol, int depth, int num,int* arr, int size)
{
        if(depth < 0 || num == 0){
                if(num == 0)
                   printSol(sol,size);
               return ;
        }
        else
        {
                if(arr[depth] <= num)
                {
                        sol[depth] = 1;
                        binaryFiboUtil(sol,depth-1,num-arr[depth],arr,size);
                        //sol[depth] = 0;
                }
                else
                {
                  sol[depth]=0;
                  binaryFiboUtil(sol,depth-1,num,arr,size);
                }
        }
}
 
void binaryFibo(int num)
{
        if(num <= 0 )
                return;
 
        int a, b, c, arr[100], top = -1;
 
        a = 0;
        b = 1;
        c = a+b;
 
        while( c <= num )
        {
                arr[++top] = c;
                a = b;
                b = c;
                c = a+b;
        }
        int sol[top+1];
 
        memset(sol,0,sizeof(sol));
        binaryFiboUtil(sol,top,num,arr,top);
}
 
int main()
{
        int num;
 
        scanf("%d", &num);
 
        binaryFibo(num);
 
        return 0;
} 
 
Thanks to a reader named "coder" for posting the code.
 

Wednesday, August 22, 2012

Fill next with node pointers which represent Inorder Successor of every node in BSTin BST

You are given a function getInorderSuccessor which takes a BST (Binary Search Tree) as it's parameter. Every node has an extra pointer "next" , which is intialized to null, fill next with node pointers which represent Inorder Successor.
In a binary tree, inorder successor of a node is the next node in inorder traversal of the binary tree. Inorder successor is NULL for the last node in inorder traversal.

PS: In BST, inorder successor of an input node can also be defined as the node with the smallest key greater than the key of input node. So, it is sometimes important to find next node in sorted order.

Given a root of a tree, and an integer k. Print all the nodes which are at k distance from root.


you have to print all possible combination of a given length let's say 'k' of a string in lexicographic order.


for Example:- input String=az k=2;
output
aa
az
za
zz..