Simultaneous minimum and maximum

How many comparisons are necessary to determine the minimum of a set of n elements?
n-1 comparisions.



It is not difficult to devise an algorithm that can find both the minimum and the maximum of
n elements using Θ(n) comparisons, which is asymptotically optimal. Simply find the
minimum and maximum independently, using n - 1 comparisons for each, for a total of 2n - 2
comparisons.
In fact, at most 3 ⌊n/2⌋ comparisons are sufficient to find both the minimum and the
maximum. The strategy is to maintain the minimum and maximum elements seen thus far.
Rather than processing each element of the input by comparing it against the current
minimum and maximum, at a cost of 2 comparisons per element, we process elements in
pairs. We compare pairs of elements from the input first with each other, and then we
compare the smaller to the current minimum and the larger to the current maximum, at a cost
of 3 comparisons for every 2 elements.
Setting up initial values for the current minimum and maximum depends on whether n is odd
or even. If n is odd, we set both the minimum and maximum to the value of the first element,
and then we process the rest of the elements in pairs. If n is even, we perform 1 comparison
on the first 2 elements to determine the initial values of the minimum and maximum, and then
process the rest of the elements in pairs as in the case for odd n.
Let us analyze the total number of comparisons. If n is odd, then we perform 3 ⌊n/2⌋
comparisons. If n is even, we perform 1 initial comparison followed by 3(n - 2)/2
comparisons, for a total of 3n/2 - 2. Thus, in either case, the total number of comparisons is at
most 3 ⌊n/2⌋.

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:

Young tablea

An m x n Young tableau is an m x n matrix such that the entries of each row are in sorted order
from left to right and the entries of each column are in sorted order from top to bottom. Some of the
entries of a Young tableau may be 1, which we treat as nonexistent elements. Thus a Young tableau
can be used to hold r <= mn numbers.

Program to insert and get min from m X n matrix.

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,

Robot in an NXN grid

Problem:

Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot?
FOLLOW UP
Imagine certain squares are “off limits”, such that the robot can not step on them. Design an algorithm to get all possible paths for the robot.

Solution:

• Start from (0,0)
• Robot can take right? i.e in boundary and cell is not marked as "off limits"
• Then take right
• Robot can take left? i.e in boundary and cell is not marked as "off limits"
• Then take left
• Do these steps recursively until destination is found or no path is found.
• return possible steps.

It can be derived in mathematical way as follows:

Result will be like this,

1 + (1+2) + (1+2+3) + (1+2+3+4) + ... + (1+2+3+4+..+N)
which can be written as,









Finally, it can be expressed as follows,


Complexity: O(N^2)
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:

Kth Largest from an infinite stream

Problem:
 Write an efficient program for printing k largest elements in an array. Elements in array can be in any order.
For example, if given array is [1, 23, 12, 9, 30, 2, 50] and you are asked for the largest 3 elements i.e., k = 3 then your program should print 50, 30 and 23.

Solution:

• Create a min-heap of size K.
• Fill the heap with first K elements from the stream
• Once K elements are filled Build-heap from those elements
• now ROOT will have the smallest of K largest elements of the stream.
• when the next element in the stream is available check NO > ROOT.
• If so, replace ROOT with that Number and call Min-Heapify of ROOT.
• At any point Stream_length >= K we can give the Kth Largest by Returning the ROOT of MIN-HEAP.

Complexity: O(N + log(K) ),where N is the length of Stream

Code:

void MinHeapify(int a[],int i,int n)
{
    int left=0;
    int right=0;
    int max=0;
    while(i<=n/2-1)
    {
        left=2*i+1;
        right=2*i+2;
        max=i;
        if(left<n && a[left]<a[max])
            max=left;
        if(right<n && a[right]<a[max])
            max=right;
        if(max!=i)
        {
            a[max]=a[max]^a[i];
            a[i]=a[max]^a[i];
            a[max]=a[max]^a[i];
        }
        else
            break;
        i=max;
    }
}
 
void BuildMinHeap(int a[],int n)
{
    int i=0;
    for(i=n/2-1;i>=0;i--)
        MinHeapify(a,i,n);
}
 
findKthLargest(int I[],int N,int k)
{
    int i=0;
    int a[k];
    for(i=0;i<N;i++)
    {
        if(i<k-1)
        {
            a[i]=I[i];
        }
        else if(i==k-1)
        {
            a[i]=I[i];
            BuildMinHeap(a,k);
        }
        else
        {
            if(I[i]>a[0])
            {
                a[0]=I[i];
                MinHeapify(a,0,k);
            }
        }
    }
    printf("Kth Largest Element:%d",a[0]);
}

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

Binary Search Trees

35-bst

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