Preps

Constructing Binary Tree from given Preorder and Inorder Traversal.

2011-10-01T21:49:00.000-07:00

Let us consider the following traversals:
Inorder sequence: D B E A F C
Preorder sequence: A B D E C F

In a Preorder sequence, leftmost element is the root of the tree. So we know ‘A’ is root for given sequences. By searching ‘A’ in Inorder sequence, we can find out all elements on left side of ‘A’ are in left subtree and elements on right are in right subtree. So we know below structure now.

A
/\
/ \
D B E F C

We recursively follow above steps and get the following tree.

A
/ \
/ \
B C
/\ /
/ \ /
D E F
Algorithm: buildTree()

1) Pick an element from Preorder. Increment a Preorder Index Variable (preIndex in below code) to pick next element in next recursive call.
2) Create a new tree node tNode with the data as picked element.
3) Find the picked element’s index in Inorder. Let the index be inIndex.
4) Call buildTree for elements before inIndex and make the built tree as left subtree of tNode.
5) Call buildTree for elements after inIndex and make the built tree as right subtree of tNode.
6) return tNode.

Removing Pair in a string.

2011-08-10T04:17:00.000-07:00

Suppose we have a string "RGBBGBGR". we have to eliminate the couple (two same chars adjacent to each other) recursively.

For example
RGBBGBGR --> RGGBGR-->RBGR

This solution is O(n) with recursion.

Program code:

#include <stdio.h>

#include <conio.h>

#include <string.h>

void pair_remove(char []);

void main()

{

char a[]="RGBBGBGRRGRR";

clrscr();

pair_remove(a);

printf("%s\n", a);

getch();

}

void pair_remove(char a[])

{

int remove=0,i,j;

int len=strlen(a);

for(i=0;i<len-1;i++){

if( a[i]== a[i+1] )

{

for(j=i+2;j<=len;j++)

{

a[i]=a[j];

i++;

remove=1;

}

if ( remove )

break;

}

if ( remove )

pair_remove(arr);

}

Spiral of a Matrix.

2011-08-09T06:17:00.000-07:00

The Following code prints the matrix in a spiral manner.

Program Code:

#include<conio.h>
#include<stdio.h>
void main()
{
int m,n,i,j,left,right,top,down,len,itr;
int a[5][5];
clrscr();
printf ("enter m (max 5): ");
scanf("%d",&m);
printf ("enter n (max 5): ");
scanf("%d",&n);
printf ("Enter the elements of matrix one by one\n");
for (i=0;i<m;i++)
for (j=0;j<n;j++)
scanf("%d",&a[i][j]);
printf ("you have entered the matrix\n");
for (i=0;i<m;i++)
{ for (j=0;j<n;j++)
printf("%6d ",a[i][j]);
printf ("\n");
}
left=0;
right=n;
top=0;
down=m;
itr=0;
len=m*n;
printf ("\n");
printf ("The spiral form is : ");
printf ("\n");
while (itr<len)
{
for (j=left;j<right;j++,itr++)
printf ("%d ",a[top][j]);
top++;

for (i=top;i<down;i++,itr++)
printf ("%d ",a[i][right-1]);
right--;

for (j=right-1;j>=left;j--,itr++)
printf ("%d ",a[down-1][j]);
down--;

for (i=down-1;i>=top;i--,itr++)
printf ("%d ",a[i][left]);
left++;
}
printf ("\n");
getch();
}

Finding the Odd repeating Number.

2011-08-05T10:36:00.000-07:00

Given an array of positive integers. Each number in the array repeats even number of times, only 1 number repeats odd number of times. Find that number.

This Solution is O(n) Time complexity.

#include<stdio.h>
#include<conio.h>
void main()
{
int a[]={4,3,4,3,1};
int len=(sizeof(a)/sizeof(int)),n=a[0],i;
clrscr();
for(i=1;i<len;i++)
{
n^=a[i];
}
printf("%d\n",n);
getch();
}

Inheritance in C.

2011-08-05T10:02:00.000-07:00

In C, Inheritance can be implemented through struct.

For example.

struct base
{
/* base class members */
}b;
struct derived
{
struct base super;
/* derived class members */
}d;
void main()
{
struct base *base_ptr = (struct base *)&d; // upcast
getch();
}

Swapping With Pointer.

2011-08-01T03:42:00.000-07:00

Swap two pointers without using temporary variables?

#include<stdio.h>
#include<conio.h>
void main()
{
int i=10;
int j=20;
int *a,*b;
clrscr();
a =&i;
b=&j;
printf("Before:%d\t%d\n",*a,*b);
*a^=*b;
*b^=*a;
*a^=*b;
printf("After:%d\t%d\n",*a,*b);
getch();
}

Finiding Max.

2011-07-28T08:32:00.000-07:00

Find the maximum of three numbers using conditional operator (ternary operator) ?

#include<stdio.h>
#include<conio.h>
void main()
{
int num1=34,num2=27,num3=61,max;
clrscr();
max=num1 > num2 ? num1 > num3 ? num1: num3: num2 >num3 ? num2: num3;
printf("%d",max);
getch();
}

Problem Based on Array.

2011-07-28T06:35:00.000-07:00

Given an array of integers, for each index i, swap the value at i with the first value smaller than a[ i ] that comes after index i. Write a C Program?

For example : If given array is a[]={3,7,4,9,10,2,1}
Output -- a[]={2,4,3,7,9,1,10}

Algorithm:
1) Start from the first element of the array and compare it with rest of the elements.
2) If a element is found which is smaller,swap it and break the execution.
3) Continue with the second element and so on.(until u reach the end of the array)
This solution is O(n^2).
Program:
#include<stdio.h>

#include<conio.h>
void fun(int a[],int,int);void main()
{
int a[]={3,7,4,9,10,2,1};
int len=sizeof(a)/sizeof(int);
int i;
clrscr();
fun(a,0,len);
getch();
}
void fun(int a[],int n,int len)
{
int temp,i;
if(n<len)
{
for(i=n+1;i<len;i++)
if(a[n]>a[i])
{
temp=a[i];
a[i]=a[n];
a[n]=temp;
break;
}
fun(a,n+1,len);
}
else
{
for(i=0;i<len;i++)
printf("%d\t",a[i]);
}
}

Permuting a String.

2011-07-27T06:56:00.000-07:00

Write a C program to print all permutations of a given string ?

For Ex: The Permutation of string "ABC" are "ABC, ACB, BAC, BCA, CAB, CBA"

Program: (using backtracking)

# include <stdio.h>

# include <conio.h>

void swap (char *x, char *y)

{

char temp;

temp = *x;

*x = *y;

*y = temp;

}

void permute(char *a, int i, int n)

{

int j;

if (i == n)

printf("%s\n", a);

else

{

for (j = i; j <= n; j++)

{

swap((a+i), (a+j));

permute(a, i+1, n);

swap((a+i), (a+j)); //backtrack

}

void main()

{

char a[] = "ABC";

clrscr();

permute(a, 0, 2);

getch();

}

Finding Sub-Strings.

2011-07-27T06:16:00.000-07:00

Print all the substrings of a given string.?
Eg: For "abc" the possible substrings are {"a","b","c","ab","bc","abc"}

Algorithm:
1) Start with two nested loops (let the loop variables are i and j, initialize them to 0)
2) Store the sum of the loop variables in another variable(say k) and store the value of (k+1)th element of the string in temporary variable(say tmp).
3) Now set the (k+1)th element of string to 0.(so that it does not print the characters after that element)
4) print the string.(expression as :s+j - so that it starts printing after the j th element in the string).
5) Now store the value of temp into the (k+1)th element of the string.
6) Repeat the steps 2 to 5 till reaching the end of the string(i.e till the termination of first loop).

Program:

#include<stdio.h>
#include<conio.h>
#include<string.h>
void main()
{
char s[]="abc";
int i,j;
clrscr();
for( i=0;i <strlen(s);i++)
{
for( j=0;j <strlen(s)-i;j++)
{
int k=j+i;
char tmp=s[k+1];
s[k+1]=0;
printf("%s\n",s+j);
s[k+1]=tmp;
}
}
getch();
}

Finding Repeated Element

2011-07-26T08:35:00.000-07:00

Find an integer that repeats more than (>)n/2 times in a given array of size n in O(1) time complexity.? Give an efficient Algorithm?
Note: The array is not sorted.

Algorithm:Let num=1st elt of array...freq=1...then for each elt e remaining if e==num increment freq else decrement..if freq becomes 0 then make num=e and freq as 1...at last num will hold the required number.

Program Coding:

#include<stdio.h>
#include<conio.h>

void main()
{
int a[]={5,1,5,2,5,3,5,4,5,3};
int len;
len=sizeof(a)/sizeof(int);
int n,f=1,i;
n=a[0];
clrscr();
for(i=1;i<len;i++)
{
if(f==0)
{
n=a[i];
f=1;
}

if(a[i]==n)
f++;
else
f--;
}
printf("%d",n);
getch();
}

Hashing Methods

2011-07-22T03:26:00.000-07:00

These are the hashing methods:

Direct method
Modulo-division
Midsquare
Digit extraction
Rotation
Folding

Direct Method

In direct hashing the key is the address without any algorithmic manipulation.
Direct hashing is limited, but it can be very powerful because it guarantees that there are no synonyms and therefore no collision.

Example :

Modulo-division Method

This is also known as division remainder method.
This algorithm works with any list size, but a list size that is a prime number produces fewer collisions than other list sizes.
The formula to calculate the address is:
Address = key MODULO listsize + 1
Where listsize is the number of elements in the arrary.

Example:
Given data
Keys are : 137456 214562 140145
137456 % 19 +1 = 11
214562 % 19 + 1 = 15
140145 % 19 + 1 = 2

Digit-extraction Method

Using digit extraction selected digits are extracted from the key and used as the address.

Example:

Using six-digit employee number to hash to a three digit address (000-999), we could select the first, third, and fourth digits( from the left) and use them as the address.

The keys are:
379452 -> 394
121267 -> 112
378845 -> 388

Folding Method
Two folding methods are used they are:

Fold shift
Fold boundary

1. Fold Shift

In fold shift the key value is divided into parts whose size matches the size of the required address. Then the left and right parts are shifted and added with the middle part.

2. Fold boundary

In fold boundary the left and right numbers are folded on a fixed boundary between them. The two outside values are thus reversed.

Midsquare Method

In midsquare hashing the key is squared and the address is selected from the middle of the square number.
Limitation is the size of the key.

Example:
9452² = 89340304: address is 3403

Rotation Method

Rotation method is generally not used by itself but rather is incorporated in combination with other hashing methods.
It is most useful when keys are assigned serially.

Hashing Basics

2011-07-22T03:03:00.000-07:00

Hashing is a Key to address mapping process.
Hashing is the transformation of a string of characters into a usually shorter fixed-length value or key that represents the original string.
Hashing is used to index and retrieve items in a database because it is faster to find the item using the shorter hashed key than to find it using the original value.

Terms must be familiarized.
Synonyms: The set of keys that hash to the same location.
Collision: A collision occurs when a hashing algorithm produces an address for an insertion key and that address is already occupied.
Home address: The address produced by the hashing algorithm is known as the home address.
Prime area: The memory that contains all of the home addresses is known as the prime area.
Probe: Each calculation of an address and test for success is known as a probe.
Hash table: Tables which can be searched for an item in O(1) time using a hash function to form an address from the key.

Hash function: Function which, when applied to the key, produces a integer which can be used as an address in a hash table.

Heap Sort.

2011-07-19T07:20:00.000-07:00

void heapsort( int a[], unsigned int n )
{
int i,temp;
for( i=n/2; i>=0; i-- ) /* build_heap */
shift_down (a, i, n-1 );
for( i=n; i>=1; i-- )
{
temp=a[0];
a[0]=a[i];
a[i]=temp; /* delete_max */
shift_down( a, 0, i-1 );
}
}
void shift_down( int a[], unsigned int i, unsigned int n )
{
unsigned int child;
int tmp;
for( tmp=a[i]; i*2<=n; i=i*2 )
{
child = i;
if( ( child != n ) && ( a[child+1] > a[child] ) )
child++;
if( tmp < a[child] )
a[i] = a[child];
else
break;
}
a[i] = tmp;
}

Heap Sort.

2011-07-19T06:05:00.000-07:00

Forming the Heap:

Start at the root node of the tree.
If the root is larger than its children, stop- you have a heap.
If not, exchange the root with the largest child
Consider the child as the current root and repeat the step from 1.

Sorting Algorithm:

Repeat n-1 times.
Exchange the root value with the last value in the tree.
Now, Drop the last value form the tree.
Reform the heap.

Example:
Consider the array elements that are already arranged as heap. Let the array elements be 87,57,44,12,15,19,23. Here's the Heap.

Exchange the root with the last value.

Drop the last value in the heap.

Reform the heap. Find the largest child of the current root.

Exchange the values.

Now exchange the root of the heap with the last value.

Drop the last value in the heap.

Reform the heap. Find the largest child of the current root.

Exchange the values.

Now exchange the root of the heap with the last value.

Drop the last value in the heap.

Reform the heap. Find the largest child of the current root.

Exchange the values.

Now exchange the root of the heap with the last value.

Drop the last value in the heap.

Reform the heap. Find the largest child of the current root.

Exchange the values.

Now exchange the root of the heap with the last value.

Drop the last value in the heap.

Reform the heap. Find the largest child of the current root.

Exchange the values

Now exchange the root of the heap with the last value.

Drop the last value in the heap.

The heap consists of a single value at this point which is in its proper position.

So the List is sorted.

Quick sort Example.

2011-07-18T11:23:00.000-07:00

Example:

1) Consider the example with array elements 44,75,23,43,55,12,64,77.

2) The First(UP) and Last(Down) element are 44 and 33 resp.

3) Let the pivot element be 44.

4) Increment Up until Up > Pivot.

5) Decrement Down Until Down <= Pivot.

6) Now, Both the Conditions satisfies. So, Exchange values of Up and Down.

7) Again Increment Up until Up > Pivot.

8) Similarly decrement Down until Down <= Pivot.

9) Now swap the values of Up and Down Values.

10) Again increment the Up pointer until Up > pivot.

11) Similarly decrement the Down until Down < = Pivot.

12) Up and Down passed each other, so exchange the pivot value and the value in the Down.

13) Note that all the values below the pivindex are <= pivot and the values above the pivindex are > pivot.
14) This gives us two new sub-arrays.

15) Repeat the process for the rest of the sub-arrays.

Merge Sort.

2011-07-18T04:53:00.000-07:00

mergesort( int a[], unsigned int n )
{
int *tmp_array;
tmp_array = (int*) malloc ( (n+1) * sizeof (int) );
if( tmp_array != NULL )
{
m_sort( a, tmp_array, 1, n );
free( tmp_array );
}
else
printf("No space for tmp array!!!");
}
void m_sort( int a[], int tmp_array[ ],int left, int right )
{
int center;
if( left < right )
{
center = (left + right) / 2;
m_sort( a, tmp_array, left, center );
m_sort( a, tmp_array, center+1, right );
merge( a, tmp_array, left, center+1, right );
}
}

void merge( int a[ ], int tmp_array[ ],int lpos,int rpos,int rend)
{
int i, lend, n, tmp_pos;
lend = rpos - 1;
tmp_pos = lpos
n = rend - lpos + 1;
/* main loop */
while( ( lpos <= lend ) && ( rpos <= rend ) )
if( a[lpos] <= a[rpos] )
tmp_array[tmp_pos++] = a[lpos++];
else
tmp_array[tmp_pos++] = a[rpos++];
while( lpos <= lend )  /* copy rest of first half */
tmp_array[tmp_pos++] = a[lpos++];
while( rpos <= rend ) /* copy rest of second half */
tmp_array[tmp_pos++] = a[rpos++];
/* copy tmp_array back */
for(i=1; i <= n; i++, rend-- )
a[rend] = tmp_array[rend];
}

Merge Sort.

2011-07-17T10:17:00.000-07:00

The fundamental operation in this algorithm is merging two sorted lists.

Algorithm:
1) Divide the array repeatedly into two halves
2) Stop dividing when there is single element left. By fact, single element is already sorted.
3) Merges two already sorted sub arrays into one.

Example:
The basic merging algorithm takes two input arrays a and b, an output array c. Consider three counters, aptr, bptr, and cptr, which are initially set to the beginning of their respective arrays.The smaller of a[aptr] and b[bptr] is copied to the next entry in c, and the appropriate counters are advanced. When either input list is exhausted, the remainder of the other list is copied to c.

If the array a contains 1, 13, 24, 26, and b contains 2, 15, 27, 38, then the algorithm proceeds as follows: First, a comparison is done between 1 and 2. 1 is added to c, and then 13 and 2 are compared.

2 is added to c, and then 13 and 15 are compared.

13 is added to c, and then 24 and 15 are compared. This proceeds until 26 and 27 are compared.

26 is added to c, and the a array is exhausted.

The remainder of the b array is then copied to c.

The time to merge two sorted lists is clearly linear, because at most n - 1 comparisons are made, where n is the total number of elements.

Insertion Sort.

2011-07-16T23:44:00.001-07:00

for ( i = 1 ; i <= 4 ; i++ )
 {
  for ( j = 0 ; j < i ; j++ )
  {
   if ( arr[j] > arr[i] )
   {
    temp = arr[j] ;
    arr[j] = arr[i] ;
    for ( k = i ; k > j ; k-- )
     arr[k] = arr[k - 1] ;
    arr[k + 1] = temp ;
   }
  }
 }

Quick Sort.

2011-07-16T23:43:00.000-07:00

void quicksort ( int a[ ], int lower, int upper )
{
 int i ;
 if ( upper > lower )
 {
  i = split ( a, lower, upper ) ;
  quicksort ( a, lower, i - 1 ) ;
  quicksort ( a, i + 1, upper ) ;
 }
}

int split ( int a[ ], int lower, int upper )
{
 int i, p, q, t ;
 p = lower + 1 ;
 q = upper ;
 i = a[lower] ;
 while ( q >= p )
 {
  while ( a[p] < i )
   p++ ;
  while ( a[q] > i )
   q-- ;
  if ( q > p )
  {
   t = a[p] ;
   a[p] = a[q] ;
   a[q] = t ;
  }
 }
 t = a[lower] ;
 a[lower] = a[q] ;
 a[q] = t ;
 return q ;
}

Selection sort.

2011-07-16T23:41:00.002-07:00

for ( i = 0 ; i <= 3 ; i++ )
 {
  for ( j = i + 1 ; j <= 4 ; j++ )
  {
   if ( arr[i] > arr[j] )
   {
    temp = arr[i] ;
    arr[i] = arr[j] ;
    arr[j] = temp ;
   }
  }
 }

Bubble Sort.

2011-07-16T23:41:00.000-07:00

for ( i = 0 ; i <= 3 ; i++ )
 {
  for ( j = 0 ; j <= 3 - i ; j++ )
  {
   if ( arr[j] > arr[j + 1] )
   {
    temp = arr[j] ;
    arr[j] = arr[j + 1] ;
    arr[j + 1] = temp ;
   }
  }
 }

Selection sort.

2011-07-16T23:03:00.000-07:00

Algorithm

Find the minimum value in the list
Swap it with the value in the first position
Repeat the steps above for the remainder of the list (starting at the second position and advancing each time).

Example:

Consider the array list 64,25,12,22,11.
Step 1: Min Value is 11.
64 25 12 22 11
Move it to the first position in the array.
Step 2: Min Value in the rest of the array is 12.
11 25 12 22 64
Move it to the second position in the array.
Step 3:Min value in the rest of the array is 22.
11 12 25 22 64
Move it to the third position in the array.
Step 4:Min value in the rest of the array is 25.
11 12 22 25 64
  Its already in the sorted position.
Step 5: It executes one more time.11 12 22 25 64

Insertion Sort.

2011-07-16T22:52:00.000-07:00

Insertion sorting algorithm is similar to bubble sort. But insertion sort is more efficient than bubble sort because in insertion sort the elements comparisons are less as compare to bubble sort. In insertion sorting algorithm compare the value until all the prior elements are lesser than compared value is not found. This mean that the all previous values are lesser than compared value.

Example:
Consider the array list 12,9,4,99,120,1,3,10.

Quick Sort.

2011-07-16T22:42:00.000-07:00

Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.

Algorithm:

If First < Last, then
Partition the elements in the sub-array First to Last so that the pivot element is in place.
Apply quick sort to the first sub-array First to pivindex-1.
Apply quick sort to the second sub-array pivindex+1 to Last.

The two Stopping cases:

If First=Last,Only one value in the array, So sorted.
If First > Last, no values in the array, So sorted.

To Partition the array:

Define the Pivot value (mostly choose first element in the array).
Initialize Up to First element and Down to last element.
Increment Up until Up > pivot.
Decrement Down until Down <= pivot.
If Up < Down exchange their values.
Repeat 3,4,5 until Up meets or Passes Down.
Exchange array[First] and array[Down].
Define pivindex as Down.

Example :
Consider the array elements as 4,2,3,5,1.
Here First(as well as Up) and Last(as well as Down) elements are 4 and 1 respectively. Let the Pivot element be 3.