How would you find out if one of the pointers in a linked list is corrupted or not?
This is a really good interview question. The reason is that linked lists are used in a wide variety of scenarios and being able to detect and correct pointer corruptions might be a very valuable tool. For example, data blocks associated with files in a file system are usually stored as linked lists. Each data block points to the next data block. A single corrupt pointer can cause the entire file to be lost!
1 Discover & Fix Bugs
Discover and fix bugs when they corrupt the linked list and not when effect becomes visible in some other part of the program. Perform frequent consistency checks (to see if the linked list is indeed holding the data that you inserted into it).
2 set Pointer to NUll after Freeing Object
It is good programming practice to set the pointer value to NULL immediately after freeing the memory pointed at by the pointer. This will help in debugging, because it will tell you that the object was freed somewhere beforehand. Keep track of how many objects are pointing to a object using reference counts if required.
3 Use Debugger Tool Like DDD,Purify,
Use a good debugger to see how the datastructures are getting corrupted and trace down the problem. Debuggers like ddd on linux and memory profilers like Purify, Electric fence are good starting points. These tools should help you track down heap corruption issues easily.
4.Avoid Global Variable
Avoid global variables when traversing and manipulating linked lists. Imagine what would happen if a function which is only supposed to traverse a linked list using a global head pointer accidently sets the head pointer to NULL!.
5 Check Add& Delete Node After such Opeartion
Its a good idea to check the addNode() and the deleteNode() routines and test them for all types of scenarios. This should include tests for inserting/deleting nodes at the front/middle/end of the linked list, working with an empty linked list, running out of memory when using malloc() when allocating memory for new nodes, writing through NULL pointers, writing more data into the node fields then they can hold (resulting in corrupting the (probably adjacent) “prev” and “next” pointer fields), make sure bug fixes and enhancements to the linked list code are reviewed and well tested (a lot of bugs come from quick and dirty bug fixing), log and handle all possible errors (this will help you a lot while debugging), add multiple levels of logging so that you can dig through the logs. The list is endless…
6.Keep Track of Number of Nodes After Every Node after Initializing Linked List
Each node can have an extra field associated with it. This field indicates the number of nodes after this node in the linked list. This extra field needs to be kept up-to-date when we inserte or delete nodes in the linked list (It might become slightly complicated when insertion or deletion happens not at end, but anywhere in the linked list). Then, if for any node, p->field > 0 and p->next == NULL, it surely points to a pointer corruption.
You could also keep the count of the total number of nodes in a linked list and use it to check if the list is indeed having those many nodes or not.
The problem in detecting such pointer corruptions in C is that its only the programmer who knows that the pointer is corrupted. The program has no way of knowing that something is wrong. So the best way to fix these errors is check your logic and test your code to the maximum possible extent. I am not aware of ways in C to recover the lost nodes of a corrupted linked list. C does not track pointers so there is no good way to know if an arbitrary pointer has been corrupted or not. The platform may have a library service that checks if a pointer points to valid memory (for instance on Win32 there is a IsBadReadPtr, IsBadWritePtr API.) If you detect a cycle in the link list, it’s definitely bad. If it’s a doubly linked list you can verify, pNode->Next->Prev == pNode.
I have a hunch that interviewers who ask this question are probably hinting at something called Smart Pointers in C++. Smart pointers are particularly useful in the face of exceptions as they ensure proper destruction of dynamically allocated objects. They can also be used to keep track of dynamically allocated objects shared by multiple owners. This topic is out of scope here, but you can find lots of material on the Internet for Smart Pointers.
Saturday, April 30, 2011
WAP to Implement Queue Using Stack Efficiently
A queue can be implemented using two stacks. Let queue to be implemented be q and stacks used to implement q be stack1 and stack2. q can be implemented in two ways:
Method 1 (By making enQueue operation costly)
This method makes sure that newly entered element is always at the top of stack 1, so that deQueue operation just pops from stack1. To put the element at top of stack1, stack2 is used.
enQueue(q, x)
1) While stack1 is not empty, push everything from satck1 to stack2.
2) Push x to stack1 (assuming size of stacks is unlimited).
3) Push everything back to stack1.
dnQueue(q)
1) If stack1 is empty then error
2) Pop an item from stack1 and return it
Method 2 (By making deQueue operation costly)
In this method, in en-queue operation, the new element is entered at the top of stack1. In de-queue operation, if stack2 is empty then all the elements are moved to stack2 and finally top of stack2 is returned.
enQueue(q, x)
1) Push x to stack1 (assuming size of stacks is unlimited).
deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, push everything from satck1 to stack2.
3) Pop the element from stack2 and return it.
Method 2 is definitely better than method 1. Method 1 moves all the elements twice in enQueue operation, while method 2 (in deQueue operation) moves the elements once and moves elements only if stack2 empty.
Implementation of method 1
Implementation of method 2
/* Program to implement a queue using two stacks */
#include
#include
/* structure of a stack node */
struct sNode
{
int 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);
/* structure of queue having two stacks */
struct queue
{
struct sNode *stack1;
struct sNode *stack2;
};
/* Function to enqueue an item to queue */
void enQueue(struct queue *q, int x)
{
push(&q->stack1, x);
}
/* Function to dequeue an item from queue */
int deQueue(struct queue *q)
{
int x;
/* If both stacks are empty then error */
if(q->stack1 == NULL && q->stack2 == NULL)
{
printf("Q is empty");
getchar();
exit(0);
}
/* Move elements from satck1 to stack 2 only if
stack2 is empty */
if(q->stack2 == NULL)
{
while(q->stack1 != NULL)
{
x = pop(&q->stack1);
push(&q->stack2, x);
}
}
x = pop(&q->stack2);
return x;
}
/* 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)
{
int 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;
}
}
/* Driver function to test anove functions */
int main()
{
/* Create a queue with items 1 2 3*/
struct queue *q = (struct queue*)malloc(sizeof(struct queue));
q->stack1 = NULL;
q->stack2 = NULL;
enQueue(q, 1);
enQueue(q, 2);
enQueue(q, 3);
/* Dequeue items */
printf("%d ", deQueue(q));
printf("%d ", deQueue(q));
printf("%d ", deQueue(q));
getchar();
}
Run here https://ideone.com/fafrK
Method 1 (By making enQueue operation costly)
This method makes sure that newly entered element is always at the top of stack 1, so that deQueue operation just pops from stack1. To put the element at top of stack1, stack2 is used.
enQueue(q, x)
1) While stack1 is not empty, push everything from satck1 to stack2.
2) Push x to stack1 (assuming size of stacks is unlimited).
3) Push everything back to stack1.
dnQueue(q)
1) If stack1 is empty then error
2) Pop an item from stack1 and return it
Method 2 (By making deQueue operation costly)
In this method, in en-queue operation, the new element is entered at the top of stack1. In de-queue operation, if stack2 is empty then all the elements are moved to stack2 and finally top of stack2 is returned.
enQueue(q, x)
1) Push x to stack1 (assuming size of stacks is unlimited).
deQueue(q)
1) If both stacks are empty then error.
2) If stack2 is empty
While stack1 is not empty, push everything from satck1 to stack2.
3) Pop the element from stack2 and return it.
Method 2 is definitely better than method 1. Method 1 moves all the elements twice in enQueue operation, while method 2 (in deQueue operation) moves the elements once and moves elements only if stack2 empty.
Implementation of method 1
Implementation of method 2
/* Program to implement a queue using two stacks */
#include
#include
/* structure of a stack node */
struct sNode
{
int 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);
/* structure of queue having two stacks */
struct queue
{
struct sNode *stack1;
struct sNode *stack2;
};
/* Function to enqueue an item to queue */
void enQueue(struct queue *q, int x)
{
push(&q->stack1, x);
}
/* Function to dequeue an item from queue */
int deQueue(struct queue *q)
{
int x;
/* If both stacks are empty then error */
if(q->stack1 == NULL && q->stack2 == NULL)
{
printf("Q is empty");
getchar();
exit(0);
}
/* Move elements from satck1 to stack 2 only if
stack2 is empty */
if(q->stack2 == NULL)
{
while(q->stack1 != NULL)
{
x = pop(&q->stack1);
push(&q->stack2, x);
}
}
x = pop(&q->stack2);
return x;
}
/* 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)
{
int 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;
}
}
/* Driver function to test anove functions */
int main()
{
/* Create a queue with items 1 2 3*/
struct queue *q = (struct queue*)malloc(sizeof(struct queue));
q->stack1 = NULL;
q->stack2 = NULL;
enQueue(q, 1);
enQueue(q, 2);
enQueue(q, 3);
/* Dequeue items */
printf("%d ", deQueue(q));
printf("%d ", deQueue(q));
printf("%d ", deQueue(q));
getchar();
}
Run here https://ideone.com/fafrK
WAP to Implement Stack using Queue Efficiently
It Can be Done using two Strategy by making push or pop oeration costly
Method A: By making Push Operation Costly
* push:
o if q1 is empty then simply add the item & return
else if q1 is not empty enqueue all items of queue1 in queue2, & then
enqueue given element in queue1
o Then enqueue all items from q2 to q1 again
this way names of queue1 and queue2
* pop:
o deqeue from queue1
Method B: By making Pop Operation Costly
* push:
o enqueue in queue1
* pop:
o while size of queue1 is bigger than 1, pipe dequeued items
from queue1 into queue2
o dequeue and return the last item of queue1, then switch the
names of queue1 and queue2
Obvious 2nd method is best because 1st moves all the element twice in in push operation
1st method implementation
import java.util.*;
class StackUsingQueues
{
Queue q1 = new LinkedList();
Queue q2 = new LinkedList();
public int pop()
{
if (q1.peek() == null) {
System.out.println("The stack is empty, nothing to return");
int i = 0;
return i;
} else {
int pop = q1.remove();
return pop;
}
}
public void push(int data) {
if (q1.peek() == null) {
q1.add(data);
} else {
for (int i = q1.size(); i > 0; i--) {
q2.add(q1.remove());
}
q1.add(data);
for (int j = q2.size(); j > 0; j--) {
q1.add(q2.remove());
}
}
}
public static void main(String[] args) {
StackUsingQueues s1 = new StackUsingQueues();
// Stack s1 = new Stack();
s1.push(1);
s1.push(2);
s1.push(3);
s1.push(4);
s1.push(5);
s1.push(6);
s1.push(7);
// s1.push(6);
System.out.println("1st = " + s1.pop());
System.out.println("2nd = " + s1.pop());
System.out.println("3rd = " + s1.pop());
System.out.println("4th = " + s1.pop());
System.out.println("5th = " + s1.pop());
System.out.println("6th = " + s1.pop());
System.out.println("7th = " + s1.pop());
}
}
2nd method--Need to Modify
import java.util.*;
class StackUsingQueues
{
Queue q1 = new LinkedList();
Queue q2 = new LinkedList();
public int pop()
{
if(q1.peek() == null)
{
System.out.println("The stack is empty, nothing to return");
int i = 0;
return i;
}
else
{
while(q1.size()>q2.size())
{
q2.add(q1.remove());
}
int size=1,pop=0;
while(size!=q1.size())
{
pop=q1.remove();
size++;
}
while(!q2.isEmpty())
{
q1.add(q2.remove());
}
return pop;
}
//return 0;
}
public void push(int data)
{
q1.add(data);
}
boolean emptys(Queue q)
{
return (q.size()==0);
}
public static void main(String[] args) {
StackUsingQueues s1 = new StackUsingQueues();
s1.push(1);
s1.push(2);
s1.push(3);
s1.push(4);
s1.push(5);
s1.push(6);
s1.push(7);
// s1.push(6);
System.out.println("1st = " + s1.pop());
System.out.println("2nd = " + s1.pop());
System.out.println("3rd = " + s1.pop());
System.out.println("4th = " + s1.pop());
System.out.println("5th = " + s1.pop());
System.out.println("6th = " + s1.pop());
System.out.println("7th = " + s1.pop());
}
}
Run here https://ideone.com/K1a3C
Method A: By making Push Operation Costly
* push:
o if q1 is empty then simply add the item & return
else if q1 is not empty enqueue all items of queue1 in queue2, & then
enqueue given element in queue1
o Then enqueue all items from q2 to q1 again
this way names of queue1 and queue2
* pop:
o deqeue from queue1
Method B: By making Pop Operation Costly
* push:
o enqueue in queue1
* pop:
o while size of queue1 is bigger than 1, pipe dequeued items
from queue1 into queue2
o dequeue and return the last item of queue1, then switch the
names of queue1 and queue2
Obvious 2nd method is best because 1st moves all the element twice in in push operation
1st method implementation
import java.util.*;
class StackUsingQueues
{
Queue
Queue
public int pop()
{
if (q1.peek() == null) {
System.out.println("The stack is empty, nothing to return");
int i = 0;
return i;
} else {
int pop = q1.remove();
return pop;
}
}
public void push(int data) {
if (q1.peek() == null) {
q1.add(data);
} else {
for (int i = q1.size(); i > 0; i--) {
q2.add(q1.remove());
}
q1.add(data);
for (int j = q2.size(); j > 0; j--) {
q1.add(q2.remove());
}
}
}
public static void main(String[] args) {
StackUsingQueues s1 = new StackUsingQueues();
// Stack s1 = new Stack();
s1.push(1);
s1.push(2);
s1.push(3);
s1.push(4);
s1.push(5);
s1.push(6);
s1.push(7);
// s1.push(6);
System.out.println("1st = " + s1.pop());
System.out.println("2nd = " + s1.pop());
System.out.println("3rd = " + s1.pop());
System.out.println("4th = " + s1.pop());
System.out.println("5th = " + s1.pop());
System.out.println("6th = " + s1.pop());
System.out.println("7th = " + s1.pop());
}
}
2nd method--Need to Modify
import java.util.*;
class StackUsingQueues
{
Queue
Queue
public int pop()
{
if(q1.peek() == null)
{
System.out.println("The stack is empty, nothing to return");
int i = 0;
return i;
}
else
{
while(q1.size()>q2.size())
{
q2.add(q1.remove());
}
int size=1,pop=0;
while(size!=q1.size())
{
pop=q1.remove();
size++;
}
while(!q2.isEmpty())
{
q1.add(q2.remove());
}
return pop;
}
//return 0;
}
public void push(int data)
{
q1.add(data);
}
boolean emptys(Queue
{
return (q.size()==0);
}
public static void main(String[] args) {
StackUsingQueues s1 = new StackUsingQueues();
s1.push(1);
s1.push(2);
s1.push(3);
s1.push(4);
s1.push(5);
s1.push(6);
s1.push(7);
// s1.push(6);
System.out.println("1st = " + s1.pop());
System.out.println("2nd = " + s1.pop());
System.out.println("3rd = " + s1.pop());
System.out.println("4th = " + s1.pop());
System.out.println("5th = " + s1.pop());
System.out.println("6th = " + s1.pop());
System.out.println("7th = " + s1.pop());
}
}
Run here https://ideone.com/K1a3C
Friday, April 29, 2011
WAP to Check if if two strings are anagrams or not. in O(n) ..?
There are 4 ways to solve this problem: as i can solve it each has complexity Issue
Solution #1: Sort the strings
boolean anagram(String s, String t)
{
return sort(s) == sort(t);
}
# include
# include
# include
/* FOLLOWING FUNCTIONS ARE ONLY FOR SORTING
PURPOSE */
void exchange(char *a, char *b)
{
char temp;
temp = *a;
*a = *b;
*b = temp;
}
int partition(char A[], int si, int ei)
{
char x = A[ei];
int i = (si - 1);
int j;
for (j = si; j <= ei - 1; j++)
{
if(A[j] <= x)
{
i++;
exchange(&A[i], &A[j]);
}
}
exchange (&A[i + 1], &A[ei]);
return (i + 1);
}
/* Implementation of Quick Sort
A[] --> Array to be sorted
si --> Starting index
ei --> Ending index
*/
void quickSort(char A[], int si, int ei)
{
int pi; /* Partitioning index */
if(si < ei)
{
pi = partition(A, si, ei);
quickSort(A, si, pi - 1);
quickSort(A, pi + 1, ei);
}
}
int anagram(char* a,int a_len,char* b,int b_len)
{
quickSort(a,0,a_len);
quickSort(b,0,b_len);
return (strcmp(a,b));
}
/* Driver program to test removeDups */
int main()
{
char a[] = "madonna louise ciccone";
char b[] ="occasional nude income";
int n=sizeof(a)/sizeof(char);
int m=sizeof(b)/sizeof(char);
printf( " %d ", anagram(a,n,b,m));
getchar();
return 0;
}
TC O(nlogn)
SC O(1)
Run here https://ideone.com/swXVj
solution #2:
Check if the two strings have identical counts for each unique char.
class Anagram
{
public static void main(String a[])
{
System.out.println(anagram(new String("william shakespeare"), new String("iam aweakishspeller")));
}
public static boolean anagram(String s, String t)
{
if (s.length() != t.length()) return false;
int[] letters = new int[256];
int num_unique_chars = 0;
int num_completed_t = 0;
char[] s_array = s.toCharArray();
for (char c : s_array) { // count number of each char in s.
if (letters[c] == 0) ++num_unique_chars;
++letters[c];
}
for (int i = 0; i < t.length(); ++i) {
int c = (int) t.charAt(i);
if (letters[c] == 0) { // Found more of char c in t than in s.
return false;
}
--letters[c];
if (letters[c] == 0) {
++num_completed_t;
if (num_completed_t == num_unique_chars) {
// it’s a match if t has been processed completely
return i == t.length() - 1;
}
}
}
return false;
}
}
TC o(n)
Scv o(n)
Run here https://ideone.com/mpWTO
3rd & 4th Solution
Take XOR of both the strings ..if they are anagram then result will be zero.
Its has two way to solve & cool ,Most Efficient as I can Say to solve the problem
#include
#include
using namespace std;
int isAnagram(char* a, char* b, int len)
{
int zor = 0;
for(int i = 0; i < len; ++i)
{
zor ^= a[i] - '0';
//printf( "%d %d \t ", (a[i]-'0'),zor);
zor ^= b[i] - '0';
//printf( "%d %d \n ", (b[i]-'0'),zor);
}
if(zor == 0)
return 1;
return 0;
}
4th Solution
Check for both xor & sum of each string if xor=0 & both sum are equals then string are Anagram of each other
int check_anagram(const char* str1, const char* str2)
{
int len = strlen(str1);
int l2=strlen(str2);
if(len != l2)
return 0;
int xorval=0;
int sum1=0,sum2=0;
for(int i=0;i
sum1 += str1[i];
sum2 += str2[i];
xorval ^= str1[i] ^ str2[i];
}
if((xorval == 0 && (sum1 == sum2))==true)
return 1;
else return 0;
return 0;
}
int main()
{
char a[] = "madonna louise ciccone";
//"william shakespeare";//"abcd";
char b[] ="occasional nude income";
//"iam aweakishspeller";//"badc";
int n=sizeof(a)/sizeof(char);//if both anagram size should be same so no issue here
printf( " %d %d ",isAnagram(a, b, n),check_anagram(a,b));
return 0;
}
TC O(n)
Sc (1)
Run Here https://ideone.com/UDk5G
Solution #1: Sort the strings
boolean anagram(String s, String t)
{
return sort(s) == sort(t);
}
# include
# include
# include
/* FOLLOWING FUNCTIONS ARE ONLY FOR SORTING
PURPOSE */
void exchange(char *a, char *b)
{
char temp;
temp = *a;
*a = *b;
*b = temp;
}
int partition(char A[], int si, int ei)
{
char x = A[ei];
int i = (si - 1);
int j;
for (j = si; j <= ei - 1; j++)
{
if(A[j] <= x)
{
i++;
exchange(&A[i], &A[j]);
}
}
exchange (&A[i + 1], &A[ei]);
return (i + 1);
}
/* Implementation of Quick Sort
A[] --> Array to be sorted
si --> Starting index
ei --> Ending index
*/
void quickSort(char A[], int si, int ei)
{
int pi; /* Partitioning index */
if(si < ei)
{
pi = partition(A, si, ei);
quickSort(A, si, pi - 1);
quickSort(A, pi + 1, ei);
}
}
int anagram(char* a,int a_len,char* b,int b_len)
{
quickSort(a,0,a_len);
quickSort(b,0,b_len);
return (strcmp(a,b));
}
/* Driver program to test removeDups */
int main()
{
char a[] = "madonna louise ciccone";
char b[] ="occasional nude income";
int n=sizeof(a)/sizeof(char);
int m=sizeof(b)/sizeof(char);
printf( " %d ", anagram(a,n,b,m));
getchar();
return 0;
}
TC O(nlogn)
SC O(1)
Run here https://ideone.com/swXVj
solution #2:
Check if the two strings have identical counts for each unique char.
class Anagram
{
public static void main(String a[])
{
System.out.println(anagram(new String("william shakespeare"), new String("iam aweakishspeller")));
}
public static boolean anagram(String s, String t)
{
if (s.length() != t.length()) return false;
int[] letters = new int[256];
int num_unique_chars = 0;
int num_completed_t = 0;
char[] s_array = s.toCharArray();
for (char c : s_array) { // count number of each char in s.
if (letters[c] == 0) ++num_unique_chars;
++letters[c];
}
for (int i = 0; i < t.length(); ++i) {
int c = (int) t.charAt(i);
if (letters[c] == 0) { // Found more of char c in t than in s.
return false;
}
--letters[c];
if (letters[c] == 0) {
++num_completed_t;
if (num_completed_t == num_unique_chars) {
// it’s a match if t has been processed completely
return i == t.length() - 1;
}
}
}
return false;
}
}
TC o(n)
Scv o(n)
Run here https://ideone.com/mpWTO
3rd & 4th Solution
Take XOR of both the strings ..if they are anagram then result will be zero.
Its has two way to solve & cool ,Most Efficient as I can Say to solve the problem
#include
#include
using namespace std;
int isAnagram(char* a, char* b, int len)
{
int zor = 0;
for(int i = 0; i < len; ++i)
{
zor ^= a[i] - '0';
//printf( "%d %d \t ", (a[i]-'0'),zor);
zor ^= b[i] - '0';
//printf( "%d %d \n ", (b[i]-'0'),zor);
}
if(zor == 0)
return 1;
return 0;
}
4th Solution
Check for both xor & sum of each string if xor=0 & both sum are equals then string are Anagram of each other
int check_anagram(const char* str1, const char* str2)
{
int len = strlen(str1);
int l2=strlen(str2);
if(len != l2)
return 0;
int xorval=0;
int sum1=0,sum2=0;
for(int i=0;i
sum1 += str1[i];
sum2 += str2[i];
xorval ^= str1[i] ^ str2[i];
}
if((xorval == 0 && (sum1 == sum2))==true)
return 1;
else return 0;
return 0;
}
int main()
{
char a[] = "madonna louise ciccone";
//"william shakespeare";//"abcd";
char b[] ="occasional nude income";
//"iam aweakishspeller";//"badc";
int n=sizeof(a)/sizeof(char);//if both anagram size should be same so no issue here
printf( " %d %d ",isAnagram(a, b, n),check_anagram(a,b));
return 0;
}
TC O(n)
Sc (1)
Run Here https://ideone.com/UDk5G
WAP to Implement DeQueue in Which Desired Operation Should be Execute in O(1)
Implement various operations of a double ended queue (Deque).
Deque is a data structure where items can be inserted and removed from both ends.
Operations :- insertToLeft(), removeFromLeft(), insertToRight(),removeFromRight().
This differs from the queue abstract data type or First-In-First-Out List (FIFO), where elements can only be added to one end and removed from the other. This general data class has some possible sub-types:
* An input-restricted deque is one where deletion can be made from both ends, but insertion can only be made at one end.
* An output-restricted deque is one where insertion can be made at both ends, but deletion can be made from one end only.
Both the basic and most common list types in computing, queues and stacks can be considered specializations of deques, and can be implemented using deques.
Implementations
There are at least two common ways to efficiently implement a deque: with a modified dynamic array or with a doubly linked list.
1st Method
using Doubly Linked List it works because we wants to do both operation start & end as DLL as prev & next pointers . it always possible to do above operation in O(1)
2nd Method
Dynamic array implementation uses a variant of a dynamic array that can grow from both ends, sometimes called array deques. These array deques have all the properties of a dynamic array, such as constant time random access, good locality of reference, and inefficient insertion/removal in the middle, with the addition of amortized constant time insertion/removal at both ends, instead of just one end. Three common implementations include:
* Storing deque contents in a circular buffer, and only resizing when the buffer becomes completely full. This decreases the frequency of resizings, but requires an expensive branch instruction for indexing.
* Allocating deque contents from the center of the underlying array, and resizing the underlying array when either end is reached. This approach may require more frequent resizings and waste more space, particularly when elements are only inserted at one end.
* Storing contents in multiple smaller arrays, allocating additional arrays at the beginning or end as needed. Indexing is implemented by keeping a dynamic array containing pointers to each of the smaller arrays.
1st Method - using Doubly Linked List
#include
#include
/*
Implement various operations of a double ended queue (Deque).
Deque is a data structure where items can be inserted and removed from both ends.
Operations :- insertToLeft(), removeFromLeft(), insertToRight(),removeFromRight().
*/
using namespace std;
class dequeu;
struct node
{
int data;
struct node *next;
struct node *prev;
friend class dequeue;
};
typedef struct node* Node;
class dequeue
{
Node head;
Node tail;
Node createNode(int data);
public:
dequeue():head(NULL),tail(NULL){}
~dequeue()
{
Node cur = head;
Node temp = NULL;
while(cur)
{
temp = cur;
cur=cur->next;
delete temp;
temp =NULL;
}
head = tail = NULL;
}
void insertToLeft(int data);
void insertToRight(int data);
int removeFromLeft();
int removeFromRight();
void print();
};
Node dequeue::createNode(int data)
{
Node temp = new struct node;
temp->data = data;
temp->prev = NULL;
temp->next = NULL;
return temp;
}
void dequeue::insertToLeft(int data)
{
Node temp = createNode(data);
if(head == NULL)
{
head= tail = temp;
}
else
{
temp->next = head;
head->prev = temp;
head = temp;
}
}
void dequeue::insertToRight(int data)
{
Node temp = createNode(data);
if(head == NULL)
{
head = tail = temp;
}
else
{
tail->next = temp;
temp->prev = tail;
tail = temp;
}
}
int dequeue::removeFromLeft()
{
if(head == NULL)
{
cout<<"Empty dequeue";
return -1;
}
else
{
Node temp = head;
if(head == tail)
{
head = tail = NULL;
}
else
{
head=head->next;
head->prev= NULL;
}
delete temp;
temp = NULL;
}
return 1;
}
int dequeue::removeFromRight()
{
if(tail == NULL)
{
cout<<"dqueue Empty ";
return -1;
}
else
{
Node temp = tail;
if(head == tail)
{
head = tail = NULL;
}
else
{
tail = tail->prev;
tail->next = NULL;
}
delete temp;
temp = NULL;
}
return 1;
}
void dequeue::print()
{
Node cur = head;
while(cur)
{
cout<<" "<data;
cur = cur->next;
}
cout<
int main()
{
dequeue q;
int i;
for(i=1;i<6;i++)
q.insertToLeft(i);
for(i=6;i<11;i++)
q.insertToRight(i);
q.print();
q.removeFromRight();
q.removeFromLeft();
q.print();
q.removeFromLeft();
q.removeFromRight();
q.print();
}
TC O(1)
SC O(1)
Run Here https://ideone.com/UhKw0
* In a doubly linked list implementation and assuming no allocation/deallocation overhead, the time complexity of all deque operations is O(1). Additionally, the time complexity of insertion or deletion in the middle, given an iterator, is O(1); however, the time complexity of random access by index is O(n).
* In a growing array, the amortized time complexity of all deque operations is O(1). Additionally, the time complexity of random access by index is O(1); but the time complexity of insertion or deletion in the middle is O(n).
Java program for Doing The Same
public class ListDeque
{
/** *//**
* This is the doubly-linked list node.
*/
private static class Node
{
public Node( AnyType d, Node p, Node n )
{
data = d; prev = p; next = n;
}
public AnyType data;
public Node prev;
public Node next;
}
private Node beginMarker;
private Node endMarker;
private int theSize;
public ListDeque()
{
beginMarker = new Node( null, null, null );
endMarker = new Node( null, beginMarker, null );
beginMarker.next = endMarker;
theSize = 0;
}
/** *//**
* Returns the number of items in this collection.
* @return the number of items in this collection.
*/
public int size( )
{
return theSize;
}
/** *//**
* Returns true if this collection is empty.
* @return true if this collection is empty.
*/
public boolean isEmpty( )
{
return (theSize == 0);
}
/** *//**
* Returns the first element of the deque
*
*/
public AnyType first()
{
if(size() == 0)
throw new QueueEmptyException("Empty Queue");
return beginMarker.next.data;
}
/** *//**
* Returns the last element of the deque
*
*/
public AnyType last()
{
if(size() == 0)
throw new QueueEmptyException("Empty Queue");
return endMarker.prev.data;
}
/** *//**
* Inserts e at the beginning (as the first element) of the deque
*
*/
public void insertFirst(AnyType e)
{
Node newNode = new Node( e, beginMarker, beginMarker.next );
newNode.prev.next = newNode;
newNode.next.prev = newNode;
theSize++;
}
/** *//**
* Inserts e at the end (as the last element) of the deque
*
*/
public void insertLast(AnyType e)
{
Node newNode = new Node( e, endMarker.prev, endMarker );
newNode.prev.next = newNode;
newNode.next.prev = newNode;
theSize++;
}
/** *//**
* Removes and returns the first element of the deque
*
*/
public AnyType removeFirst()
{
if(size() == 0)
throw new QueueEmptyException("Empty Queue");
AnyType temp = beginMarker.next.data;
beginMarker.next = beginMarker.next.next;
beginMarker.next.prev = beginMarker;
theSize--;
return temp;
}
/** *//**
* Removes and returns the last element of the deque
*
*/
public AnyType removeLast()
{
if(size() == 0)
throw new QueueEmptyException("Empty Queue");
AnyType temp = endMarker.prev.data;
endMarker.prev = endMarker.prev.prev;
endMarker.prev.next = endMarker;
theSize--;
return temp;
}
}
public class QueueEmptyException extends RuntimeException
{
public QueueEmptyException(String err) {
super(err);
}
}
public class Main6
{
public static void main(String[] args)
{
ListDeque deck = new ListDeque();
deck.insertFirst(new Integer(3));
deck.insertFirst(new Integer(5));
// (5,3)
System.out.println(deck.removeFirst()); // prints 5
// (3)
deck.insertLast(new Integer(7));
// (3,7)
System.out.println(deck.removeFirst()); // prints 3
//(7)
System.out.println(deck.removeLast()); // prints 7
// ()
deck.insertFirst(new Integer(1));
// (1)
System.out.println(deck.first()); // prints 1
// (1)
deck.insertFirst(new Integer(5));
// (5,1)
System.out.println(deck.last()); // prints 1
//
System.out.println(deck.removeFirst()); // prints 5
// (1)
deck.insertLast(new Integer(7));
// (1,7)
System.out.println(deck.removeFirst()); // prints 1
//(7)
System.out.println(deck.removeLast()); // prints 7
// ()
try
{
Integer a = deck.removeFirst();
System.out.println(a);
}
catch (Exception ex)
{
System.err.println(ex);
}
}
}
TC O(1) for Insertion/Deletion
SC O(1)
* In a doubly linked list implementation and assuming no allocation/deallocation overhead, the time complexity of all deque operations is O(1). Additionally, the time complexity of insertion or deletion in the middle, given an iterator, is O(1); however, the time complexity of random access by index is O(n).
* In a growing array, the amortized time complexity of all deque operations is O(1). Additionally, the time complexity of random access by index is O(1); but the time complexity of insertion or deletion in the middle is O(n).
2nd Method Using Dynamic Array
/* Program of input and output restricted dequeue using array*/
# include
# define MAX 5
int deque_arr[MAX];
int left = -1;
int right = -1;
input_que()
{
int choice;
while(1)
{
printf("1.Insert at right\n");
printf("2.Delete from left\n");
printf("3.Delete from right\n");
printf("4.Display\n");
printf("5.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
insert_right();
break;
case 2:
delete_left();
break;
case 3:
delete_right();
break;
case 4:
display_queue();
break;
case 5:
exit();
default:
printf("Wrong choice\n");
}/*End of switch*/
}/*End of while*/
}/*End of input_que() */
output_que()
{
int choice;
while(1)
{
printf("1.Insert at right\n");
printf("2.Insert at left\n");
printf("3.Delete from left\n");
printf("4.Display\n");
printf("5.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
insert_right();
break;
case 2:
insert_left();
break;
case 3:
delete_left();
break;
case 4:
display_queue();
break;
case 5:
exit();
default:
printf("Wrong choice\n");
}/*End of switch*/
}/*End of while*/
}/*End of output_que() */
insert_right()
{
int added_item;
if((left == 0 && right == MAX-1) || (left == right+1))
{
printf("Queue Overflow\n");
return;
}
if (left == -1) /* if queue is initially empty */
{
left = 0;
right = 0;
}
else
if(right == MAX-1) /*right is at last position of queue */
right = 0;
else
right = right+1;
printf("Input the element for adding in queue : ");
scanf("%d", &added_item);
deque_arr[right] = added_item ;
}/*End of insert_right()*/
insert_left()
{
int added_item;
if((left == 0 && right == MAX-1) || (left == right+1))
{
printf("Queue Overflow \n");
return;
}
if (left == -1)/*If queue is initially empty*/
{
left = 0;
right = 0;
}
else
if(left== 0)
left=MAX-1;
else
left=left-1;
printf("Input the element for adding in queue : ");
scanf("%d", &added_item);
deque_arr[left] = added_item ;
}/*End of insert_left()*/
delete_left()
{
if (left == -1)
{
printf("Queue Underflow\n");
return ;
}
printf("Element deleted from queue is : %d\n",deque_arr[left]);
if(left == right) /*Queue has only one element */
{
left = -1;
right=-1;
}
else
if(left == MAX-1)
left = 0;
else
left = left+1;
}/*End of delete_left()*/
delete_right()
{
if (left == -1)
{
printf("Queue Underflow\n");
return ;
}
printf("Element deleted from queue is : %d\n",deque_arr[right]);
if(left == right) /*queue has only one element*/
{
left = -1;
right=-1;
}
else
if(right == 0)
right=MAX-1;
else
right=right-1;
}/*End of delete_right() */
display_queue()
{
int front_pos = left,rear_pos = right;
if(left == -1)
{
printf("Queue is empty\n");
return;
}
printf("Queue elements :\n");
if( front_pos <= rear_pos )
{
while(front_pos <= rear_pos)
{
printf("%d ",deque_arr[front_pos]);
front_pos++;
}
}
else
{
while(front_pos <= MAX-1)
{
printf("%d ",deque_arr[front_pos]);
front_pos++;
}
front_pos = 0;
while(front_pos <= rear_pos)
{
printf("%d ",deque_arr[front_pos]);
front_pos++;
}
}/*End of else */
printf("\n");
}/*End of display_queue() */
int main()
{
int choice;
printf("1.Input restricted dequeue\n");
printf("2.Output restricted dequeue\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1 :
input_que();
break;
case 2:
output_que();
break;
default:
printf("Wrong choice\n");
}/*End of switch*/
}/*End of main()*/
TC O(1) for Insertion/Deletion
SC O(1)
* In a doubly linked list implementation and assuming no allocation/deallocation overhead, the time complexity of all deque operations is O(1). Additionally, the time complexity of insertion or deletion in the middle, given an iterator, is O(1); however, the time complexity of random access by index is O(n).
* In a growing array, the amortized time complexity of all deque operations is O(1). Additionally, the time complexity of random access by index is O(1); but the time complexity of insertion or deletion in the middle is O(n).
Java Program of Dequeue Using Dynamic Array
import java.lang.reflect.Array;
class Deque-
{
private int maxSize=100;
private final Item[] array;
private int front,rear;
private int numberOfItems;
public Deque()
{
array=(Item[])(new Object[maxSize]);
front=0;
rear=-1;
numberOfItems=0;
}
public boolean isEmpty()
{
return (numberOfItems==0);
}
public void addFirst(Item item)
{
if(front==0)
front=maxSize;
array[--front]=item;
numberOfItems++;
}
public void addLast(Item item)
{
if(rear==maxSize-1)
rear=-1;
array[++rear]=item;
numberOfItems++;
}
public Item removeFirst()
{
Item temp=array[front++];
if(front==maxSize)
front=0;
numberOfItems--;
return temp;
}
public Item removeLast()
{
Item temp=array[rear--];
if(rear==-1)
rear=maxSize-1;
numberOfItems--;
return temp;
}
public int getFirst()
{
return front;
}
public int getLast()
{
return rear;
}
public static void main(String[] args)
{
Deque element1=new Deque();
Deque element2=new Deque();
for(int i=0;i
try {
for(;element1.numberOfItems+1>0;)
{
String temp=element1.removeFirst();
System.out.println(temp);
}
}
catch(Exception ex)
{
System.out.println("End Of Execution due to remove from empty queue");
}
System.out.println();
for(int i=0;i
try {
for(;element2.numberOfItems+1>0;)
{
String temp=element2.removeLast();
System.out.println(temp);
}
}
catch(Exception ex)
{
System.out.println("End Of Execution due to remove from empty queue");
}
}
}
Deque is a data structure where items can be inserted and removed from both ends.
Operations :- insertToLeft(), removeFromLeft(), insertToRight(),removeFromRight().
This differs from the queue abstract data type or First-In-First-Out List (FIFO), where elements can only be added to one end and removed from the other. This general data class has some possible sub-types:
* An input-restricted deque is one where deletion can be made from both ends, but insertion can only be made at one end.
* An output-restricted deque is one where insertion can be made at both ends, but deletion can be made from one end only.
Both the basic and most common list types in computing, queues and stacks can be considered specializations of deques, and can be implemented using deques.
Implementations
There are at least two common ways to efficiently implement a deque: with a modified dynamic array or with a doubly linked list.
1st Method
using Doubly Linked List it works because we wants to do both operation start & end as DLL as prev & next pointers . it always possible to do above operation in O(1)
2nd Method
Dynamic array implementation uses a variant of a dynamic array that can grow from both ends, sometimes called array deques. These array deques have all the properties of a dynamic array, such as constant time random access, good locality of reference, and inefficient insertion/removal in the middle, with the addition of amortized constant time insertion/removal at both ends, instead of just one end. Three common implementations include:
* Storing deque contents in a circular buffer, and only resizing when the buffer becomes completely full. This decreases the frequency of resizings, but requires an expensive branch instruction for indexing.
* Allocating deque contents from the center of the underlying array, and resizing the underlying array when either end is reached. This approach may require more frequent resizings and waste more space, particularly when elements are only inserted at one end.
* Storing contents in multiple smaller arrays, allocating additional arrays at the beginning or end as needed. Indexing is implemented by keeping a dynamic array containing pointers to each of the smaller arrays.
1st Method - using Doubly Linked List
#include
#include
/*
Implement various operations of a double ended queue (Deque).
Deque is a data structure where items can be inserted and removed from both ends.
Operations :- insertToLeft(), removeFromLeft(), insertToRight(),removeFromRight().
*/
using namespace std;
class dequeu;
struct node
{
int data;
struct node *next;
struct node *prev;
friend class dequeue;
};
typedef struct node* Node;
class dequeue
{
Node head;
Node tail;
Node createNode(int data);
public:
dequeue():head(NULL),tail(NULL){}
~dequeue()
{
Node cur = head;
Node temp = NULL;
while(cur)
{
temp = cur;
cur=cur->next;
delete temp;
temp =NULL;
}
head = tail = NULL;
}
void insertToLeft(int data);
void insertToRight(int data);
int removeFromLeft();
int removeFromRight();
void print();
};
Node dequeue::createNode(int data)
{
Node temp = new struct node;
temp->data = data;
temp->prev = NULL;
temp->next = NULL;
return temp;
}
void dequeue::insertToLeft(int data)
{
Node temp = createNode(data);
if(head == NULL)
{
head= tail = temp;
}
else
{
temp->next = head;
head->prev = temp;
head = temp;
}
}
void dequeue::insertToRight(int data)
{
Node temp = createNode(data);
if(head == NULL)
{
head = tail = temp;
}
else
{
tail->next = temp;
temp->prev = tail;
tail = temp;
}
}
int dequeue::removeFromLeft()
{
if(head == NULL)
{
cout<<"Empty dequeue";
return -1;
}
else
{
Node temp = head;
if(head == tail)
{
head = tail = NULL;
}
else
{
head=head->next;
head->prev= NULL;
}
delete temp;
temp = NULL;
}
return 1;
}
int dequeue::removeFromRight()
{
if(tail == NULL)
{
cout<<"dqueue Empty ";
return -1;
}
else
{
Node temp = tail;
if(head == tail)
{
head = tail = NULL;
}
else
{
tail = tail->prev;
tail->next = NULL;
}
delete temp;
temp = NULL;
}
return 1;
}
void dequeue::print()
{
Node cur = head;
while(cur)
{
cout<<" "<
cur = cur->next;
}
cout<
int main()
{
dequeue q;
int i;
for(i=1;i<6;i++)
q.insertToLeft(i);
for(i=6;i<11;i++)
q.insertToRight(i);
q.print();
q.removeFromRight();
q.removeFromLeft();
q.print();
q.removeFromLeft();
q.removeFromRight();
q.print();
}
TC O(1)
SC O(1)
Run Here https://ideone.com/UhKw0
* In a doubly linked list implementation and assuming no allocation/deallocation overhead, the time complexity of all deque operations is O(1). Additionally, the time complexity of insertion or deletion in the middle, given an iterator, is O(1); however, the time complexity of random access by index is O(n).
* In a growing array, the amortized time complexity of all deque operations is O(1). Additionally, the time complexity of random access by index is O(1); but the time complexity of insertion or deletion in the middle is O(n).
Java program for Doing The Same
public class ListDeque
{
/** *//**
* This is the doubly-linked list node.
*/
private static class Node
{
public Node( AnyType d, Node
{
data = d; prev = p; next = n;
}
public AnyType data;
public Node
public Node
}
private Node
private Node
private int theSize;
public ListDeque()
{
beginMarker = new Node
endMarker = new Node
beginMarker.next = endMarker;
theSize = 0;
}
/** *//**
* Returns the number of items in this collection.
* @return the number of items in this collection.
*/
public int size( )
{
return theSize;
}
/** *//**
* Returns true if this collection is empty.
* @return true if this collection is empty.
*/
public boolean isEmpty( )
{
return (theSize == 0);
}
/** *//**
* Returns the first element of the deque
*
*/
public AnyType first()
{
if(size() == 0)
throw new QueueEmptyException("Empty Queue");
return beginMarker.next.data;
}
/** *//**
* Returns the last element of the deque
*
*/
public AnyType last()
{
if(size() == 0)
throw new QueueEmptyException("Empty Queue");
return endMarker.prev.data;
}
/** *//**
* Inserts e at the beginning (as the first element) of the deque
*
*/
public void insertFirst(AnyType e)
{
Node
newNode.prev.next = newNode;
newNode.next.prev = newNode;
theSize++;
}
/** *//**
* Inserts e at the end (as the last element) of the deque
*
*/
public void insertLast(AnyType e)
{
Node
newNode.prev.next = newNode;
newNode.next.prev = newNode;
theSize++;
}
/** *//**
* Removes and returns the first element of the deque
*
*/
public AnyType removeFirst()
{
if(size() == 0)
throw new QueueEmptyException("Empty Queue");
AnyType temp = beginMarker.next.data;
beginMarker.next = beginMarker.next.next;
beginMarker.next.prev = beginMarker;
theSize--;
return temp;
}
/** *//**
* Removes and returns the last element of the deque
*
*/
public AnyType removeLast()
{
if(size() == 0)
throw new QueueEmptyException("Empty Queue");
AnyType temp = endMarker.prev.data;
endMarker.prev = endMarker.prev.prev;
endMarker.prev.next = endMarker;
theSize--;
return temp;
}
}
public class QueueEmptyException extends RuntimeException
{
public QueueEmptyException(String err) {
super(err);
}
}
public class Main6
{
public static void main(String[] args)
{
ListDeque
deck.insertFirst(new Integer(3));
deck.insertFirst(new Integer(5));
// (5,3)
System.out.println(deck.removeFirst()); // prints 5
// (3)
deck.insertLast(new Integer(7));
// (3,7)
System.out.println(deck.removeFirst()); // prints 3
//(7)
System.out.println(deck.removeLast()); // prints 7
// ()
deck.insertFirst(new Integer(1));
// (1)
System.out.println(deck.first()); // prints 1
// (1)
deck.insertFirst(new Integer(5));
// (5,1)
System.out.println(deck.last()); // prints 1
//
System.out.println(deck.removeFirst()); // prints 5
// (1)
deck.insertLast(new Integer(7));
// (1,7)
System.out.println(deck.removeFirst()); // prints 1
//(7)
System.out.println(deck.removeLast()); // prints 7
// ()
try
{
Integer a = deck.removeFirst();
System.out.println(a);
}
catch (Exception ex)
{
System.err.println(ex);
}
}
}
TC O(1) for Insertion/Deletion
SC O(1)
* In a doubly linked list implementation and assuming no allocation/deallocation overhead, the time complexity of all deque operations is O(1). Additionally, the time complexity of insertion or deletion in the middle, given an iterator, is O(1); however, the time complexity of random access by index is O(n).
* In a growing array, the amortized time complexity of all deque operations is O(1). Additionally, the time complexity of random access by index is O(1); but the time complexity of insertion or deletion in the middle is O(n).
2nd Method Using Dynamic Array
/* Program of input and output restricted dequeue using array*/
# include
# define MAX 5
int deque_arr[MAX];
int left = -1;
int right = -1;
input_que()
{
int choice;
while(1)
{
printf("1.Insert at right\n");
printf("2.Delete from left\n");
printf("3.Delete from right\n");
printf("4.Display\n");
printf("5.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
insert_right();
break;
case 2:
delete_left();
break;
case 3:
delete_right();
break;
case 4:
display_queue();
break;
case 5:
exit();
default:
printf("Wrong choice\n");
}/*End of switch*/
}/*End of while*/
}/*End of input_que() */
output_que()
{
int choice;
while(1)
{
printf("1.Insert at right\n");
printf("2.Insert at left\n");
printf("3.Delete from left\n");
printf("4.Display\n");
printf("5.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
insert_right();
break;
case 2:
insert_left();
break;
case 3:
delete_left();
break;
case 4:
display_queue();
break;
case 5:
exit();
default:
printf("Wrong choice\n");
}/*End of switch*/
}/*End of while*/
}/*End of output_que() */
insert_right()
{
int added_item;
if((left == 0 && right == MAX-1) || (left == right+1))
{
printf("Queue Overflow\n");
return;
}
if (left == -1) /* if queue is initially empty */
{
left = 0;
right = 0;
}
else
if(right == MAX-1) /*right is at last position of queue */
right = 0;
else
right = right+1;
printf("Input the element for adding in queue : ");
scanf("%d", &added_item);
deque_arr[right] = added_item ;
}/*End of insert_right()*/
insert_left()
{
int added_item;
if((left == 0 && right == MAX-1) || (left == right+1))
{
printf("Queue Overflow \n");
return;
}
if (left == -1)/*If queue is initially empty*/
{
left = 0;
right = 0;
}
else
if(left== 0)
left=MAX-1;
else
left=left-1;
printf("Input the element for adding in queue : ");
scanf("%d", &added_item);
deque_arr[left] = added_item ;
}/*End of insert_left()*/
delete_left()
{
if (left == -1)
{
printf("Queue Underflow\n");
return ;
}
printf("Element deleted from queue is : %d\n",deque_arr[left]);
if(left == right) /*Queue has only one element */
{
left = -1;
right=-1;
}
else
if(left == MAX-1)
left = 0;
else
left = left+1;
}/*End of delete_left()*/
delete_right()
{
if (left == -1)
{
printf("Queue Underflow\n");
return ;
}
printf("Element deleted from queue is : %d\n",deque_arr[right]);
if(left == right) /*queue has only one element*/
{
left = -1;
right=-1;
}
else
if(right == 0)
right=MAX-1;
else
right=right-1;
}/*End of delete_right() */
display_queue()
{
int front_pos = left,rear_pos = right;
if(left == -1)
{
printf("Queue is empty\n");
return;
}
printf("Queue elements :\n");
if( front_pos <= rear_pos )
{
while(front_pos <= rear_pos)
{
printf("%d ",deque_arr[front_pos]);
front_pos++;
}
}
else
{
while(front_pos <= MAX-1)
{
printf("%d ",deque_arr[front_pos]);
front_pos++;
}
front_pos = 0;
while(front_pos <= rear_pos)
{
printf("%d ",deque_arr[front_pos]);
front_pos++;
}
}/*End of else */
printf("\n");
}/*End of display_queue() */
int main()
{
int choice;
printf("1.Input restricted dequeue\n");
printf("2.Output restricted dequeue\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1 :
input_que();
break;
case 2:
output_que();
break;
default:
printf("Wrong choice\n");
}/*End of switch*/
}/*End of main()*/
TC O(1) for Insertion/Deletion
SC O(1)
* In a doubly linked list implementation and assuming no allocation/deallocation overhead, the time complexity of all deque operations is O(1). Additionally, the time complexity of insertion or deletion in the middle, given an iterator, is O(1); however, the time complexity of random access by index is O(n).
* In a growing array, the amortized time complexity of all deque operations is O(1). Additionally, the time complexity of random access by index is O(1); but the time complexity of insertion or deletion in the middle is O(n).
Java Program of Dequeue Using Dynamic Array
import java.lang.reflect.Array;
class Deque
{
private int maxSize=100;
private final Item[] array;
private int front,rear;
private int numberOfItems;
public Deque()
{
array=(Item[])(new Object[maxSize]);
front=0;
rear=-1;
numberOfItems=0;
}
public boolean isEmpty()
{
return (numberOfItems==0);
}
public void addFirst(Item item)
{
if(front==0)
front=maxSize;
array[--front]=item;
numberOfItems++;
}
public void addLast(Item item)
{
if(rear==maxSize-1)
rear=-1;
array[++rear]=item;
numberOfItems++;
}
public Item removeFirst()
{
Item temp=array[front++];
if(front==maxSize)
front=0;
numberOfItems--;
return temp;
}
public Item removeLast()
{
Item temp=array[rear--];
if(rear==-1)
rear=maxSize-1;
numberOfItems--;
return temp;
}
public int getFirst()
{
return front;
}
public int getLast()
{
return rear;
}
public static void main(String[] args)
{
Deque
Deque
for(int i=0;i
try {
for(;element1.numberOfItems+1>0;)
{
String temp=element1.removeFirst();
System.out.println(temp);
}
}
catch(Exception ex)
{
System.out.println("End Of Execution due to remove from empty queue");
}
System.out.println();
for(int i=0;i
try {
for(;element2.numberOfItems+1>0;)
{
String temp=element2.removeLast();
System.out.println(temp);
}
}
catch(Exception ex)
{
System.out.println("End Of Execution due to remove from empty queue");
}
}
}
WAP to find Nth Twin prime Efficiently-UnSolved Problem In Mathematics In Prime Number Theory
You will have to take an integer n as input. and output should be the nth twin prime pair
A twin prime is a prime number that differs from another prime number by two. Except for the pair (2, 3), this is the smallest possible difference between two primes. Some examples of twin prime pairs are (3, 5), (5, 7), (11, 13), (17, 19), (29, 31) and (41, 43). Sometimes the term twin prime is used for a pair of twin primes; an alternative name for this is prime twin.
public class TwinPrime {
public static void main(String a[])
{
boolean flag=false; int i,n=10024;
boolean k=false;
for(i=3;n>0;i+=2)
{
k=isPRIME(i)==true && isPRIME(i+2)==true;
if(k)
n--;
//System.out.println( "" + i + "" + (i+2));
}
System.out.println("Twins Prime are:" + (i-2) + ":" + i);
}
static boolean isPRIME(int x)
{
int i=0;
if(x <= 1)
return false;
int s = (int)Math.sqrt(x);
for(i = 2; i <= s; i++)
if(x%i == 0)
{
//System.out.println("" + x + "is prime" );
return false;
}
return true;
}
}
List : http://primes.utm.edu/lists/small/100ktwins.txt
Run Here http://ideone.com/TeJKSv
A twin prime is a prime number that differs from another prime number by two. Except for the pair (2, 3), this is the smallest possible difference between two primes. Some examples of twin prime pairs are (3, 5), (5, 7), (11, 13), (17, 19), (29, 31) and (41, 43). Sometimes the term twin prime is used for a pair of twin primes; an alternative name for this is prime twin.
public class TwinPrime {
public static void main(String a[])
{
boolean flag=false; int i,n=10024;
boolean k=false;
for(i=3;n>0;i+=2)
{
k=isPRIME(i)==true && isPRIME(i+2)==true;
if(k)
n--;
//System.out.println( "" + i + "" + (i+2));
}
System.out.println("Twins Prime are:" + (i-2) + ":" + i);
}
static boolean isPRIME(int x)
{
int i=0;
if(x <= 1)
return false;
int s = (int)Math.sqrt(x);
for(i = 2; i <= s; i++)
if(x%i == 0)
{
//System.out.println("" + x + "is prime" );
return false;
}
return true;
}
}
List : http://primes.utm.edu/lists/small/100ktwins.txt
Run Here http://ideone.com/TeJKSv
WAP to .Count of -ve numbers Effciiently in 2D Matrix(n * n) of positive and negative numbers is given. Matrix is sorted rowwise and columnwise.
Its Not tough but Its Tricky & Requires Deep Thing so why it has Great Credit
Algorithm
if a[0][n]<0 it menas all the element before it are negative so add count+=j+1; & incement row number
else if its greater > 0 then decrement the column number
#include
using namespace std;
int main()
{
int a[4][3] ={{-30,-29,-28},{-29,30,40},{-25,40,60},{55,65,75}}; // 4*3 Matrix
/*{ { -9, -3,- 2, 120 },
{ -8, -2, 30, 230 },
{ -7, -1, 40, 420 }, 4*4 Matrix
{ -6, 90, 91, 520 }
};
{
{-15, -10, 4, 6},
{-10, -3, 7, 10}, 3*4 Matrix
{-5, -1, 12, 15},
};
*/
int m=4, n=3, num=0, count=0;
for(int i=0, j=n-1; i=0; )
{
if(num > a[i][j])
{
i++;
count += (j+1);
}
else
j--;
}
cout << count << endl;
return 0;
}
TC O(n)
SC O(1)
Run Here https://ideone.com/GhUXg
Algorithm
if a[0][n]<0 it menas all the element before it are negative so add count+=j+1; & incement row number
else if its greater > 0 then decrement the column number
#include
using namespace std;
int main()
{
int a[4][3] ={{-30,-29,-28},{-29,30,40},{-25,40,60},{55,65,75}}; // 4*3 Matrix
/*{ { -9, -3,- 2, 120 },
{ -8, -2, 30, 230 },
{ -7, -1, 40, 420 }, 4*4 Matrix
{ -6, 90, 91, 520 }
};
{
{-15, -10, 4, 6},
{-10, -3, 7, 10}, 3*4 Matrix
{-5, -1, 12, 15},
};
*/
int m=4, n=3, num=0, count=0;
for(int i=0, j=n-1; i
{
if(num > a[i][j])
{
i++;
count += (j+1);
}
else
j--;
}
cout << count << endl;
return 0;
}
TC O(n)
SC O(1)
Run Here https://ideone.com/GhUXg
Thursday, April 28, 2011
WAP to Check One Tree is SubTree of Another Tree
You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.
The treeMatch procedure visits each node in the small tree at most once and is called no more than once per node of the large tree. Worst case runtime is at most O(n * m), where n and m are the sizes of trees T1 and T2, respectively. If k is the number of occurrences of T2’s root in T1, the worst case runtime can be characterized as O(n + k * m).
#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);
}
/* Given two trees, return true if they are
structurally identical */
int identicalTrees(struct node* a, struct node* b)
{
/* If Any one Tree is Empty This can be omitted as it is covered else part */
//if(t1==NULL|| t2==NULL)
// return 0;
/*1. both empty */
if (a==NULL && b==NULL)
return 1;
/* 2. both non-empty -> compare them */
else if (a!=NULL && b!=NULL)
{
return
(
a->data == b->data &&
identicalTrees(a->left, b->left) &&
identicalTrees(a->right, b->right)
);
}
/* 3. one empty, one not -> false */
else return 0;
}
int subTree(struct node* a, struct node* b)
{
if(a==NULL)
return false;
if(b==NULL)
return true;
if(a->data==b->data)
return identicalTrees(a,b);
return (subTree(a->left,b)|| subTree(a->right,b));
}
/* Driver program to test identicalTrees function*/
int main()
{
struct node *root1 = newNode(1);
struct node *root2 = newNode(5);
root1->left = newNode(2);
root1->right = newNode(3);
root1->left->left = newNode(4);
root1->left->right = newNode(5);
root1->left->left->left = newNode(6);
root1->left->right->left = newNode(7);
root1->left->right->right = newNode(8);
root1->left->right->right->left = newNode(9);
root1->left->right->right->right = newNode(10);
root2->left = newNode(7);
root2->right = newNode(8);
root2->right->left = newNode(9);
root2->right->right = newNode(10); //to Test Diff it Try Diff Test cases
if(subTree(root1, root2))
printf("T2 is SubTree of T1");
else
printf("t2 is not SubTree of T1");
getchar();
return 0;
}
TC O(n^2)
SC O(1)
Run Here https://ideone.com/S0xWf
2nd Method to Solve It using Suffix Tree & Tree Traversal
What if We have huge Data how we can optimize it . whats the efficient way to solve it..here we go .Note that the problem here specifies that T1 has millions of nodes—this means that we should be careful of how much space we use. Let’s say, for example, T1 has 10 million nodes—this means that the data alone is about 40 mb. We could create a string representing the inorder and preorder traversals. If T2’s preorder traversal is a substring of T1’s preorder traversal, and T2’s inorder traversal is a substring of T1’s inorder traversal, then T2 is a substring
of T1. We can check this using a suffix tree. However, we may hit memory limitations because suffix trees are extremely memory intensive. If this become an issue, we can use an alternative approach.
so Now problem reduce to sub-string matching isn't it..??
Using Tree Traversal
TC O(n^2)
Sc O(1)
using KMP String Search
TC O(m+n)
SC (1)
Using Suffix Tree
TC O(m) m is length of substring
Sc O(1)
To Build Suffix tree Check My Post in Blog
http://shashank7s.blogspot.com/2011/03/wap-for-given-string-s-and-array-of.html
http://www.allisons.org/ll/AlgDS/Tree/Suffix/
The treeMatch procedure visits each node in the small tree at most once and is called no more than once per node of the large tree. Worst case runtime is at most O(n * m), where n and m are the sizes of trees T1 and T2, respectively. If k is the number of occurrences of T2’s root in T1, the worst case runtime can be characterized as O(n + k * m).
#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);
}
/* Given two trees, return true if they are
structurally identical */
int identicalTrees(struct node* a, struct node* b)
{
/* If Any one Tree is Empty This can be omitted as it is covered else part */
//if(t1==NULL|| t2==NULL)
// return 0;
/*1. both empty */
if (a==NULL && b==NULL)
return 1;
/* 2. both non-empty -> compare them */
else if (a!=NULL && b!=NULL)
{
return
(
a->data == b->data &&
identicalTrees(a->left, b->left) &&
identicalTrees(a->right, b->right)
);
}
/* 3. one empty, one not -> false */
else return 0;
}
int subTree(struct node* a, struct node* b)
{
if(a==NULL)
return false;
if(b==NULL)
return true;
if(a->data==b->data)
return identicalTrees(a,b);
return (subTree(a->left,b)|| subTree(a->right,b));
}
/* Driver program to test identicalTrees function*/
int main()
{
struct node *root1 = newNode(1);
struct node *root2 = newNode(5);
root1->left = newNode(2);
root1->right = newNode(3);
root1->left->left = newNode(4);
root1->left->right = newNode(5);
root1->left->left->left = newNode(6);
root1->left->right->left = newNode(7);
root1->left->right->right = newNode(8);
root1->left->right->right->left = newNode(9);
root1->left->right->right->right = newNode(10);
root2->left = newNode(7);
root2->right = newNode(8);
root2->right->left = newNode(9);
root2->right->right = newNode(10); //to Test Diff it Try Diff Test cases
if(subTree(root1, root2))
printf("T2 is SubTree of T1");
else
printf("t2 is not SubTree of T1");
getchar();
return 0;
}
TC O(n^2)
SC O(1)
Run Here https://ideone.com/S0xWf
2nd Method to Solve It using Suffix Tree & Tree Traversal
What if We have huge Data how we can optimize it . whats the efficient way to solve it..here we go .Note that the problem here specifies that T1 has millions of nodes—this means that we should be careful of how much space we use. Let’s say, for example, T1 has 10 million nodes—this means that the data alone is about 40 mb. We could create a string representing the inorder and preorder traversals. If T2’s preorder traversal is a substring of T1’s preorder traversal, and T2’s inorder traversal is a substring of T1’s inorder traversal, then T2 is a substring
of T1. We can check this using a suffix tree. However, we may hit memory limitations because suffix trees are extremely memory intensive. If this become an issue, we can use an alternative approach.
so Now problem reduce to sub-string matching isn't it..??
Using Tree Traversal
TC O(n^2)
Sc O(1)
using KMP String Search
TC O(m+n)
SC (1)
Using Suffix Tree
TC O(m) m is length of substring
Sc O(1)
To Build Suffix tree Check My Post in Blog
http://shashank7s.blogspot.com/2011/03/wap-for-given-string-s-and-array-of.html
http://www.allisons.org/ll/AlgDS/Tree/Suffix/
Wednesday, April 27, 2011
WAP to Find majority Eelement In Linked lIst In One Pass
you hve a linked list of unknown length n. there is an element which is repeated more than n/2 number of times. find that element... you should use constant extra space and can make only one pass over the list.....
#include
#include
struct node
{
int data;
struct node *next;
};
struct node *head = NULL;
struct node *tail = NULL;
int push(int input)
{
struct node *newnode = (struct node *)malloc(sizeof(struct node));
if(!newnode) return 0;
newnode->data = input;
if(tail) {
tail->next = newnode;
}
newnode->next = NULL;
tail = newnode;
if(!head) head = newnode;
return 1;
}
int display()
{
struct node *current = head;
while(current)
{
printf("%d\n", current->data);
current = current->next;
}
}
int freenodes()
{
struct node *current = head;
if(head) head = head->next;
while(current)
{
free(current);
current = head;
if(head) head = head->next;
}
printf("Linked List Freed\n");
}
int findmaxrepeat()
{
if(!head) return 0;
struct node *current = head->next;
int value = 0;
int count = 0;
int maxvalue = 0;
int maxvaluecnt = 0;
value = head->data; count +=1;
maxvalue = value;
maxvaluecnt = count;
while(current)
{
if(current->data == value) count +=1;
else
{
if(maxvaluecnt < count) { maxvaluecnt = count; maxvalue = value;}
value = current->data; count = 1;
}
current = current->next;
}
return maxvalue;
}
int main()
{
push(1);
push(3);
push(2);
push(3);
push(3);
push(1);
push(1);
push(3);
push(3);
push(1);
push(3);
display();
printf("%d is the maxrepeated value\n", findmaxrepeat());
freenodes();
}
TC O(n)
SC O(1)
Run Here https://ideone.com/qmu7Z
#include
#include
struct node
{
int data;
struct node *next;
};
struct node *head = NULL;
struct node *tail = NULL;
int push(int input)
{
struct node *newnode = (struct node *)malloc(sizeof(struct node));
if(!newnode) return 0;
newnode->data = input;
if(tail) {
tail->next = newnode;
}
newnode->next = NULL;
tail = newnode;
if(!head) head = newnode;
return 1;
}
int display()
{
struct node *current = head;
while(current)
{
printf("%d\n", current->data);
current = current->next;
}
}
int freenodes()
{
struct node *current = head;
if(head) head = head->next;
while(current)
{
free(current);
current = head;
if(head) head = head->next;
}
printf("Linked List Freed\n");
}
int findmaxrepeat()
{
if(!head) return 0;
struct node *current = head->next;
int value = 0;
int count = 0;
int maxvalue = 0;
int maxvaluecnt = 0;
value = head->data; count +=1;
maxvalue = value;
maxvaluecnt = count;
while(current)
{
if(current->data == value) count +=1;
else
{
if(maxvaluecnt < count) { maxvaluecnt = count; maxvalue = value;}
value = current->data; count = 1;
}
current = current->next;
}
return maxvalue;
}
int main()
{
push(1);
push(3);
push(2);
push(3);
push(3);
push(1);
push(1);
push(3);
push(3);
push(1);
push(3);
display();
printf("%d is the maxrepeated value\n", findmaxrepeat());
freenodes();
}
TC O(n)
SC O(1)
Run Here https://ideone.com/qmu7Z
WAP to Find majority Eelement In Linked lIst In One Pass
you hve a linked list of unknown length n. there is an element which is repeated more than n/2 number of times. find that element... you should use constant extra space and can make only one pass over the list.....
#include
#include
struct node
{
int data;
struct node *next;
};
struct node *head = NULL;
struct node *tail = NULL;
int push(int input)
{
struct node *newnode = (struct node *)malloc(sizeof(struct node));
if(!newnode) return 0;
newnode->data = input;
if(tail) {
tail->next = newnode;
}
newnode->next = NULL;
tail = newnode;
if(!head) head = newnode;
return 1;
}
int display()
{
struct node *current = head;
while(current)
{
printf("%d\n", current->data);
current = current->next;
}
}
int freenodes()
{
struct node *current = head;
if(head) head = head->next;
while(current)
{
free(current);
current = head;
if(head) head = head->next;
}
printf("Linked List Freed\n");
}
int findmaxrepeat()
{
if(!head) return 0;
struct node *current = head->next;
int value = 0;
int count = 0;
int maxvalue = 0;
int maxvaluecnt = 0;
value = head->data; count +=1;
maxvalue = value;
maxvaluecnt = count;
while(current)
{
if(current->data == value) count +=1;
else
{
if(maxvaluecnt < count) { maxvaluecnt = count; maxvalue = value;}
value = current->data; count = 1;
}
current = current->next;
}
return maxvalue;
}
int main()
{
push(1);
push(3);
push(2);
push(3);
push(3);
push(1);
push(1);
push(3);
push(3);
push(1);
push(3);
display();
printf("%d is the maxrepeated value\n", findmaxrepeat());
freenodes();
}
#include
#include
struct node
{
int data;
struct node *next;
};
struct node *head = NULL;
struct node *tail = NULL;
int push(int input)
{
struct node *newnode = (struct node *)malloc(sizeof(struct node));
if(!newnode) return 0;
newnode->data = input;
if(tail) {
tail->next = newnode;
}
newnode->next = NULL;
tail = newnode;
if(!head) head = newnode;
return 1;
}
int display()
{
struct node *current = head;
while(current)
{
printf("%d\n", current->data);
current = current->next;
}
}
int freenodes()
{
struct node *current = head;
if(head) head = head->next;
while(current)
{
free(current);
current = head;
if(head) head = head->next;
}
printf("Linked List Freed\n");
}
int findmaxrepeat()
{
if(!head) return 0;
struct node *current = head->next;
int value = 0;
int count = 0;
int maxvalue = 0;
int maxvaluecnt = 0;
value = head->data; count +=1;
maxvalue = value;
maxvaluecnt = count;
while(current)
{
if(current->data == value) count +=1;
else
{
if(maxvaluecnt < count) { maxvaluecnt = count; maxvalue = value;}
value = current->data; count = 1;
}
current = current->next;
}
return maxvalue;
}
int main()
{
push(1);
push(3);
push(2);
push(3);
push(3);
push(1);
push(1);
push(3);
push(3);
push(1);
push(3);
display();
printf("%d is the maxrepeated value\n", findmaxrepeat());
freenodes();
}
Subscribe to:
Posts
(
Atom
)
