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[].