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 Find Next Greater Palindrom Then the Given Number

#include

int ten(int s)
{
int i=1,product=1;
for(i=1;i<=s;i++)
product=product*10;
return product;
}
int main()
{
int n=0,num=0,b=0,c=0,d=0,i=1,input=99999,upper=0,lower=0,output=0;

num=input;
while(num!=0)
{
n++;
num/=10;
}
num=input;
printf("\n n=%d",n);
lower=num%ten(n/2);
printf("\nlower=%d",lower); //34 45
c=num/ten(n/2); //12 123
d=c;
if(n%2!=0)//if not even digits
d=c/10; // 12 12
printf("\n%d%d",c,d);
while(d!=0)
{
upper=upper*10+(d%10);
d=d/10;
}
printf("\nupper=%d",upper);//21 21
if(upper>lower)
{
output=c*ten(n/2)+upper;
}
else
{
c=c+1; //124
d=c;
upper=0;
if(n%2!=0)
d=d/10; //12
while(d!=0)
{
upper=upper*10+(d%10);
printf("\nd=%d",d);
d=d/10;
}
output=c*ten(n/2)+upper;
}
printf("\noutput=%d",output); //1331 12421

}

WAP to Removing characters from an input string in place.

#include
#include

WAP To Implement The Bitonic Sorting Can Be extended to K-tonic Sorting

public class BitonicSorterForArbitraryN
{
private static int[] a;
private final static boolean ASCENDING=true; // sorting direction

public static void sort(int[] ar)
{
a=ar;
bitonicSort(0, a.length, ASCENDING);
}

private static void bitonicSort(int lo, int n, boolean dir)
{
if (n>1)
{
int m=n/2;
bitonicSort(lo, m, !dir);
bitonicSort(lo+m, n-m, dir);
bitonicMerge(lo, n, dir);
}
}

private static void bitonicMerge(int lo, int n, boolean dir)
{
if (n>1)
{
int m=greatestPowerOfTwoLessThan(n);
for (int i=lo; i compare(i, i+m, dir);
bitonicMerge(lo, m, dir);
bitonicMerge(lo+m, n-m, dir);
}
}

private static void compare(int i, int j, boolean dir)
{
if (dir==(a[i]>a[j]))
exchange(i, j);
}

private static void exchange(int i, int j)
{
int t=a[i];
a[i]=a[j];
a[j]=t;
}

private static int greatestPowerOfTwoLessThan(int n)
{
int k=1;
while (k k=k<<1;
return k>>1;
}

public static void main(String ar[])
{
int a[]={1,2,3,4,5,9,8,7,6};
sort(a);
for(int i=0;i<9;i++)
System.out.println(a[i]);
}

}

The new sorting network for arbitrary n can be embedded into an original bitonic sorting network for 2k. Therefore, it also consists of ceiling 1log(n)ceiling 2 · (ceiling 1log(n)ceiling 2 + 1) / 2 stages. Each stage consists of at most n/2 comparators. This results in a complexity of O(n log(n)2) comparators, just as the original bitonic sorting network.


Time Complexity O(n(logn)^2))
Space O(1)

WAP remove(Delete Node From Binary Tree

WAP to SumTwo Number Which are represented by node in linked list

#include<stdio.h>
#include<malloc.h>
 
/* Link list node */
struct node
{
int data;
struct node* next;
};
 
/* Function to reverse the linked list */
static void reverse(struct node** head_ref)
{
struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}
 
/* Function to push a node */
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;
}
 
 
 
struct node* addition (struct node* temp1, struct node* temp2)
{
 
struct node* prev = NULL;
int carry = 0,a,b,result;
 
while (temp1 || temp2) //while both lists exist
{
 
if(temp1) a=temp1->data;
else a=0;
 
if(temp2) b=temp2->data;
else b=0;
 
 
 
 
result = carry;
if(temp1)
result+=temp1->data;
if(temp2)
result+=temp2->data;
 
 
carry=result/10;
 
struct node * newnode = (struct node*) malloc (sizeof(struct node));
newnode->data=(result)%10;
newnode->next = prev;
 
prev=newnode;
if(temp1)
temp1=temp1->next;
if(temp2)
temp2=temp2->next;
}
return prev;
 
}
void printList(struct node *node)
{
while(node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
} 
 
/* Drier program to test above function*/
int main(void)
{
/* Start with the empty list */
struct node* head = NULL;
struct node* head1 = NULL;
struct node* head2 = NULL;
 
 
/* Created Linked list is 1->2->3->4->5->6->7->8 */
 
push(&head1, 4);
push(&head1, 3);
push(&head1, 2);
push(&head1, 1);
 
reverse(&head1); 
 
push(&head2, 6);
push(&head2, 5);
push(&head2, 4);
 
reverse(&head2); 
 
head=addition(head1,head2); 
 
 
 
printList(head);
 
return(0);
}

TC O(n+m) where n,m are the number of digits in given numbers.
SC O(1)
Run Here https://ideone.com/j4Z8Z

WAP Find Minimu Number of Jumps to Reach In The End , In An UnSorted Array

#include
#include

int main()
{

int arr[] = {1 ,3, 5, 8 ,9 ,2, 6,7, 6, 8, 9};//{1, 3, 6, 0, 0, 3, 2, 3, 6, 8, 9};
int size=11;

int step=0,jump=0;
int i=0,j=0,max=0;

while( i< size)
{
jump++;
max=0;
step=0;

/*computes max distance it can cover in this jump*/
for(j=1;j<=arr[i];j++)
{
if(arr[i+j]+j>max)
{
max=arr[i+j]+j;
step=j;
}
}
i=i+step;
}

printf ( " %d ",jump);



return 0;
}

Run Here https://ideone.com/bvQph
Still DP is Best Will Post Soln Soon Using DP

WAP Find Minimu Number of Jumps to Reach In The End , In An UnSorted Array

#include
#include

int main()
{

int arr[] = {1 ,3, 5, 8 ,9 ,2, 6,7, 6, 8, 9};//{1, 3, 6, 0, 0, 3, 2, 3, 6, 8, 9};
int size=11;

int step=0,jump=0;
int i=0,j=0,max=0;

while( i< size)
{
jump++;
max=0;
step=0;

/*computes max distance it can cover in this jump*/
for(j=1;j<=arr[i];j++)
{
if(arr[i+j]+j>max)
{
max=arr[i+j]+j;
step=j;
}
}
i=i+step;
}

printf ( " %d ",jump);



return 0;
}

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