Binary tree, find 2 leaf nodes say X and Y

Problem:
Given a binary tree, find 2 leaf nodes say X and Y such that F(X,Y) is maximum where F(X,Y) = sum of nodes in the path from root to X + sum of nodes in the path from root to Y - sum of nodes in the common path from root to first common ancestor of the Nodes X and Y
Solution:

Complexity: O(n) TC O(n) SC
Code:

combinations of n-pairs of parentheses.

Problem:

Implement an algorithm to print all valid (e.g., properly opened and closed) combinations of n-pairs of parentheses.
EXAMPLE:
input: 3 (e.g., 3 pairs of parentheses)
output: ()()(), ()(()), (())(), ((()))

Solution:
Solve recursively.

Complexity:
Code:

Permutation of Strings

Problem:
Write a method to compute all permutations of a string.


Solution:

Let’s assume a given string S represented by the letters A1, A2, A3, ... , An
To permute set S, we can select the first character, A1, permute the remainder of the string to get a new list. Then, with that new list, we can “push” A1 into each possible position.
For example, if our string is “abc”, we would do the following:
1. Let first = “a” and let remainder = “bc”
2. Let list = permute(bc) = {“bc”, “cd”}
3. Push “a” into each location of “bc” (--> “abc”, “bac”, “bca”) and “cb” (--> “acb”, “cab”, “cba”)
4. Return our new list



Complexity: O(n!)


Code:



Another approach:



With Repeated characters in the input string:

In a loop,a particular character must be swapped with current index only once,

PowerSet

Problem:
Write a method that returns all subsets of a set.
Solution:
Recursive approach:

• The set of subsets of {1} is {{}, {1}}
• For {1, 2}, take {{}, {1}}, add 2 to each subset to get {{2}, {1, 2}} and take the union with {{}, {1}} to get {{}, {1}, {2}, {1, 2}}
• Repeat till you reach n

Complexity: O(2^n)
Code:

Iterative Approach:

nth Fibonacci number

Problem:
Write a method to generate the nth Fibonacci number.
Solution:
There are three potential approaches: (1) recursive approach (2) iterative approach (3) using matrix math. We have described the recursive and iterative approach below, as you would not be expected to be able to derive the matrix-based approach in an interview. For the interested math-geeks, you may read about the (most efficient) matrix-based algorithm at http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form.
Complexity: 
Code:

Recursive Solution:


Iterative Solution:

Maximal Contiguous Subsequent Sum Problem

Problem:

Maximum Contiguous Subsequence Sum:  given (a possibly 
negative) integers A1, A2, …, AN, find (and identify the 
sequence corresponding to) the maximum value of  
∑
=
j
k i
Ak         
For the degenerate case when all of the integers are negative, 
the maximum contiguous subsequence sum is zero. 



Solution:

• Initialize start=0,end=0,max=0,S=0,tmpstart=0
• Loop over all the elements of array
•  if S > max  then assign max=S,end=currentindex,start=tmpstart
• if  S < 0 (that means we can omit all values calculated so for) then assign S=0,tmpstart=i+1
• tmpstart represents temporary start index which is used to store the start index of current subarray.
• then print max,end and start index.

Complexity: O(n)


Code:

Product of numbers in an array

Problem:

Given an integer array. 
e.g. 1,2,3,4,5 
Compute array containing elements 
120,60,40,30,24 (2*3*4*5,1*3*4*5, 1*2*4*5, 1*2*3*5, 1*2*3*4)

Solution:
              Find the product by first finding all its left part then find right part and multiply both the results to get the output.

Complexity:   O(n) TC and O(n) SC


Code:

Finding repetitions in an array (constant space)

Problem:
              You have a read-only array A[1..n] which is populated by numbers from 1..n-1, which implies atleast one repetition. However, there can be more. Find any one repeated number in linear time using constant space.          
    
Solution:
             Consider this problem as Finding a loop in a linked list.
             Since array contents are A[1..n-1] that means 'n' will not be there so we can make our starting point as 'n' which is last element in the array.
             Once we found whether loop exists or not then we can move one pointer from the beginning and one from where we found the loops exists.
             Now we can find the repeating element once the two pointer points to same value(Repeating element)


Complexity:
                  
Code:

Delete alternate nodes of a Linked List

Problem:

Given a Singly Linked List, starting from the second node delete all alternate nodes of it. For example, if the given linked list is 1->2->3->4->5 then your function should convert it to 1->3->5, and if the given linked list is 1->2->3->4 then convert it to 1->3.
Solution:

•   Have two pointers p and q

• Initially p points head and q points to link of p i.e 2nd node (if exists).
• Make the link of p to point to link of q
• free q
• move p to its link i.e next node
• move q to next node of p
• loop until p or q becomes NULL.

Complexity: O(n)
Code:

List *deletealternative(List *head)
{
    if(head==NULL)
        return NULL;
    List *p=head;
    List *q=p->link;
    
    while(p!=NULL && q!=NULL)
    {
        p->link=q->link;
        free(q);
        p=p->link;
        if(p!=NULL)
            q=p->link;
    }
    return head;
}

A program to check if a binary tree is BST or not

Problem:
 A binary search tree (BST) is a node based binary tree data structure which has the following properties.
• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.
From the above properties it naturally follows that:
• Each node (item in the tree) has a distinct key.

Solution:

• Start from root with min = -INF and max = + INF
• At each node check whether node's data is in range [min,max]
• If not it violates binary search tree,return 0. 
• you can use the below isbst() trace,

 
Complexity: worst case - when it is a bst, O(n) where n is the  number of nodes.
Code:

int isBSTUtil(Tnode *root,int min,int max)
{
    if(root==NULL)
        return 1;
    if(root->data < min || root->data >= max)
        return 0;
    return isBSTUtil(root->left,min,root->data) && isBSTUtil(root->right, root->data + 1, max);
}
 
int isBST(Tnode *root)
{
    int min=1<<((sizeof(int)*8)-1);
    int max=~min;
    //printf("min=%d max=%d",min,max);
    
    return isBSTUtil(root,min,max);
}

Cut Gold Puzzle

You've got someone working for you for seven days and a gold bar to pay them. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker? 

Solution: 

            Let us consider the gold  bar like this, 

 Lets split the chain as,

 
           Day 1: Give A.(+1)
           Day 2: Get back A, give B.(-1, +2)
           Day 3: Give A.(+1)
           Day 4:Get back A and B, give C. (-2,-1,+4)
           Day 5:Give A. (+1)
           Day 6:Get back A, give B. (-1,+2)
           Day 7:Give A.(+1)
    
               

Get Level of a node in a Binary Tree

Given a Binary Tree and a key, write a function that returns level of the key.
For example, consider the following tree. If the input key is 3, then your function should return 1. If the input key is 4, then your function should return 3. And for key which is not present in key, then your function should return 0.

Solution:
             While calling left sub tree or right sub tree increment the level by 1. When the Key is found return the current level.

Complexity:   O(n), where n is the number of nodes.

Code:

int getNodeL(Tnode *root, int key, int level) {
    

    int leftlevel = 0, rightlevel = 0;
    
    if (root == NULL)
        return 0;
    
    if (key == root->data)
        return level;
    
    leftlevel = getNodeL(root->left, key, level + 1);
    
    if (leftlevel == 0)
        rightlevel = getNodeL(root->right, key, level + 1);
    
    return leftlevel + rightlevel;
}

Print Ancestors of a given node in Binary Tree

Given a Binary Tree and a key, write a function that prints all the ancestors of the key in the given binary tree.
For example, if the given tree is following Binary Tree and key is 7, then your function should print 4, 2 and 1.

              1
            /   \
          2      3
        /  \
      4     5
     /
    7

Solution: 

Traverse the tree recursively until the key is found, 

start printing the data in the nodes as the recursive call 

returns.

Complexity: O(n), where n is the no of nodes.

Code: 

int printAncestor(Tnode *root,int key)
{
    if(root==NULL)
        return 0;
    if(key==root->data)
        return 1;
    if(printAncestor(root->left, key) ||
            printAncestor(root->right, key))
    {
        printf(" %d ",root->data);
        return 1;
    }
    return 0;
}

Print BST keys in the given range

Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Print all the keys of tree in range k1 to k2. i.e. print all x such that k1<=x<=k2 and x is a key of given BST. Print all the keys in increasing order.
For example, if k1 = 10 and k2 = 22, then your function should print 12, 20 and 22.

Solution:
              Do inorder traversal, if current nodes' data is between K1 and K2 (K1<= root->data  >= K2) Print it.

Time Complexity :   O(log n) + O(k) , where n = no of nodes and k = no of keys printed.

Code:

void printbstkeys(Tnode *root,int k1,int k2)
{
    if(root==NULL)
        return;
    printbstKey(root->left, k1, k2);
    if(root->data >=k1 && root->data <=k2)
        printf(" %d ",root->data);
    printbstKey(root->right,k1,k2);
    return;
}

To avoid unwanted traversals we can compare current node's

data with K1 for left subtree and K2 for right subtree.

void printbstkeys(Tnode *root,int k1,int k2)
{
    if(root==NULL)
        return;
    if(root->data>=k1)
        printbstKey(root->left, k1, k2);
    if(root->data >=k1 && root->data <=k2)
        printf(" %d ",root->data);
    if(root->data<k2)
        printbstKey(root->right,k1,k2);
    return;
}  

Check if a given Binary Tree is SumTree

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 

Solution:

For each node check the following,

Right child  : non-leaf

Left child   : non-leaf

  root->data==2*root->left->data + 2*root->right->data.

Right child  : leaf

Left child   : leaf 

 root->data==root->left->data + root->right->data.

Right child  : leaf

Left child   : non-leaf

 root->data==2*root->left->data + root->right->data.

Right child  : non-leaf

Left child   : leaf

 root->data==root->left->data + 2*root->right->data.

Code:

int isSumTree_reentrant(Tnode *root) {
    if (root == NULL)
        return 0;
    if (isleaf(root) == 1)
        return 1;
    int nleft = 0, nright = 0;
    if (root->left != NULL) {
        nleft = root->left->data;
        if (isleaf(root->left) == 0)
            nleft = 2 * nleft;
    }
    if (root->right != NULL) {
        nright = root->right->data;
        if (isleaf(root->right) == 0)
            nright = 2 * nright;
    }
    if (root->data != nleft + nright)
        return 0;
    int a = 1, b = 1;
    if (root->left != NULL)
        a = isSumTree_reentrant(root->left);
    if (root->right != NULL)
        b = isSumTree_reentrant(root->right);
    return a & b;
}