Find the minimum distance between two sorted lists

Find the minimum  distance between two sorted lists where distance is the absolute difference between pair of elements

For Example:

int a[] = {2, 3, 5, 11, 18, 19, 20};
 int b[]= {15, 24, 27, 29};

Output should be 3 (18-15)

Solution:

int minDist(int a[], int m, int b[], int n){

    int i = 0,
        j = 0, 
        min = INT_MAX,
        cur;

    while(i < m && j < n) {

        cur = abs(a[i] - b[j]);

        min  = min < cur ? min : cur;

        if(a[i] < b[j])
            i++;
        else
            j++;
    }

    return min;
}

Populate next higher number in a linked list

struct node

{
    int data;
    struct node *next;
    struct node *next_larger;
}

initially next_larger of every node points to NULL.

now write a c code which set all node's next_larger pointer.

where next_largest point to the next larger then its own value and largest value node's next_larger pointer points to NULL

http://www.geeksforgeeks.org/point-to-next-higher-value-node-in-a-linked-list-with-an-arbitrary-pointer/

Pending

Generic Linked List

Implement a generic Linked List
Or
Given a structure

struct node 
{ 
void *data; 
struct node *link; 

}; 
write a function to insert elements in list.

Code:

void insert(struct node **s, void *data,unsigned int n)
{
struct node *temp,*r;
int i;
if(*s == NULL)
{
temp = malloc(sizeof(struct node));
temp->data = malloc(n);
for (i = 0; i < n; i++)
*(char *)(temp->data + i) = *(char *)(data + i);
temp->link = NULL;
*s = temp;
}
else
{
temp =*s;
while(temp->link != NULL)
temp = temp->link;
r = malloc(sizeof(struct node));
r->data = malloc(sizeof(n));
for (i = 0; i < n; i++)
*(char *)(r->data + i) = *(char *)(data + i);
r->link = NULL;
temp->link = r;
}
}

In order to display the value You need to send the type of data it is storing as a parameter.

Get middle node of a linked list

Write a C function to print the middle of a given linked list

Method:Two Pointers

Traverse linked list using two pointers. Move one pointer by one and other pointer by two. When the fast pointer reaches end slow pointer will reach middle of the linked list.

struct node* GetMiddle(struct node *head)

{

  struct node *slow_ptr = head;

  struct node *fast_ptr = head;

 

  if(head!=NULL)

  {

       while((fast_ptr->link)!=NULL &&

               (fast_ptr->link->link)!=NULL)

       {

          fast_ptr = fast_ptr->link->link;

          slow_ptr = slow_ptr->link;

       }

       return slow_ptr;

  }

}

Minimum length unsorted subarray to make a sorted array

Given an unsorted array arr[0..n-1] of size n, find the minimum length subarray arr[s..e] such that sorting this subarray makes the whole array sorted.

Examples:
1) If the input array is [10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60], your program should be able to find that the subarray lies between the indexes 3 and 8.
2) If the input array is [0, 1, 15, 25, 6, 7, 30, 40, 50], your program should be able to find that the subarray lies between the indexes 2 and 5.

http://www.geeksforgeeks.org/minimum-length-unsorted-subarray-sorting-which-makes-the-complete-array-sorted/
https://noobtogeek.wordpress.com/2014/03/25/find-the-minimum-length-unsorted-subarray-sorting-which-makes-the-complete-array-sorted/

Method :
a) Scan from left to right and find the first element which is greater than the next element. Let s be the index of such an element.
b) Scan from right to left and find the first element (first in right to left order) which is smaller than the next element (next in right to left order). Let e be the index of such an element.
c) Find the minimum and maximum values in arr[s..e]. Let minimum and maximum values be min and max.
d) Find the first element (if there is any) in arr[0..s-1] which is greater than min, change s to index of this element.
e) Find the last element (if there is any) in arr[e+1..n-1] which is smaller than max, change e to index of this element.

Pending

Pending

Reverse an array

Write both iterative and recursive methods for reversing an array

Iterative Method:

void reverseArray(int arr[], int start, int end)

{

  int i;

  int temp;

  while(start < end)

  {

    temp = arr[start];

    arr[start] = arr[end];

    arr[end] = temp;

    start++;

    end--;

  }

}  

Recursive Method

void reverseArray(int arr[], int start, int end)

{

   int temp;

   if(start >= end)

     return;

   temp = arr[start];

   arr[start] = arr[end];

   arr[end] = temp;

   reverseArray(arr, start+1, end-1);

}

GCD of a number

WHat do you mean by GCD of a number.

Useful Links:
http://en.wikipedia.org/wiki/Greatest_common_divisor

Merge Sorted arrays with empty slots

There are two sorted arrays A1 and A2. Array A1 is full where as array A2 is partially empty and number of empty slots are just enough to accommodate all elements of A1. Write a program to merge the two sorted arrays to fill the array A2. You cannot use any additional memory and expected run time is O(n).

Question 2:
Merge two sorted arrays without extra space.

Method 1:Moving To End
Concept:

Let first array be mPlusN[] and other array be N[]
1) Move m elements of mPlusN[] to end.
2) Start from nth element of mPlusN[] and 0th element of N[] and merge them
    into mPlusN[].

 For Example

  int mPlusN[9] = {2, 8, NA, NA, NA, 13, NA, 15, 20};

  int N[] = {5, 7, 9, 25};

Output: int mPlusN[9]={2,5,7,8,9,13,15,20,25}

Code:
#define NA -1
void moveToEnd(int mPlusN[], int size)
{
  int i = 0, j = size - 1;
  for (i = size-1; i >= 0; i--)
    if(mPlusN[i] != NA)
    {
      mPlusN[j] = mPlusN[i];
      j--;
    }
}

int merge(int mPlusN[], int N[], int m, int n)
{
  int i = n;
  int j = 0;
  int k = 0;
  while(k <= (m+n))
  {
    if((i < (m+n) && mPlusN[i] <= N[j]) || ( j == n))
    {
      mPlusN[k] = mPlusN[i];
      k++;
      i++;
    }
    else
    {
      mPlusN[k] = N[j];
      k++;
      j++;
    }
  }
}
Time Complexity:O(m+n)

Alternatively [ Better Solution ],
We will start with three pointers: a_end, a_tail and b_tail where;
a_end - last memory location of A
a_tail - last non-zero element of A
b_tail - last non-zero element of B

We start the merge from the end by comparing elements at a_tail and b_tail and putting the greater one at a_end.

#include<stdio.h>
#include<stdlib.h>

void mergeArrays(int* A, int* B, int a_size, int b_size)
{
    int a_end = a_size + b_size - 1;
    int a_tail = a_size - 1;
    int b_tail = b_size - 1;

    while((a_tail >= 0) && (b_tail >= 0))
    {
        if(B[b_tail] > A[a_tail])
            A[a_end--] = B[b_tail--];
        else
            A[a_end--] = A[a_tail--];
    }

    while(b_tail >=0)
        A[a_end--] = B[b_tail--];
}

int main()
{
    int A[200] = {0,};
    int B[50] = {0,};
    int i;

    for(i=80; i<230; i++)
        A[i-80] = i*2;

    for(i=0; i<50; i++)
        B[i] = i;

    mergeArrays(A, B, 150, 50);

    for(i=0; i<200; i++)
        printf("A[%d] =  %d\n", i, A[i]);
    getchar();
    return 0;
}

Method 2:Merge inplace
In this method we progressively compare the elements of 1st array (of size X Y) with the first element of the 2nd array (of size Y). Since the numbers are stored in increasing order if the number of 1st array is smaller than the 2nd array then it will come at a smaller index in the final list otherwise we exchange the two elements.
Now the element exchange may result in the 2nd array having a greater number and hence it will have to be shifted to the correct position by successively comparing in the 2nd array. This procedure does not make use of extra memory.
Finally both the arrays will be sorted and contain elements in increasing order with earlier elements in the 1st array and the larger elements in the 2nd array, then we just need to append the 2nd array to the end of 1st array.

Code:
Let a1 contain X+Y elements and a2 contain X elements. L1=X+Y L2=Y

  for(int i=0;i < l1;i++)
    {
            if(a1[i] > a2[0])
            {
                           swap(a1[i],a2[0]);
                           for(int j=1;j < l2;j++)
                           {
                                   if(a2[j-1] > a2[j])
                                      swap(a2[j-1],a2[j]);
                                   else
                                       break;
                           }
            }
    }
    int y=l1-l2;
    for(int i=0;i < l1;i++)
        a1[i]=a2[i-y];




Minimum number of steps to cover distance between 2 points

You are in an infinite 2D grid where you can move in any of the 8 directions :

 (x,y) to 
    (x+1, y), 
    (x - 1, y), 
    (x, y+1), 
    (x, y-1), 
    (x-1, y-1), 
    (x+1,y+1), 
    (x-1,y+1), 
    (x+1,y-1) 

You are given a sequence of points and the order in which you need to cover the points. Give the minimum number of steps in which you can achieve it. You start from the first point.
Example :

Input : [(0, 0), (1, 1), (1, 2)]
Output : 2

It takes 1 step to move from (0, 0) to (1, 1). It takes one more step to move from (1, 1) to (1, 2).

Solution:

class Solution {
    public:
        int coverPoints(vector<int> x, vector<int> y) {
            if (x.size() <= 1) return 0;
            assert(x.size() == y.size());
            int ans = 0;
            for (int i = 1; i < x.size(); i++) {
                ans += max(abs(x[i] - x[i-1]), abs(y[i] - y[i-1]));
            }
            return ans;
        }
};

Median in stream of integers

Given that integers are read from a data stream. Find median of elements read so for in efficient way. For simplicity assume there are no duplicates. For example, let us consider the stream 5, 15, 1, 3 …

After reading 1st element of stream - 5 -> median - 5
After reading 2nd element of stream - 5, 15 -> median - 10
After reading 3rd element of stream - 5, 15, 1 -> median - 5
After reading 4th element of stream - 5, 15, 1, 3 -> median - 4, so on...

Making it clear, when the input size is odd, we take the middle element of sorted data. If the input size is even, we pick average of middle two elements in sorted stream.

Note that output is effective median of integers read from the stream so far. Such an algorithm is called online algorithm. Any algorithm that can guarantee output of i-elements after processing i-th element, is said to be online algorithm. Let us discuss three solutions for the above problem.

http://www.programcreek.com/2015/01/leetcode-find-median-from-data-stream-java/

We will insert the received numbers into such a data structure that we’ll be able to find the median very efficiently. Let’s analyse the possible options.

Method 1:Array Based Solution:

We can insert the integers to an unsorted array, so we’ll just append the numbers to the array one by one as we receive. Insertion complexity is O(1) but finding the median will take O(N) time, if we use the Median of Medians algorithm that I described in my previous post. However, our goal is to find the median most efficiently, we don’t care that much about insertion performance. But this algorithm does the exact opposite, so unsorted array is not a feasible solution.

What about using a sorted array? We can find the position to insert the received number in O(logN) time using binary search. And at any time if we’re asked for the median we can just return the middle element if the array length is odd, or the average of middle elements if the length is even. This can be done in O(1) time, which is exactly what we’re looking for. But there’s a major drawback of using a sorted array. To keep the array sorted after inserting an element, we may need to shift the elements to the right, which will take O(N) time. So, even if finding the position to insert the number takes O(logN) time, the overall insertion complexity is O(N) due to shifting. But finding the median is still extremely efficient, constant time. However, linear time insertion is pretty inefficient and we would prefer a better performance.

Insertion Sort

If we can sort the data as it appears, we can easily locate median element. Insertion Sort is one such online algorithm that sorts the data appeared so far. At any instance of sorting, say after sorting i-th element, the first i elements of array are sorted. The insertion sort doesn’t depend on future data to sort data input till that point. In other words, insertion sort considers data sorted so far while inserting next element. This is the key part of insertion sort that makes it an online algorithm.

However, insertion sort takes O(n²) time to sort n elements. Perhaps we can use binary search oninsertion sort to find location of next element in O(log n) time. Yet, we can’t do data movement in O(log n) time. No matter how efficient the implementation is, it takes polynomial time in case of insertion sort.

Linked Lists:

Let’s try linked lists. First unsorted linked list. Insertion is O(1), we can insert either to the head or tail but we suffer from the same problem of unsorted array. Finding the median is O(N). What if we keep the linked list sorted? We can find the median in O(1) time if we keep track of the middle elements. Insertion to a particular location is also O(1) in any linked list, so it seems great thus far. But, finding the right location to insert is not O(logN) as in sorted array, it’s instead O(N) because we can’t perform binary search in a linked list even if it is sorted. So, using a sorted linked list doesn’t worth the effort, insertion is O(N) and finding median is O(1), same as the sorted array. In sorted array insertion is linear due to shifting, here it’s linear because we can’t do binary search in a linked list. This is a very fundamental data structure knowledge that we should keep at the top of our heads all the time.

Using a stack or queue wouldn’t help as well. Insertion would be O(1) but finding the median would be O(N), very inefficient.

Method 2: Augmented self balanced binary search tree (AVL, RB, etc…)

What if we use trees? Let’s use a binary search tree with additional information at each node, number of children on the left and right subtrees. We also keep the number of total nodes in the tree. Using this additional information we can find the median in O(logN) time, taking the appropriate branch in the tree based on number of children on the left and right of the current node. However, the insertion complexity is O(N) because a standard binary search tree can degenerate into a linked list if we happen to receive the numbers in sorted order.

So, let’s use a balanced binary search tree to avoid worst case behaviour of standard binary search trees. In a height balanced binary search tree (i.e. AVL tree) the balance factor is the difference between the heights of left and right subtrees. A node with balance factor 0, +1, or -1 is considered to be balanced. However, in our tree the balance factor won’t be height, it is the number of nodes in the left subtree minus the number of nodes in the right subtree. And only the nodes with balance factor of +1 or 0 are considered to be balanced. So, the number of nodes on the left subtree is either equal to or 1 more than the number of nodes on the right subtree, but not less. If we ensure this balance factor on every node in the tree, then the root of the tree is the median, if the number of elements is odd. In the even case, the median is the average of the root and its inorder successor, which is the leftmost descendent of its right subtree. So, complexity of insertion maintaining balance condition is O(logN) and find median operation is O(1) assuming we calculate the inorder successor of the root at every insertion if the number of nodes is even. Insertion and balancing is very similar to AVL trees. Instead of updating the heights, we update the number of nodes information.

Thus,

At every node of BST, maintain number of elements in the subtree rooted at that node. We can use a node as root of simple binary tree, whose left child is self balancing BST with elements less than root and right child is self balancing BST with elements greater than root. The root element always holdseffective median.

If left and right subtrees contain same number of elements, root node holds average of left and right subtree root data. Otherwise, root contains same data as the root of subtree which is having more elements. After processing an incoming element, the left and right subtrees (BST) are differed utmost by 1.

Self balancing BST is costly in managing balancing factor of BST. However, they provide sorted data which we don’t need. We need median only. The next method make use of Heaps to trace median.

Method 3:Heaps
Balanced binary search trees seem to be the most optimal solution, insertion is O(logN) and find median is O(1). Can we do better? We can achieve the same complexity with a simpler and more elegant solution. We will use 2 heaps simultaneously, a max-heap and a min-heap with 2 requirements. The first requirement is that the max-heap contains the smallest half of the numbers and min-heap contains the largest half. So, the numbers in max-heap are always less than or equal to the numbers in min-heap. Let’s call this the order requirement. The second requirement is that, the number of elements in max-heap is either equal to or 1 more than the number of elements in the min-heap. So, if we received 2N elements (even) up to now, max-heap and min-heap will both contain N elements. Otherwise, if we have received 2N+1 elements (odd), max-heap will contain N+1 and min-heap N. Let’s call this the size requirement.

The heaps are constructed considering the two requirements above. Then once we’re asked for the median, if the total number of received elements is odd, the median is the root of the max-heap. If it’s even, then the median is the average of the roots of the max-heap and min-heap. Let’s now analyse why this approach works, and how we construct the heaps.

We will have two methods, insert a new received number to the heaps and find median. The insertion procedure takes the two requirements into account, and it’s executed every time we receive a new element. We take two different approaches depending on whether the total number of elements is even or odd before insertion.

Let’s first analyze the size requirement during insertion. In both cases we insert the new element to the max-heap, but perform different actions afterwards. In the first case, if the total number of elements in the heaps is even before insertion, then there are N elements both in max-heap and min-heap because of the size requirement. After inserting the new element to the max-heap, it contains N+1 elements but this doesn’t violate the size requirement. Max-heap can contain 1 more element than min-heap. In the second case, if the number of elements is odd before insertion, then there are N+1 elements in max-heap and N in min-heap. After we insert the new element to the max-heap, it contains N+2 elements. But this violates the size constraint, max-heap can contain at most 1 more element than min-heap. So we pop an element from max-heap and push it to min-heap. The details will be described soon.

Now let’s analyse the order requirement. This requirement forces every element in the max-heap to be less than or equal to all the elements in min-heap. So the max-heap contains the smaller half of the numbers and the min-heap contains the larger half. Note that by design the root of the max-heap is the maximum of the lower half, and root of the min-heap is the minimum of the upper half. Keeping these in mind, we again take two different actions depending on whether the total number of elements is even or odd before insertion. In the even case we just inserted the new element to the max-heap. If the new element is less than all the elements in the min-heap, then the order constraint is satisfied and we’re done. We can perform this check by comparing the new element to the root of the min-heap in O(1) time since the root of the min-heap is the minimum. But if the new element is larger than the root of min-heap then we should exchange those elements to satisfy the order requirement. Note that in this case the root of the max-heap is the new element. So we pop the the root of min-heap and insert it to max-heap. Also pop the root of max-heap and insert it to min-heap. In second case, where the total number of elements before insertion is odd, we inserted the new element to max-heap, then we popped an element and pushed it to the min-heap. To satisfy the order constraint, we pop the maximum element of the max-heap, the root, and insert it to the min-heap. Insertion complexity is O(logN), which is the insertion complexity of a heap.

That is exactly how the insertion procedure works. We ensured that both size and order requirements are satisfied during insertion. Find median function works as follows. At any time we will be queried for the median element. If the total number of elements at that time is odd, then the median is the root of the max-heap. Let’s visualize this with an example. Assume that we have received 7 elements up to now, so the median is the 4th number in sorted order. Currently, max-heap contains 4 smallest elements and min-heap contains 3 largest because of the requirements described above. And since the root of the max-heap is the maximum of the smallest four elements, it’s the 4th element in sorted order, which is the median. Else if the total number of elements is even, then the median is the average of the roots of max-heap and min-heap. Let’s say we have 8 elements, so the median is the average of 4th and 5th elements in sorted order. Currently, both the max-heap and min-heap contain 4 numbers. Root of the max-heap is the maximum of the smallest numbers, which is 4th in sorted order. And root of the min-heap is the minimum of the largest numbers, which is 5th in sorted order. So, the median is the average of the roots. In both cases we can find the median in O(1) time because we only access the roots of the heaps, neither insertion nor removal is performed. Therefore, overall this solution provides O(1) find heap and O(logN) insert.

A code is worth a thousand words, here is the code of the 2-heaps solution. As you can see, it’s much less complicated than it’s described. We can use the heapq module in python, which provides an implementation of min-heap only. But we need a max-heap as well, so we can make a min-heap behave like a max-heap by multiplying the number to be inserted by -1 and then inserting. So, every time we insert or access an element from the max-heap, we multiply the value by -1 to get the original number:

class streamMedian:
    def __init__(self):
        self.minHeap, self.maxHeap = [], []
        self.N=0

    def insert(self, num):
        if self.N%2==0:
            heapq.heappush(self.maxHeap, -1*num)
            self.N+=1
            if len(self.minHeap)==0:
                return
            if -1*self.maxHeap[0]>self.minHeap[0]:
                toMin=-1*heapq.heappop(self.maxHeap)
                toMax=heapq.heappop(self.minHeap)
                heapq.heappush(self.maxHeap, -1*toMax)
                heapq.heappush(self.minHeap, toMin)
        else:
            toMin=-1*heapq.heappushpop(self.maxHeap, -1*num)
            heapq.heappush(self.minHeap, toMin)
            self.N+=1

    def getMedian(self):
        if self.N%2==0:
            return (-1*self.maxHeap[0]+self.minHeap[0])/2.0
        else:
            return -1*self.maxHeap[0]

Useful Links:

http://www.geeksforgeeks.org/archives/14873
http://www.ardendertat.com/2011/11/03/programming-interview-questions-13-median-of-integer-stream/

Example 2:
How to find the sorted median of a continuous stream of integers. let the stream is 0,1,2,3,4 the median is 2. now let -2 comes and the median for stream -2,0,1,2,3,4 still the median is 2 or it can be 1. now again -4 comes the median for the stream -4,-2,0,1,2,3,4 is 1. 

Pending

IdenticalTree(), mirrorTree(), isFoldableTree() and isSumTree()

Same Tree:

Given two binary trees, return true if they are structurally identical -- they are made of nodes with the same values arranged in the same way

http://www.geeksforgeeks.org/write-c-code-to-determine-if-two-trees-are-identical/
http://www.geeksforgeeks.org/iterative-function-check-two-trees-identical/

int sameTree(struct node* a, struct node* b) { 

int sameTree(struct tree* a, struct tree* b)
{

    if (a==NULL && b==NULL)
        return 1;
    else if (a!=NULL && b!=NULL)
   {
        return
        (
            a->data == b->data &&
           sameTree(a->left, b->left) &&
           sameTree(a->right, b->right)
        );
    }
    else return 0;
}
Time Complexity:
Complexity of the identicalTree() will be according to the tree with lesser number of nodes. Let number of nodes in two trees be m and n then complexity of sameTree() is O(m) where m < n.

Iterative solution:

If they are binary search trees then you can do any kind of traversal such as inorder, preorder etc, in case of a general tree we can do a breadth first traversal from left most to right most child of a node and if that is same then the two trees are identical.

Mirror Tree
Change a tree so that the roles of the left and right pointers are swapped at every node.
So the tree...
       4
      / \
     2   5
    / \
   1   3

 is changed to...
       4
      / \
     5   2
        / \
       3   1

void mirror(struct tree* root)

{

  if (root==NULL)

    return;

  else

  {

    struct node* temp;

    mirror(root->left);

    mirror(root->right);

    temp        = root->left;

    root->left  = root->right;

    root->right = temp;

  }

}

Time Complexity:O(n)
Auxiliary Space : If we don’t consider size of stack for function calls then O(1) otherwise O(n).

Fold-able Tree:

Given a binary tree,find whether it can be foldable or not :

A tree can be folded if left and right subtrees of the tree are structure wise mirror image of each other. An empty tree is considered as foldable.

Method 1:Without Mirroring
There are mainly two functions:
// Checks if tree can be folded or not

IsFoldable(root)
1) If tree is empty then return true
2) Else check if left and right subtrees are structure wise mirrors of
    each other. Use utility function IsFoldableUtil(root->left,
    root->right) for this.

// Checks if n1 and n2 are mirror of each other.

IsFoldableUtil(n1, n2)
1) If both trees are empty then return true.
2) If one of them is empty and other is not then return false.
3) Return true if following conditions are met
   a) n1->left is mirror of n2->right
   b) n1->right is mirror of n2->left




Code:

bool IsFoldable(struct node *root)

{

     if (root == NULL)

     {  return true;  }

     return IsFoldableUtil(root->left, root->right);

}

bool IsFoldableUtil(struct node *n1, struct node *n2)

{

    if (n1 == NULL && n2 == NULL)

    {  return true;  }

    if (n1 == NULL || n2 == NULL)

    {  return false; }

    return IsFoldableUtil(n1->left, n2->right) &&

           IsFoldableUtil(n1->right, n2->left);

}

Method 2:Mirroring Tree

1) If tree is empty, then return true.
2) Convert the left subtree to its mirror image
    mirror(root->left);
3) Check if the structure of left subtree and right subtree is same
   and store the result.
    res = isStructSame(root->left, root->right); /*isStructSame()
        recursively compares structures of two subtrees and returns
        true if structures are same */
4) Revert the changes made in step (2) to get the original tree.
    mirror(root->left);
5) Return result res stored in step 2.

Code:

bool isFoldable(struct node *root)

{

  bool res;

  if(root == NULL)

    return true;

  mirror(root->left);

  res = isStructSame(root->left, root->right);

  mirror(root->left);

  return res;

}

bool isStructSame(struct node *a, struct node *b)

{

  if (a == NULL && b == NULL)

  {  return true; }

  if ( a != NULL && b != NULL &&

       isStructSame(a->left, b->left) &&

       isStructSame(a->right, b->right)

     )

  {  return true; }

  return false;

}

void mirror(struct node* node)

{

  if (node==NULL)

    return;

  else

  {

    struct node* temp;

    mirror(node->left);

    mirror(node->right);

    temp        = node->left;

    node->left  = node->right;

    node->right = temp;

  }

}

Time complexity: O(n)

Sum Tree:
http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-sumtree/
http://www.geeksforgeeks.org/convert-a-given-tree-to-sum-tree/
http://www.geeksforgeeks.org/check-for-children-sum-property-in-a-binary-tree/
http://www.geeksforgeeks.org/convert-an-arbitrary-binary-tree-to-a-tree-that-holds-children-sum-property/
http://www.geeksforgeeks.org/transform-bst-sum-tree/

Double Tree:
For each node in a binary search tree, create a new duplicate node, and insert the duplicate as the left child of the original node. The resulting tree should still be a binary search tree.
So the tree...
    2
   / \
  1   3

 is changed to...
       2
      / \
     2   3
    /   /
   1   3
  /
 1
Concept:
Recursively convert the tree to double tree in postorder fashion. For each node, first convert the left subtree of the node, then right subtree, finally create a duplicate node of the node and fix the left child of the node and left child of left child.
Code:

void doubleTree(struct node* node)

{

  struct node* oldLeft;

  if (node==NULL) return;

  doubleTree(node->left);

  doubleTree(node->right);

  oldLeft = node->left;

  node->left = newNode(node->data);

  node->left->left = oldLeft;

}
Time Complexity: O(n) where n is the number of nodes in the tree.

Matrix Chain Multiplication-DP

Describe a fast way to multiply n matrices using DP

Useful Links:
http://en.wikibooks.org/wiki/Algorithms/Dynamic_Programming

Average Salary

Five coworkers want to know what the average of all their salaries is, but refuse to reveal ANY information about their own salaries to their coworkers. How can they calculate the average?

Islanders with dotted forheads

There is an island with 100 women. 50 of the women have red dots on their foreheads, and the other 50 women have blue dots on their foreheads.

If a woman ever learns the color of the dot on her forehead, she must permanently leave the island in the middle of that night.

One day, an oracle appears and says "at least one woman has a blue dot on her forehead." The woman all know that the oracle speaks the truth.

All the woman are perfect logicians (and know that the others are pefect logicians too). What happens next?

Cards in the Dark

You are standing in a pitch-dark room. A friend walks up and hands you a normal deck of 52 cards. He tells you that 13 of the 52 cards are face-up, the rest are face-down. These face-up cards are distributed randomly throughout the deck.

Your task is to split up the deck into two piles, using all the cards, such that each pile has the same number of face-up cards. The room is pitch-dark, so you can't see the deck as you do this.

How can you accomplish this seemingly impossible task?

Arithmetic Puzzles

1.Using only and all the numbers 3, 3, 7, 7, along with the arithmetic operations +,-,*, and /, can you come up with a calculation that gives the number 24? No decimal points allowed.

2.Using 5,5,5,5,5 can you make 37 along with any arithmetic operation.

Useful Links:
http://www.counton.org/explorer/puzzle/?archive=y

Brothers and sisters

You and a friend are standing in front of two houses. In each house lives a family with two children.

"The family on the left has a boy who loves history, but their other child prefers math," your friend tells you.

"The family on the right has a 7-year old boy, and they just had a new baby," he explains.

"Does either family have a girl?" you ask.

"I'm not sure," your friend says. "But pick the family that you think is more likely to have a girl. If they do have a girl, I'll give you $100."

Which family should you pick, or does it not matter?

Poison in the wine

The King of a small country invites 1000 senators to his annual party. As gifts, each senator brings the King a bottle of wine, for a grand total of 1000 bottles of wine. Each bottle is signed by the senator who gave it.

At the end of the party, the Queen tells the King that one of the senators is trying to assassinate him, and has put deadly poison in the bottle of wine he gave as a gift. Unfortunately, the Queen doesn't know which senator is the traitor (and thus doesn't know which bottle of wine has the poison in it).

The King has 10 servants. He views them as expendable, and does not care if they live or die. He decides to use them to figure out which bottle is poisoned, which will then indicate which senator is trying to assassinate him.

His plan is to make each servant drink from zero or more of the bottles of wine. The King knows that the poison is such that if a servant drinks it, he will feel fine until noon on the next day, at which point he will instantly drop dead.

The King must know for sure who the traitor is by noon on the day after the party, or else the traitor will try to find another way to assassinate him. This essentially means that he has one shot to make his servants drink the wine in order to figure out which is the poison wine.

Note that the King can make any of the servants drink from any of the wine bottles. He does not need to make all of the servants drink wine if he doesn't want to. Any servant who drinks from the poisoned bottle will die the next day at noon.

How can the King figure out for sure who the traitor is by noon on the following day?

Robots on a line

Two robots are placed at different points on a straight line of infinite length. When they are first placed down, they each spray out some oil to mark their starting points.                 

You must program each robot to ensure that the robots will eventually crash into each other. A program can consist of the following four instructions:

• Go left one space
• Go right one space
• Skip the next instruction if there is oil in my current spot
• Go to a label

[Note that a "label" is a name that refers to a line of your code. For example, you could label the third line of your program "surveying". Then, the instruction "goto surveying" would jump to line 3 and start executing from there on the next cycle.]

A robot will carry out one instruction per second. Both robots need not have the same program. Note that you won't know ahead of time which robot is on the left and which is on the right.

Dropping Eggs from a building

You stand before a 100-story building with two eggs. Using only these two eggs, you must figure out the highest floor from which you can drop an egg such that the egg won't break when it hits the ground (we'll call this the "highest safe floor"). Every floor is equally likely to be the highest safe floor, including the top floor, and it's also just as likely that the egg will break from every floor. You can assume that if you drop an egg and it doesn't break, its shell is just as strong as it was before you dropped it.

If you want to minimize the expected number of drops you have to perform, what strategy should you use for picking which floors to drop the eggs from? You should write a program to solve this problem.

Adding upto 15

How can you place the numbers 1 through 9 in a 3x3 grid such that every row, column, and the two diagonals all add up to 15?

Solution:

It first seems logical to put the 5 in the middle square becuase it is the median and mean of the numbers from 1 to 9 (and also the average of any 3 numbers adding up to 15).

The next thing to do is place the 1 since it's the smallest and will thus be likely to quickly constrain what we can do afterward. We can try to place the 1 in either a side square or a corner square, but once we place it, it forces us to place the 9 on the opposite side. At this point, we just play around with the remaining numbers to see if we can work out a solution 

9 Dots, 4 Lines

Look at the 9 dots in this image. Can you draw 4 straight lines, without picking up your pen, that go through all 9 dots?


Solution:

Knight's Tour

The Knight's Tour is a famous chess problem, in which a knight starts on the top-left square of an ordinary chessboard and then makes 63 moves, landing on every square of the chessboard exactly once (except for the starting square).

Can you complete the Knight's Tour? For a further challenge, can you find a "closed" solution, meaning that the knight can make a 64th move to land back on the starting square (thus making the solution circular)?

Solution:

This pictures shows a non-cyclical solution. The strategy is to essentially cover the border (outer 3 rows/columns) first, and then cover the inner part of the board

Programs on input/output

1.Write a program to count number of 1]characters,2]lines & words in a given sentence[may be taken from standard input]?Also count the number of digits, white spaces and others in an input
2.Write a program to count blanks, tabs, and newlines.
3.Write a program to copy its input to its output, replacing each string of one or more blanks by a single blank.
4.Write a program to copy its input to its output, replacing each tab by \t, each backspace by \b, and each backslash by \\. This makes tabs and backspaces visible in an unambiguous way.
5.How would you test the word count program? What kinds of input are most likely to uncover bugs if there are any?
6.Write a program that prints its input one word per line.
7.Write a program to print a histogram of the lengths of words in its input. It is easy to draw the histogram with the bars horizontal; a vertical orientation is more challenging.
8.Write a program to print a histogram of the frequencies of different characters in its input.
9.Write a program to print all input lines that are longer than 80 characters.
10.Write a program to remove trailing blanks and tabs from each line of input, and to delete entirely blank lines.
11.Write a function reverse(s) that reverses the character string s. Use it to write a program that reverses its input a line at a time.
12.Write a program detab that replaces tabs in the input with the proper number of blanks to space to the next tab stop. Assume a fixed set of tab stops, say every n columns. Should n be a variable or a symbolic parameter?
13.Write a program entab that replaces strings of blanks by the minimum number of tabs and blanks to achieve the same spacing. Use the same tab stops as for detab. When either a tab or a single blank would suffice to reach a tab stop, which should be given preference?
14.Write a program to ``fold'' long input lines into two or more shorter lines after the last non-blank character that occurs before the n-th column of input. Make sure your program does something intelligent with very long lines, and if there are no blanks or tabs before the specified column.
15.Write a program to remove all comments from a C program. Don't forget to handle quoted strings and character constants properly. C comments don't nest.
16.Write a program to check a C program for rudimentary syntax errors like unmatched parentheses, brackets and braces. Don't forget about quotes, both single and double, escape sequences, and comments. (This program is hard if you do it in full generality.)