Hi There

This is the first non algo post from my side.
If there are any good question which you think should be here kindly put a comment to this post along with your solution. We all can learn in this process.

Maximum Contiguous Subarray Product

An Array of N Elements are given which contains both +ve and -ve elements..
Find the Contiguous Subarray which contains the maximum Product.
P.S Neglect the Overflow and assume only integers are given as input.


Divide the array in groups with delimiters as zero. Now analyze each subgroup for number of nonnegative numbers.
If it is even then product of all numbers is the max of that subgroup otherwise
we have to divide the array in the following manner:
Let there be n+1 negative numbers where n +1 is odd,(o1,o2,o3....on) we have to include either {o1.....on } or {o2.....on+1} in the product and all the other positive numbers in between them.

Now using the above logic we get the max of that sub group. We iterate over all other subsets to determine the maximum among them.

Array Difference

Given an array of size n.find 2 numbers from array whose difference is least.

Solution:

Sort the list and substract consecutive numbers to get the smallest difference.

Time : O(nlogn)

Max of two integers

Max of two integers without using any conditional operators.
-b)

Solution 1:
===========
max = (a + b + absolute(a - b))/2

If a > b then max = (a + b + a - b)/2 = 2*a/2 = a
otherwise a < b then max = (a + b + b - a)/2 = 2*b/2 = b


Solution 2:
===========
max = b*(((a-b)& 0x8000)>>32) + a*(((b-a)& 0x8000)>>32)

Matrix Sorted Search Problem

Given a Matrix of size n*n and an element E to search in the Matrix. Each row and each column of the Matrix is sorted. We need to find an efficient algorithm to search this matrix.

Solution:

Take the last element of the first row and go either down or left using the following logic:

1. If the search element E is greater than the current element go down one step. i.e change the row to the next row.

2. If the search element E is less than the current element then go one step to the left. i.e change the col = col - 1.

Do the above operation till u find the element E or you have reached the end of the Matrix. End of the Matrix means we cannot move either to left or down.

Runtime of the algorithm would be around O(n).

Same Depth nodes

Problem is to find print all the nodes at the same levels of a binary tree.Inputs given are root pointer and the pointer to the node (let it be A)whose level elements need to be printed.

Solution:
Find the depth of the node A.
Then do a depth wise traversal of the tree by tracking the level u are at currently.
Now when u get a node of equal depth as A then print it and do a back traversal from there as other nodes from the current node will result in a higher depth. Thus we can find all the nodes at the current level.

Depth can be found in the following ways
1. If parent pointers are there at each node then finding the depth is easy.
2. Otherwise search for the node in a depth first manner and then compute the node depth.

Pairwise Sum

If pairwise sums of 'n' numbers are given in non-decreasing order identify the individual numbers. If the sum is corrupted print -1
Example:
i/p:
4
4 5 7 10 12 13

o/p:
1 3 4 9

Here's the solution courtsey TopCoder.com

We will build A up from smallest element to largest. Suppose A and B are integer lists such that B gives the pairwise sums for A, where A[0] < A[1] < A[2] < ... and B[0] <= B[1] <= B[2] <= ... . Given B, we wish to find A. Suppose that we already know A[0]. Then, since P[0] is the smallest element in B, it can only arise as A[0] + A[1]. Similarly, P[1] must equal A[0] + A[2]. Therefore, if we know A[0], we can compute A[1] and A[2].

After that, however, this pattern breaks down. B[2] could either be A[0] + A[3] or A[1] + A[2] and without prior knowledge, we cannot know which one it is.

If we know A[0], we can compute A[1] and A[2] as described above, and then remove A[1] + A[2] from B. The next smallest element is then guaranteed to be A[0] + A[3], which allows us to find A[3].

Similarly, if we know A[0], A[1], A[2], and A[3], we can remove A{i}+A[j], 0 <= i < j <= 3, from B. The next smallest element of B will be A[0]+A[4], which allows us to compute A[4]. Repeating in this way, we can find all of A without ever backtracking.

Thus, once we know A[0], we can compute the rest of A. For this problem, we can now simply try every possibility for A[0]. We are given A contains only distinct non-negative integers, and A[1] > A[0], so A[0] must be an integer between 0 and B[0]/2 - 1 inclusive.

So whatever is the maximum value of B[0], we will have to try B[0]/2 possibilities for A[0].

Max Sum Sub Matrix

Given a integer matrix of size m*n. We need to find a sub matrix with the largest sum.

Note:
Negative and Positive numbers are also present.

Solution 1:
List all the Sub Matrices and find the sum of each matrix and then find the maximum sum.

Solution 2:
We construct an output array from the input array in the following manner:
inputArr[m][n] be the input array.
And let us make another array outputArr[m][n] with all fields set to zero by default.
Each element of the array say outputArr[i][j] will store the sum of elements from inputArr[0][0] till inputArr[i][j].

So determine outputArr[i][j] =
inputArr[i][j] + outputArr[i-1][j] + outputArr[i][j-1] - outputArr[i-1][j-1]

Now to find the matrix sum of a matrix starting at i1,j1 till i2,j2 is
sum = outputArr[i2][j2]- outputArr[i1][j2] - outputArr[i2][j1] + outputArr[i1-1][j1-1]

Now we can run an algorithm similar to the first solution only difference is that finding the sum is easier now.

For each sub matrix find the sum and then compare with the maximum sum found till now. Then output the result in the end.

Finding occurence count

Given a Integer array, we have to print the occurence count for each Integer. What will be the optimal solution.

best solution is to build a binary search tree...if while searching u come across a NULL ...insert that node there....if while searching u find that element increase the count...Then print each element in the tree by traversing it.

First Non Repeating Character

Find the first non-repeating character in a string:("ABCA" -> B )

Solution:

Let the given input be of n characters.(let it be inputArray[])
First have an array of 256 characters which will store the repeat count of each character (let it be countArray[]).
Now scan through the input and update the increment count of that character in the above countArray[].
After the above exercise is done scan through the inputArray[]. For each character in the array check if the count in the countArray[] is 1. Break here and print the output as the current character in inputArray[].

Max Heap + Binary Search Tree

A rooted binary tree with keys in its nodes has the binary search tree property (BST property) if, for every node, the keys in its left subtree are smaller than its own key, and the keys in its right subtree are larger than its own key. It has the heap property if, for every node, the keys of its children are all smaller than its own key.
You are given a set of n binary tree nodes that each contain an integer i and an integer j. No two i values are equal and no two j values are equal. We must assemble the nodes into a single binary tree where the i values obey the BST property and the j values obey the heap property. If you pay attention only to the second key in each node, the tree looks like a heap, and if you pay attention only to the first key in each node, it looks like a binary search tree.Describe a recursive algorithm for assembling such a tree

Solution:
Lets assume that the tree node has two keys K1 and K2.
K1 satisfies the BST property
K2 satisfies the Max Heap Property.

Our problem is to build a binary tree which satisfies both the properties.
For a maximal heap the root node must be the maximum.
So we find the node which has the K2 max. And make it as the root node.
Among the remaining nodes, The nodes to the left of the tree will be those whose K1 value is less than that of the Root nodes K1. And rest will be on the right side of the root. Now again repeat the procedure for finding the next left node of root and right node of root using the same logic above.

Measure 4 Ltr using 8 5 3 ltr cans

Question:
You have three cans of capacity 8, 5, 3 ltrs. 8 ltr can is filled with 8 ltrs of water, 5 and 3 ltr cans are empty. How do u measure 4 ltrs without throwing away water and without adding any.

Solution:
8 5 3 Cans
==================
8 0 0 Initial State
3 5 0
3 2 3
6 2 0
6 0 2
1 5 2
1 4 3