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

Repeated Digits

Given a number with n digits.
Find whether there are repeated digits in that number.

If n > 10, return true //there are repeated digits
if n <= 10, we can create an array of size 10 and record number of entries...this wont need many resources...

Hex Format

PRINT A NO IN HEX FORMAT

int main()
{
int num,i=0,index;
char buff[17]="0123456789ABCDEF";
printf("Enter Num: ");
scanf(" %d",&num);

printf("0x");
for(i=7;i greaterThanEqualTo 0;i--)
{
index = ((num rightShift i*4)&15);
printf("%c",buff[index]);
}
printf("\n");
}

Sorting a Stack

/****
Given a stack S, write a C program to sort the stack (in the ascending
order).

We are not allowed to make any assumptions about how the stack is implemented.
The only functions to be used are:
Push
Pop
Top
IsEmpty
IsFull
****/
void recursive(Stack s)
{
if(s.isEmpty == true)
return ;
elem temp = s.pop();
recursive(s);
recur_push(temp, s);
return;
}
recur_push(elem t, stack s)
{
if(s.isEmpty == null || s.top() > t)
{
s.push(t);
return;
}
temp1= s.pop()
recur_push(t,s);
s.push(temp1);
}

Pass code Problem

/*
Problem Description
A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may asked for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.The main input, contains fifty successful login attempts.Given that the three characters are always asked for in order, analyse the file so as to determine the shortest possible secret passcode of unknown length.

Sample Input
Assuming 2 successful attempts (NOTE: Input would have 50)123142

Sample Output
1423
*/
int INPUT_ROW_SIZE;
int INPUT_COL_SIZE;
typedef enum
{
FALSE = -1,
TRUE = 1
}BOOLEAN;
typedef enum
{
OFF = 0,
ON = 1
}STATUS;
char **inputArray;
int **relationshipMatrix;
char *passCode;
char *uniqueArray;
unsigned int uniqueArrayIndex;
unsigned int rowSize,colSize;
unsigned int passCodeIndex;
void printInputArray(void)
{
int i,j;
printf("\n");
for(i=0;i lessThan INPUT_ROW_SIZE;i++)
{
for(j=0;j lessThan INPUT_COL_SIZE;j++)
{
printf("%2c",inputArray[i][j]);
}
printf("\n");
}
}
void printUniqueArray()
{
int i =0;
printf("Unique Array:\n");
for(i=0;i lessThan uniqueArrayIndex;i++)
{
printf("%2c",uniqueArray[i]);
}
printf("\n");
}
void printRelationshipArray()
{
int i,j;
printf("RelationshipArray\n");
for(i=0;i lessThan rowSize;i++)
{
for(j=0;j lessThan colSize;j++)
{
printf("%2d",relationshipMatrix[i][j]);
}
printf("\n");
}
}

void setUniqueArray()
{
BOOLEAN foundMatch = FALSE;
int i=0,j=0,k=0;
for(i=0;i lessThan INPUT_ROW_SIZE;i++)
{
for(j=0;j lessThan INPUT_COL_SIZE;j++)
{
foundMatch = FALSE;
for(k=0;k lessThan uniqueArrayIndex;k++)
{
if(inputArray[i][j] == uniqueArray[k])
{
foundMatch = TRUE;
}
}
if(foundMatch == TRUE)
{
continue;
}
else
{
uniqueArray[uniqueArrayIndex] = inputArray[i][j];
uniqueArrayIndex++;
}
}
}
}
void setRelationshipArray()
{
int i=0,j=0,k=0;
int rowIndex,colIndex;
relationshipMatrix = (int **)malloc(uniqueArrayIndex*sizeof(int *));
for(i=0;i lessThan uniqueArrayIndex;i++)
{
relationshipMatrix[i]= (int *)malloc(uniqueArrayIndex*sizeof(int));
}
for(i=0;i lessThan uniqueArrayIndex;i++)
{
for(j=0;j lessThan uniqueArrayIndex;j++)
relationshipMatrix[i][j]= OFF;
}

for(i=0;i lessThan INPUT_ROW_SIZE;i++)
{
for(j=0;j lessThan INPUT_COL_SIZE - 1;j++)
{
/*locate inputArray[i][j] in the uniqueArray*/
for(k=0;k lessThan uniqueArrayIndex;k++)
{
if(inputArray[i][j] == uniqueArray[k])
{
break;
}
}
if(k == uniqueArrayIndex )
{
printf("Match not found in unique Array\n");
return;
}
rowIndex = k;
/*locate inputArray[i][j+1] in the uniqueArray*/
for(k=0;k lessThan uniqueArrayIndex;k++)
{
if(inputArray[i][j+1] == uniqueArray[k])
{
break;
}
}
if(k == uniqueArrayIndex )
{
printf("Match not found in unique Array\n");
return;
}
colIndex = k;
relationshipMatrix[rowIndex][colIndex] = ON;
}
}
}
BOOLEAN matrixCorrectnessCheck()
{
int i , j=0;
for(i=0;i lessThan rowSize; i++)
{
for(j=0;j lessThan colSize;j++)
{
if((i != j )&& relationshipMatrix[i][j] == ON && relationshipMatrix[j][i] == ON)
{
printf("Invalid relation between %c and %c",uniqueArray[i],uniqueArray[j]);
return FALSE;
}
}
}
return TRUE;
}
int whichColHasAllZeros()
{
int i,j=0;
int sum = 0;
if(colSize == 0 || rowSize == 0)
{
printf("Reached the end of the input with row=%d col=%d\n",rowSize,colSize);
return FALSE;
}
for(j=0;j lessThan colSize;j++)
{
sum = 0;
for(i=0;i lessThan rowSize;i++)
{
sum= sum+relationshipMatrix[i][j];
}
if(sum == 0)
{
return j;
}
}
return FALSE;
}
void exchangeRowCol(int index)
{
char temp1=0;
int temp = 0;
int i,j;
/*exhange row of relationship matrix*/
for(i=0;i lessThan colSize;i++)
{
temp = relationshipMatrix[index][i];
relationshipMatrix[index][i] = relationshipMatrix[rowSize-1][i];
relationshipMatrix[rowSize-1][i] = temp;
}
rowSize--;
/*exhange col of relationship matrix*/
for(i=0;i lessThan colSize;i++)
{
temp = relationshipMatrix[i][index];
relationshipMatrix[i][index] = relationshipMatrix[i][colSize -1];
relationshipMatrix[i][colSize -1] = temp;
}
colSize--;
/*exhange elem for uniqueArray*/
temp1 = uniqueArray[index];
uniqueArray[index] = uniqueArray[uniqueArrayIndex - 1];
uniqueArray[uniqueArrayIndex - 1] = temp1;
uniqueArrayIndex--;
}
void setPasscodeArray(void)
{
int colIndex = 0;
passCode = (char *)malloc(sizeof(char)*uniqueArrayIndex);

while(colIndex != FALSE)
{
colIndex = whichColHasAllZeros();
if(colIndex != FALSE)
{
passCode[passCodeIndex] = uniqueArray[colIndex];
passCodeIndex++;
exchangeRowCol(colIndex);
}
}

}
void printPasscodeArray(void)
{
int i=0;
printf("Passcode Array\n");
for(i=0;i lessThan passCodeIndex;i++)
{
printf("%2c",passCode[i]);
}
printf("\n");
return;
}

void makeSmallestPasscode(void)
{
int i , j=0;
BOOLEAN retVal = FALSE;

setUniqueArray();
printUniqueArray();

rowSize = uniqueArrayIndex;
colSize = uniqueArrayIndex;

setRelationshipArray();
printRelationshipArray();
retVal = matrixCorrectnessCheck();

setPasscodeArray();
printPasscodeArray();
}
main()
{
int i = 0,j=0;
printf("Enter Row size of INPUT: ");
scanf(" %d",&INPUT_ROW_SIZE);
printf("Enter Col size of INPUT:");
scanf(" %d",&INPUT_COL_SIZE);
printf("Enter Input:\n");
inputArray = (char **)malloc(INPUT_ROW_SIZE*sizeof(char*));
uniqueArray = (char *)malloc(INPUT_ROW_SIZE*INPUT_COL_SIZE*sizeof(char));
for(i=0;i lessThan INPUT_ROW_SIZE;i++)
{
inputArray[i] = (char *)malloc(INPUT_COL_SIZE*sizeof(char));
for(j=0;j lessThan INPUT_COL_SIZE;j++)
{
printf("Enterarr[%d][%d]\n",i,j);
scanf(" %c",&inputArray[i][j]);
}
}
printInputArray();
makeSmallestPasscode();
}

Probability

You are provided with a function f() which returns either 0 or 1 with probability 1/2. Using this to construct a function f1() which returns 0 with probability 1/3 and 1 with probability 2/3.


int f1(){
while( true ){
if( f()==1 ) return 1;
if( f()==1 ) return 0;
}
}

int f1()
{
while( true)
{
int x = f();
int y = f();
if(x==1) return 1;
if(y==1) return 0;
}

}

int f1()
{
int x = 2;
while(x ==2)
{
x=f() + f();
}
return x;
}

Original array

/*
You are given an array of n numbers and each element is equal to the value of numbers less than that number in right hand side of the original array we have to find the original array
for ex. if the original array is 4,1,3,2
then we would we given the array 3,0,1,0
and we have to find the original array ,it is given that the numbers in the original array is from 1 to n.
ex no 2. original array 2,3,1,4
given array 1,1,0,0
ex no. 3 original array 5,2,1,3,4
given array 4,1,0,0,0
*/
Solution1:
main()
{
int *array;
int *value;
int *input;
int *orig;
unsigned int origIndex = 0;
unsigned int size = 0;
unsigned int sizeValue = 0;
unsigned int sizeArray = 0;
int i,j,k;
printf("Enter the size of input Array: ");
scanf(" %d",&size);
input = (int *)malloc(sizeof(int)*size);
array = (int *)malloc(sizeof(int)*size);
value = (int *)malloc(sizeof(int)*size);
orig = (int *)malloc(sizeof(int)*size);
for(i=0;i lessThan size;i++)
{
printf("Enter arr[%d]=",i);
scanf(" %d",&input[i]);
array[i] = i+1;
value[i] = i;
orig[i] = 0;
}
sizeValue = size;
for(i=0;i lessThan size;i++)
{
for(j=0;j lessThan sizeValue;j++)
{
if(input[i] == value[j])
{
orig[origIndex] = array[j];
origIndex++;
/*Shift the array and its value*/
for(k=j+1;k lessThan sizeValue;k++)
{
value[k] = (value[k] == 0)? 0: (value[k]-1);
}
for(k=j;k lessThan sizeValue-1;k++)
{
array[k] = array[k+1];
value[k] = value[k+1];
}
sizeValue--;
break;
}
}
}
printf("\n");
for(i=0;i lessThan size;i++)
printf("%2d",orig[i]);
printf("\n");
}



Solution2:
Let us assume that output has n elements.
We init an array say helperArray[i] = i; for i from 1 till n
Also have an outputArr[] which is init to 0.

Now take the input array inputArr[].
Step1. Check what is inputArr[i] let it be k.
Step2. Then we ask this qn what is the number which has exactly k lesser elements than itself. For this we check the helperArray[] and find the element from there. Let that element be helperArray[j]. Now strike of this element and do the above step again. But we dont take the striked off elements into considerations.

We take a simple example
let input 4 1 0 0 0
output 0 0 0 0 0
helper 1 2 3 4 5

Iteration1: k = 4 then output[0] = 5 as number which has 4 less numbers is 5
strike of 5 in helper so after 1st iteration we have
input 4 1 0 0 0
output 5 0 0 0 0
helper 1 2 3 4

Iteration2: k = 1 then output[1] = 2 as number which has 1 less numbers is 2
strike of 2 in helper so after 1st iteration we have
input 4 1 0 0 0
output 5 2 0 0 0
helper 1 3 4

Iteration3: k = 0 then output[2] = 1 as number which has 0 less numbers is 1
strike of 2 in helper so after 1st iteration we have
input 4 1 0 0 0
output 5 2 1 0 0
helper 3 4

Iteration4: k = 0 then output[3] = 3 as number which has 0 less numbers is 3
strike of 3 in helper so after 1st iteration we have
input 4 1 0 0 0
output 5 2 1 3 0
helper 3 4

Iteration5: k = 0 then output[4] = 4 as number which has 0 less numbers is 4
strike of 4 in helper so after 1st iteration we have
input 4 1 0 0 0
output 5 2 1 3 4
helper

Next Power of 2

Given a number N, find out the nearest power of 2 which is greater than or equal to N..

int Closest(int x)
{
int higher = 1;
int orig = x;
while( x greaterThan 0 )
{
x = x rightShift 1;
higher = higher leftShift 1;
}
if(orig * 2 == higher)
return orig;
else
return higher;
}

Open Nth File

I have a program that has to output some data to
different files each having a unique filename like :

file01.dat , file02.dat, file03.dat ,.......

my question is how can you use fopen to do this job?

FILE *fopenNth(int n) /* 0 lessThanEqualTo n lessThan 100 ! */
{
char * name = "file00.dat";
name[4]+=n / 10;
name[5]+=n % 10;

return fopen (name, "w");
}