WAP to Remove Loop From Doubly Linked List Efficiently

Algorithm


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.

Note:One Test case Not Covered That I Will Do Later it Involve Prev Pointer




#include
#include

struct node
{
int data;
struct node *next;
struct node *prev;
};

/* Function to remove loop. */
int removeLoop(struct node *, struct node *);

/* This function detects and removes loop in the list
If loop was there in the list then it returns 1,
otherwise returns 0 */
int detectAndRemoveLoop(struct node *list)
{
struct node *slow_p = list, *fast_p = list;

while (slow_p && fast_p && fast_p->next)
{
slow_p = slow_p->next;
fast_p = fast_p->next->next;

/* If slow_p and fast_p meet at some point then there
is a loop */
if (slow_p == fast_p)
{
removeLoop(slow_p, list);

/* Return 1 to indicate that loop is found */
return 1;
}
}

/* Return 0 to indeciate that ther is no loop*/
return 0;
}

/* Function to remove loop.
loop_node --> Pointer to one of the loop nodes
head --> Pointer to the start node of the linked list */
int removeLoop(struct node *loop_node, struct node *head)
{
struct node *ptr1 = loop_node;
struct node *ptr2 = loop_node;

// Count the number of nodes in loop
unsigned int k = 1, i;
while (ptr1->next != ptr2)
{
ptr1 = ptr1->next;
k++;
}

// Fix one pointer to head
ptr1 = head;

// And the other pointer to k nodes after head
ptr2 = head;
for(i = 0; i < k; i++)
ptr2 = ptr2->next;

/* Move both pointers at the same pace,
they will meet at loop starting node */
while(ptr2 != ptr1)
{
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}

// Get pointer to the last node
ptr2 = ptr2->next;
while(ptr2->next != ptr1)
ptr2 = ptr2->next;

/* Set the next node of the loop ending node
to fix the loop */
ptr2->next = NULL;
}

/* UTILITY FUNCTIONS */
/* Given a reference (pointer to pointer) to the head
of a list and an int, pushes a new node on the front
of the list. */
/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginging of the Doubly Linked List */
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;

/* since we are adding at the begining,
prev is always NULL */
new_node->prev = NULL;

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

/* change prev of head node to new node */
if((*head_ref) != NULL)
(*head_ref)->prev = new_node ;

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


/* Function to print linked list */
void printList(struct node *node)
{
while(node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
}

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

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

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

detectAndRemoveLoop(head);

printf("Linked List after removing loop \n");
printList(head);

getchar();
return 0;
}

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

WAP to Detect Loop In Doubly Linked List

Algorithm : Floyd’s Cycle-Finding 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. Apart from above case one more cases may arises.

Case 1 : Whole link list is in loop. It Means last node points to first node. This can be solved by using two pointers. one pointer points to given node in link list and another pointers loops around the link list
If (Given_node == node->next) or or if(fast->prev=slow->prev)  Explained Above

Case 2: Part of link list is in loop
If (node->next != node->next->next->prev) is true means double link list is a loop.

 Time Complexity Will be O(N) N is length of Linked List




#include
#include

struct node
{
int data;
struct node *next;
struct node *prev;
};

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

while(slow_p && fast_p &&
fast_p->next )
{
slow_p = slow_p->next;
fast_p = fast_p->next->next;
if (fast_p->prev==slow_p->prev|| slow_p == fast_p) //Look Closely !!!!!!!!!!!!!!!
{
printf("Found Loop");
return 1;
}

}
return 0;
}

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

new_node->data = new_data;

prev is always NULL */
new_node->prev = NULL;

new_node->next = (*head_ref);

if((*head_ref) != NULL)
(*head_ref)->prev = new_node ;

(*head_ref) = new_node;
}

void printList(struct node *node)
{
while(node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}

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

/* Let us create a sorted linked list to test the functions
Created linked list will be 10->8->4->2 */
push(&head, 2);
push(&head, 4);
push(&head, 8);
push(&head, 10);

printf("\n Original Doubly Linked list ");
printList(head);

//head->next->next->next=head->next; //1st test case
// head->next=head;//2nd test case //head->prev=head not necessary
head->next->next->prev=head;// 3rd Test Case
/* similarly we can do it using prev pointer for this we have to go to last node first the
start form its prev pointer .. so making the loop in program is our choice it depnds how we
connects them using prev & next pointer */

detectLoop(head);


//printf("\n After Looping Doubly Linked list ");
//printList(head); //Testing Purpose Only

getchar();
}

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

WAP to Construct Fully Binary Tree From Given Number of Nodes. Efficiently

Given a number of nodes N of a binary tree , how many structurally different full binary trees are possible.
A binary tree is said to be full binary tree , if for every node in the tree there exists exactly zero or 2 children.

Example: When N = 5 , No. of possible trees = 2

{{{

o o
/ \ / \
o o o o
/ \ / \
o o o o

}}}


The idea behind this deduction is that successive applications of a binary operator can be represented in terms of a full binary tree.If there are n binary operators then there will be n+1 operands and total number of representations (which will be full binary trees) will be equal to Catalan number for 'n'.
e.g. if we take nodes as a,b,c and +,+. Then total number of nodes is 5 and total number of binary operator is 2 so total number of structurally different full binary trees is 2.
So if we simulate in the same way that how many structurally different full binary trees can be created for a given N (total number of nodes) we can observe that
N = n (number of operator) + (n+1) (number of operands)
so n = (N-1)/2
Now get the corresponding Catalan number for n, which is the answer to this question.

#include

int fact(unsigned int n)
{
if (n <= 1)k
return 1;
else
return n * fact(n-1);
}

int fully_bst(int n) //n= N-1/2
{

if(n==0||n==1)
return 1;
else return ((fact(2*n))/(fact(n+1)*fact(n)));
}

int main()
{

printf("%d ",fully_bst(2));

return 0;
}

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

WAP to Check Given Binary Tree Can Have Mirror Image e.g we have to Check wheather This Tree Can Be Foldable or Not

A tree can be folded if left and right subtrees of the tree are structure wise mirror image of each other. An empty tree is considered as foldable.

Consider the below trees:
(a) can be folded.
(d) cannot be folded.


a)
10
/ \
7 15
\ /
9 11


(c)
b
/ \
f e
/ /
a q

(d)

a
/ \
b c
/ \ /
e f d


Algorithm

IsFold(root)
1) If tree is empty then return true
2) Else check if left and right subtrees are structure wise mirrors of
each other. Use utility function IsFoldable(root->left,
root->right) for this.

// Checks if n1 and n2 are mirror of each other.

IsFoldable(n1, n2)
1) If both trees are empty then return true.
2) If one of them is empty and other is not then return false.
3) Return true if following conditions are met
a) n1->left is mirror of n2->right
b) n1->right is mirror of n2->left


#include
#include

/* You would want to remove below 3 lines if your compiler
supports bool, true and false */
#define bool int
#define true 1
#define false 0

/* 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;
};

/* A utility function that checks if trees with roots as n1 and n2
are mirror of each other */
bool IsFoldable(struct node *n1, struct node *n2);

/* Returns true if the given tree can be folded */
bool IsFold(struct node *root)
{
if (root == NULL)
{ return true; }

return IsFoldable(root->left, root->right);
}

/* A utility function that checks if trees with roots as n1 and n2
are mirror of each other */
bool IsFoldable(struct node *n1, struct node *n2)
{
/* If both left and right subtrees are NULL,
then return true */
if (n1 == NULL && n2 == NULL)
{ return true; }

/* If one of the trees is NULL and other is not,
then return false */
if (n1 == NULL || n2 == NULL)
{ return false; }

/* Otherwise check if left and right subtrees are mirrors of
their counterparts */
return IsFoldable(n1->left, n2->right) &&
IsFoldable(n1->right, n2->left);
}

/*UTILITY FUNCTIONS */
/* 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);
}

/* Driver program to test mirror() */
int main(void)
{
/* The constructed binary tree is
1
/ \
2 3
\ /
4 5
*/
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->right = newNode(4);
root->right->left = newNode(5);

if(IsFold(root) == true)
{ printf("\n tree is foldable"); }
else
{ printf("\n tree is not foldable"); }

getchar();
return 0;
}

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

WAP Convert Given Binary Tree into its Mirror Tree Efficiently

This Problem Can Be Solved Using Two Approach

1.Top Down
2 Bottom Up


1.Top Down
Start from The Root create copy of it & then create copy for left & right sub tree by calling copy function recursively


#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);
}

/* Change a tree so that the roles of the left and
right pointers are swapped at every node.

So the tree...
4
/ \
2 5
/ \
1 3

is changed to...
4
/ \
5 2
/ \
3 1
*/
struct node* copy(struct node *root)
{
struct node *temp;

if(root==NULL)
return(NULL);
temp = (struct node*) malloc(sizeof(struct node));
temp->data= root->data;

temp->left = copy(root->right);
temp->right = copy(root->left);

return(temp);
}

/* Helper function to test mirror(). Given a binary
search tree, print out its data elements in
increasing sorted order.*/
void inOrder(struct node* node)
{
if (node == NULL)
return;

inOrder(node->left);
printf("%d ", node->data);

inOrder(node->right);
}

/* Driver program to test mirror() */
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->left->left->left = newNode(6);
root->left->right->right = newNode(7);
/* Print inorder traversal of the input tree */
printf("\n Inorder traversal of the constructed tree is \n");
inOrder(root);

/* Convert tree to its mirror */
root=copy(root);

/* Print inorder traversal of the mirror tree */
printf("\n Inorder traversal of the mirror tree is \n");
inOrder(root);

getchar();
return 0;
}

Time Complexity O(n)
Space Complexity O(1) if stack space not considered else O(n)
Run Here https://ideone.com/QnMjQ


Bottom Up Approach ..First create mirror tree for left & right sub tree them comes to root


#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);
}

/* Change a tree so that the roles of the left and
right pointers are swapped at every node.

So the tree...
4
/ \
2 5
/ \
1 3

is changed to...
4
/ \
5 2
/ \
3 1
*/
void copy(struct node* node)
{
if (node==NULL)
return;
else
{
struct node* temp;

/* do the subtrees */
copy(node->left);
copy(node->right);

/* swap the pointers in this node */
temp = node->left;
node->left = node->right;
node->right = temp;
}
}

/* Helper function to test mirror(). Given a binary
search tree, print out its data elements in
increasing sorted order.*/
void inOrder(struct node* node)
{
if (node == NULL)
return;

inOrder(node->left);
printf("%d ", node->data);

inOrder(node->right);
}

/* Driver program to test mirror() */
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);

/* Print inorder traversal of the input tree */
printf("\n Inorder traversal of the constructed tree is \n");
inOrder(root);

/* Convert tree to its mirror */
copy(root);

/* Print inorder traversal of the mirror tree */
printf("\n Inorder traversal of the mirror tree is \n");
inOrder(root);

getchar();
return 0;
}


Time Complexity O(n)
Space Complexity O(1) if stack space not considered else O(n)
Run Here https://ideone.com/emkO7

WAP to find minimum difference between elements of N sorted list of K size each Efficiently..I have done it O(n)

Given an N arrays of size K each.. each of these K elements in the N arrays are sorted, each of these N*K elements are unique. Choose a single element from each of the N arrays, from the chosen subset of N elements. Subtract the minimum and maximum element. Now, this
difference should be least possible Minimum.. Hope the problem is clear :) :)

Sample:

N=3, K=3

N=1 : 6, 16, 67
N=2 : 11,17,68
N=3 : 10, 15, 100

here if 16, 17, 15 are chosen.. we get the minimum difference as
17-15=2.


its very simple question but i saw lot people stuck to solve & approach in this.. i solved it

#include
#include
#include

int min_num(int a,int b ,int c)
{
int m=a;
if(m>b)
m=b;
if(m>c)
m=c;
return m;

}

int max_num(int a,int b,int c)
{
int m=a;
if(m m=b;
if(m m=c;
return m;
}

int minDist(int a[],int b[],int c[], int n)
{

int i = 0,
j = 0, k=0,
min=INT_MAX,
max=INT_MIN,
mins=INT_MAX,
cur;

while(i < n && j < n && k {
max=max_num(a[i],b[j],c[k]);
min=min_num(a[i],b[j],c[k]);

if(min==a[i])
i++;
else if(min==b[j])
j++;
else
k++;



cur = abs(max-min);

mins = mins < cur ? mins : cur;


}

return mins;
}

int main()
{

int a[]={6, 16, 67};
int b[]={11,17,68};
int c[]={ 10, 15, 100};
printf("%d\n", minDist(a,b,c,sizeof(a)/sizeof(int)));//all have equal size

return 0;
}


TC O(n)
Run here https://ideone.com/qq4ZN

WAP to Concatenating the Two String while removing duplicate characters Efficiently

Given two strings s1 and s2, s1 has some characters at the end which are same as some of s2's starting characters, so you have to concatenate the strings so that the repeated portion occurs only once.

ex: S1="ABCDEFGHIJK"
S2="GHIJKXYZ"

OUTPUT="ABCDEFGHIJKXYZ"


#include
#include
int main()
{
char s1[] ="ABCDEFGHIJK";//"ABCDCDEF";
char s2[]="GHIJKXYZ";// "CDEFGHI";
char s3[100];
char *p1;
char *p2;
p1= s1;
p2 =s2;
int i =0;
while(*p1 )
{
if(*p1 != *p2)
{
s3[i++] = *p1;
p1++;

}
if(*p1 == *p2)
{
s3[i++] = *p1;
p1++;
p2++;
}

}
while(*p2)
{
s3[i++] = *p2;
p2++;
}
s3[i] = '\0';
printf("string is %s",s3);
getchar();
}

Run Here https://ideone.com/Y1yGb

WAP to Implement String reverse function using Bit Manipulation

#include

/* Function to reverse str[] from start to end*/
void rverese(char str[], int start, int end)
{
char temp;
while(start < end)
{
/* swap str[start] and str[end]*/
if(str[start]!= str[end])
{
str[start] ^= str[end];
str[end] ^= str[start];
str[start] ^= str[end];
}

start++;
end--;
}
}

int main()
{
char str[] = "CrackingTheCode";
printf("Original string is %s\n", str);
rverese(str, 0, 12);
printf("Reversed string is %s\n", str);
getchar();
return 0;
}

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


2nd Method

#include


int main()
{
char ip[10];
char op[10];
char *p,*q;

scanf("%s",ip);
p=ip;
q=op;

//point p to last character of i/p string
while(*(++p)!='\0');
p--;

//now p piinte to last & s points to start of i/p string so copy from p to q
//and now q will contain the reverse of original string

while(p!=ip)
{
*(q++)=*(p--);
}
*(q++)=*(p--); // first character of string
*q='\0';

printf("%s",op);
return 0;
}

TC O(N)
SC O(1)
Run Here https://ideone.com/MkDDs

WAP to Find Occurance of a Number N in Sorted Array in O(logn)

Given a sorted array and a number n.How can u find the number of occurance of n in the array . should be o(logn)


Modified Binary Search Algorithm

mid=low+high/2;
if(a[mid]>num)
search in right side & set low=mid+1 & return ;
else if(a[mid]search in left side of mid set high=mid-1 & return ;
else //its important instead of just of printing the num or incrementing the counter //i tried if you will do like this then it will be O(n) not O(logn) , si i will add 1 to recursively call for left side + recursively call for right side so every time this line executes we are incrementing the counter &
return 1+left_binsearch()+right_binsearch thus it will be in O(logn)


you people can dry run for this 1 2 2 3 3 3 4 4 4 low=0 high=8 mid=4 & run it



#include


int CountFreq (int *A, int value, int low, int high)
{
int mid;
if (high < low)
return 0;
mid = low + (high - low);
if (A[mid] > value)
return CountFreq (A, value, low, mid - 1);
else if (A[mid] < value)
return CountFreq (A, value, mid + 1, high);
else
return 1 + CountFreq (A, value, low, mid - 1) + CountFreq (A, value, mid + 1, high);
}

int main() {

int A[] = { 1,2,2,2,2,3, 3, 3,4,4,4, 4};
int value = 2;



printf("%d\n", CountFreq(A, value, 0, sizeof(A)/sizeof(int)-1));

return 0;

}

TC O(n) consider ar[]={3,3,3,3,3,3}, & x=3 T(n)=2*T(n/2)+c leads to O(n)
Sc O(1)
Run Here https://ideone.com/clone/mTGes


Method 2 Modified Binary Search

1) Use Binary search to get index of the first occurrence of x in arr[]. Let the index of the first occurrence be i.
2) Use Binary search to get index of the last occurrence of x in arr[]. Let the index of the last occurrence be j.
3) Return (j – i + 1);

why it works because we know that array i sorted so if find the first occurrence at position i & last occurrence at position j then we are sure that all the elements between i & j are the same value what they at ith & jth position it works because array is sorted & we have done ....Cheers

#include


/* if x is present in arr[] then returns the index of FIRST occurrence
of x in arr[0..n-1], otherwise returns -1 */
int first(int arr[], int low, int high, int x, int n)
{
if(high >= low)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/
if( ( mid == 0 || x > arr[mid-1]) && arr[mid] == x)
return mid;
else if(x > arr[mid])
return first(arr, (mid + 1), high, x, n);
else
return first(arr, low, (mid -1), x, n);
}
return -1;
}

/* if x is present in arr[] then returns the index of LAST occurrence
of x in arr[0..n-1], otherwise returns -1 */
int last(int arr[], int low, int high, int x, int n)
{
if(high >= low)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/
if( ( mid == n-1 || x < arr[mid+1]) && arr[mid] == x )
return mid;
else if(x < arr[mid])
return last(arr, low, (mid -1), x, n);
else
return last(arr, (mid + 1), high, x, n);
}
return -1;
}


/* if x is present in arr[] then returns the count of occurrences of x,
otherwise returns -1. */
int count(int arr[], int x, int n)
{
int i; // index of first occurrence of x in arr[0..n-1]
int j; // index of last occurrence of x in arr[0..n-1]

/* get the index of first occurrence of x */
i = first(arr, 0, n-1, x, n);

/* If x doesn't exist in arr[] then return -1 */
if(i == -1)
return i;

/* Else get the index of last occurrence of x */
j = last(arr, 0, n-1, x, n);

/* return count */
return j-i+1;
}



/* driver program to test above functions */
int main()
{
int arr[] = {1, 2, 2, 2, 2, 3, 3};
int x = 2; // Element to be counted in arr[]
int n = sizeof(arr)/sizeof(arr[0]);
int c = count(arr, x, n);
printf(" %d occurs %d times ", x, c);
getchar();
return 0;
}

TC O(logn)
Sc O(1)
Run here https://ideone.com/J0enE

WAP to Find Square root of Perfect Square Number Efficiently Yes in O(logn)

As its a perfect square!! So arrange numbers from 1 to n/2 and do a binary search..
ie for i from 1 to n/2

Now compare mind*mid to n

if mid*midrecursively check right half
else
recursively check left half

#include

int sqrtof_perfect(int start,int end,int n)
{
if(start>end)
return 0;
while(start<=end)
{
int mid=(start+end)/2;
//int temp=mid*mid;
if(mid*mid==n)
return mid;
else if(mid*mid>n)
end=mid-1;
else
start=mid+1;

}
return -1;
}


int main()
{
int n=144;//9;//25; // so

printf("\n %d",sqrtof_perfect(1,n/2,n));
getchar();
return 0;
}


TC O(logn)
Sc O(1)