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 Print All Possible Combination of Balanced Parenthesis

# include
# define MAX_SIZE 100

void _printParenthesis(int pos, int n, int open, int close);

/* Wrapper over _printParenthesis()*/
void printParenthesis(int n)
{
if(n > 0)
_printParenthesis(0, n, 0, 0);
return;
}

void _printParenthesis(int pos, int n, int open, int close)
{
static char str[MAX_SIZE];

if(close == n)
{
printf("%s \n", str);
return;
}
else
{
if(open > close) {
str[pos] = '}';
_printParenthesis(pos+1, n, open, close+1);
}
if(open < n) {
str[pos] = '{';
_printParenthesis(pos+1, n, open+1, close);
}
}
}

/* driver program to test above functions */
int main()
{
int n = 3;
printParenthesis(n);
getchar();
return 0;
}

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

Hash Table Implementation Using Quadratic probing

import java.io.*;
class hash_quadratic{
public static void main(String args[]) throws Exception{
int n=11,i,k,j,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 to be sorted");
for(i=0;i a[i]= Integer.parseInt(cin.readLine());
hash[i]=0;
}
for(i=0;i flag=0;
j=0;
while(flag!=1){
k=((2*a[i]+5)%11+j*j)%11;
if(hash[k]==0){
hash[k]=a[i];
flag=1;}
else{
j++;
}

}
}
System.out.println("hash table is");
for(i=0;i System.out.print(i+"\t");
System.out.println(hash[i]);
}
}
}

Run Here https://ideone.com/7CsuT

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 Remove Remove vowels from a string in place.

This is asked in many preliminary tech interviews.

Question:

Write a program to remove all vowels from a string in place.

The key to solving this is that since we are removing characters from the string, the resultant string length will be less than or equal to the original string's length. So, the idea here would be to accumulate all the vowels and push them towards the end of the string and at the end, if we keep a running count of the number of vowels in the string and we already know the length of the original string, we can place our C string terminating null char at the appropriate position to give us a new string, sans the vowels. The algorithm in plain words is as follows:

We run across the word from left to right. The first time we encounter a vowel, we store that position (the index if you look at the string as a char array) in the string in a variable.

Each time we encounter a consonant we swap its position with the position of the vowel and just increment the index that points to the vowel. If another vowel is encountered, we just increment a count that stores the vowels encountered thus far.

This keeps all the vowels contiguous in the string and as each swap with a consonant happens, this contiguous block of vowels gets pushed further down the string until we reach the end of string. We can then just put a null char at (n - vowel_count) where n is the length of the original string.

For the example word PEEPERS:

1. vowel_count=0, vowel_start_index=-1
2. P is encountered first, do nothing because we haven't come across a vowel yet.
3. E is encountered next, so vowel_count=1 and vowel_start_index=1 (assuming 0 based array indices. So the first E is at position number 1 in the string PEEPERS
4. E is encountered again, so vowel_count=2
5. P is encountered next, its a consonant so swap position of P with position held in vowel_start_index. Then increment vowel_start_index. So the string looks like PPEEERS and vowel_start_index=2
6. E is encountered next (this is the third E in PEEPERS). vowel_count becomes 3.
7. R is encountered. Its a consonant so swap it with character held at vowel_start_index (which is 2). So the string becomes PPREEES and increment vowel_start_index to 3
8. Finally we come across S. Do the same as above and whola!! You have the string PPRSEEE with vowel_count = 3.
9. Now just place a null at (n - vowel_count) = 7-3 = 4 and you have the string PPRS which is the desired output.

The code is as follows. It uses C++ string but can easily be emulated for C style strings.
We scan through the string only once and no extra storage space is used. So time complexity is O(n) and space complexity is O(1).

#include

bool isVowel(char a)
{
if(a == 'a' || a == 'A' ||
a == 'e' || a == 'E' ||
a == 'i' || a == 'I' ||
a == 'o' || a == 'O' ||
a == 'u' || a == 'U')
return true;
else
return false;
}

void removeLetters(std::string& s)
{
int len = s.length();
int vcount = 0;
int vstart = -1;

for(int i=0; i {
if(isVowel(s[i]))
{
if(vstart == -1)
vstart = i;
vcount++;
}

if(!isVowel(s[i]) && vstart != -1)
{
/* Encountered letter is a consonant. So do swap.
The below method for swap does not need a tmp variable */
s[i] = s[i] + s[vstart];
s[vstart] = s[i] - s[vstart];
s[i] = s[i] - s[vstart];
vstart++;
}
}
s = s.substr(0, len-vcount);
}

int main(int argc, char** argv)
{
std::string s = "the rain in spain is mainly from the plains.";
removeLetters(s);
std::cout << s << std::endl;
return 0;
}

Compute the minimum or maximum of two integers without branching

/* The obvious approach to find minimum (involves branching) */
int min(int x, int y)
{
return (x < y) ? x : y
}

Below are the methods to get minimum(or maximum) without using branching. Typically, the obvious approach is best, though.

Method 1(Use XOR and comparison operator)

Minimum of x and y will be

y ^ ((x ^ y) & -(x < y))

It works because if x < y, then -(x < y) will be all ones, so r = y ^ (x ^ y) & ~0 = y ^ x ^ y = x. Otherwise, if x >= y, then -(x < y) will be all zeros, so r = y ^ ((x ^ y) & 0) = y. On some machines, evaluating (x < y) as 0 or 1 requires a branch instruction, so there may be no advantage.

To find the maximum, use

x ^ ((x ^ y) & -(x < y));

?
#include

/*Function to find minimum of x and y*/
int min(int x, int y)
{
return y ^ ((x ^ y) & -(x < y));
}

/*Function to find maximum of x and y*/
int max(int x, int y)
{
return x ^ ((x ^ y) & -(x < y));
}

/* Driver program to test above functions */
int main()
{
int x = 15;
int y = 6;
printf("Minimum of %d and %d is ", x, y);
printf("%d", min(x, y));
printf("\nMaximum of %d and %d is ", x, y);
printf("%d", max(x, y));
getchar();
}

Method 2(Use subtraction and shift)
If we know that

INT_MIN <= (x - y) <= INT_MAX

, then we can use the following, which are faster because (x - y) only needs to be evaluated once.

Minimum of x and y will be

y + ((x - y) & ((x - y) >>(sizeof(int) * CHAR_BIT - 1)))

This method shifts the subtraction of x and y by 31 (if size of integer is 32). If (x-y) is smaller than 0, then (x -y)>>31 will be 1. If (x-y) is greater than or equal to 0, then (x -y)>>31 will be 0.
So if x >= y, we get minimum as y + (x-y)&0 which is y.
If x < y, we get minimum as y + (x-y)&1 which is x.

Similarly, to find the maximum use

x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)))

?
#include
#define CHAR_BIT 8

/*Function to find minimum of x and y*/
int min(int x, int y)
{
return y + ((x - y) & ((x - y) >>
(sizeof(int) * CHAR_BIT - 1)));
}

/*Function to find maximum of x and y*/
int max(int x, int y)
{
return x - ((x - y) & ((x - y) >>
(sizeof(int) * CHAR_BIT - 1)));
}

/* Driver program to test above functions */
int main()
{
int x = 15;
int y = 6;
printf("Minimum of %d and %d is ", x, y);
printf("%d", min(x, y));
printf("\nMaximum of %d and %d is ", x, y);
printf("%d", max(x, y));
getchar();
}

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

Compute the minimum or maximum of two integers without branching

/* The obvious approach to find minimum (involves branching) */
int min(int x, int y)
{
return (x < y) ? x : y
}

Below are the methods to get minimum(or maximum) without using branching. Typically, the obvious approach is best, though.

Method 1(Use XOR and comparison operator)

Minimum of x and y will be

y ^ ((x ^ y) & -(x < y))

It works because if x < y, then -(x < y) will be all ones, so r = y ^ (x ^ y) & ~0 = y ^ x ^ y = x. Otherwise, if x >= y, then -(x < y) will be all zeros, so r = y ^ ((x ^ y) & 0) = y. On some machines, evaluating (x < y) as 0 or 1 requires a branch instruction, so there may be no advantage.

To find the maximum, use

x ^ ((x ^ y) & -(x < y));

?
#include

/*Function to find minimum of x and y*/
int min(int x, int y)
{
return y ^ ((x ^ y) & -(x < y));
}

/*Function to find maximum of x and y*/
int max(int x, int y)
{
return x ^ ((x ^ y) & -(x < y));
}

/* Driver program to test above functions */
int main()
{
int x = 15;
int y = 6;
printf("Minimum of %d and %d is ", x, y);
printf("%d", min(x, y));
printf("\nMaximum of %d and %d is ", x, y);
printf("%d", max(x, y));
getchar();
}

Method 2(Use subtraction and shift)
If we know that

INT_MIN <= (x - y) <= INT_MAX

, then we can use the following, which are faster because (x - y) only needs to be evaluated once.

Minimum of x and y will be

y + ((x - y) & ((x - y) >>(sizeof(int) * CHAR_BIT - 1)))

This method shifts the subtraction of x and y by 31 (if size of integer is 32). If (x-y) is smaller than 0, then (x -y)>>31 will be 1. If (x-y) is greater than or equal to 0, then (x -y)>>31 will be 0.
So if x >= y, we get minimum as y + (x-y)&0 which is y.
If x < y, we get minimum as y + (x-y)&1 which is x.

Similarly, to find the maximum use

x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)))

?
#include
#define CHAR_BIT 8

/*Function to find minimum of x and y*/
int min(int x, int y)
{
return y + ((x - y) & ((x - y) >>
(sizeof(int) * CHAR_BIT - 1)));
}

/*Function to find maximum of x and y*/
int max(int x, int y)
{
return x - ((x - y) & ((x - y) >>
(sizeof(int) * CHAR_BIT - 1)));
}

/* Driver program to test above functions */
int main()
{
int x = 15;
int y = 6;
printf("Minimum of %d and %d is ", x, y);
printf("%d", min(x, y));
printf("\nMaximum of %d and %d is ", x, y);
printf("%d", max(x, y));
getchar();
}

Note that the 1989 ANSI C specification doesn't specify the result of signed right-shift, so above method is not portable. If exceptions are thrown on overflows, then the values of x and y should be unsigned or cast to unsigned for the subtractions to avoid unnecessarily throwing an exception, however the right-shift needs a signed operand to produce all one bits when negative, so cast to signed there.

WAP to Insert Node in Circuler Linked List In Sorted Order

#include
#include

/* structure for a node */
struct node
{
int data;
struct node *next;
};

/* function to insert a new_node in a list in sorted way.
Note that this function expects a pointer to head_ref
as this can modify the head of the input linked list */
void sortedInsert(struct node** head_ref, struct node* new_node)
{
struct node* current = *head_ref;

if (current == NULL)
{
new_node->next = new_node;
*head_ref = new_node;
}

/* Special case for the head end */
else if (current->data >= new_node->data)
{
/* If value is smaller than head's value then
we need to change next of last node */
while(current->next != *head_ref)
current = current->next;
current->next = new_node;
new_node->next = *head_ref;
*head_ref = new_node;
}
else
{
/* Locate the node before the point of insertion */
while (current->next!= *head_ref && current->next->data < new_node->data)
current = current->next;

new_node->next = current->next;
current->next = new_node;
}
}

/* Function to print nodes in a given linked list */
void printList(struct node *start);

int main()
{
int arr[] = {12, 56, 2, 11, 1, 90};
int list_size, i;

/* start with empty linked list */
struct node *start = NULL;
struct node *temp;

/* Create linked list from the array arr[].
Created linked list will be 1->11->2->56->12 */
for(i = 0; i< 6; i++)
{
temp = (struct node *)malloc(sizeof(struct node));
temp->data = arr[i];
sortedInsert(&start, temp);
}

printList(start);
getchar();
return 0;
}

/* Function to print nodes in a given linked list */
void printList(struct node *start)
{
struct node *temp;

if(start != NULL)
{
temp = start;
printf("\n");
do {
printf("%d ", temp->data);
temp = temp->next;
} while(temp != start);
}
}



https://ideone.com/NdBum

WAP for KMP String Search

e
#include
/* KMP algorithm for string Matching */
main()
{
char *p="This is my first post to this group";
char *T="to this group this is my post";
int len = strlen(p);
int len1 = strlen(T);
printf("len:%d len1:%d\n",len,len1);
int k = 0,i;
int array[40]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
/* Pre processing which takes O(m)*/
for(i = 2; i< len; i++)
{
while(k > 0 && p[k+1] != p[i])
{
k = array[k];
}

if(p[k+1] == p[i])
{
k++;
array[i] = k;
}
}

/* Matching which takes O(n) */
k = 1;
for(i = 0; i< len1; i++)
{

while(k > 0 && p[k+1] != T[i])
{
k = array[k];
}

if(p[k+1] == T[i])
{
k++;
printf("%d %d %c\n",k,i,p[k]);
if(k == 10)
{
printf("String Matched\n");
}
}
}
}

Given a telephone number print or produce all the possible telephone words or combinations of letters that can represent the given telephone number

import java.util.*;

class PhoneMmemonics
{

/**
* Mapping between a digit and the characters it represents
*/
private static Map> numberToCharacters = new
HashMap>();

static {
numberToCharacters.put('0',new ArrayList(Arrays.asList('0')));
numberToCharacters.put('1',new ArrayList(Arrays.asList('1')));
numberToCharacters.put('2',new ArrayList(Arrays.asList('A','B','C')));
numberToCharacters.put('3',new ArrayList(Arrays.asList('D','E','F')));
numberToCharacters.put('4',new ArrayList(Arrays.asList('G','H','I')));
numberToCharacters.put('5',new ArrayList(Arrays.asList('J','K','L')));
numberToCharacters.put('6',new ArrayList(Arrays.asList('M','N','O')));
numberToCharacters.put('7',new ArrayList(Arrays.asList('P','Q','R')));
numberToCharacters.put('8',new ArrayList(Arrays.asList('T','U','V')));
numberToCharacters.put('9',new ArrayList(Arrays.asList('W','X','Y','Z')));
}

/**
* Generates a list of all the mmemonics that can exists for the number
* @param phoneNumber
* @return
*/
public static List getMmemonics(int phoneNumber) {

// prepare results
StringBuilder stringBuffer = new StringBuilder();
List results = new ArrayList();

// generate all the mmenonics
generateMmemonics(Integer.toString(phoneNumber), stringBuffer, results);

// return results
return results;
}

/**
* Recursive helper method to generate all mmemonics
*
* @param partialPhoneNumber Numbers in the phone number that haven't converted to characters yet
* @param partialMmemonic The partial word that we have come up with so far
* @param results total list of all results of complete mmemonics
*/
private static void generateMmemonics(String partialPhoneNumber, StringBuilder partialMmemonic, List results) {

// are we there yet?
if (partialPhoneNumber.length() == 0) {

// base case: so add the mmemonic is complete
results.add(partialMmemonic.toString());
return;
}

// prepare variables for recursion
int currentPartialLength = partialMmemonic.length();
char firstNumber = partialPhoneNumber.charAt(0);
String remainingNumbers = partialPhoneNumber.substring(1);

// for each character that the single number represents
for(Character singleCharacter : numberToCharacters.get(firstNumber)) {

// append single character to our partial mmemonic so far
// and recurse down with the remaining characters
partialMmemonic.setLength(currentPartialLength);
generateMmemonics(remainingNumbers, partialMmemonic.append(singleCharacter), results);
}
}

public static void main(String a[])
{
List results = new ArrayList();
results=getMmemonics(23);

Iterator it=results.iterator();
while(it.hasNext())
{

System.out.println(it.next());
}

}

}


General Formula is Product of (nCr) where n ={0...9} & r={ 1,2,3};
if n=23

AD
AE
AF
BD
BE
BF
CD
CE
CF

3c1 * 3c1=9

for n=234

ADG
ADH
ADI
AEG
AEH
AEI
AFG
AFH
AFI
BDG
BDH
BDI
BEG
BEH
BEI
BFG
BFH
BFI
CDG
CDH
CDI
CEG
CEH
CEI
CFG
CFH
CFI

3c1*3c1*3c1=27

and so on


Another Method

class Program
{
static void Main(string[] args)
{
int[] phoneNumber = new int[]{2,3,4};
List telephoneWords = GetTelephoneWords(phoneNumber, 0);
}

//get all the combinations / telephone words for a given telephone number
static List GetTelephoneWords(int[] numbers, int index)
{
List newWords = new List();
if (index == numbers.Length - 1)
{
newWords.AddRange(GetLetters(numbers[index]));
}
else
{
List wordsSoFar = GetTelephoneWords(numbers, index + 1);
string[] letters = GetLetters(numbers[index]);

foreach (string letter in letters)
{
foreach (string oldWord in wordsSoFar)
{
newWords.Add(letter + oldWord);
}
}
}
return newWords;
}

//gets the letters corresponding to a telephone digit
static string[] GetLetters(int i)
{
switch (i)
{
case 1: return new string[]{"1"};
case 2: return new string[] { "a", "b", "c" };
case 3: return new string[] { "d", "e", "f" };
case 4: return new string[] { "g", "h", "i" };
case 5: return new string[] { "j", "k", "l" };
case 6: return new string[] { "m", "n", "o" };
case 7: return new string[] { "p", "q", "r", "s" };
case 8: return new string[] { "t", "u", "v" };
case 9: return new string[] { "w", "x", "y", "z" };
case 0: return new string[]{"0"};
default: return new string[] { };
}
}
}

Implementing a Least-Recently-Used(LRU) Cache

Quickly i want to tell you about my approach , what DS we can use to implement in most efficient manner .

we can use Combination of Queue + HashMap  Data Structure OR

                                     LinkedList + HaspMap

Here algorithmic with explanation of DS

Why combination of two Data Structure ?  Let me tell you how LRU works : LRU caches have a maximum number of data items that they will hold and these items are usually arranged in a some data structure (list or queue). When an item is added to the cache, and every time it is accessed after that, it is automatically moved to the head of the list. If the cache is full and a slot is required for a new item, the cache makes room by discarding the entry at the tail of the list - the least-recently used item.  So we need to remove the Eldest entry from list/queue in the same in which inserted both queue and list provide this facility to , we need insert element at the  head of queue/list and remove the element from tail or queue/ list , since queue itself require list to be implement , we can directly use LinkedList . we can do insert and remove in O(1) .

Now , Before Inserting entry in list or queue , we need to check if that entry alraedy exist in Cache or not  , how we will do that , we need some DS again fro the same , HashMap is used for the same , that gurentte , get and set in O(1) .

As you asked in java , Java Provide the DS called  LinkedHashMap that has both feature.

An Important feature of LinkedHashMap is that it provides the methodremoveEldestEntry (Map.Entry e) that remove the eldest entry from the cache when it becmoe full and a new entry need to be inserted .

In this section, you will learn about th least-recently- used (LRU) cache in Java. LRU Cache helps you how to use the buffer and how to limit or fixed the size of buffer and how to manage storing and retrieving process of the buffer which size is limited.

In this section, you can create a LRU(least-recently-used) Cache and manage it efficiently. Here the given program takes a in numeric input to fix the size of the LRU Cache. If your entry exceeds the size of the LRU Cache the the eldest element with key is removed. LRU Cache is implemented through 

theLinkedHashMap class. LinkedHashMap holds values with unique key. You you store values with a duplicate key then the LinkedHashMap replace the old value of that key with the new value of the key.

Code Description:

This program shows the object keys and values by using the LRU cache. Many methods and APIs which have been used in the following program are explained as follows:

LinkedHashMap:This is the class of the java.util.*; package. This class is also used for the implementing 
the doubly linked list which tracks either insertion or access order. The put() method is used for the insertion process to the LinkedHashMap with the value and the unique key regarding the value.

put(Object key, Object value):This method has been used to add a value with it's unique key in the LRU Cache. This method of the LinkedHashMap class takes two argument in which first is the key and another is the value for the specified key.

Map.Entry:This interface returns the view of map of collection . The Map.Entry objects are valid only to the duration of the iteration. This is the nested class of the Map class from the java.util.*; package.

e.getKey():Above method of the Map.Entry class which returns the key corresponding to the value. Here 'e' is the instance of the Map.Entry class.

e.getValue():Above written is also a method of the Map.Entry class which returns the value corresponding to the key of the index of the LRU Cache. 

Here is the code of program:

Source :http://www.roseindia.net/java/example/java/util/LRUCacheExample.shtml

Breadth First Search(BFS) and Depth First Search(DFS) Traversal

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

 class Node
{
        public char label;
        public boolean visited=false;
        public Node(char l)
        {
            this.label=l;
        }
}


class Graph
{
       public Node rootNode;
       public ArrayList nodes=new ArrayList();
       public int[][] adjMatrix;//Edges will be represented as adjacency Matrix
       int size;
       public void setRootNode(Node n)
       {
           this.rootNode=n;
       }
      
       public Node getRootNode()
       {
           return this.rootNode;
       }
      
       public void addNode(Node n)
       {
           nodes.add(n);
       }
      
       //This method will be called to make connect two nodes
       public void connectNode(Node start,Node end)
       {
           if(adjMatrix==null)
           {
               size=nodes.size();
               adjMatrix=new int[size][size];
           }
  
           int startIndex=nodes.indexOf(start);
           int endIndex=nodes.indexOf(end);
           adjMatrix[startIndex][endIndex]=1;
           adjMatrix[endIndex][startIndex]=1;
       }
      
       private Node getUnvisitedChildNode(Node n)
       {
          
           int index=nodes.indexOf(n);
           int j=0;
           while(j<size)
           {
               if(adjMatrix[index][j]==1 && ((Node)nodes.get(j)).visited==false)
               {
                   return (Node)nodes.get(j);
               }
               j++;
           }
           return null;
       }
      
       //BFS traversal of a tree is performed by the bfs() function
       public void bfs()
       {
          
           //BFS uses Queue data structure
           Queue q=new LinkedList();
           q.add(this.rootNode);
           printNode(this.rootNode);
           rootNode.visited=true;
           while(!q.isEmpty())
           {
               Node n=(Node)q.remove();
               Node child=null;
               while((child=getUnvisitedChildNode(n))!=null)
               {
                   child.visited=true;
                   printNode(child);
                   q.add(child);
               }
           }
           //Clear visited property of nodes
           clearNodes();
       }
      
       //DFS traversal of a tree is performed by the dfs() function
       public void dfs()
       {
           //DFS uses Stack data structure
           Stack s=new Stack();
           s.push(this.rootNode);
           rootNode.visited=true;
           printNode(rootNode);
           while(!s.isEmpty())
           {
              Node n=(Node)s.peek();
               Node child=getUnvisitedChildNode(n);
               if(child!=null)
               {
                  child.visited=true;
                  printNode(child);
                  s.push(child);
              }
              else
              {
                 s.pop();
              }
          }
         //Clear visited property of nodes
          clearNodes();
      }
     
     
      //Utility methods for clearing visited property of node
      private void clearNodes()
      {
          int i=0;
         while(i<size)
          {
             Node n=(Node)nodes.get(i);
              n.visited=false;
              i++;
          }
      }
     
      //Utility methods for printing the node's label
     private void printNode(Node n)
      {
          System.out.print(n.label+" ");
      }
 
    
     
     
 
  }

public class Main {
  
       /**
        * @param args
        */
       public static void main(String[] args)
       {
          
           //Lets create nodes as given as an example in the article
           Node nA=new Node('A');
           Node nB=new Node('B');
           Node nC=new Node('C');
           Node nD=new Node('D');
           Node nE=new Node('E');
           Node nF=new Node('F');
  
           //Create the graph, add nodes, create edges between nodes
           Graph g=new Graph();
           g.addNode(nA);
           g.addNode(nB);
           g.addNode(nC);
           g.addNode(nD);
           g.addNode(nE);
           g.addNode(nF);
           g.setRootNode(nA);
          
           g.connectNode(nA,nB);
           g.connectNode(nA,nC);
           g.connectNode(nA,nD);
          
           g.connectNode(nB,nE);
           g.connectNode(nB,nF);
           g.connectNode(nC,nF);
          
          
           //Perform the traversal of the graph
           System.out.println("DFS Traversal of a tree is ------------->");
           g.dfs();
          
           System.out.println("\nBFS Traversal of a tree is ------------->");
           g.bfs();
          
          
          
          
       }
  
 }

   




Time Complexity O(M+N)m is no od edges & n no of nodes in case of connected graph
is will be O(M).
Space Complexity Depends on Implementation if Adjency matrix is Used then it will be O(MN)
else if adjency list is used then it will be equals to number of adjecent nodes of each node. it will O(M+N)

Application of BFS:
1.Finding Connected Components in Graph.
2.Check Graph is Bipartite or Not.
3.Finding interesting web pages (expanding from 
links). Breadth-first works very nicely and quickly 
finds pages with high PageRank R(p). PageRank 
is the scoring measure used by Google.
k is an index over all pages that link to page p; 
C(k) is the total number of links out of k;
R(k) is the PageRank for page k;
T is the total number of web pages on the internet;
d is a number 0 < d < 1.

Application of DFS
1.2-Edge Connectivity in Graph.
2. 2-node connectivity in graph.
3. Check Grap0h is planer or not.
4. solving Puzzles like mouse in the maze

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

Populating next right pointers in each node (Sibling)

struct Node {
Node* leftChild;
Node* rightChild;
Node* nextRight;
}

Populate the nextRight pointers in each node.
You may assume that it is a full binary tree (ie, each node other than the leaves has two children.)

Naive Algorithm:-
1. Most likely this can be implemented recursively, because you can identify the linking of nodes as sub-problems.
2. The main difficulty of this problem is linking rightChild with the nextSibling of rightChild.
3. Each node has no parent pointer. Therefore, there is no way linking the rightChild with its nextSibling at a level.

as its naive you will find exactness of some more test cases covered in below working code .

Pseudo Code :-

void connect(Node* p)
{
if (!p) return;
if (p->leftChild)
p->leftChild->nextRight = p->rightChild;
if (p->rightChild)
p->rightChild->nextRight = (p->nextRight) ?
p->nextRight->leftChild :
NULL;
connect(p->leftChild);
connect(p->rightChild);
}



#include <stdio.h>
#include <stdlib.h>

/* 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;
    struct node* nextRight;

};

/* 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;
  node->nextRight=NULL;
  return(node);
}

void connect(struct node* p) {
  if (!p)
  return;
 
  if (p->left)
  {
    if(p->right)//its necessary else NULL Pointer Exception
          p->left->nextRight = p->right;

    else if(p->nextRight)
    {
        if(p->nextRight->left)/// we can add one more if(p->nextRight)
          p->left->nextRight=p->nextRight->left;
        else if(p->nextRight->right)
          p->left->nextRight=p->nextRight->right;
    }  
    else
         p->left->nextRight=NULL;//if all are null except that node at that level
  }

  if (p->right)
  {
    if(p->nextRight)
    {
        if(p->nextRight->left)//skipping checking the root null or not
            p->right->nextRight =p->nextRight->left;
        else if(p->nextRight->right)//skipping checking the root null or not
            p->right->nextRight =p->nextRight->right;
    }
    else
             p->right->nextRight=NULL;
  }
  connect(p->left);
  connect(p->right);
}

/* Driver program to test above functions*/
int main()
{
  struct node *root = newNode(1);
  root->left        = newNode(2);
  root->right       = newNode(3);
  root->left->left  = newNode(4);
  root->left->right  = newNode(5);
  root->right->left= newNode(6);
  root->right->right= newNode(7);
  root->left->left->left  = newNode(8);
  root->left->left->right  = newNode(9);
  root->left->right->left  = newNode(10);
  root->left->right->right  = newNode(11);
  root->right->left->left= newNode(12);
  root->right->left->right= newNode(13);
  root->right->right->left= newNode(14);
  root->right->right->right= newNode(15);



  connect(root);
 
  printf( " %d %d %d ", root->left->left->nextRight->data,root->left->right->nextRight->data,root->right->left->nextRight->data);
  printf(" %d %d %d ",root->left->left->left->nextRight->data,root->left->left->right->nextRight->data,root->right->right->left->nextRight->data);//,root->right->right->right->nextRight->data); it will be null


  getchar();
  return 0;
}

Time Complexity O(N^2)
Space Complexity O(1)
Run Here https://ideone.com/lTPuY


2nd Method Using Queue
Just modified the structure of node of tree
struct tree{ int val; tree* left; tree* right; tree* rpeer; };
‘rpeer’ will have the address of next node of same level. For last node at any level, rpeer will be NULL.

At the beginning, all the rpeer nodes are assigned NULL. Write a program to populate correct value in rpeer for whole tree.

Example:
Input tree:Output tree: horizontal arrows are showing rpeer for every node.
Answer: As we are seeing that rpeer is next element at the same level. So if we are able to fetch the next element at same level, we are done. As per our prior knowledge, we can access these element using breadth first traversal.

Now only problem is how to check if we are at last element at any level. For this reason, we should be appending a delimiter (NULL in this case) to mark end of a level.

Efficient Algorithm:

Put root in queue.Put NULL in queue.While Queue is not emptyx = fetch first element from queueIf x is not NULL x->rpeer <= top element of queue. put left and right child of x in queueelse if queue is not empty put NULL in queueend ifend whilereturn
Code:

Algo is Correct Code Modification Needed :P  BDW Enjoy its Great Spoon Feeding :)

#include <stdio.h>
#include <stdlib.h>
#include <list>


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

}node;

typedef node * Tree;

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

return(node);
}


void connect(Tree root)
{
std::list que; //Queue to store tree nodes
que.push_back(root);
que.push_back(NULL); //null is the delimeter to show end of the level

if (!root)
return;

Tree *l, *r;

while(!que.empty())
{
Tree *tmp= que.front();
que.pop_front();

if(tmp != NULL)
{
tmp->nextRight= que.front();
l = tmp->left;
r = tmp->right;
if(l) que.push_back(l);
if(r) que.push_back(r);
}
else
{
if (!que.empty())
que.push_back(NULL);
}
}
return;
}

int main()
{
Tree root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left= newNode(6);
root->right->right= newNode(7);
root->left->left->left = newNode(8);
root->left->left->right = newNode(9);
root->left->right->left = newNode(10);
root->left->right->right = newNode(11);
root->right->left->left= newNode(12);
root->right->left->right= newNode(13);
root->right->right->left= newNode(14);
root->right->right->right= newNode(15);



connect(root);

printf( " %d %d %d ", root->left->left->nextRight->data,root->left->right->nextRight->data,root->right->left->nextRight->data);
printf(" %d %d %d ",root->left->left->left->nextRight->data,root->left->left->right->nextRight->data,root->right->right->left->nextRight->data);//,root->right->right->right->nextRight->data); it will be null


getchar();
return 0;
}

Time Complexity O(N^2)
Run Here  https://ideone.com/8Kgnb
Space Complexity O(1)
R