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

JAVA Questions and Answers

Let us discuss some of the important questions/topics to be prepared for JAVA technical interviews.

1. Difference btw interface and abstract class

2. Collections - Arraylists, HashMap, TreeSet, HashSet, LinkedList

3. Design patterns - Factory, Singleton, Observer, Facade

4. Function over riding and overloading difference. Run time binding.

5. How to traverse through a collection using iterators. What is the difference between using iterators or using "for each" ().

6. In a map having Key, Value pairs, how to remove all odd entries (Or how to remove all keys from this map?)

---------------------------------------

Implement a high performance cache which allows multiple readers, but single writer to keep the integrity. How will you implement it?

Lock provide two separate lock for reading and writing and hence we can make use of it.

The major advantage of lock interfaces on multi-threaded and concurrent programming is they provide two separate lock for reading and writing which enables you to write high performance data structure like ConcurrentHashMap and conditional blocking.

Read more(This site seems to be really good): http://javarevisited.blogspot.com/2011/07/java-multi-threading-interview.html#ixzz29SEjkpq4