Q) #level-order-traversal #binary-tree
 Reverse level order traversal of a binary tree

                          1
                    2          3
                4     5     6   7

should print   4 5 6 7 2 3 1

Ans) Use stack and store the results of level order traversal. While doing level order traversal make sure  we're traversing right child first and then left child so that finally popping out each elements from the stack will give the required output.

Q) Print all unique rows in a boolean matrix

Q) In an array containing only 1s and 0s, find longest consecutive sequence which contain same number of 1s and 0s
   (Replace 0s with -1s and form a new array with each element having sum till that element. Then the problem reduces to finding longest sequence having sum as zero whose solution is already discussed earlier).

Q) Given an array of integers , find 3 indexes i,j,k such that, i<j<k and a[i] < a[j] < a[k]

Ans) Let's take an example

A = {4, 1, 3, 5, 8}

In the above example, we've  {1,3,5}, {1,3,8}, ... which satisfies the condition given in the question.
So that means for each element, we've to see whether there is a smaller element to the left of that element and a bigger element to the right of that element.
That'll give us a brute force approach of O(n^2)
     for (int i=0; i<n; i++) {
          leftIndex = rightIndex = -1;
          for (int left=0; left<i; left++)  {
               if (a[left] < a[i]) {
                      leftIndex = left;
                      break;
                }
         }
         // Similarly find right index which is greater than a[i]
         if (leftIndex != -1 && rightIndex != -1) {
              printf("%d %d %d", leftIndex, i, rightIndex);
              return;
         }
    }

OK. That's fine. Now how to optimize this solution.
Instead of searching in left and right for a smaller and bigger element each time, we can store the minimum in the left and maximum in the right for each element. So we can save the operation to check whether there is a smaller element exist in left or not.

So let's take 2 new arrays, leftMin[] and rightMax[] such that leftMin[i] stores the INDEX of minimum element from 0 to i, and rightMax[i] stores index of maximum element from 'n' to i.
Then it's just a matter of checking a[i] with leftMin[i] and rightMax[i] to get the solution. It works in O(N) run time complexity and O(N) space complexity.

eg: If array is A = {4, 1, 3, 5, 8}, we form following arrays:
leftMin = { 0, 1, 1, 1, 1}  // Index of 1 in original array is 1
rightMax = {4,4,4,4,4}  // Index of 8 in original array is 4

Sample Code
==========
// Initialize 2 arrays
leftMinIndex = 0; rightMaxIndex = n-1;
for (int i=1, j=n-1; i<n; i++, j--)
{
     if (a[i] < a[leftMinIndex])
     {
         leftMinIndex = i;
     }
     leftMin[i] = leftMinIndex;

     // Initialize rightMax

     if (a[i] > a[rightMaxIndex])
     {
         rightMaxIndex = i;
     }
     rightMax[i] = rightMaxIndex;

}

// Now traverse input array again to find the output
for (int i=0; i<n; i++)
{
    if (a[i] > leftMin[i] && a[i] < rightMax[i]) {
          printf("%d,  %d,  %d", leftMin[i], i, rightMax[i]);
          return;
    }
}
printf("Triplets not found");
}

Q.1) Given an array of size 2N such that 1st N elements are odd and remaining N elements are even. Update this array such that after 1st odd number, 1st even number will come, then 2nd odd number and then 2nd even number and so on.

So if input array is { 1, 3, 5, 7, 2, 4, 6, 8}

Output array will be {1, 2, 3, 4, 5, 6, 7, 8}

Ans)

If we can use extra memory, we can easily achieve this in O(n) but problem to achieve O(n) without using extra space.

Approach #1
-------------
The new position of an element can be obtained as follows:
new index = (2*old index)%N where N is the final index(Num of elements - 1)

Sample code
arrange(int[] a, int N) {
    int count = 0, i=1, temp = 0;
    if (N >= 1) {
           temp = a[1];
    }
    while (count < (N-1)) {//To keep track of num of rearranges which is N-1 in total
         swap(temp, a[(2*i)%N]);
         i = (2*i)%N;
         count++;
    }
}

Approach #2
--------------
You can refer different approaches in the below link
http://dailyjobquestions.com/2011/10/16/divide-and-conquer/

Q.2) Now, an extension to above question.
Convert an array "a1 a2 a3.. an b1 b2 b3 .. bn c1 c2 c3 ... cn" to "a1 b1 c1 a2 b2 c2 ... an bn cn" in place.

Apporach #1
--------------
Above approach of finding final position and swapping will work good in this one also. Only difference is final position need to be calculate as i = (3*i)%N

Approach #2
--------------

Refer this link for some good questions including this one

Explanation from above link

Solution:we divide the array in four sections:[X,Y|A,B]
It is easy to see that with swaps we can modify it to the form [X,A|Y,B].
Now do recursion to solve [X|A] and [Y|B] separately,essentially using divide and conquer.[as given in comments section]

For example:
{ 1,2,3,4,5,6,7,8,a,b,c,d,e,f,g,h }
X = { 1,2,3,4 }, Y = { 5,6,7,8 }, A = { a,b,c,d }, B = {e,f,g,h}

{ 1,2,3,4,a,b,c,d,5,6,7,8,e,f,g,h }

[X|A] = {1,2,3,4,a,b,c,d }

U = { 1,2 }, V = {3,4}, W = {a,b}, Z = {c,d}
swap V and W:
[U,W|V,Z] = { 1,2,a,b,3,4,c,d }

[U|W] = { 1,2,a,b }
swap 2 and a:
{ 1,a,2,b }
=======================
Based on that solution, we can naively solve our problem as follows:
First, convert it to a1, b1, a2, b2, ..., an, bn, c1, c2, ..., cn

Next, convert the new array to the desired form a1, b1, c1, a2, b2, c2, ..., an, bn, cn by considering (a1, b1) as A1, ... (an, bn) as An

Q.1) Find Lowest Common Ancestor(LCA) of 2 nodes in a binary tree.

With top-down approach, this can become complicated and a straight forward solution can be of O(n^2)
But if we follow bottom up approach, we can solve this in O(n) run time complexity.

Node *LCA(Node *root, Node *p, Node *q) {
if (!root) return NULL;
if (root == p || root == q) return root;

Node *L = LCA(root->left, p, q);
Node *R = LCA(root->right, p, q);

if (L && R) return root; // if p and q are on both sides

//Either both are in left or right sub-trees or may not be present in the tree
return L ? L : R;
}

The above solution fails if P or Q is not present in the tree. We can solve it simply by having a wrapper function which first traverse the tree once to see whether those 2 nodes are present in the tree and then only call the above function.

Q) Given a Binary Tree where each node has one extra pointer along with left and right pointers, write a function to populate this extra pointer for all nodes with inorder successor of that node.

struct node
{
int data;
struct node *left;
struct node *right;
struct node *next;
}
Initially, all next pointers have NULL values. We should populate these next pointers so that they point to inorder successor.

Ans)
We can do reverse inorder traversal so that we'll first traverse inorder succesor of each node before traversing the node.

So following will do:
1. Traverse Right sub-tree
2. Traverse the node. Save this node for storing as inorder successor of next node
3. Traverse Left sub-tree

void inorder_succ(node *ptr)
{
static node *tmp = NULL;
if (!ptr)
     return;

inorder_succ(ptr->right);
ptr->next = tmp;
tmp = ptr;
inorder_succ(ptr->left);
}

Q) How to print a binary tree in spiral direction (Zig Zag)

Example:

 If tree is      
                                   1

                           2               3

                      4       5         6   7

you've to print     1 2 3 7 6 5 4

We can achieve this by using 2 stacks, one for storing nodes while traversing from left to right, and other one for storing nodes while traversing from right to left.

//Have 2 stacks S1 and S2.
void printZigZag(node *root)
{
   node *ptr = NULL;
   int leftToRight = 1;
  S1.push(root);
  while (!S1.isEmpty() || !S2.isEmpty())
  {
       if (leftToRight)
       {
            while (!S1.isEmpty())
            {
               ptr = S1.pop();
               printf("%d", ptr->data);

               if (ptr->right)
                    S2.push(ptr->right);

               if (ptr->left)
                    S2.push(ptr->left);
            }
       } else {
            while (!S2.isEmpty())
            {
                ptr = S2.pop();
                printf("%d", ptr->data);
                if (ptr->left)
                     S1.push(ptr->left);

                if (ptr->right)
                     S1.push(ptr->right);

            }
       }
       leftToRight = 1 - leftToRight;
 }

Code to find longest sub-array having given sum in an integer array

1. Write code to find longest contiguous sub-array having given sum in an integer array.

Example:  If array is {3, -5, 2, 3, 1, 4}, and given sum is 4:
   There are many contiguous sub arrays having sum=0  like   {3,1}.  {3,-5,2,3,1}, {4}. So output will be the longest among them being {3,-5,2,3,1}.

Ans)
  We can come up with brute force approach of O(n^2) by checking sum of each sequence for all the elements in the array. But that definitely is not efficient.

So one efficient solution in O(n):

1. Form a new array such that a[i] = a[i-1]+a[i-2]+.. for each element a[i].
2. Now if we check the new array, we can see that whichever elements have the difference of given sum, all elements between those elements will add up to that sum. So our solution would be to find such pairs whose difference is given sum in the new array and find the farthest among them. So to make it efficient, we can use hash map to store sums till now instead of storing in a new array.

So taking example above:

{3, -5, 2, 3, 1, 4}

New Array: {0,3, -2, 0, 3, 4, 8}
If given sum is 4, we can find all pairs whose difference is 4. Or in case of hash map implementation, for each element a[i], check if (a[i]+4) or (a[i]-4) is present in the hash map.

Sample Code in JAVA
(Logic is little bit modified from whatever explained above. Here I'm using a hash map to store sums and in one parse of the array itself, finding the longest sub-array)



    private int givenSum = 4;
    private int[] mArray = { 1, 3, 3, -6, 1, 2 };
    private int maxLen = 0;
    private int maxStrtIndex = -1;

   
    // Hashmap where key is sum till a particular index and value is the 1st
    // index in the mArray where this sum is met
    private HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();



    private void findLongestSubArray() {
        int sum = 0;
        for (int i = 0; i < mArray.length; i++) {
            // Add this sum to hashmap if its not there already.We need to add
            // only first time since we're interested in finding longest
            // subsequence
            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
            sum += mArray[i];
            // Check for elements with sum difference as given sum is present in
            // array and if so, get the index of such an element
            int strtIndex = -1;
            if (map.containsKey(sum - givenSum)) {
                strtIndex = map.get(sum - givenSum);
            }
            if (map.containsKey(sum + givenSum)) {
                int tmp = map.get(sum + givenSum);
                // Get the least start index value so that length will be max
                if (tmp < strtIndex) {
                    strtIndex = tmp;
                }
            }
            if (strtIndex != -1) {
                int seqLen = i + 1 - strtIndex;
                // Update max len in case this is the max sub array
                if (seqLen > maxLen) {
                    maxLen = seqLen;
                    maxStrtIndex = strtIndex;
                }
            }
        }
    }