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

Row with Maximum 0s

/***
There is a 2D nxn array of 0's and 1's. Each and every row is sorted.
Now you have to report the row with max no. of zeros in O(n) time.
***/
void rowWithMaxNumberOfZeros(int **arr,int r,int c)
{
int i=0,j=0;
int optRow=0,optCol=c-1;
int found = 0;
for(j=0;j lessThan c;j++)
{
if(arr[0][j] == ONE)
{
optCol = j-1;
found = 1;
break;
}
}
if(found == 0 && j ==c)
{
optCol=c-1;
}
i++;

while(i lessThan r && (optCol+1) lessThan c)
{
if(arr[i][optCol+1] == ZERO )
{
found = 0;
for(j=optCol+1;j lessThan c;j++)
{
if(arr[i][j] == ONE)
{
found = 1;
optCol = j-1;
optRow = i;
break;
}
}
if(found == 0 && j ==c)
{
optCol=c-1;
optRow = i;
}
}
i++;
}
printf("Row containg max number of zeros is %d till this column %d\n",optRow,optCol);
}

Longest Palindrome

Write a program which finds the longest palindrome in a given string of characters.
/******
Assumption1.
===========
So if it were of even length then the centre would be i and i+1 for example
KaaK
0123
so centers are 1,2
but for a odd length palindrome the centers are one and the same as in
KapaK
01234
so centers are 2,2

Assumption2:
============
If two strings have the same center and smaller one is not a palindrome then bigger can't be a palindrome

for example:abcddeba
index willb:01234567
since str[3,4] is a palindrome then [2,5] may be a palindrome
but since str[2,5] is not a palindrome [1,6] can't become palindrome.

Logic:
======
Here i take every index in the array as the center of the palindrome.
Now first loop searches for odd lenght palindromes in the string.
Taking the first 0,0 as the centers we try to expand our palindrome till we
encounter the boundaries or a mismatch. In such a way we can eliminate all
the strings with the same base which are not palindromes.

******/

void longestPalindrome(char *input)
{
int len;
int i=0,j=0,k=0,l=0;
int lower=0,upper=0;
len = strlen(input);

/*Odd length Palindromes*/
while(i lessThan len && j lessThan len)
{
k=i;
l=j;
while(( k greaterThan =0 && l lessThan len) && (input[k] == input[l]))
{
if((upper - lower) lessThan = (l-k))
{
lower=k;
upper=l;
}
k--;
l++;
}
i++;
j++;
}

/*Even length Palindromes*/
i = 0;
j = 1;
while(i lessThan len && j lessThan len)
{
k=i;
l=j;
while(( k greaterThan =0 && l lessThan len) && (input[k] == input[l]))
{
if((upper - lower) lessThan = (l-k))
{
lower=k;
upper=l;
}
k--;
l++;
}
i++;
j++;
}

for(i=lower;i lessThan =upper;i++)
{
printf("%c",input[i]);
}
printf("\n");
}

How many possible Brackets?

/******
Given a number n, print all possible combinations of n pairs of braces that are balanced
I/P:1
O/P:
()

I/P:2
(())
()()

I/P:3
O/P:
((()))
(()())
(())()
()(())
()()()

I/P:4
O/P:
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()

******/
int lbCount;
int rbCount;
void printLeftBrace(int index);
void printRightBrace(int index);
void printLeftBrace(int index)
{
int i = 0;
int lbLoc ,rbLoc ;
lbCount--;
temp[index] = ')';
if( lbCount == 0 && rbCount == 0)
{
printf("%s\n",temp);
return;
}
for(i=0;i lessThan 2;i++)
{
if(i==0)
{
if(rbCount greaterThan 0)
{
lbLoc = lbCount;
rbLoc = rbCount;
printRightBrace(index+1);
lbCount = lbLoc;
rbCount = rbLoc;

}
}
else
{
if(rbCount lessThan lbCount)
{
lbLoc = lbCount;
rbLoc = rbCount;
printLeftBrace(index+1);
lbCount = lbLoc;
rbCount = rbLoc;
}
}
}
}
void printRightBrace(int index)
{
int i = 0;
int lbLoc ,rbLoc ;
if(rbCount greaterThan 0)
{
temp[index] = '(';
rbCount--;
}
for(i=0;i lessThan 2;i++)
{
if(i==0)
{
if(rbCount greaterThan 0)
{
lbLoc = lbCount;
rbLoc = rbCount;
printRightBrace(index+1);
lbCount = lbLoc;
rbCount = rbLoc;
}
}
else
{
lbLoc = lbCount;
rbLoc = rbCount;
printLeftBrace(index+1);
lbCount = lbLoc;
rbCount = rbLoc;
}
}
}
main()
{
lbCount = 0;
rbCount = 0;

printf("Enter the Number of Braces: ");
scanf(" %d",&rbCount);
lbCount = rbCount;
temp = (char *) malloc((rbCount+lbCount+1)*sizeof(char));
memset(temp,0,sizeof(temp));
printRightBrace(0);
}

N Sorted Arrays

Given n streams of sorted data (each of which can be infinite in length). Give an efficient way to merge them to give a single sorted stream..

Best method would be to store all the streams in a heap. With each node in the heap having the head value of the stream. So when we pop out one element from the heap. We push back the stream with the head removed and pushing the next element as the head. This way we can merge the streams quickly.

Majority element

/********
A majority element in an array A, of size N is an element that appears more than N/2 times (and hence there is atmost
one such element)

Write a function which takes an array and emits the majority element (if it exists), otherwise prints NONE as follows:

I/P : 3 3 4 2 4 4 2 4 4
O/P : 4

I/P : 3 3 4 2 4 4 2 4
O/P : NONE

Answer:

As we sweep through the sequence, we maintain a pair consisting of a current candidate and a counter. Initially, the current candidate is unknown and the counter is 0. When we move the pointer forward over an element e:
If the counter is 0, we set the current candidate to e and we set the counter to 1.
If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate. When we are done, the current candidate is the majority element, if there is a majority.
If you must confirm that the chosen element is indeed the majority element, you must take one more linear pass through the data to do it.
******/
int find_majority(int *a, int n)
{
int count = 1;
currentIndex = 0;
for (i = 1 ; i lessThan n; i ++)
{
if (a[i] == a[currentIndex])
count++;
else
count--;
if (count == 0)
{
currentIndex = i;
count = 1;
}

}
return a[currentIndex];
}