WAP to Genrate All Possible Subset of Set S..Thats The Power Set

Algorithm:

Powerset: A recursive algorithm

If S = (a, b, c) then the powerset(S) is the set of all subsets

powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}

The first "trick" is to try to define recursively.

What would be a stop state?
S = () has what powerset(S)?

How get to it?
Reduce set by one element

Consider taking an element out - in the above example, take out {c}

S = (a,b) then powerset(S) = {(), (a), (b), (a,b), }

What is missing?
powerset(S) = { (c), (a,c), (b,c), (a,b,c)}

hmmm
Notice any similarities? Look again...
powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}

take any element out

powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)} IS

powerset(S - {c}) = {(), (a), (b), (a,b)} unioned with
{c} U powerset(S - {c}) = { (c), (a,c), (b,c), (a,b,c)}

powerset(S) = powerset(S - {e_i}) U ({e_i} U powerset(S - {e_i}))

where e_i is an element of S (a singleton)

Pseudo-algorithm

1. Is the set passed empty? Done
2. If not, take an element out
   • recursively call method on the remainder of the set
   • return the set composed of the Union of
     (1) the powerset of the set without the element (from the recursive call)
     (2) this same set (i.e., (1)) but with each element therein unioned with the element initially taken out

Go backwards:
powerset(S) when S = {()} is {()}
powerset(S) when S = {(a)} is {(), (a)}
powerset(S) when S = {(a,b)} is {(), (a), (b), (a,b)}
etc...


Power Set Power set P(S) of a set S is the set of all subsets of S. For example S = {a, b, c} then P(s) = {{}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c}}.

If S has n elements in it then P(s) will have 2^n elements



1st using Recursion

public class PowerSet {


private void printPowerSet(String inputString, String prefixString, int startIndex){
if(inputString == null){
return;
}
for(int i=startIndex;iString str = "";
str = prefixString + inputString.charAt(i);
System.out.println("{" + str + "}\n");
printPowerSet(inputString, str, i+1);
}

}




public static void main(String args[]){
String inputStr ="123";
System.out.println("{ }\n");
for(int i=0; iPowerSet powerSet = new PowerSet();

System.out.println("{" + inputStr.charAt(i) + "}\n");
powerSet.printPowerSet(inputStr, Character.toString(inputStr.charAt(i)), i+1);

}
}


}

TC O(n^2)
Sc O(n)

Run here https://ideone.com/8RuF1


2nd Iterative Method

Algorithm:

Input: Set[], set_size
1. Get the size of power set
powet_set_size = pow(2, set_size)
2 Loop for counter from 0 to pow_set_size
(a) Loop for i = 0 to set_size
(i) If ith bit in counter is set
Print ith element from set for this subset
(b) Print seperator for subsets i.e., newline

Example:

Set = [a,b,c]
power_set_size = pow(2, 3) = 8
Run for binary counter = 000 to 111

Value of Counter Subset
000 -> Empty set
001 -> a
011 -> ab
100 -> c
101 -> ac
110 -> bc
111 -> abc


#include
#include

void printPowerSet(char *set, int set_size)
{
/*set_size of power set of a set with set_size
n is (2**n -1)*/
unsigned int pow_set_size = pow(2, set_size);
int counter, j;

/*Run from counter 000..0 to 111..1*/
for(counter = 0; counter < pow_set_size; counter++)
{
for(j = 0; j < set_size; j++)
{
/* Check if jth bit in the counter is set
If set then pront jth element from set */
if(counter & (1< printf("%c", set[j]);
}
printf("\n");
}
}

/*Driver program to test printPowerSet*/
int main()
{
char set[] = {'a','b','c','d'};
printPowerSet(set, 4);

getchar();
return 0;
}

TC O(n*2^n)
SC O(1)
Rune Here https://ideone.com/z5tHG


Java program for Doing The Same

class PowerSet {

int arr[]={1,2,3};
int number=0;
void powerSet(){
for(int i=0;iint k=i;
int counter=0;
while(k>0){
if((k & 1) == 1){
System.out.print(arr[counter]);

}
counter++;
k=k>>1;
}
System.out.println();
number++;
}

}
public static void main(String[] args) {
PowerSet p=new PowerSet();
p.powerSet();
System.out.println("Total number of subsets are"+p.number);

}

}

Run Here https://ideone.com/LtjsT


More  http://en.wikipedia.org/wiki/Power_set
http://www.ecst.csuchico.edu/~amk/foo/csci356/notes/ch1/solutions/recursionSol.html
http://stackoverflow.com/questions/1670862/obtaining-powerset-of-a-set-in-java
http://rosettacode.org/wiki/Power_set
http://ruslanspivak.com/2011/06/09/power-set-generation-a-joy-of-python/
http://www.roseindia.net/tutorial/java/core/powerset.html
http://shriphani.com/blog/2008/03/31/one-step-forward-two-steps-back/
http://planetmath.org/?op=getobj&from=objects&id=136

There are n rocks in the river, using which the frog can leap across the river.

I saw a discussion on this question on careercup as its good question..so i pasted it here

A frog has to cross a river. There are n rocks in the river, using which the frog can leap across the river. On its way across the river the frog can chose to skip a rock, but it cannot skip two consecutive rocks because that would be two far a distance for the frog to hop, also the from would not skip the first rock and the last rock. E.g. if there are 3 rocks, 1,2,3 and 4, there could be three following routes it could take:
1,2,3,4
1,2,3,4
1,3,4
1,2,4

Write a recursive algorithm, that takes a number of rocks' and prints all the feasible paths. Ofcourse there can be other arguments too.



A frog has to cross a river. There are n rocks in the river, using which the frog can leap across the river. On its way across the river the frog can chose to skip a rock, but it cannot skip two consecutive rocks because that would be two far a distance for the frog to hop, also the from would not skip the first rock and the last rock. E.g. if there are 3 rocks, 1,2,3 and 4, there could be three following routes it could take:
1,2,3,4
1,2,3,4
1,3,4
1,2,4

Write a recursive algorithm, that takes a number of rocks' and prints all the feasible paths.


#include
#include
#include


void printFrogLeap (int* pArray, int num, int count)
{
if(count > num)
{
return;
}
if(count == num)
{
int i;
if(pArray[count-1] == 1) /*path is complete or not*/
{
for (i=0; i < num; i++)
{
if (pArray[i] == 1)
{
printf ("[%d]", i+1);
}
}
printf ("\n");
}
return;
}
pArray [count] = 1;
printFrogLeap (pArray, num, count+1);
if(count+1 < num)
{
pArray [count+1] = 0;/*exclude this entry from path, since its used*/
}
printFrogLeap (pArray, num, count+2);
if(count+2 < num)
{
pArray [count+2] = 0;/*exclude this entry from path, since its used*/
}
}



int main ()
{
int *array, num=4;

array = (int*)malloc (sizeof(int)*num);
memset (array,0x00,num);
printf ("Total paths: \n");
printFrogLeap (array, num, 0);
free (array);
return 0;
}

Run Here https://ideone.com/o00za
Solution By Tully From CareerCup

You have a string "RGBBGBGR". Eliminate the pairs (two same chars adjacent to each other) recursively.

Example:
RGBBGBGR --> RGGBGR-->RBGR
Answer: Here recursively mean not a recursive function but to do it in the manner shown in example. Still we can do it recursively like below:

Fun_rcur(string)
{
if pairs
Remove pairs in string
Fun_recur(string)
Else
Return
}

But this is very costly:
1) Extra space (stack space for recursive calls)
2) You need to go through entire string in each recursive call.

Lets see an iterative approach for the same. We should check if we have character pair then cancel it and then check for next character and previous element. Keep canceling the characters until you either reach start of the array, end of the array or not find a pair.



C Code Complexity O(N^2) & Space O(1) Recursion

#include
#include
void couple_remove(char []);
int main(){
char arr[]="RGBBGBGR";// "RGBBGBGRRGRR";
couple_remove(arr);
printf("\n\n%s\n\n", arr);
return 0;
}

void couple_remove(char arr[]){
int remove=0,i,j;
int len=strlen(arr);
for(i=0;i if( arr[i]== arr[i+1] ){
for(j=i+2;j<=len;j++) {
arr[i]=arr[j];
i++;
remove=1;
}
}
if ( remove )
break;
}
if ( remove )
couple_remove(arr);
}

Rune Here https://ideone.com/urZEo


Java Code Complexity O(n) & Space O(n) Iterative

import java.util.Stack;
class CoupleElimination {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Stack st = new Stack();
String inputString = "RGBBGBGR";
for( int i=0 ; i < inputString.length() ; i++ )
{
char ch = inputString.charAt(i);
char top ;
if( !st.empty())
{
top = st.peek();

if( top == ch)
st.pop();
else
st.push(ch);
}

else
st.push(ch);
}
String result = "";
while( !st.empty() )
{
result = st.pop()+result;
}
System.out.println(result);
}
}

Run Here https://ideone.com/UF0Ao

Amplitude of Element In Unsorted Array

/*
The amplitude of a non-empty zero-indexed array A consisting of N numbers is defined as

amplitude(A) = max { A[P] - A[Q] : 0 <= P, Q < N }

Write a function

int amplitude(int[] A);

that given a non-empty zero-indexed array A consisting of N non-negative integers returns its amplitude. Assume that the length of the array does not exceed 1,000,000. Assume that each element of the array is a non-negative integer not exceeding 5,000,000.

For example, given array A such that

A[0]=10, A[1]=2, A[2]=44, A[3]=15, A[4]=39, A[5]=20

the function should return 42.

*/

Java Code

class array
{
public static void main(String a[])

{

System.out.println(amplitude(new int[]{10, 2, 44, 15, 39, 20}));

}

static int amplitude ( int[] A )
{
// write your code here
int min=A[0];
int max=A[0];
int diff=0;

if(A==null)
return 0;
if(A.length==0)
return 0;

if(A.length>1000000)
{
return 0;
}
else
{

for(int i=0;i {
if(A[i] min=A[i];
if(A[i]>max)
max=A[i];

diff=max-min;
}

}
return diff;
}

}

WAP to Remove The Node From Binary Search Tree

#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/* Helper function that allocates a new node
with the given data and NULL left and right
pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

/* Give a binary search tree and a number,
inserts a new node with the given number in
the correct place in the tree. Returns the new
root pointer which the caller should then use
(the standard trick to avoid using reference
parameters). */
struct node* insert(struct node* node, int data)
{
/* 1. If the tree is empty, return a new,
single node */
if (node == NULL)
return(newNode(data));
else
{
/* 2. Otherwise, recur down the tree */
if (data <= node->data)
node->left = insert(node->left, data);
else
node->right = insert(node->right, data);

/* return the (unchanged) node pointer */
return node;
}
}

struct node* search(struct node* tmp, struct node** parent,struct node* item)
{
struct node* root;
root=tmp;

if(!root)
{
//*parent=NULL;
return NULL;
}
if(root->data==item->data)
{
return root;
}

*parent=root;

if(item->data<=root->data)
{
return search(root->left,parent,item);
}
else
{

return search(root->right,parent,item);
}

}

void deletes(struct node* root,struct node* srch)
{
struct node* parent;
struct node* succ=NULL;

if(!root)
return;

parent=NULL;

struct node* x=search(root,&parent,srch);

/* if the node to be deleted has no child */
if(x->left==NULL && x->right==NULL)
{

if(parent->left==x)
parent->left=NULL;
else
parent->right=NULL;

free(x);
return;
}


/* if the node to be deleted has only rightchild */
if (x->left == NULL && x->right!= NULL )
{
if ( parent->left == x )
parent->left = x->right ;
else
parent->right= x->right;

free ( x ) ;
return ;
}

/* if the node to be deleted has only left child */
if (x->left != NULL && x->right== NULL )
{
if ( parent->left == x )
parent->left= x->left ;
else
parent->right = x->left ;

free ( x ) ;
return ;
}


/* if the node to be deleted has two children */

if(x->left!=NULL && x->right!=NULL)
{
parent=x;
succ=x->right;

while(succ->left!=NULL)
{
parent=succ;
succ=succ->left;
}

x->data=succ->data;
x=succ;
free(x);//free(succ).....problem Might be here I dont Know why
}
}

/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct node* node)
{
if (node == NULL)
return;

/* first recur on left child */
printInorder(node->left);

/* then print the data of node */
printf("%d ", node->data);

/* now recur on right child */
printInorder(node->right);
}


/* Driver program to test sameTree function*/
int main()
{
struct node* root = NULL;
root = insert(root, 4);
insert(root, 2);
insert(root, 1);
insert(root, 3);
insert(root, 6);
insert(root, 5);

struct node* parent= NULL;

root=search(root,&parent,root->left->right);
printf(" %d %d ", root->data, parent->data);

deletes(root,root->left->right);

printInorder(root);

getchar();
return 0;
}

Check for balanced parentheses in an expression

Given an expression string exp, write a program to examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”[","]” are correct in exp. For example, the program should print true for exp = “[()]{}{[()()]()}” and false for exp = “[(])”

Algorithm:
1) Declare a character stack S.
2) Now traverse the expression string exp.
a) If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[') then push it to stack.
b) If the current character is a closing bracket (')' or '}' or ']‘) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
3) After complete traversal, if there is some starting bracket left in stack then “not balanced”


#include
#include
#define bool int

/* structure of a stack node */
struct sNode
{
char data;
struct sNode *next;
};

/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data);

/* Function to pop an item from stack*/
int pop(struct sNode** top_ref);

/* Returns 1 if character1 and character2 are matching left
and right Parenthesis */
bool isMatchingPair(char character1, char character2)
{
if(character1 == '(' && character2 == ')')
return 1;
else if(character1 == '{' && character2 == '}')
return 1;
else if(character1 == '[' && character2 == ']')
return 1;
else
return 0;
}

/*Return 1 if expression has balanced Parenthesis */
bool areParenthesisBalanced(char exp[])
{
int i = 0;

/* Declare an empty character stack */
struct sNode *stack = NULL;

/* Traverse the given expression to check matching parenthesis */
while(exp[i])
{
/*If the exp[i] is a starting parenthesis then push it*/
if(exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
push(&stack, exp[i]);

/* If exp[i] is a ending parenthesis then pop from stack and
check if the popped parenthesis is a matching pair*/
if(exp[i] == '}' || exp[i] == ')' || exp[i] == ']')
{

/*If we see an ending parenthesis without a pair then return false*/
if(stack == NULL)
return 0;

/* Pop the top element from stack, if it is not a pair
parenthesis of character then there is a mismatch.
This happens for expressions like {(}) */
else if ( !isMatchingPair(pop(&stack), exp[i]) )
return 0;
}
i++;
}

/* If there is something left in expression then there is a starting
parenthesis without a closing parenthesis */
if(stack == NULL)
return 1; /*balanced*/
else
return 0; /*not balanced*/
}

/* UTILITY FUNCTIONS */
/*driver program to test above functions*/
int main()
{
char exp[100] = "{()}[]";
if(areParenthesisBalanced(exp))
printf("\n Balanced ");
else
printf("\n Not Balanced "); \
getchar();
}

/* Function to push an item to stack*/
void push(struct sNode** top_ref, int new_data)
{
/* allocate node */
struct sNode* new_node =
(struct sNode*) malloc(sizeof(struct sNode));

if(new_node == NULL)
{
printf("Stack overflow \n");
getchar();
exit(0);
}

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*top_ref);

/* move the head to point to the new node */
(*top_ref) = new_node;
}

/* Function to pop an item from stack*/
int pop(struct sNode** top_ref)
{
char res;
struct sNode *top;

/*If stack is empty then error */
if(*top_ref == NULL)
{
printf("Stack overflow \n");
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->data;
*top_ref = top->next;
free(top);
return res;
}
}

Source Geeks4Geeks

WAP to Find Longest Comman Subsequence

The longest common subsequence (or LCS) of groups A and B is the longest group of elements from A and B that are common between the two groups and in the same order in each group. For example, the sequences "1234" and "1224533324" have an LCS of "1234":

1234
1224533324

For a string example, consider the sequences "thisisatest" and "testing123testing". An LCS would be "tsitest":

thisisatest
testing123testing

In this puzzle, your code only needs to deal with strings. Write a function which returns an LCS of two strings (case-sensitive). You don't need to show multiple LCS's.

More Info Wiki

C Code of LCS

#include
#include
#include

#define MAX(A,B) (((A)>(B))? (A) : (B))

char * lcs(const char *a,const char * b) {
int lena = strlen(a)+1;
int lenb = strlen(b)+1;

int bufrlen = 40;
char bufr[40], *result;

int i,j;
const char *x, *y;
int *la = calloc(lena*lenb, sizeof( int));
int **lengths = malloc( lena*sizeof( int*));
for (i=0; i
for (i=0,x=a; *x; i++, x++) {
for (j=0,y=b; *y; j++,y++ ) {
if (*x == *y) {
lengths[i+1][j+1] = lengths[i][j] +1;
}
else {
int ml = MAX(lengths[i+1][j], lengths[i][j+1]);
lengths[i+1][j+1] = ml;
}
}
}

result = bufr+bufrlen;
*--result = '\0';
i = lena-1; j = lenb-1;
while ( (i>0) && (j>0) ) {
if (lengths[i][j] == lengths[i-1][j]) i -= 1;
else if (lengths[i][j] == lengths[i][j-1]) j-= 1;
else {
// assert( a[i-1] == b[j-1]);
*--result = a[i-1];
i-=1; j-=1;
}
}
free(la); free(lengths);
return strdup(result);
}

int main()
{
printf("%s\n", lcs("thisisatest", "testing123testing")); // tsitest
return 0;
}

Run Here https://ideone.com/tCMa0

Java Code of LCS

class LCS
{

public static String lcs_dp(String a, String b) {
int[][] lengths = new int[a.length()+1][b.length()+1];

// row 0 and column 0 are initialized to 0 already

for (int i = 0; i < a.length(); i++)
for (int j = 0; j < b.length(); j++)
if (a.charAt(i) == b.charAt(j))
lengths[i+1][j+1] = lengths[i][j] + 1;
else
lengths[i+1][j+1] =
Math.max(lengths[i+1][j], lengths[i][j+1]);

// read the substring out from the matrix
StringBuffer sb = new StringBuffer();
for (int x = a.length(), y = b.length();
x != 0 && y != 0; ) {
if (lengths[x][y] == lengths[x-1][y])
x--;
else if (lengths[x][y] == lengths[x][y-1])
y--;
else {
assert a.charAt(x-1) == b.charAt(y-1);
sb.append(a.charAt(x-1));
x--;
y--;
}
}

return sb.reverse().toString();
}


public static String lcs_rec(String a, String b){
int aLen = a.length();
int bLen = b.length();
if(aLen == 0 || bLen == 0){
return "";
}else if(a.charAt(aLen-1) == b.charAt(bLen-1)){
return lcs_rec(a.substring(0,aLen-1),b.substring(0,bLen-1))
+ a.charAt(aLen-1);
}else{
String x = lcs_rec(a, b.substring(0,bLen-1));
String y = lcs_rec(a.substring(0,aLen-1), b);
return (x.length() > y.length()) ? x : y;
}
}

public static void main(String a[])
{
System.out.println(lcs_rec("ABCDEFG", "FACHDGB"));
System.out.println(lcs_dp("ABCDEFG", "FACHDGB"));

}

}

Source http://www.ics.uci.edu/~eppstein/161/960229.html

Run Here https://ideone.com/lsc8b

WAP to Removing characters from an input string in place.

#include
#include

WAP to Find & Remove The Loop From Linked List

1st Algorithm:
Floyd’s Cycle-Finding Algorithm:

Algorithm
This is the fastest method. Traverse linked list using two pointers. Move one pointer by one and other pointer by two. If these pointers meet at some node then there is a loop. If pointers do not meet then linked list doesn’t have loop.

Working Code For Loop Detection

#include
#include

/* Link list node */
struct node
{
int data;
struct node* next;
};

void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*head_ref);

/* move the head to point to the new node */
(*head_ref) = new_node;
}

int detectloop(struct node *list)
{
struct node *slow_p = list, *fast_p = list;

while(slow_p && fast_p &&
slow_p->next &&
fast_p->next &&
fast_p->next->next )
{
slow_p = slow_p->next;
fast_p = fast_p->next->next;
if (slow_p == fast_p)
{
printf("Found Loop");
return 1;
}
}
return 0;
}

/* Drier program to test above function*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;

push(&head, 20);
push(&head, 4);
push(&head, 15);

/* Create a loop for testing */
head->next->next = head;
detectloop(head);

getchar();
}

Time Compelxity O(n)
Space Compelxity O(1)

2nd Algorithm
Brent Algorithm For Loop Detection in Linked List

#include
#include

/* Link list node */
struct node
{
int data;
struct node* next;
};

void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*head_ref);

/* move the head to point to the new node */
(*head_ref) = new_node;
}

int findLoop(struct node* head)
{
if (head == NULL)
return 0;
struct node* slow = head;
struct node* fast = head;
int i = 0;
int k = 1;

while (slow != NULL)
{
slow = slow->next;
i++;
if (slow == fast)
return 1;
if (i == k)
{
fast = slow;
k*= 2;
}
}
return 0;
}

/* Drier program to test above function*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;

push(&head, 20);
push(&head, 4);
push(&head, 15);

/* Create a loop for testing */
head->next->next = head;
printf(" %d ",findLoop(head));

getchar();
}

Time Compelxity O(n)
Space Compelxity O(1)

Both Above Algos are basically used to detct cycle in Graph.

Algorithm for Removing loop From Linked List

This method is also dependent on Floyd’s Cycle detection algorithm.
1) Detect Loop using Floyd’s Cycle detection algo and get the pointer to a loop node.
2) Count the number of nodes in loop. Let the count be k.
3) Fix one pointer to the head and another to kth node from head.
4) Move both pointers at the same pace, they will meet at loop starting node.
5) Get pointer to the last node of loop and make next of it as NULL.

Working Code For Removing Loop

#include
#include

/* Link list node */
struct Node
{
int value;
struct Node* next;
};

void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));

/* put in the data */
new_node->value= new_data;

/* link the old list off the new node */
new_node->next = (*head_ref);

/* move the head to point to the new node */
(*head_ref) = new_node;
}

void removeloop(struct Node *head)
{

struct Node *p1 = NULL, *p2 = NULL;

while(head)
{
if (p1 == NULL && p2 == NULL)
{
// 1. Two pointers start from head

p1 = head;
p2 = head;
}
else
{
// 2 If two pointers meet, there is a loop

if (p1 == p2)
break;
}

// 3 If pointer reachs the end, there is no loop
if (p2->next == NULL || p2->next->next == NULL)
{
printf("There is no loop in the list.\n");
return ;
}

// 4. One pointer advances one while the other advances two.
p1 = p1->next;
p2 = p2->next->next;
}

// 5. Find out how many nodes in the loop, say k.

unsigned int k = 1;
p2 = p2->next;
while (p1 != p2)
{
p2 = p2->next;
k++;
}
printf("There are %d nodes in the loop of the list.\n", k);

// 6. Reset one pointer to the head, and the other pointer to head + k.
p1 = head;
p2 = head;

for (unsigned int i = 0; i < k; i++) p2 = p2->next;

// 7. Move both pointers at the same pace, they will meet at loop starting node
while(p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}

printf("node %d is the loop starting node.\n", p1->value);

// 8. Move one of the pointer till its next node is the loop starting node.
// It's the loop ending node
p2 = p2->next;
while(p2->next != p1)
p2 = p2->next;

printf("node %d is the loop ending node.\n", p2->value);
// 9. Set the next node of the loop ending node to fix the loop
p2->next = NULL;

}

/* Utility function to print a linked list */
void printList(struct Node *head)
{
while(head!=NULL)
{
printf("%d ",head->value);
head=head->next;
}
printf("\n");
}


int main()
{
/* Start with the empty list */
struct Node *head = NULL;

push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);

head->next->next->next->next->next=head->next->next;

removeloop(head);

printList(head);

printf("\n");
}

Time Compelxity O(n)
Space Compelxity O(1)
Run Here https://ideone.com/wN4tR
You can Have a Look at http://ostermiller.org/find_loop_singly_linked_list.html

WAP to Find Kth Maximum or Kth Minimum in Array in Linear Time

Other Variation

You have to develop a piece of code that can be attached to a program
like Microsoft Word, which would list the last "N" words of the
document in descending order of their occurrence, and update the list
as the user types. What code would you write? Using pseudo code is
fine, just list the basic things you would consider

Given a stream of distance of millions of stars from the earth, find the nearest n star from the earth.


Algorithm

1) Build a Min Heap MH of the first k elements (arr[0] to arr[k-1]) of the given array. O(k)
2) For each element, after the kth element (arr[k] to arr[n-1]), compare it with root of MH.
a) If the element is greater than the root then make it root and call heapify for MH
b) Else ignore it.
O((n-k)*logk)
3) Finally, MH has k largest elements and root of the MH is the kth largest element.

Time Complexity: O(k + (n-k)Logk) without sorted output. If sorted output is needed then O(k + (n-k)Logk + kLogk)



Java Code


class Heap_new
{
int arr[]; // pointer to array of elements in heap
int heap_size;
Heap_new()
{

}

Heap_new(int a[], int size)
{
heap_size = size;
arr = a;
}


int getRoot() {return arr[0];}
int parent(int i){ return (i-1)/2; } ;
int left(int i) { return (2*i + 1); } ;
int right(int i) { return (2*i + 2); } ;

void changeRoot(int x)
{
int root = arr[0];
if (root < x)
{
arr[0] = x;
}
minHeapify(0);
}

void swap(int i,int j)
{
int temp=i;
i=j;
j=temp;
}

void minHeapify(int i) {
int l = left(i);
int r = right(i);
int largest;
if (l < heap_size && arr[l] < arr[i])
largest = l;
else
largest = i;
if (r < heap_size && arr[r] < arr[largest])
largest = r;
if (largest != i)
{
swap(arr[i], arr[largest]);
minHeapify(largest);
}
}

void buildminHeap()
{
int i = (heap_size - 1)/2;
while (i >= 0)
{
minHeapify(i);
i--;
}
}

void kthLargest(int arr[], int n, int k)
{
Heap_new hp=new Heap_new(arr,k);
hp.buildminHeap();

int i;
for(i = k; i < n; i++)
{
changeRoot(arr[i]);
}

}

public static void main(String a[])
{
int k = 4;
int arr[] = new int[]{12, 34, 10, 8, 9, 24, 66};
Heap_new h=new Heap_new();
h.kthLargest(arr,arr.length,k);
int i=0;
for(i=0;iSystem.out.println(arr[i]);

}


}



Run Here https://ideone.com/UKAzU

C++ Code for Kth Maximum In Array


#include
#include
using namespace std;

void swap(int *x, int *y) {
int temp = *x;
*x = *y;
*y = temp;
}

class Heap
{
int *arr; // pointer to array of elements in heap
int heap_size;
public:
Heap(int a[], int size);
void buildminHeap();
void minHeapify(int );
void heapSort();
void changeRoot(int x);
int getRoot() {return arr[0];}
int parent(int i){ return (i-1)/2; } ;
int left(int i) { return (2*i + 1); } ;
int right(int i) { return (2*i + 2); } ;
};

Heap::Heap(int a[], int size) {
heap_size = size;
arr = a;
}

void Heap::changeRoot(int x)
{
int root = arr[0];
if (root < x)
{
arr[0] = x;
}
minHeapify(0);
}

void Heap::minHeapify(int i) {
int l = left(i);
int r = right(i);
int largest;
if (l < heap_size && arr[l] < arr[i])
largest = l;
else
largest = i;
if (r < heap_size && arr[r] < arr[largest])
largest = r;
if (largest != i)
{
swap(&arr[i], &arr[largest]);
minHeapify(largest);
}
}

void Heap::buildminHeap() {
int i = (heap_size - 1)/2;
while (i >= 0)
{
minHeapify(i);
i--;
}
}

void kthLargest(int arr[], int n, int k)
{
Heap hp(arr, k);
hp.buildminHeap();
int i;
for(i = k; i < n; i++)
{
hp.changeRoot(arr[i]);
}

}

int main()
{
int k = 4;
int arr[] = {12, 34, 10, 22, 9, 4, 56};
int n = sizeof(arr)/sizeof(arr[0]);
kthLargest(arr, n, k);


int i=0;
for(i=0;iprintf(" %d ",arr[i]);

getchar();
return 0;
}


Run here https://ideone.com/f8Or0

C++ Code For Kth Minimum In Array

#include
#include
using namespace std;

void swap(int *x, int *y) {
int temp = *x;
*x = *y;
*y = temp;
}

class Heap
{
int *arr; // pointer to array of elements in heap
int heap_size;
public:
Heap(int a[], int size);
void buildmaxHeap();
void maxHeapify(int );
void heapSort();
void changeRoot(int x);
int getRoot() {return arr[0];}
int parent(int i){ return (i-1)/2; } ;
int left(int i) { return (2*i + 1); } ;
int right(int i) { return (2*i + 2); } ;
};

Heap::Heap(int a[], int size) {
heap_size = size;
arr = a;
}

void Heap::changeRoot(int x)
{
int root = arr[0];
if (root > x)
{
arr[0] = x;
}
maxHeapify(0);
}

void Heap::maxHeapify(int i) {
int l = left(i);
int r = right(i);
int largest;
if (l < heap_size && arr[l] >arr[i])
largest = l;
else
largest = i;
if (r < heap_size && arr[r] > arr[largest])
largest = r;
if (largest != i)
{
swap(&arr[i], &arr[largest]);
maxHeapify(largest);
}
}

void Heap::buildmaxHeap() {
int i = (heap_size - 1)/2;
while (i >= 0)
{
maxHeapify(i);
i--;
}
}

int kthMinimum(int arr[], int n, int k)
{
Heap hp(arr, k);
hp.buildmaxHeap();
int i;
for(i = k; i < n; i++)
{
hp.changeRoot(arr[i]);
}
return hp.getRoot();
}

int main()
{
int k = 4;
int arr[] = {12, 34, 10, 8, 9, 4, 56};
int n = sizeof(arr)/sizeof(arr[0]);
printf(" %d ", kthMinimum(arr, n, k));
int i=0;
for(i=0;i printf(" %d ",arr[i]);

getchar();
return 0;
}

Run Here https://ideone.com/JIu1s

Source Sandeep
Enjoy

WAP to SUM the Fibonnaci Series

#include
#include
long int fib(long int);
int main()
{
long int sum=0;
long int k;
int i,n;
printf("\nEnter the number of element in the series : ");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
k=fib(i);
sum=sum+k;
}
printf("sum of %ld",sum);
return (0);
}
long int fib(long int n)
{
if(n<=1)
{
return n;
}
else
{
return fib(n-1)+fib(n-2);
}
}

Hash Table Implementation Using Linear Probing

import java.io.*;
class hash
{
public static void main(String args[]) throws Exception
{
int n=11,l,i,k,flag;
int a[]=new int[11];
int hash[]=new int[11];
BufferedReader cin= new BufferedReader (new InputStreamReader(System.in));
System.out.println("Enter the elements ");
for(i=0;i {
a[i]= Integer.parseInt(cin.readLine());
hash[i]=0;
}
for(i=0;i {
k=(2*a[i]+5)%11;
flag=0;
while(flag!=1){
if(hash[k]==0){
hash[k]=a[i];
flag=1;
}
else
k=(k+1)%11;//linear probing
}
}
System.out.println("hash table is");
for(i=0;i System.out.print(i+"\t");
System.out.println(hash[i]);
}
}
}


TC O(n)
Sc O(n)
Rune https://ideone.com/xdpXr

WAP to Convert Decimal to BInary Without An Extra Memory

#include

void showbits ( int n )
{
int i, k, andmask ;
for ( i = 8 ; i >= 0 ; i-- )
{
andmask = 1 << i ;
k = n & andmask ;
k == 0 ? printf ( "0" ) : printf ( "1" ) ;
}
}

int main()
{
showbits(10);


}

WAP to Sort 2D Array/Matrix

// --Sorting Program--
// -------------------
// Example Program to sort
// 2D array using linear
// representation of the array
#include

#define MAX 3

int main(void)
{
int arr[MAX][MAX]={{8,9,7},{3,2,1},{5,4,6}} ;
int i,j,temp;
int *arr_ptr;



// we have taken a pointer
// to the 2D array to
// represent it linearly

// C-style type cast
// is necessary here
arr_ptr=(int*)arr;

// sorting is done here.
// selection sort method of
// sorting is employed here
// you can use whichever
// method you like

// here MAX*MAX is used
// because the no. of elements
// in the linear representation
// of the 2D array has that
// many elements
for(i=0;i<((MAX*MAX)-1);i++)
for(j=i+1;j<(MAX*MAX);j++)
if(*(arr_ptr+i)>*(arr_ptr+j))
{
temp=*(arr_ptr+i);
*(arr_ptr+i)=*(arr_ptr+j);
*(arr_ptr+j)=temp;
}
// sorting is done till here



for(i=0;i {
for(j=0;j printf(" %d ",arr[i][j]);
printf(" \n");
}
}

WAP to Check Integer OverFlow in Differnt Logical & Arithmetic Operation

Write a “C” function, int addOvf(int* result, int a, int b) If there is no overflow, the function places the resultant = sum a+b in “result” and returns 0. Otherwise it returns -1. The solution of casting to long and adding to find detecting the overflow is not allowed.

Method 1
There can be overflow only if signs of two numbers are same, and sign of sum is opposite to the signs of numbers.

1) Calculate sum
2) If both numbers are positive and sum is negative then return -1
Else
If both numbers are negative and sum is positive then return -1
Else return 0

?
#include
#include

/* Takes pointer to result and two numbers as
arguments. If there is no overflow, the function
places the resultant = sum a+b in “result” and
returns 0, otherwise it returns -1 */
int addOvf(int* result, int a, int b)
{
*result = a + b;
if(a > 0 && b > 0 && *result < 0)
return -1;
if(a < 0 && b < 0 && *result > 0)
return -1;
return 0;
}

int main()
{
int *res = (int *)malloc(sizeof(int));
int x = 2147483640;
int y = 10;

printf("%d", addOvf(res, x, y));

printf("\n %d", *res);
getchar();
return 0;
}

Time Complexity : O(1)
Space Complexity: O(1)


Method 2

#include
#include
#include

int addOvf(int* result, int a, int b)
{
if( a > INT_MAX - b)
return -1;
else
{
*result = a + b;
return 0;
}
}

int main()
{
int *res = (int *)malloc(sizeof(int));
int x = 2147483640;
int y = 10;

printf("%d", addOvf(res, x, y));
printf("\n %d", *res);
getchar();
return 0;
}

Time Complexity : O(1)
Space Complexity: O(1)


Source http://joyofprogramming.com/Docs_ColumnArticles/27-JoP-Mar-09.pdf

WAP to Compute modulus division by a power-of-2-number

Compute n modulo d without division(/) and modulo(%) operators, where d is a power of 2 number.

Let ith bit from right is set in d. For getting n modulus d, we just need to return 0 to i-1 (from right) bits of n as they are and other bits as 0.

For example if n = 6 (00..110) and d = 4(00..100). Last set bit in d is at position 3 (from right side). So we need to return last two bits of n as they are and other bits as 0, i.e., 00..010.

#include

/* This function will return n % d.
d must be one of: 1, 2, 4, 8, 16, 32, … */
unsigned int getModulo(unsigned int n, unsigned int d)
{
return ( n & (d-1) );
}

/* Driver program to test above function */
int main()
{
unsigned int n = 6;
unsigned int d = 4; /*d must be a power of 2*/
printf("%u moduo %u is %u", n, d, getModulo(n, d));

getchar();
return 0;
}


Source http://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs

WAP for Find Prime Factor Number (Prime Factors Only)

#include

double sqroot(const double s)
{

double xn = s / 2.0;
double lastX = 0.0;

// Looping this way ensures we perform only as many calculations as necessary.
// Can be replaced with a static for loop if you really want to.
while(xn != lastX)
{
lastX = xn;
xn = (xn + s/xn) / 2.0;
}
return xn;
}

int main()
{
int n=100,i;
int upper_bound=(int)sqroot(n);
for(i=2;i<=upper_bound;i++)
{
if(n%i==0)
{
printf("%d,",i);
n=n/i;
i--;
if(n==1)
break;
}
}

}

Time Complexity O(sqrt(n))
Space Complexity O(1)
Run Here https://ideone.com/ot5Y3

More Info http://mathworld.wolfram.com/PrimeFactor.html

WAP for External Sorting

/* external sort */

#include
#include
#include

/****************************
* implementation dependent *
****************************/

/* template for workfiles (8.3 format) */
#define FNAME "_sort%03d.dat"
#define LNAME 13

/* comparison operators */
#define compLT(x,y) (x < y)
#define compGT(x,y) (x > y)

/* define the record to be sorted here */
#define LRECL 100
typedef int keyType;
typedef struct recTypeTag {
keyType key; /* sort key for record */
#if LRECL
char data[LRECL-sizeof(keyType)]; /* other fields */
#endif
} recType;

/******************************
* implementation independent *
******************************/

typedef enum {false, true} bool;

typedef struct tmpFileTag {
FILE *fp; /* file pointer */
char name[LNAME]; /* filename */
recType rec; /* last record read */
int dummy; /* number of dummy runs */
bool eof; /* end-of-file flag */
bool eor; /* end-of-run flag */
bool valid; /* true if rec is valid */
int fib; /* ideal fibonacci number */
} tmpFileType;

static tmpFileType **file; /* array of file info for tmp files */
static int nTmpFiles; /* number of tmp files */
static char *ifName; /* input filename */
static char *ofName; /* output filename */

static int level; /* level of runs */
static int nNodes; /* number of nodes for selection tree */

void deleteTmpFiles(void) {
int i;

/* delete merge files and free resources */
if (file) {
for (i = 0; i < nTmpFiles; i++) {
if (file[i]) {
if (file[i]->fp) fclose(file[i]->fp);
if (*file[i]->name) remove(file[i]->name);
free (file[i]);
}
}
free (file);
}
}

void termTmpFiles(int rc) {

/* cleanup files */
remove(ofName);
if (rc == 0) {
int fileT;

/* file[T] contains results */
fileT = nTmpFiles - 1;
fclose(file[fileT]->fp); file[fileT]->fp = NULL;
if (rename(file[fileT]->name, ofName)) {
perror("io1");
deleteTmpFiles();
exit(1);
}
*file[fileT]->name = 0;
}
deleteTmpFiles();
}

void cleanExit(int rc) {

/* cleanup tmp files and exit */
termTmpFiles(rc);
exit(rc);
}

void *safeMalloc(size_t size) {
void *p;

/* safely allocate memory and initialize to zero */
if ((p = calloc(1, size)) == NULL) {
printf("error: malloc failed, size = %d\n", size);
cleanExit(1);
}
return p;
}

void initTmpFiles(void) {
int i;
tmpFileType *fileInfo;

/* initialize merge files */
if (nTmpFiles < 3) nTmpFiles = 3;
file = safeMalloc(nTmpFiles * sizeof(tmpFileType*));
fileInfo = safeMalloc(nTmpFiles * sizeof(tmpFileType));
for (i = 0; i < nTmpFiles; i++) {
file[i] = fileInfo + i;
sprintf(file[i]->name, FNAME, i);
if ((file[i]->fp = fopen(file[i]->name, "w+b")) == NULL) {
perror("io2");
cleanExit(1);
}
}
}

recType *readRec(void) {

typedef struct iNodeTag { /* internal node */
struct iNodeTag *parent;/* parent of internal node */
struct eNodeTag *loser; /* external loser */
} iNodeType;

typedef struct eNodeTag { /* external node */
struct iNodeTag *parent;/* parent of external node */
recType rec; /* input record */
int run; /* run number */
bool valid; /* input record is valid */
} eNodeType;

typedef struct nodeTag {
iNodeType i; /* internal node */
eNodeType e; /* external node */
} nodeType;

static nodeType *node; /* array of selection tree nodes */
static eNodeType *win; /* new winner */
static FILE *ifp; /* input file */
static bool eof; /* true if end-of-file, input */
static int maxRun; /* maximum run number */
static int curRun; /* current run number */
iNodeType *p; /* pointer to internal nodes */
static bool lastKeyValid; /* true if lastKey is valid */
static keyType lastKey; /* last key written */

/* read next record using replacement selection */

/* check for first call */
if (node == NULL) {
int i;

if (nNodes < 2) nNodes = 2;
node = safeMalloc(nNodes * sizeof(nodeType));
for (i = 0; i < nNodes; i++) {
node[i].i.loser = &node[i].e;
node[i].i.parent = &node[i/2].i;
node[i].e.parent = &node[(nNodes + i)/2].i;
node[i].e.run = 0;
node[i].e.valid = false;
}
win = &node[0].e;
lastKeyValid = false;

if ((ifp = fopen(ifName, "rb")) == NULL) {
printf("error: file %s, unable to open\n", ifName);
cleanExit(1);
}
}

while (1) {

/* replace previous winner with new record */
if (!eof) {
if (fread(&win->rec, sizeof(recType), 1, ifp) == 1) {
if ((!lastKeyValid || compLT(win->rec.key, lastKey))
&& (++win->run > maxRun))
maxRun = win->run;
win->valid = true;
} else if (feof(ifp)) {
fclose(ifp);
eof = true;
win->valid = false;
win->run = maxRun + 1;
} else {
perror("io4");
cleanExit(1);
}
} else {
win->valid = false;
win->run = maxRun + 1;
}

/* adjust loser and winner pointers */
p = win->parent;
do {
bool swap;
swap = false;
if (p->loser->run < win->run) {
swap = true;
} else if (p->loser->run == win->run) {
if (p->loser->valid && win->valid) {
if (compLT(p->loser->rec.key, win->rec.key))
swap = true;
} else {
swap = true;
}
}
if (swap) {
/* p should be winner */
eNodeType *t;

t = p->loser;
p->loser = win;
win = t;
}
p = p->parent;
} while (p != &node[0].i);

/* end of run? */
if (win->run != curRun) {
/* win->run = curRun + 1 */
if (win->run > maxRun) {
/* end of output */
free(node);
return NULL;
}
curRun = win->run;
}

/* output top of tree */
if (win->run) {
lastKey = win->rec.key;
lastKeyValid = true;
return &win->rec;
}
}
}

void makeRuns(void) {
recType *win; /* winner */
int fileT; /* last file */
int fileP; /* next to last file */
int j; /* selects file[j] */


/* Make initial runs using replacement selection.
* Runs are written using a Fibonacci distintbution.
*/

/* initialize file structures */
fileT = nTmpFiles - 1;
fileP = fileT - 1;
for (j = 0; j < fileT; j++) {
file[j]->fib = 1;
file[j]->dummy = 1;
}
file[fileT]->fib = 0;
file[fileT]->dummy = 0;

level = 1;
j = 0;


win = readRec();
while (win) {
bool anyrun;

anyrun = false;
for (j = 0; win && j <= fileP; j++) {
bool run;

run = false;
if (file[j]->valid) {
if (!compLT(win->key, file[j]->rec.key)) {
/* append to an existing run */
run = true;
} else if (file[j]->dummy) {
/* start a new run */
file[j]->dummy--;
run = true;
}
} else {
/* first run in file */
file[j]->dummy--;
run = true;
}

if (run) {
anyrun = true;

/* flush run */
while(1) {
if (fwrite(win, sizeof(recType), 1, file[j]->fp) != 1) {
perror("io3");
cleanExit(1);
}
file[j]->rec.key = win->key;
file[j]->valid = true;
if ((win = readRec()) == NULL) break;
if (compLT(win->key, file[j]->rec.key)) break;
}
}
}

/* if no room for runs, up a level */
if (!anyrun) {
int t;
level++;
t = file[0]->fib;
for (j = 0; j <= fileP; j++) {
file[j]->dummy = t + file[j+1]->fib - file[j]->fib;
file[j]->fib = t + file[j+1]->fib;
}
}
}
}

void rewindFile(int j) {
/* rewind file[j] and read in first record */
file[j]->eor = false;
file[j]->eof = false;
rewind(file[j]->fp);
if (fread(&file[j]->rec, sizeof(recType), 1, file[j]->fp) != 1) {
if (feof(file[j]->fp)) {
file[j]->eor = true;
file[j]->eof = true;
} else {
perror("io5");
cleanExit(1);
}
}
}

void mergeSort(void) {
int fileT;
int fileP;
int j;
tmpFileType *tfile;

/* polyphase merge sort */

fileT = nTmpFiles - 1;
fileP = fileT - 1;

/* prime the files */
for (j = 0; j < fileT; j++) {
rewindFile(j);
}

/* each pass through loop merges one run */
while (level) {
while(1) {
bool allDummies;
bool anyRuns;

/* scan for runs */
allDummies = true;
anyRuns = false;
for (j = 0; j <= fileP; j++) {
if (!file[j]->dummy) {
allDummies = false;
if (!file[j]->eof) anyRuns = true;
}
}

if (anyRuns) {
int k;
keyType lastKey;

/* merge 1 run file[0]..file[P] --> file[T] */

while(1) {
/* each pass thru loop writes 1 record to file[fileT] */

/* find smallest key */
k = -1;
for (j = 0; j <= fileP; j++) {
if (file[j]->eor) continue;
if (file[j]->dummy) continue;
if (k < 0 ||
(k != j && compGT(file[k]->rec.key, file[j]->rec.key)))
k = j;
}
if (k < 0) break;

/* write record[k] to file[fileT] */
if (fwrite(&file[k]->rec, sizeof(recType), 1,
file[fileT]->fp) != 1) {
perror("io6");
cleanExit(1);
}

/* replace record[k] */
lastKey = file[k]->rec.key;
if (fread(&file[k]->rec, sizeof(recType), 1,
file[k]->fp) == 1) {
/* check for end of run on file[s] */
if (compLT(file[k]->rec.key, lastKey))
file[k]->eor = true;
} else if (feof(file[k]->fp)) {
file[k]->eof = true;
file[k]->eor = true;
} else {
perror("io7");
cleanExit(1);
}
}

/* fixup dummies */
for (j = 0; j <= fileP; j++) {
if (file[j]->dummy) file[j]->dummy--;
if (!file[j]->eof) file[j]->eor = false;
}

} else if (allDummies) {
for (j = 0; j <= fileP; j++)
file[j]->dummy--;
file[fileT]->dummy++;
}

/* end of run */
if (file[fileP]->eof && !file[fileP]->dummy) {
/* completed a fibonocci-level */
level--;
if (!level) {
/* we're done, file[fileT] contains data */
return;
}

/* fileP is exhausted, reopen as new */
fclose(file[fileP]->fp);
if ((file[fileP]->fp = fopen(file[fileP]->name, "w+b"))
== NULL) {
perror("io8");
cleanExit(1);
}
file[fileP]->eof = false;
file[fileP]->eor = false;

rewindFile(fileT);

/* f[0],f[1]...,f[fileT] <-- f[fileT],f[0]...,f[T-1] */
tfile = file[fileT];
memmove(file + 1, file, fileT * sizeof(tmpFileType*));
file[0] = tfile;

/* start new runs */
for (j = 0; j <= fileP; j++)
if (!file[j]->eof) file[j]->eor = false;
}
}

}
}


void extSort(void) {
initTmpFiles();
makeRuns();
mergeSort();
termTmpFiles(0);
}

int main(int argc, char *argv[]) {

/* command-line:
*
* ext ifName ofName nTmpFiles nNodes
*
* ext in.dat out.dat 5 2000
* reads in.dat, sorts using 5 files and 2000 nodes, output to out.dat
*/
if (argc != 5) {
printf("%s ifName ofName nTmpFiles nNodes\n", argv[0]);
cleanExit(1);
}

ifName = argv[1];
ofName = argv[2];
nTmpFiles = atoi(argv[3]);
nNodes = atoi(argv[4]);

printf("extSort: nFiles=%d, nNodes=%d, lrecl=%d\n",
nTmpFiles, nNodes, sizeof(recType));

extSort();

return 0;
}

WAP Horner Rule

coefficients := [-19, 7, -4, 6] # list coefficients of all x^0..x^n in order
x := 3
accumulator := 0
for i in length(coefficients) downto 1 do
# Assumes 1-based indexing for arrays
accumulator := ( accumulator * x ) + coefficients[i]
done
# accumulator now has the answer



A fast scheme for evaluating a polynomial such as:

-19+7x-4x^2+6x^3,

when

x=3;.

is to arrange the computation as follows:

((((0) x + 6) x + (-4)) x + 7) x + (-19;

And compute the result from the innermost brackets outwards as in this pseudocode:


#include

double horner(double *coeffs, int s, double x)
{
int i;
double res = 0.0;

for(i=s-1; i >= 0; i--)
{
res = res * x + coeffs[i];
}
return res;
}


int main()
{
double coeffs[] = { 3.0, 2.0, 1.0, 1.0 };

printf("%5.1f\n", horner(coeffs, sizeof(coeffs)/sizeof(double), 2.0));
return 0;
}

TC O(n)
SC O(1)
Run Here https://ideone.com/uGAZC

Write C code to implement the strstr() (search for a substring) function.

This is also one of the most frequently asked interview questions. Its asked almost 99% of the times. Here are a few C programs to implement your own strstr() function.

There are a number of ways to find a string inside another string. Its important to be aware of these algorithms than to memorize them. Some of the fastest algorithms are quite tough to understand!.


Method1

The first method is the classic Brute force method. The Brute Force algorithm checks, at all positions in the text between 0 and (n-m), if an occurrence of the pattern starts at that position or not. Then, after each successfull or unsuccessful attempt, it shifts the pattern exactly one position to the right. The time complexity of this searching phase is O(mn). The expected number of text character comparisons is 2n.

Here 'n' is the size of the string in which the substring of size 'm' is being searched for.

Here is some code (which works!)



#include

void BruteForce(char *x /* pattern */,
int m /* length of the pattern */,
char *y /* actual string being searched */,
int n /* length of this string */)
{
int i, j;
printf("\nstring : [%s]"
"\nlength : [%d]"
"\npattern : [%s]"
"\nlength : [%d]\n\n", y,n,x,m);


/* Searching */
for (j = 0; j <= (n - m); ++j)
{
for (i = 0; i < m && x[i] == y[i + j]; ++i);
if (i >= m) {printf("\nMatch found at\n\n->[%d]\n->[%s]\n",j,y+j);}
}
}


int main()
{
char *string = "hereroheroero";
char *pattern = "hero";

BF(pattern,strlen(pattern),string,strlen(string));
printf("\n\n");
return(0);
}




This is how the comparison happens visually


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
|||| ----> Match!
hero


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
!
hero







Method2

The second method is called the Rabin-Karp method.

Instead of checking at each position of the text if the pattern occurs or not, it is better to check first if the contents of the current string "window" looks like the pattern or not. In order to check the resemblance between these two patterns, a hashing function is used. Hashing a string involves computing a numerical value from the value of its characters using a hash function.

The Rabin-Karp method uses the rule that if two strings are equal, their hash values must also be equal. Note that the converse of this statement is not always true, but a good hash function tries to reduce the number of such hash collisions. Rabin-Karp computes hash value of the pattern, and then goes through the string computing hash values of all of its substrings and checking if the pattern's hash value is equal to the substring hash value, and advancing by 1 character every time. If the two hash values are the same, then the algorithm verifies if the two string really are equal, rather than this being a fluke of the hashing scheme. It uses regular string comparison for this final check. Rabin-Karp is an algorithm of choice for multiple pattern search. If we want to find any of a large number, say k, fixed length patterns in a text, a variant Rabin-Karp that uses a hash table to check whether the hash of a given string belongs to a set of hash values of patterns we are looking for. Other algorithms can search for a single pattern in time order O(n), hence they will search for k patterns in time order O(n*k). The variant Rabin-Karp will still work in time order O(n) in the best and average case because a hash table allows to check whether or not substring hash equals any of the pattern hashes in time order of O(1).

Here is some code (not working though!)


#include

hashing_function()
{
// A hashing function to compute the hash values of the strings.
....
}

void KarpRabinR(char *x, int m, char *y, int n)
{
int hx, hy, i, j;

printf("\nstring : [%s]"
"\nlength : [%d]"
"\npattern : [%s]"
"\nlength : [%d]\n\n", y,n,x,m);


/* Preprocessing phase */
Do preprocessing here..

/* Searching */
j = 0;
while (j <= n-m)
{
if (hx == hy && memcmp(x, y + j, m) == 0)
{
// Hashes match and so do the actual strings!
printf("\nMatch found at : [%d]\n",j);
}

hy = hashing_function(y[j], y[j + m], hy);
++j;
}
}


int main()
{

char *string="hereroheroero";
char *pattern="hero";

KarpRabin(pattern,strlen(pattern),string,strlen(string));

printf("\n\n");
return(0);

}



This is how the comparison happens visually


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
|||| ----> Hash values match, so do the strings!
hero


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
!
hero





Method3

The Knuth-Morris-Pratt or the Morris-Pratt algorithms are extensions of the basic Brute Force algorithm. They use precomputed data to skip forward not by 1 character, but by as many as possible for the search to succeed.

Here is some code


void preComputeData(char *x, int m, int Next[])
{
int i, j;
i = 0;
j = Next[0] = -1;

while (i < m)
{
while (j > -1 && x[i] != x[j])
j = Next[j];
Next[++i] = ++j;

}
}


void MorrisPrat(char *x, int m, char *y, int n)
{
int i, j, Next[1000];

/* Preprocessing */
preComputeData(x, m, Next);

/* Searching */
i = j = 0;
while (j < n)
{
while (i > -1 && x[i] != y[j])
i = Next[i];
i++;
j++;
if (i >= m)
{
printf("\nMatch found at : [%d]\n",j - i);
i = Next[i];
}
}
}


int main()
{
char *string="hereroheroero";
char *pattern="hero";

MorrisPrat(pattern,strlen(pattern),string,strlen(string));

printf("\n\n");
return(0);
}



This is how the comparison happens visually


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
!
hero


hereroheroero
!
hero



hereroheroero
|||| ----> Match found!
hero


hereroheroero
!
hero




Method4

The Boyer Moore algorithm is the fastest string searching algorithm. Most editors use this algorithm.

It compares the pattern with the actual string from right to left. Most other algorithms compare from left to right. If the character that is compared with the rightmost pattern symbol does not occur in the pattern at all, then the pattern can be shifted by m positions behind this text symbol.


The following example illustrates this situation.

Example:


0 1 2 3 4 5 6 7 8 9 ...
a b b a d a b a c b a
| |
b a b a c |
<------ |
|
b a b a c


The comparison of "d" with "c" at position 4 does not match. "d" does not occur in the pattern. Therefore, the pattern cannot match at any of the positions 0,1,2,3,4, since all corresponding windows contain a "d". The pattern can be shifted to position 5. The best case for the Boyer-Moore algorithm happens if, at each search attempt the first compared character does not occur in the pattern. Then the algorithm requires only O(n/m) comparisons .

Bad character heuristics

This method is called bad character heuristics. It can also be applied if the bad character (the character that causes a mismatch), occurs somewhere else in the pattern. Then the pattern can be shifted so that it is aligned to this text symbol. The next example illustrates this situation.


Example:


0 1 2 3 4 5 6 7 8 9 ...
a b b a b a b a c b a
|
b a b a c
<----
|
b a b a c



Comparison between "b" and "c" causes a mismatch. The character "b" occurs in the pattern at positions 0 and 2. The pattern can be shifted so that the rightmost "b" in the pattern is aligned to "b".


Good suffix heuristics

Sometimes the bad character heuristics fails. In the following situation the comparison between "a" and "b" causes a mismatch. An alignment of the rightmost occurence of the pattern symbol a with the text symbol a would produce a negative shift. Instead, a shift by 1 would be possible. However, in this case it is better to derive the maximum possible shift distance from the structure of the pattern. This method is called good suffix heuristics.

Example:


0 1 2 3 4 5 6 7 8 9 ...
a b a a b a b a c b a
| | |
c a b a b
<----
| | |
c a b a b


The suffix "ab" has matched. The pattern can be shifted until the next occurence of ab in the pattern is aligned to the text symbols ab, i.e. to position 2.


In the following situation the suffix "ab" has matched. There is no other occurence of "ab" in the pattern.Therefore, the pattern can be shifted behind "ab", i.e. to position 5.

Example:


0 1 2 3 4 5 6 7 8 9 ...
a b c a b a b a c b a
| | |
c b a a b
c b a a b



In the following situation the suffix "bab" has matched. There is no other occurence of "bab" in the pattern. But in this case the pattern cannot be shifted to position 5 as before, but only to position 3, since a prefix of the pattern "ab" matches the end of "bab". We refer to this situation as case 2 of the good suffix heuristics.

Example:


0 1 2 3 4 5 6 7 8 9 ...
a a b a b a b a c b a
| | | |
a b b a b
a b b a b



The pattern is shifted by the longest of the two distances that are given by the bad character and the good suffix heuristics.

The Boyer-Moore algorithm uses two different heuristics for determining the maximum possible shift distance in case of a mismatch: the "bad character" and the "good suffix" heuristics. Both heuristics can lead to a shift distance of m. For the bad character heuristics this is the case, if the first comparison causes a mismatch and the corresponding text symbol does not occur in the pattern at all. For the good suffix heuristics this is the case, if only the first comparison was a match, but that symbol does not occur elsewhere in the pattern.


More Resources

http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node41.html
http://www.cs.aau.dk/~simas/aalg04/slides/aalg3.ppt
http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_string_search_algorithm