Multiple of 8

using bit manipulation, find next multiple of 8 for a given number

int nextMultipleOfEight(int num)
{
i = i rightShift 3;
i++;
i=i leftShift 3;
printf("%d\n",i);
}

Maximum Sub Array Sum

/***
Input Array has both +ve and -ve ints.
Find the sub array with maximum sum.

Solution:
Run Time : O(n)
Assumes that whenever thisSum is less than 0 then we can get a better sum from the index following the current one.
***/
int maxSubSum3( int [ ] a )
{
int maxSum = 0;
int thisSum = 0;
int i=0;
int j=0;

while (j lessThan a.length)
{
if(a[j] lessThan 0)
{
thisSum = 0;
j++;
continue;
}
thisSum =thisSum + a[ j ];

if( thisSum greaterThan maxSum )
{
maxSum = thisSum;
seqStart = i;
seqEnd = j;
}
else if( thisSum lessThan 0 )
{
i = j + 1;
thisSum = 0;
}
j=j+1;
}

return maxSum;
}

Other Solution

Reverse Stack

/****
Reverse a stack with recursion...u have only pop, push, size,isEmpty functions
****/
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.push(t);
return;
}
temp1= s.pop()
recur_push(t,s);
s.push(temp1);
}

Merge with a twist!!

/***
Given a array of size M+N in which first M numbers are sorted and last N spaces are vacant. Another array of size N which is sorted. Now merge these two arrays without using any extra space so that the array of M+N size is sorted. Optimize it to hav complexity M+N.
***/

#include
#define M 10
#define N 5
void printArr(int *arr1,int *arr2)
{
int i,j;
printf("\n");
printf("Arr1 Elements\n");
for(i=0;i lessThan M+N;i++)
{
printf("%3d",arr1[i]);
}
printf("\n");
printf("Arr2 Elements\n");
for(i=0;i lessThan N;i++)
{
printf("%3d",arr2[i]);
}
printf("\n");
}
main()
{
int arr1[M+N] = {0};
int arr2[N] = {0};
int i = 0, j =0,temp=0,k=0;
printf("Arr1 Elements\n");

for(i=0;i lessThan M;i++)
{
printf("arr1[%d] = ",i);
scanf(" %d",&arr1[i+N]);
}
printf("Arr2 Elements\n");
for(i=0;i lessThan N;i++)
{
printf("arr2[%d] = ",i);
scanf(" %d",&arr2[i]);
}
printArr(arr1,arr2);
j = 0;
i = N;
k = 0;
while(i lessThan M+N && j lessThan N)
{
if(arr1[i] lessThan arr2[j])
{
arr1[k]=arr1[i];
k++;
i++;
}
else if(arr1[i] greaterThan arr2[j])
{
arr1[k] = arr2[j];
k++;
j++;
}
else
{
arr1[k] = arr2[j];
k++;
j++;
arr1[k] = arr1[i];
k++;
i++;
}
}
while(i lessThan M+N && k lessThan M+N)
{
arr1[k]=arr1[i];
k++;
i++;
}
while(j lessThan N && k lessThan M+N)
{
arr1[k]=arr2[j];
k++;
j++;
}
printArr(arr1,arr2);
}

Little / Big Endian

/***
A program to find if a machine is big or little endian.
***/
#include
main()
{
int i = 1;
char *p= (char *)&i;

if(*p == 1)
printf("Little");
else
printf("Big");
printf(" Endian\n");
}

Rotate Array

/***
Rotate the array about an index k.
So if the input was 0 1 2 3 4 5 6
rotating the array about index = 2the o/p would be
3 4 5 6 0 1 2
***/
First, reverse the order of the elements in the whole list:
{xn, xn-1, ..., x1}

Then reverse the sublist containing the last k-1 elements, and then also the sublist containing the other n-k+1 elements:

{xk, xk+1, ..., xn, x1, ..., xk-1}

To illustrate rotating a list of n=5 elements so that k=4 is first:

1 2 3 4 5
reverse list:
5 4 3 2 1
break into sublists and reverse:
5 4 3 2 1
4 5 1 2 3

Each reversal is clearly O(n) and the swapping requires some small constant amount of storage.

Array flip

Write a function that will flip the n*n array about its non major diagonal.
Example 3 5 7 makes the non major diagonal in the following manner.
1 2 3 --- 9 6 3
4 5 6 --- 8 5 2
7 8 9 --- 7 4 1

#define N 10
main()
{
int arr[N][N] = {0};
int i=0,j=0,k=1,temp=0;
printf("\n");
initializeArray(arr,N);
for(i = 0; i lessThan N ; i++)
{
for(j = 0 ; j lessThan N-i-1; j++)
{
temp = arr[i][j];
arr[i][j] = arr[N-1-j][N-1-i];
arr[N-1-j][N-1-i] = temp;
}
}
printf("\n");
printArray(arr,N);
}

Tree sum

/***
Given a tree and a sum, write an algorithm to return TRUE if there is a path from the root node down to a leaf such that adding all values of the nodes along the path equals the given sum.
***/

BOOLEAN rootToLeafSumEqualsInput(NODE *root,int sum)
{
if(root.left == NULL && root.right == NULL)
{
if(root.value == sum)
{
printf root.value;
return TRUE;
}
else
return FALSE;
}
if(root.left != NULL)
{
if(rootToLeafSumEqualsInput(root.left,(sum - root.value)) == TRUE)
{
printf root.value;
return TRUE;
}
}
if(root.right != NULL)
{
if(rootToLeafSumEqualsInput(root.left,(sum - root.value)) == TRUE)
{
printf root.value;
return TRUE;
}
}
}

Arrays Extra Element

/***
Given two arrays A and B. Array 'A' contains all the elements of 'B' but
one more element extra.
Find out the extra element......
Restrictions: Dont use any relational ops ( > or > or == etc....), array
elements are not in order ...,
***/
main()
{
int A[]={1,4,2,4,5};
int B[]={1,4,2,4};
int sa=5,sb=4;
int sumA=0;
int sumB=0;
int i=0;

for(i=0;i lessThan sa;i++)
{
sumA+=A[i];
}
for(i=0;i lessThan sb;i++)
{
sumB+=B[i];
}

printf("%d\n",sumA-sumB);
}

0s to Left 1s to the Right

Given an array with random 0,1 ,sort 0's to left and 1's to right???
in time complexity O(n)..

main()
{
int i = 0;
int arr[]={1,1,0,1,0,1,0,0,1};
int size = 9;
int oneP=0;
int zeroP=0;
while(oneP lessThan size && zeroP lessThan size)
{
if(arr[zeroP] == 0 )
{
zeroP++;
oneP++;
continue;
}
if(arr[oneP] == 0)
{
arr[zeroP] = 0;
arr[oneP] = 1;
zeroP++;
}
oneP++;
}
for(i=0;i lessThan size;i++)
printf("arr[%d]= %d\n",i,arr[i]);
}

ZigZag

Problem Statement
A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence.

For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

import java.util.Random;
class ZigZag
{
static void print(int[] arr)
{
System.out.println();
for(int i=0;i lessThan arr.length;i++)
{
System.out.print(" "+arr[i]);
}
System.out.println();
}
public static void main(String[] args)
{

int[] arr ={ 70, 55, 13, 2, 99, 2, 80, 80, 80, 80, 100, 19, 7, 5, 5, 5,1000,32,32};
int n=arr.length;
int[] numb = new int[n];
int sign=0;
int i=0;
Random r=new Random();
numb[0]=1;
numb[1]=1;
if(arr[0]!=arr[1])
numb[1]=2;
print(arr);
for(i=2;i lessThan n;i++)
{
sign=arr[i-1]-arr[i-2];
print(numb);
if(sign==0 || arr[i]==arr[i-1])
{
numb[i]=numb[i-1];
continue;
}
if(sign lessThan 0 && arr[i]-arr[i-1] greaterThan 0)
{
numb[i]=numb[i-1]+1;
continue;
}
if(sign greaterThan 0 && arr[i]-arr[i-1] lessThan 0)
{
numb[i]=numb[i-1]+1;
continue;
}
if(sign lessThan 0 && arr[i]-arr[i-1] greaterThan 0)
{
numb[i]=numb[i-1];
continue;
}
if(sign lessThan 0 && arr[i]-arr[i-1] lessThan 0)
{
numb[i]=numb[i-1];
continue;
}

}
print(numb);
}
}

Group Characters Together in Order

/**
Input will be a string. We need to o/p a string with the order of characters same as the input but with same characters grouped together.
I/P: abcdacde
O/P: aabccdde

I/P: kapilrajadurga
O/P: kaaaapilrrjdug

I/P: 1232
O/P: 1223
**/
I have found out two methods:
Method 1:
/**
Running Time: O(n*n*n)
Here we take one char see if there are any characters which equal it. If any two characters are equal we shift the array by 1 to the right(from the character till the first match) . and keep the matching element in that blank.
For example:
I/P: abcdead
Iteration 1: a bcded
Iteration 2: aabcded
Iteration 3: aabcded
Iteration 4: aabcded
Iteration 5: aabcd e
Iteration 6: aabcdde
Here Blank places mean that we shifted the array from that point till the first match from that point.

**/
main(int argc,char **argv)
{
int i = 0,j=0,k = 0;
int length = 0;
char *inputPtr;
char input[MAX_ALPHABET_LENGTH]={0};
int temp[MAX_ALPHABET_LENGTH]={0};
if(argc lessThan 2)
{
printf("Enter the input String as command line argument\n");
return;
}
strcpy(input,argv[1]);

inputPtr = input;
length = strlen(argv[1]);
printf("Method 1:\n");
printf("I/P: %s\n",inputPtr);

for(i=0;i lessThan length;i++)
{
for(j = i+1;j lessThan length; j++)
{
if(inputPtr[i] == inputPtr[j])
{
for(k = j; k greaterThan i; k-- )
{
inputPtr[k] = inputPtr[k-1];
}
inputPtr[i+1]=inputPtr[i];
}
}
}
printf("O/P: %s\n",inputPtr);

}
Method 2:
/**
Running Time: O(n) with O(1) constant space.
Here i am making the following assumption
1. The character set is limited to 256 characters.

Here we deploy hashing for this:
We have a bucket for 256 characters.
Step 1: We init the bucket to 0.
Step 2: We traverse through the input String and increment the corresponding bucket.
Step 3: We then traverse through the whole input array and check the order of the characters. So once we have printed the input character bucket[character] times then we make the bucket entry for that character to 0.

Though the last for loop seems to be O(n*n) actually it is O(n) only.
**/
main(int argc,char **argv)
{
int i = 0,j=0,k = 0;
int length = 0;
char *inputPtr;
char input[MAX_ALPHABET_LENGTH]={0};
int temp[MAX_ALPHABET_LENGTH]={0};
if(argc < 2)
{
printf("Enter the input String as command line argument\n");
return;
}

printf("Method 2:\n");
strcpy(input,argv[1]);
inputPtr = input;
length = strlen(argv[1]);
printf("I/P: %s %d\n",inputPtr,length);
for(i = 0; i lessThan length; i++)
{
temp[inputPtr[i]]++;
}
printf("O/P: ");
for( i = 0; i lessThan length ; i++ )
{
for(k=0; k lessThan temp[inputPtr[i]]; k++)
{
printf("%c",inputPtr[i]);
}
temp[inputPtr[i]]=0;
}
printf("\n");
}

First repeating element

/*
How will u find the first repeating letter in a string?... Remember solution should be efficient in both time and space...

Example:
abcdabccccaab
Reapeating letters are: a, b, c
take an auxilary array of 256 ...O(n) complixity in time also
*/

#define MAX 500
int main()
{
char arr[MAX],aux[256];
int i,j;
for(i=0;i lessThan 256;i++)
aux=0;
scanf("%s",arr);

for(i=0;i lessThan j;i++)
if(aux[arr[i]])
{
printf("The repeting character is %c",arr);
break;
}
else
aux[arr[ i]]++;
return ;
}

Index Same As Element

Suppose that you are given a sorted sequence of distinct integers{a1,a2,...an} . Give an O(log(n)) algorithm to determine whether there exists an index i such at ai = i . For example, in arr[]={-1,0,3,6,7} since arr[3] == 3 the solution should be three.

Solution
We do a binary search for the array. Compare the index of the curr element(ind) and the current elements(arr[ind]). If the ind is less than arr[ind] then match can be found only in the lower half(since all elements are distict). Similarly if ind is greater than arr[ind] then match can be found in the upper half. If Equal then match is found.

pseudo code

int matchIndToElem(int arr[], int size)
{
low = 0;
upper = size - 1;
mid = (low+upper)/2;
while(low < upper)
{
if( mid == arr[mid])
{
printf("Match Found at index %d",mid);
return mid;
}
else if( mid < arr[mid])
{
low = low;
upper = mid;
mid = (upper + low)/2;
}
else
{
low = mid;
upper = upper;
mid = (upper +low)/2;
}
}
if(arr[low] == low)
{
printf("Match Found at index %d",low);
return low;
}
return -1;
}

Median

/*********************************************
X[1...n] and Y[1....n] are 2 sorted arrays....
give O(log n) algo to find median of the array
formed by merging the 2 arrays
*********************************************/

/***
Take the middle of Arr X call it midX and middle element of
Arr Y call it midY..
***/
int findMedian(Array arrX[])
{
lowX=0
lowY=0
highX=arrX.size - 1
highY=arrY.size - 1

midX = (highX - lowX)/2
midY = (highY - lowY)/2
while(lowX != highX || lowY !=highY)
{
if(midX < midY)
{
/**
median lies in between the upperHalf of arrX and lower half of arrY
lowX=midX
highY=midY
midX = midX + (highX - lowX)/2;
midY = (highY - lowY)/2;
**/
}
else if (midX > midY)
{
/**
median lies in between the upperHalf of arrX and lower half of arrY
lowY =midY
highX=midX
midY = midY + (highY - lowY)/2;
midX = (highX - lowX)/2;
**/
}
else
{
printf("median %d",arrX[midX]);
return arrX[midX];
}
}
return arrX[midX];/*or return arrY[midY]*/
}

Rotate one to get Another

/****************************************
Given a string s1 and a string s2,
write a snippet to say whether s2 is a
rotation of s1?

Solution:
concatenate s1 with s1 and do a search
for s2 in that. If found then s2 is a
rotation of s1.
****************************************/
int isRotation(char *s1,char *s2)
{
strcat(s1,s1);
if((temp = strstr(s1,s2))!= NULL)
{
if(strcmp(s1,temp)!= 0)
{
printf("s2 is a rotation of s1 and vice versa\n");
return 1;
}
}
return 0;
}

Distance[2]

/***
You are given 2 pointers to two nodes (p1, p2) in a binary tree. Devise an algorithm to find the distance between p1 and p2 (i.e. the length of the shortest path between them).
***/

Trace back to the top of the tree from each node, recording the left and right subtrees as 0 and 1 in a binary string. Compare the binary strings. The sum of the lengths of the two minus twice the length of the common parts at the end gives the distance.

Distance[1]

/***
You are given 2 pointers to two nodes (p1, p2) in a binary search tree. Devise an algorithm to find the distance between p1 and p2 (i.e. the length of the shortest path between them).
***/
take ln as the lowest value node, and hn as the high value node,cn has the current node

Node cn=ln;
int c=0;
while (cn != root && cn.parent < hn)
cn = cn.parent
c++;
endwhile
while (cn != hn)
cn = cn > hn ? cn.left : cn.right;
c++;
endwhile

Nth Element from end SLL

/*
How to find nth element from end of a single linked list.
*/
list_ptr *p1, *p2;

p1 = p2 = list.head

for( i = 0; i < n; ++i )
p2 = p2->next;

while( p2 )
{
p1 = p1->next;
p2 = p2->next;
}

C or C++

Write a program that will print "C" if compiled as an (ANSI) C program, and "C++" if compiled as a C++ program.

$cat a.c
#include

int
main ()
{
char ch[][5]={"C++","C"};
printf ("%s \n",ch[( 2 //*
/ 2) -1] // */ 1) -1]
);
return 0;
}

$cc a.c ; ./a.out ????
$cc -ansi a.c ; ./a.out ????
Contributed by -KC

Permutations!!

/**********************************************************************************
A program to find out all possible Permutations.
If I/P is 3 then o/p is
Permute[ 0] 1 2 3
Permute[ 1] 1 3 2
Permute[ 2] 2 1 3
Permute[ 3] 2 3 1
Permute[ 4] 3 2 1
Permute[ 5] 3 1 2
**********************************************************************************/

void permute(int i)
{
int j=0,k=0,temp=0;
if(i == size)
{
return;
}
for(j = i; j < size; j++)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
permute(i+1);
if(i == size - 1)
{
printf("Permute[%3d]",count++);
for(k = 0;k< size;k++)
printf(" %3d ",arr[k]);
printf("\n");
}
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
main()
{
int i = 0;
size = 3;
count = 0;
arr = (int *)malloc(size*sizeof(int));
for(i=0;i arr[i] = i+1;
permute(0);
}

8 Queens Problem

/**********************************************************************************
A program to generate all possible positions of keeping maximum queens on a n*n chess board with neither of them attacking each other.
***********************************************************************************/
void generateCases(int row)
{
int col = 0;
BOOLEAN retVal = FALSE;
if(row greaterThanEqualTo SIZE)
{
return;
}
for(col = 0 ; col lessThan SIZE; col++)
{
/**************************************
This function will check if the new
queen(row,col) can be placed in the
board. Returns true if we can.
***************************************/
retVal = validatePosition(row,col,QUEEN);
if(retVal == TRUE)
{
piecePositions[size_g].row = row;
piecePositions[size_g].col = col;
size_g++;
if(row == SIZE-1)
{
printBoard();/*Prints the board*/
count_g++;
}
generateCases(row+1);
size_g--;
}
}
}

main()
{
int r = 0;
INIT_GLOBALS();
size_g=0;
memset(piecePositions,0,sizeof(piecePositions));
generateCases(0);
}

Map of India

/*how this works? I dont know..*/
#include
main()
{
int a,b,c;
for (c=b=10;a=
"VAMSI PERI,TFy!QJu ROo TNn(ROo)SLq SLq ULo+ UHs UJq TNn*RPn/QPbEWS_JSWQAIJO^ NBELPeHBFHT}TnALVlBLOFAkHFOuFETp HCStHAUFAgcEAelclcn^r^r\\tZvYxXy T|S~Pn SPm SOn TNn ULo0ULo#ULo-W Hq!WFs XDt!" [b++];)

for(; a-- > 64 ; )
putchar ( ++c==90 ? c=10:33^b&1);

}

Decimal to Roman

Write a function to convert a number to its equivalent roman numeral value. You have to convert only numbers < 1000. Analyze the runtime. (This was really hard, and I fluffed my way through it.)


char* u2roman(unsigned n)
{
static char* roman_digits[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
static char* roman_tenths[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
static char* roman_hundreds[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
static char buf[13]; // Max length is 12 symbols
int cnt;

if (n >= 1000) return 0;

cnt = sprintf(buf, "%s", roman_hundreds[ n / 100 ]);
cnt += sprintf(buf + cnt, "%s", roman_tenths[ n / 10 ]);
sprintf(buf + cnt, "%s", roman_digits[ n % 10 ]);

return buf;
}

Array[3][3]

Sort a 2d array(m*n). Such that if we print the array in zigzag manner you get the sorted array(first row than second row and so on..). The array being such that each of its rows and its cols are in increasing order
e.g
I/P:
2 4 5
3 6 8
5 7 9

O/P:
2 3 4
5 5 6
7 8 9

Solution :
O(m*n*log(n))
Since the rows are sorted we can do this...
Take Row[0] and Row[1] merge them, Row [2] Row[3] merge them.....
so the tree looks like this.... Row[i,j] implies that Row[i] through Row[j] are sorted(i.e if we go from Row[i][0] till Row[j][n-1] it will be in sorted manner)...
___________________________Row[0,n-1]
___________________________/______.
.
.
___________/______________\___________
______Row[0,1]___________Row[2,3]_________________Row[n-2,n-1]
_____/________\________/_________\________________/__________Row[0]____Row[1]___Row[2]___Row[3]_____________Row[n-2]___Row[n-1]

This is similar to To merge sort of m*n elements only differernce is that we already have sorted arrays and thus we reduce the height of our merge tree....

Set Operations

Set Operations on Array
U - Universal Set
A - Subset
B - Subset

1. Union - All elements in A or B.
2. Intersection - All elements in A and B.
3. Minus - All elements in A but not in B.
4. Complement - All elements in U - A.

If the A, B, U are sorted
1. Union
Do a merge of A and B. If we get two elements with same value then take one of them and proceed.
i=0;
k=0;
j=0;
while(i lessThan n && j lessThan n)
{
_____if(A[i] lessThan B[j])
_____{
__________C[k] = A[i];
__________i++;
__________k++;
_____}
_____else if(A[i] greaterThan B[j])
_____{
__________C[k] = B[i];
__________j++;
__________k++;
_____}
_____else
_____{
__________C[k] = A[i];
__________j++;
__________k++;
__________i++;
_____}
}
while(i lessThan n)
{
__________C[k] = A[i];
__________i++;
__________k++;
}
while(j lessThan n)
{
__________C[k] = B[j];
__________j++;
__________k++;
}

2. Intersection
Normal Merge of A and B.
A[0,n-1] B[0,n-1]
Assuming that since these arrays represent sets we dont have any repeating elements
i=0;
k=0;
j=0;
while(k lessThan n && i lessThan n && j lessThan n)
{
_____if(A[i] == B[j])
_____{
__________print A[i];
__________i++;
__________j++;
__________k++;
_____}
_____else if(A[i] lessThan B[j])
_____{
__________i++;
_____}
_____else
_____{
___________j++;
_____}
}

3. Minus
C = A - B

while(k lessThan n && i lessThan n && j lessThan n)
{
_____if(A[i] == B[j])
_____{
__________i++;
__________j++;
_____}
_____else if(A[i] lessThan B[j])
_____{
__________C[k] = A[i];
__________k++;
__________i++;
_____}
_____else
_____{
___________j++;
_____}
}
if(j greaterThanEqualTo n)
{
_____while(k lessThan n && i lessThan n)
_____{
__________C[k]=A[i];
__________i++;
__________k++;
_____}
}

3. Complement
Same as Minus. complement(A) = U - A