Problem:
There are 2 link lists merging at some node. Find the node, where these 2 lists merge.

Solution:
             

1. Point both the heads with temp1 and temp2 pointers.
2. Move both pointers one step at a time.
3. Repeat step 2 until temp1 or temp2 reaches the last node.
4. Make a pointer P1 to point the head of longest list and pointer P2 to point the head of another list.
5. Move the temp pointer of longest list and another pointer from its list head one position at a time until temp reaches the last node.
6. Now we have two pointers with equal numbers of nodes.
7. move two pointers one at a time until they both meet.
8. return the merge node.

Complexity: O(m+n)
Code:

Reverse a Linked List recursively

A Problem with Fenwick Tree

Problem:
You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create
another array ar_low[] such that ar_low[i] = number of elements lower
than or equal to ar[i] in ar[i+1:n-1].
So the output of above should be {0,2,1,2,2,1,0}
Time complexity : O(nlogn)
use of extra space allowed.

Solution:
              Use Binary Indexed Tree.

Complexity: O(n log n)
Code:

Binary Indexed Trees

Refer here for complete tutorial : http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees

C 3D Array

To do so, we start by allocating space for all array elements in one call to malloc.

int *allElements = malloc(x * y * z * sizeof(int));

Next, we create the arrays of pointers, and point to the contiguous elements we’ve already allocated.

int ***array3D = malloc(x * sizeof(int **));

for(i = 0; i < x; i++)

{

    array3D[i] = malloc(y * sizeof(int *));

    for(j = 0; j < y; j++)

    {

        array3D[i][j] = allElements + (i * y * z) + (j * z);

    }

}

Endianness

Temple Puzzle

Problem:

Mr. X has gone to Temple A, B.C. These temples are having magic pond in each. It will double the thing, whatever you have in your hand, when you come out of the pond. (e.g. if you have Rs.1/- in your hand, and when you come of pond, you will have Rs.2/- in your hand)


Mr. X is having certain number of flowers. The terms and conditions of this quiz is that you have to surrender equal number of flowers to each temple and when you come out of Temple C, no flower should be in your hand.


Please find out how many flowers Mr. X was having with him when he entered into Temple A and how much flowers has he surrendered at each temple.



Solution:

     8X-7Y  =  0
     8X        =  7Y
           X    =  7/8Y     
    =>  X    =   7  when Y = 8 

Which can be generalized as X = 2^n - 1 and Y = 2^n          

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.

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:

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:

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:

JAVA - synchronized

synchronized methods acquire lock on objects.


Here "my" and "yours" are two different instances, so "my" threads willl acquire lock on "my" instance and "yours" threads will acquire lock on "yours" instance.

Example is shown below:

JAVA - join() Method

When non-static join() method is invoked it will make currently running thread to wait until the invoking thread finished its execution.

Here th[i].join() will make main thread to wait until it is finished. So,

main--->

             th[0].join()---> 

                                  main-->

                                             th[1].join()---> 

                                                                  main-->

                                                                             th[2].join()--->   

                                                                                                   main---->

Thus join() method makes to Join the current thread after 

it goes to dead state.

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