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();
}
Sunday, April 24, 2011
WAP to Find Majority Element In Sorted Array Ofcourse It Shoud be Done in O(logn)
/* Program to check for majority element in a sorted array */
#include
# define bool int
/* If x is present in arr[low...high] then returns the index of
first occurance of x, otherwise returns -1 */
int _binarySearch(int arr[], int low, int high, int x);
/* This function returns true if the x is present more than n/2
times in arr[] of size n */
bool isMajority(int arr[], int n, int x)
{
int i = _binarySearch(arr, 0, n-1, x);
printf ( " %d ", i);
/* check if the element is present more than n/2 times */
if(((i + n/2) <= (n -1)) && arr[i + n/2] == x)
return 1;
else
return 0;
}
/* Standard Binary Search function*/
int _binarySearch(int arr[], int low, int high, int x)
{
if(high >= low)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/
/* Check if arr[mid] is the first occurrence of x.
arr[mid] is first occurrence if x is one of the following
is true:
(i) mid == 0 and arr[mid] == x
(ii) arr[mid-1] < x and arr[mid] == x
*/
if(( mid == 0 || x > arr[mid-1]) && (arr[mid] == x))
return mid;
else if(x > arr[mid])
return _binarySearch(arr, (mid + 1), high, x);
else
return _binarySearch(arr, low, (mid -1), x);
}
/*Return -1 if element does not appear more than n/2 times*/
return -1;
}
/* Driver program to check above functions */
int main()
{
int arr[] = {1, 3, 3, 3,3,4,10};//sorted
int n = 7;
int x = 3;
if(isMajority(arr, n, x))
printf("%d appears more than %d times in arr[]", x, n/2);
else
printf("%d does not appear more than %d times in arr[]", x, n/2);
getchar();
return 0;
}
Time Complexity O(logn)
Space Complexity O(1)
Run Here https://ideone.com/kEdi4
#include
# define bool int
/* If x is present in arr[low...high] then returns the index of
first occurance of x, otherwise returns -1 */
int _binarySearch(int arr[], int low, int high, int x);
/* This function returns true if the x is present more than n/2
times in arr[] of size n */
bool isMajority(int arr[], int n, int x)
{
int i = _binarySearch(arr, 0, n-1, x);
printf ( " %d ", i);
/* check if the element is present more than n/2 times */
if(((i + n/2) <= (n -1)) && arr[i + n/2] == x)
return 1;
else
return 0;
}
/* Standard Binary Search function*/
int _binarySearch(int arr[], int low, int high, int x)
{
if(high >= low)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/
/* Check if arr[mid] is the first occurrence of x.
arr[mid] is first occurrence if x is one of the following
is true:
(i) mid == 0 and arr[mid] == x
(ii) arr[mid-1] < x and arr[mid] == x
*/
if(( mid == 0 || x > arr[mid-1]) && (arr[mid] == x))
return mid;
else if(x > arr[mid])
return _binarySearch(arr, (mid + 1), high, x);
else
return _binarySearch(arr, low, (mid -1), x);
}
/*Return -1 if element does not appear more than n/2 times*/
return -1;
}
/* Driver program to check above functions */
int main()
{
int arr[] = {1, 3, 3, 3,3,4,10};//sorted
int n = 7;
int x = 3;
if(isMajority(arr, n, x))
printf("%d appears more than %d times in arr[]", x, n/2);
else
printf("%d does not appear more than %d times in arr[]", x, n/2);
getchar();
return 0;
}
Time Complexity O(logn)
Space Complexity O(1)
Run Here https://ideone.com/kEdi4
WAP to Find Two elements in Array whose sum is closest to zero
Algorithm
1) Sort all the elements of the array.
2) Find the index of first positive element, this is initial value of right index r.
3) Initialize: left index l = r – 1. min_sum = INT_MIN
4) In a loop, look for the candidates by comparing sum with minimum sum. If arr[l] + arr[r] becomes negative then increment the right index r, else decrement left index l.
#include
#include
#include
void quickSort(int *, int, int);
/* Function to print pair of elements having minimum sum */
void minAbsSumPair(int arr[], int arr_size)
{
int l, r = 0, min_sum, sum = 0, min_l, min_r;
/* Array should have at least two elements*/
if(arr_size < 2)
{
printf("Invalid Input");
return;
}
/* Sort the elements */
quickSort(arr, 0, arr_size-1);
/* Find the first positive element. Note that we have condition "r < arr_size -1"
-1 is there to handle the cases when all elements are negative */
while(arr[r] < 0 && r < arr_size - 1)
r++;
/* If all elements are positive then first two elements
are the minimum sum elements */
if(r == 0)
{
printf(" The first two elements %d and %d have minimum sum",
arr[0], arr[1]);
return;
}
/* Start looking for the pair from the first positive element
and last negative element */
l = r - 1;
min_sum = arr[l] + arr[r];
min_l = l; /* min_l is for the left element of minimum sum pair*/
min_r = r; /* min_r is for the right element of minimum sum pair*/
while(l >= 0 && r < arr_size)
{
sum = arr[l] + arr[r];
/*If abs(sum) is less then update the result items*/
if(abs(sum) < abs(min_sum))
{
min_sum = sum;
min_l = l;
min_r = r;
}
if(sum < 0)
r++;
else
l--;
printf (" %d %d %d \n ",min_sum,l,r);
}
printf(" The two elements whose sum is minimum are %d and %d",
arr[min_l], arr[min_r]);
}
/* Driver program to test above function */
int main()
{
int arr[] = {1, 60, -10, 70, -80, 85};
minAbsSumPair(arr, 6);
getchar();
return 0;
}
/* FOLLOWING FUNCTIONS ARE ONLY FOR SORTING
PURPOSE */
void exchange(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int si, int ei)
{
int x = arr[ei];
int i = (si - 1);
int j;
for (j = si; j <= ei - 1; j++)
{
if(arr[j] <= x)
{
i++;
exchange(&arr[i], &arr[j]);
}
}
exchange (&arr[i + 1], &arr[ei]);
return (i + 1);
}
/* Implementation of Quick Sort
arr[] --> Array to be sorted
si --> Starting index
ei --> Ending index
*/
void quickSort(int arr[], int si, int ei)
{
int pi; /* Partitioning index */
if(si < ei)
{
pi = partition(arr, si, ei);
quickSort(arr, si, pi - 1);
quickSort(arr, pi + 1, ei);
}
}
Tim Complexity O(nlogn)
Space Complexity O(1)
Run Here https://ideone.com/Y4sk0
1) Sort all the elements of the array.
2) Find the index of first positive element, this is initial value of right index r.
3) Initialize: left index l = r – 1. min_sum = INT_MIN
4) In a loop, look for the candidates by comparing sum with minimum sum. If arr[l] + arr[r] becomes negative then increment the right index r, else decrement left index l.
#include
#include
#include
void quickSort(int *, int, int);
/* Function to print pair of elements having minimum sum */
void minAbsSumPair(int arr[], int arr_size)
{
int l, r = 0, min_sum, sum = 0, min_l, min_r;
/* Array should have at least two elements*/
if(arr_size < 2)
{
printf("Invalid Input");
return;
}
/* Sort the elements */
quickSort(arr, 0, arr_size-1);
/* Find the first positive element. Note that we have condition "r < arr_size -1"
-1 is there to handle the cases when all elements are negative */
while(arr[r] < 0 && r < arr_size - 1)
r++;
/* If all elements are positive then first two elements
are the minimum sum elements */
if(r == 0)
{
printf(" The first two elements %d and %d have minimum sum",
arr[0], arr[1]);
return;
}
/* Start looking for the pair from the first positive element
and last negative element */
l = r - 1;
min_sum = arr[l] + arr[r];
min_l = l; /* min_l is for the left element of minimum sum pair*/
min_r = r; /* min_r is for the right element of minimum sum pair*/
while(l >= 0 && r < arr_size)
{
sum = arr[l] + arr[r];
/*If abs(sum) is less then update the result items*/
if(abs(sum) < abs(min_sum))
{
min_sum = sum;
min_l = l;
min_r = r;
}
if(sum < 0)
r++;
else
l--;
printf (" %d %d %d \n ",min_sum,l,r);
}
printf(" The two elements whose sum is minimum are %d and %d",
arr[min_l], arr[min_r]);
}
/* Driver program to test above function */
int main()
{
int arr[] = {1, 60, -10, 70, -80, 85};
minAbsSumPair(arr, 6);
getchar();
return 0;
}
/* FOLLOWING FUNCTIONS ARE ONLY FOR SORTING
PURPOSE */
void exchange(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
int partition(int arr[], int si, int ei)
{
int x = arr[ei];
int i = (si - 1);
int j;
for (j = si; j <= ei - 1; j++)
{
if(arr[j] <= x)
{
i++;
exchange(&arr[i], &arr[j]);
}
}
exchange (&arr[i + 1], &arr[ei]);
return (i + 1);
}
/* Implementation of Quick Sort
arr[] --> Array to be sorted
si --> Starting index
ei --> Ending index
*/
void quickSort(int arr[], int si, int ei)
{
int pi; /* Partitioning index */
if(si < ei)
{
pi = partition(arr, si, ei);
quickSort(arr, si, pi - 1);
quickSort(arr, pi + 1, ei);
}
}
Tim Complexity O(nlogn)
Space Complexity O(1)
Run Here https://ideone.com/Y4sk0
WAP to Find Median of Two Sorted Array in O(logn) Time
There are 2 sorted arrays A and B of size n each. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n))
Median: In probability theory and statistics, a median is described as the number separating the higher half of a sample from the lower half.
The median of a finite list of numbers can be found by arranging all the numbers from lowest value to highest value and picking the middle one.
For getting the median of input array { 12, 11, 15, 10, 20 }, first sort the array. We get { 10, 11, 12, 15, 20 } after sorting. Median is the middle element of the sorted array which is 12.
Algo 1 merge both array & return avg of a[n/2]+a[n/2-1]/2;but merging requires extra space of size O(2n)
Algo 2 Linear Time O(n)
Use merge procedure of merge sort. Keep track of count while comparing elements of two arrays. If count becomes n(For 2n elements), we have reached the median. Take the average of the elements at indexes n-1 and n in the merged array. See the below implementation.
if (i==n) base case when all elements of 1st array is less then 1st element of 2nd Array
then m1=m2;
m2=a[0];//obvious
break
if(j==n)
base case when all elements of 2nd array is less then 1st element of 1st Array
then
m1=m2;
m2=a1[0]; //obvious
& break
#include
/* This function returns median of ar1[] and ar2[].
Assumptions in this function:
Both ar1[] and ar2[] are sorted arrays
Both have n elements */
int getMedian(int ar1[], int ar2[], int n)
{
int i = 0; /* Current index of i/p array ar1[] */
int j = 0; /* Current index of i/p array ar2[] */
int count;
int m1 = -1, m2 = -1;
/* Since there are 2n elements, median will be average
of elements at index n-1 and n in the array obtained after
merging ar1 and ar2 */
for(count = 0; count <= n; count++)
{
/*Below is to handle case where all elements of ar1[] are
smaller than smallest(or first) element of ar2[]*/
if(i == n)
{
m1 = m2;
m2 = ar2[0];
break;
}
/*Below is to handle case where all elements of ar2[] are
smaller than smallest(or first) element of ar1[]*/
else if(j == n)
{
m1 = m2;
m2 = ar1[0];
break;
}
if(ar1[i] < ar2[j])
{
m1 = m2; /* Store the prev median */
m2 = ar1[i];
i++;
}
else
{
m1 = m2; /* Store the prev median */
m2 = ar2[j];
j++;
}
}
return (m1 + m2)/2;
}
/* Driver program to test above function */
int main()
{
int ar1[] = {1, 12, 15, 26, 38};
int ar2[] = {2, 13, 17, 30, 45};
printf("%d", getMedian(ar1, ar2, 5)) ;
getchar();
return 0;
}
Time Complexity O(n)
Space Complexity O(1)
Run Here https://ideone.com/er0L7
3rd Algo O(logn)
This method works by first getting medians of the two sorted arrays and then comparing them.
Let ar1 and ar2 be the input arrays.
Algorithm:
1) Calculate the medians m1 and m2 of the input arrays ar1[]
and ar2[] respectively.
2) If m1 and m2 both are equal then we are done.
return m1 (or m2)
3) If m1 is greater than m2, then median is present in one
of the below two subarrays.
a) From first element of ar1 to m1 (ar1[0...|_n/2_|])
b) From m2 to last element of ar2 (ar2[|_n/2_|...n-1])
4) If m2 is greater than m1, then median is present in one
of the below two subarrays.
a) From m1 to last element of ar1 (ar1[|_n/2_|...n-1])
b) From first element of ar2 to m2 (ar2[0...|_n/2_|])
5) Repeat the above process until size of both the subarrays
becomes 2.
6) If size of the two arrays is 2 then use below formula to get
the median.
Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
Example:
ar1[] = {1, 12, 15, 26, 38}
ar2[] = {2, 13, 17, 30, 45}
For above two arrays m1 = 15 and m2 = 17
For the above ar1[] and ar2[], m1 is smaller than m2. So median is present in one of the following two subarrays.
[15, 26, 38] and [2, 13, 17]
Let us repeat the process for above two subarrays:
m1 = 26 m2 = 13.
m1 is greater than m2. So the subarrays become
[15, 26] and [13, 17]
Now size is 2, so median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
= (max(15, 13) + min(26, 17))/2
= (15 + 17)/2
= 16
#include
/* This function returns median of ar1[] and ar2[].
Assumptions in this function:
Both ar1[] and ar2[] are sorted arrays
Both have n elements */
int getMedian(int ar1[], int ar2[], int n)
{
int i = 0; /* Current index of i/p array ar1[] */
int j = 0; /* Current index of i/p array ar2[] */
int count;
int m1 = -1, m2 = -1;
/* Since there are 2n elements, median will be average
of elements at index n-1 and n in the array obtained after
merging ar1 and ar2 */
for(count = 0; count <= n; count++)
{
/*Below is to handle case where all elements of ar1[] are
smaller than smallest(or first) element of ar2[]*/
if(i == n)
{
m1 = m2;
m2 = ar2[0];
break;
}
/*Below is to handle case where all elements of ar2[] are
smaller than smallest(or first) element of ar1[]*/
else if(j == n)
{
m1 = m2;
m2 = ar1[0];
break;
}
if(ar1[i] < ar2[j])
{
m1 = m2; /* Store the prev median */
m2 = ar1[i];
i++;
}
else
{
m1 = m2; /* Store the prev median */
m2 = ar2[j];
j++;
}
}
return (m1 + m2)/2;
}
/* Driver program to test above function */
int main()
{
int ar1[] = {1, 12, 15, 26, 38};
int ar2[] = {2, 13, 17, 30, 45};
printf("%d", getMedian(ar1, ar2, 5)) ;
getchar();
return 0;
}
Time Complexity O(logn)
Space Complexity O(1)
Run Here https://ideone.com/ZE4Vq
Complete Reference From G4G & http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf
Median: In probability theory and statistics, a median is described as the number separating the higher half of a sample from the lower half.
The median of a finite list of numbers can be found by arranging all the numbers from lowest value to highest value and picking the middle one.
For getting the median of input array { 12, 11, 15, 10, 20 }, first sort the array. We get { 10, 11, 12, 15, 20 } after sorting. Median is the middle element of the sorted array which is 12.
Algo 1 merge both array & return avg of a[n/2]+a[n/2-1]/2;but merging requires extra space of size O(2n)
Algo 2 Linear Time O(n)
Use merge procedure of merge sort. Keep track of count while comparing elements of two arrays. If count becomes n(For 2n elements), we have reached the median. Take the average of the elements at indexes n-1 and n in the merged array. See the below implementation.
if (i==n) base case when all elements of 1st array is less then 1st element of 2nd Array
then m1=m2;
m2=a[0];//obvious
break
if(j==n)
base case when all elements of 2nd array is less then 1st element of 1st Array
then
m1=m2;
m2=a1[0]; //obvious
& break
#include
/* This function returns median of ar1[] and ar2[].
Assumptions in this function:
Both ar1[] and ar2[] are sorted arrays
Both have n elements */
int getMedian(int ar1[], int ar2[], int n)
{
int i = 0; /* Current index of i/p array ar1[] */
int j = 0; /* Current index of i/p array ar2[] */
int count;
int m1 = -1, m2 = -1;
/* Since there are 2n elements, median will be average
of elements at index n-1 and n in the array obtained after
merging ar1 and ar2 */
for(count = 0; count <= n; count++)
{
/*Below is to handle case where all elements of ar1[] are
smaller than smallest(or first) element of ar2[]*/
if(i == n)
{
m1 = m2;
m2 = ar2[0];
break;
}
/*Below is to handle case where all elements of ar2[] are
smaller than smallest(or first) element of ar1[]*/
else if(j == n)
{
m1 = m2;
m2 = ar1[0];
break;
}
if(ar1[i] < ar2[j])
{
m1 = m2; /* Store the prev median */
m2 = ar1[i];
i++;
}
else
{
m1 = m2; /* Store the prev median */
m2 = ar2[j];
j++;
}
}
return (m1 + m2)/2;
}
/* Driver program to test above function */
int main()
{
int ar1[] = {1, 12, 15, 26, 38};
int ar2[] = {2, 13, 17, 30, 45};
printf("%d", getMedian(ar1, ar2, 5)) ;
getchar();
return 0;
}
Time Complexity O(n)
Space Complexity O(1)
Run Here https://ideone.com/er0L7
3rd Algo O(logn)
This method works by first getting medians of the two sorted arrays and then comparing them.
Let ar1 and ar2 be the input arrays.
Algorithm:
1) Calculate the medians m1 and m2 of the input arrays ar1[]
and ar2[] respectively.
2) If m1 and m2 both are equal then we are done.
return m1 (or m2)
3) If m1 is greater than m2, then median is present in one
of the below two subarrays.
a) From first element of ar1 to m1 (ar1[0...|_n/2_|])
b) From m2 to last element of ar2 (ar2[|_n/2_|...n-1])
4) If m2 is greater than m1, then median is present in one
of the below two subarrays.
a) From m1 to last element of ar1 (ar1[|_n/2_|...n-1])
b) From first element of ar2 to m2 (ar2[0...|_n/2_|])
5) Repeat the above process until size of both the subarrays
becomes 2.
6) If size of the two arrays is 2 then use below formula to get
the median.
Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
Example:
ar1[] = {1, 12, 15, 26, 38}
ar2[] = {2, 13, 17, 30, 45}
For above two arrays m1 = 15 and m2 = 17
For the above ar1[] and ar2[], m1 is smaller than m2. So median is present in one of the following two subarrays.
[15, 26, 38] and [2, 13, 17]
Let us repeat the process for above two subarrays:
m1 = 26 m2 = 13.
m1 is greater than m2. So the subarrays become
[15, 26] and [13, 17]
Now size is 2, so median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
= (max(15, 13) + min(26, 17))/2
= (15 + 17)/2
= 16
#include
/* This function returns median of ar1[] and ar2[].
Assumptions in this function:
Both ar1[] and ar2[] are sorted arrays
Both have n elements */
int getMedian(int ar1[], int ar2[], int n)
{
int i = 0; /* Current index of i/p array ar1[] */
int j = 0; /* Current index of i/p array ar2[] */
int count;
int m1 = -1, m2 = -1;
/* Since there are 2n elements, median will be average
of elements at index n-1 and n in the array obtained after
merging ar1 and ar2 */
for(count = 0; count <= n; count++)
{
/*Below is to handle case where all elements of ar1[] are
smaller than smallest(or first) element of ar2[]*/
if(i == n)
{
m1 = m2;
m2 = ar2[0];
break;
}
/*Below is to handle case where all elements of ar2[] are
smaller than smallest(or first) element of ar1[]*/
else if(j == n)
{
m1 = m2;
m2 = ar1[0];
break;
}
if(ar1[i] < ar2[j])
{
m1 = m2; /* Store the prev median */
m2 = ar1[i];
i++;
}
else
{
m1 = m2; /* Store the prev median */
m2 = ar2[j];
j++;
}
}
return (m1 + m2)/2;
}
/* Driver program to test above function */
int main()
{
int ar1[] = {1, 12, 15, 26, 38};
int ar2[] = {2, 13, 17, 30, 45};
printf("%d", getMedian(ar1, ar2, 5)) ;
getchar();
return 0;
}
Time Complexity O(logn)
Space Complexity O(1)
Run Here https://ideone.com/ZE4Vq
Complete Reference From G4G & http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf
WAP to Find Median of Two Sorted Array in O(logn) Time
There are 2 sorted arrays A and B of size n each. Write an algorithm to find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). The complexity should be O(log(n))
Median: In probability theory and statistics, a median is described as the number separating the higher half of a sample from the lower half.
The median of a finite list of numbers can be found by arranging all the numbers from lowest value to highest value and picking the middle one.
For getting the median of input array { 12, 11, 15, 10, 20 }, first sort the array. We get { 10, 11, 12, 15, 20 } after sorting. Median is the middle element of the sorted array which is 12.
Algo 1 merge both array & return avg of a[n/2]+a[n/2-1]/2;but merging requires extra space of size O(2n)
Algo 2 Linear Time O(n)
Use merge procedure of merge sort. Keep track of count while comparing elements of two arrays. If count becomes n(For 2n elements), we have reached the median. Take the average of the elements at indexes n-1 and n in the merged array. See the below implementation.
if (i==n) base case when all elements of 1st array is less then 1st element of 2nd Array
then m1=m2;
m2=a[0];//obvious
break
if(j==n)
base case when all elements of 2nd array is less then 1st element of 1st Array
then
m1=m2;
m2=a1[0]; //obvious
& break
#include
/* This function returns median of ar1[] and ar2[].
Assumptions in this function:
Both ar1[] and ar2[] are sorted arrays
Both have n elements */
int getMedian(int ar1[], int ar2[], int n)
{
int i = 0; /* Current index of i/p array ar1[] */
int j = 0; /* Current index of i/p array ar2[] */
int count;
int m1 = -1, m2 = -1;
/* Since there are 2n elements, median will be average
of elements at index n-1 and n in the array obtained after
merging ar1 and ar2 */
for(count = 0; count <= n; count++)
{
/*Below is to handle case where all elements of ar1[] are
smaller than smallest(or first) element of ar2[]*/
if(i == n)
{
m1 = m2;
m2 = ar2[0];
break;
}
/*Below is to handle case where all elements of ar2[] are
smaller than smallest(or first) element of ar1[]*/
else if(j == n)
{
m1 = m2;
m2 = ar1[0];
break;
}
if(ar1[i] < ar2[j])
{
m1 = m2; /* Store the prev median */
m2 = ar1[i];
i++;
}
else
{
m1 = m2; /* Store the prev median */
m2 = ar2[j];
j++;
}
}
return (m1 + m2)/2;
}
/* Driver program to test above function */
int main()
{
int ar1[] = {1, 12, 15, 26, 38};
int ar2[] = {2, 13, 17, 30, 45};
printf("%d", getMedian(ar1, ar2, 5)) ;
getchar();
return 0;
}
Time Complexity O(n)
Space Complexity O(1)
Run Here https://ideone.com/er0L7
3rd Algo O(logn)
This method works by first getting medians of the two sorted arrays and then comparing them.
Let ar1 and ar2 be the input arrays.
Algorithm:
1) Calculate the medians m1 and m2 of the input arrays ar1[]
and ar2[] respectively.
2) If m1 and m2 both are equal then we are done.
return m1 (or m2)
3) If m1 is greater than m2, then median is present in one
of the below two subarrays.
a) From first element of ar1 to m1 (ar1[0...|_n/2_|])
b) From m2 to last element of ar2 (ar2[|_n/2_|...n-1])
4) If m2 is greater than m1, then median is present in one
of the below two subarrays.
a) From m1 to last element of ar1 (ar1[|_n/2_|...n-1])
b) From first element of ar2 to m2 (ar2[0...|_n/2_|])
5) Repeat the above process until size of both the subarrays
becomes 2.
6) If size of the two arrays is 2 then use below formula to get
the median.
Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
Example:
ar1[] = {1, 12, 15, 26, 38}
ar2[] = {2, 13, 17, 30, 45}
For above two arrays m1 = 15 and m2 = 17
For the above ar1[] and ar2[], m1 is smaller than m2. So median is present in one of the following two subarrays.
[15, 26, 38] and [2, 13, 17]
Let us repeat the process for above two subarrays:
m1 = 26 m2 = 13.
m1 is greater than m2. So the subarrays become
[15, 26] and [13, 17]
Now size is 2, so median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
= (max(15, 13) + min(26, 17))/2
= (15 + 17)/2
= 16
Complete Reference From http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf & geeksForgeeks
Median: In probability theory and statistics, a median is described as the number separating the higher half of a sample from the lower half.
The median of a finite list of numbers can be found by arranging all the numbers from lowest value to highest value and picking the middle one.
For getting the median of input array { 12, 11, 15, 10, 20 }, first sort the array. We get { 10, 11, 12, 15, 20 } after sorting. Median is the middle element of the sorted array which is 12.
Algo 1 merge both array & return avg of a[n/2]+a[n/2-1]/2;but merging requires extra space of size O(2n)
Algo 2 Linear Time O(n)
Use merge procedure of merge sort. Keep track of count while comparing elements of two arrays. If count becomes n(For 2n elements), we have reached the median. Take the average of the elements at indexes n-1 and n in the merged array. See the below implementation.
if (i==n) base case when all elements of 1st array is less then 1st element of 2nd Array
then m1=m2;
m2=a[0];//obvious
break
if(j==n)
base case when all elements of 2nd array is less then 1st element of 1st Array
then
m1=m2;
m2=a1[0]; //obvious
& break
#include
/* This function returns median of ar1[] and ar2[].
Assumptions in this function:
Both ar1[] and ar2[] are sorted arrays
Both have n elements */
int getMedian(int ar1[], int ar2[], int n)
{
int i = 0; /* Current index of i/p array ar1[] */
int j = 0; /* Current index of i/p array ar2[] */
int count;
int m1 = -1, m2 = -1;
/* Since there are 2n elements, median will be average
of elements at index n-1 and n in the array obtained after
merging ar1 and ar2 */
for(count = 0; count <= n; count++)
{
/*Below is to handle case where all elements of ar1[] are
smaller than smallest(or first) element of ar2[]*/
if(i == n)
{
m1 = m2;
m2 = ar2[0];
break;
}
/*Below is to handle case where all elements of ar2[] are
smaller than smallest(or first) element of ar1[]*/
else if(j == n)
{
m1 = m2;
m2 = ar1[0];
break;
}
if(ar1[i] < ar2[j])
{
m1 = m2; /* Store the prev median */
m2 = ar1[i];
i++;
}
else
{
m1 = m2; /* Store the prev median */
m2 = ar2[j];
j++;
}
}
return (m1 + m2)/2;
}
/* Driver program to test above function */
int main()
{
int ar1[] = {1, 12, 15, 26, 38};
int ar2[] = {2, 13, 17, 30, 45};
printf("%d", getMedian(ar1, ar2, 5)) ;
getchar();
return 0;
}
Time Complexity O(n)
Space Complexity O(1)
Run Here https://ideone.com/er0L7
3rd Algo O(logn)
This method works by first getting medians of the two sorted arrays and then comparing them.
Let ar1 and ar2 be the input arrays.
Algorithm:
1) Calculate the medians m1 and m2 of the input arrays ar1[]
and ar2[] respectively.
2) If m1 and m2 both are equal then we are done.
return m1 (or m2)
3) If m1 is greater than m2, then median is present in one
of the below two subarrays.
a) From first element of ar1 to m1 (ar1[0...|_n/2_|])
b) From m2 to last element of ar2 (ar2[|_n/2_|...n-1])
4) If m2 is greater than m1, then median is present in one
of the below two subarrays.
a) From m1 to last element of ar1 (ar1[|_n/2_|...n-1])
b) From first element of ar2 to m2 (ar2[0...|_n/2_|])
5) Repeat the above process until size of both the subarrays
becomes 2.
6) If size of the two arrays is 2 then use below formula to get
the median.
Median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
Example:
ar1[] = {1, 12, 15, 26, 38}
ar2[] = {2, 13, 17, 30, 45}
For above two arrays m1 = 15 and m2 = 17
For the above ar1[] and ar2[], m1 is smaller than m2. So median is present in one of the following two subarrays.
[15, 26, 38] and [2, 13, 17]
Let us repeat the process for above two subarrays:
m1 = 26 m2 = 13.
m1 is greater than m2. So the subarrays become
[15, 26] and [13, 17]
Now size is 2, so median = (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1]))/2
= (max(15, 13) + min(26, 17))/2
= (15 + 17)/2
= 16
Complete Reference From http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf & geeksForgeeks
Saturday, April 23, 2011
WAP to print 2D array matrix in Spiral Order
Question: Given a 2D array / matrix of integers. Write a program to print the elements in spiral order. Consider a matrix as show in the diagram to the right. The desired output of the program should be as: 1,2,3,4,8,12,16,20,19,18,17,13,9,5,6, 7,11,15,14,10.
Solution: There are several ways to solve this problem, but I am mentioning a method that is intuitive to understand and easy to implement. The idea is to consider the matrix similar to onion which can be peeled layer after layer. We can use the same approach to print the outer layer of the matrix and keep doing it recursively on a smaller matrix (with 1 less row and 1 less column).
Refer to the image below for a visual explanation. We start by printing the top-right layer of the matrix by calling the print_layer_top_right. It will print 1,2,3,4,8,12,16,20. The print_layer_top_right method then calls the print_layer_bottom_left method which will print 19,18,17,13,9,5. If you observe the size of the target matrix is reducing after each call. Each method basically calls the other method and passes the matrix indexes for the reduced matrix. Both methods take 4 index parameters which represent the target matrix. When the target matrix size is such that there is only one layer left the recursion terminates and by this time the code has printed all the numbers in the full matrix.
Code (C language):
#include
void print_layer_top_right(int a[][4], int x1, int y1, int x2, int y2);
void print_layer_bottom_left(int a[][4], int x1, int y1, int x2, int y2);
int main(void)
{
int a[5][4] = {
{1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,16},
{17,18,19,20}
};
print_layer_top_right(a,0,0,3,4);
}
//
// prints the top and right shells of the matrix
//
void print_layer_top_right(int a[][4], int x1, int y1, int x2, int y2)
{
int i = 0, j = 0;
// print the row
for(i = x1; i<=x2; i++)
{
printf("%d,", a[y1][i]);
}
//print the column
for(j = y1 + 1; j <= y2; j++)
{
printf("%d,", a[j][x2]);
}
// see if we have more cells left
if(x2-x1 > 0)
{
// 'recursively' call the function to print the bottom-left layer
print_layer_bottom_left(a, x1, y1 + 1, x2-1, y2);
}
}
//
// prints the bottom and left shells of the matrix
//
void print_layer_bottom_left(int a[][4], int x1, int y1, int x2, int y2)
{
int i = 0, j = 0;
//print the row of the matrix in reverse
for(i = x2; i>=x1; i--)
{
printf("%d,", a[y2][i]);
}
// print the last column of the matrix in reverse
for(j = y2 - 1; j >= y1; j--)
{
printf("%d,", a[j][x1]);
}
if(x2-x1 > 0)
{
// 'recursively' call the function to print the top-right layer
print_layer_top_right(a, x1+1, y1, x2, y2-1);
}
}
Solution: There are several ways to solve this problem, but I am mentioning a method that is intuitive to understand and easy to implement. The idea is to consider the matrix similar to onion which can be peeled layer after layer. We can use the same approach to print the outer layer of the matrix and keep doing it recursively on a smaller matrix (with 1 less row and 1 less column).
Refer to the image below for a visual explanation. We start by printing the top-right layer of the matrix by calling the print_layer_top_right. It will print 1,2,3,4,8,12,16,20. The print_layer_top_right method then calls the print_layer_bottom_left method which will print 19,18,17,13,9,5. If you observe the size of the target matrix is reducing after each call. Each method basically calls the other method and passes the matrix indexes for the reduced matrix. Both methods take 4 index parameters which represent the target matrix. When the target matrix size is such that there is only one layer left the recursion terminates and by this time the code has printed all the numbers in the full matrix.
Code (C language):
<script type="syntaxhighlighter" class="brush: html"><![CDATA[
#include
void print_layer_top_right(int a[][4], int x1, int y1, int x2, int y2);
void print_layer_bottom_left(int a[][4], int x1, int y1, int x2, int y2);
int main(void)
{
int a[5][4] = {
{1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,16},
{17,18,19,20}
};
print_layer_top_right(a,0,0,3,4);
}
//
// prints the top and right shells of the matrix
//
void print_layer_top_right(int a[][4], int x1, int y1, int x2, int y2)
{
int i = 0, j = 0;
// print the row
for(i = x1; i<=x2; i++)
{
printf("%d,", a[y1][i]);
}
//print the column
for(j = y1 + 1; j <= y2; j++)
{
printf("%d,", a[j][x2]);
}
// see if we have more cells left
if(x2-x1 > 0)
{
// 'recursively' call the function to print the bottom-left layer
print_layer_bottom_left(a, x1, y1 + 1, x2-1, y2);
}
}
//
// prints the bottom and left shells of the matrix
//
void print_layer_bottom_left(int a[][4], int x1, int y1, int x2, int y2)
{
int i = 0, j = 0;
//print the row of the matrix in reverse
for(i = x2; i>=x1; i--)
{
printf("%d,", a[y2][i]);
}
// print the last column of the matrix in reverse
for(j = y2 - 1; j >= y1; j--)
{
printf("%d,", a[j][x1]);
}
if(x2-x1 > 0)
{
// 'recursively' call the function to print the top-right layer
print_layer_top_right(a, x1+1, y1, x2, y2-1);
}
}
]]></script>
Run Here https://ideone.com/ut0Hx
Friday, April 22, 2011
WAP to Write Find MaximumSize Sub-Matrix From Given Matrxi having Size of R*C
Maximum size square sub-matrix with all 1s
April 4, 2010
Given a binary matrix, find out the maximum size square sub-matrix with all 1s.
For example, consider the below binary matrix.
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0
The maximum square sub-matrix with all set bits is
1 1 1
1 1 1
1 1 1
Algorithm:
Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] and M[i][j] is the rightmost and bottommost entry in sub-matrix.
1) Construct a sum matrix S[R][C] for the given M[R][C].
a) Copy first row and first columns as it is from M[][] to S[][]
b) For other entries, use following expressions to construct S[][]
If M[i][j] is 1 then
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
Else /*If M[i][j] is 0*/
S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print
sub-matrix of M[][]
For the given M[R][C] in above example, constructed S[R][C] would be:
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 2 2 0
1 2 2 3 1
0 0 0 0 0
The value of maximum entry in above matrix is 3 and coordinates of the entry are (4, 3). Using the maximum value and its coordinates, we can find out the required sub-matrix.
C program
#include
#define bool int
#define R 6
#define C 5
/* UTILITY FUNCTIONS */
/* Function to get minimum of three values */
int min(int a, int b, int c)
{
int m = a;
if (m > b)
m = b;
if (m > c)
m = c;
return m;
}
void printMaxSubSquare(bool M[R][C])
{
int i,j;
int S[R][C];
int max_of_s, max_i, max_j;
/* Set first column of S[][]*/
for(i = 0; i < R; i++)
S[i][0] = M[i][0];
/* Set first row of S[][]*/
for(j = 0; j < C; j++)
S[0][j] = M[0][j];
/* Construct other entries of S[][]*/
for(i = 1; i < R; i++)
{
for(j = 1; j < C; j++)
{
if(M[i][j] == 1)
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1;
else
S[i][j] = 0;
}
}
/* Find the maximum entry, and indexes of maximum entry
in S[][] */
max_of_s = S[0][0]; max_i = 0; max_j = 0;
for(i = 0; i < R; i++)
{
for(j = 0; j < C; j++)
{
if(max_of_s < S[i][j])
{
max_of_s = S[i][j];
max_i = i;
max_j = j;
}
}
}
printf("\n Maximum size sub-matrix is: \n");
for(i = max_i; i > max_i - max_of_s; i--)
{
for(j = max_j; j > max_j - max_of_s; j--)
{
printf("%d ", M[i][j]);
}
printf("\n");
}
}
/* Driver function to test above functions */
int main()
{
bool M[R][C] = {{0, 1, 1, 0, 1},
{1, 1, 0, 1, 0},
{0, 1, 1, 1, 0},
{1, 1, 1, 1, 0},
{1, 1, 1, 1, 1},
{0, 0, 0, 0, 0}};
printMaxSubSquare(M);
getchar();
}
Run Here https://ideone.com/oFXO6
April 4, 2010
Given a binary matrix, find out the maximum size square sub-matrix with all 1s.
For example, consider the below binary matrix.
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0
The maximum square sub-matrix with all set bits is
1 1 1
1 1 1
1 1 1
Algorithm:
Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] and M[i][j] is the rightmost and bottommost entry in sub-matrix.
1) Construct a sum matrix S[R][C] for the given M[R][C].
a) Copy first row and first columns as it is from M[][] to S[][]
b) For other entries, use following expressions to construct S[][]
If M[i][j] is 1 then
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
Else /*If M[i][j] is 0*/
S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print
sub-matrix of M[][]
For the given M[R][C] in above example, constructed S[R][C] would be:
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 2 2 0
1 2 2 3 1
0 0 0 0 0
The value of maximum entry in above matrix is 3 and coordinates of the entry are (4, 3). Using the maximum value and its coordinates, we can find out the required sub-matrix.
C program
#include
#define bool int
#define R 6
#define C 5
/* UTILITY FUNCTIONS */
/* Function to get minimum of three values */
int min(int a, int b, int c)
{
int m = a;
if (m > b)
m = b;
if (m > c)
m = c;
return m;
}
void printMaxSubSquare(bool M[R][C])
{
int i,j;
int S[R][C];
int max_of_s, max_i, max_j;
/* Set first column of S[][]*/
for(i = 0; i < R; i++)
S[i][0] = M[i][0];
/* Set first row of S[][]*/
for(j = 0; j < C; j++)
S[0][j] = M[0][j];
/* Construct other entries of S[][]*/
for(i = 1; i < R; i++)
{
for(j = 1; j < C; j++)
{
if(M[i][j] == 1)
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1;
else
S[i][j] = 0;
}
}
/* Find the maximum entry, and indexes of maximum entry
in S[][] */
max_of_s = S[0][0]; max_i = 0; max_j = 0;
for(i = 0; i < R; i++)
{
for(j = 0; j < C; j++)
{
if(max_of_s < S[i][j])
{
max_of_s = S[i][j];
max_i = i;
max_j = j;
}
}
}
printf("\n Maximum size sub-matrix is: \n");
for(i = max_i; i > max_i - max_of_s; i--)
{
for(j = max_j; j > max_j - max_of_s; j--)
{
printf("%d ", M[i][j]);
}
printf("\n");
}
}
/* Driver function to test above functions */
int main()
{
bool M[R][C] = {{0, 1, 1, 0, 1},
{1, 1, 0, 1, 0},
{0, 1, 1, 1, 0},
{1, 1, 1, 1, 0},
{1, 1, 1, 1, 1},
{0, 0, 0, 0, 0}};
printMaxSubSquare(M);
getchar();
}
Run Here https://ideone.com/oFXO6
Tuesday, April 19, 2011
WAP for Given a binary tree, write a program to find the cousin nodes of the given node.
//find the level and print the cousins
#include
#include
using namespace std;
struct node{
struct node* left;
struct node* right;
int data;
};
void inorder(struct node* root,int present_level,int level,struct node* parent)
{
if(root!=NULL)
{
if(parent!=root)
inorder(root->left,present_level+1,level,parent);
if(level==present_level)
cout<data<<" ";
if(parent!=root)
inorder(root->right,present_level+1,level,parent);
}
}
void make_tree(struct node **root,int data)
{
if((*root)==NULL)
{
(*root)=new node;
(*root)->left=NULL;
(*root)->right=NULL;
(*root)->data=data;
return;
}
else
{
if(((*root)->data)
else
make_tree(&((*root)->left),data);
}
}
struct node* find_level_and_parent(struct node* root,int data,int* level)
{
struct node* parent=NULL;
struct node* child=root;
while(1)
{
if(child==NULL)
return NULL;
if(child->data==data)
{
return parent;
}
if(data>child->data)
{
parent=child;
child=child->right;
*level=*level+1;
}
else if(data<=child->data)
{
parent=child;
child=child->left;
*level=*level+1;
}
}
}
int main()
{
struct node* root=NULL;
make_tree(&root,6);
make_tree(&root,8);
make_tree(&root,3);
make_tree(&root,4);
make_tree(&root,44);
make_tree(&root,34);
make_tree(&root,12);
make_tree(&root,8);
make_tree(&root,2);
make_tree(&root,1);
make_tree(&root,33);
int level=0;
struct node* temp=find_level_and_parent(root,12,&level);
if(temp!=NULL)
{
cout<<"Level="<
}
Solution Provide By Ankit From CareerCup
Run Here https://ideone.com/ybavU
#include
#include
using namespace std;
struct node{
struct node* left;
struct node* right;
int data;
};
void inorder(struct node* root,int present_level,int level,struct node* parent)
{
if(root!=NULL)
{
if(parent!=root)
inorder(root->left,present_level+1,level,parent);
if(level==present_level)
cout<
if(parent!=root)
inorder(root->right,present_level+1,level,parent);
}
}
void make_tree(struct node **root,int data)
{
if((*root)==NULL)
{
(*root)=new node;
(*root)->left=NULL;
(*root)->right=NULL;
(*root)->data=data;
return;
}
else
{
if(((*root)->data)
else
make_tree(&((*root)->left),data);
}
}
struct node* find_level_and_parent(struct node* root,int data,int* level)
{
struct node* parent=NULL;
struct node* child=root;
while(1)
{
if(child==NULL)
return NULL;
if(child->data==data)
{
return parent;
}
if(data>child->data)
{
parent=child;
child=child->right;
*level=*level+1;
}
else if(data<=child->data)
{
parent=child;
child=child->left;
*level=*level+1;
}
}
}
int main()
{
struct node* root=NULL;
make_tree(&root,6);
make_tree(&root,8);
make_tree(&root,3);
make_tree(&root,4);
make_tree(&root,44);
make_tree(&root,34);
make_tree(&root,12);
make_tree(&root,8);
make_tree(&root,2);
make_tree(&root,1);
make_tree(&root,33);
int level=0;
struct node* temp=find_level_and_parent(root,12,&level);
if(temp!=NULL)
{
cout<<"Level="<
}
Solution Provide By Ankit From CareerCup
Run Here https://ideone.com/ybavU
WAP to Populate The next Higher in Singly Linked List
struct node
{
int data;
struct node *next;
struct node *next_larger;
}
initially next_larger of every node is point to NULL.
now write a c code which set all node's next_larger pointer.
where next_largest point to the next larger then its own value and largest value node's next_larger pointer points to NULL
i.e.
if LL is 3->1->5->6->4
then 3's next_larger points to 4
and 1's next_larger points to 3
and 5's next_larger points to 6
and 6's next_larger points to NULL
and 4's next_larger points to 5
#include
#include
struct node
{
int data;
struct node *next;
struct node *next_higher;
};
struct node* setNextHigher(struct node** head)
{
if(head==NULL)
return NULL;
struct node *start=*head;
(*head)=(*head)->next;
while((*head))
{
if((*head)->datadata)
{
(*head)->next_higher=start;
start= (*head);
}
else
{
struct node *p=start;
while(p->next_higher&&(*head)->data>=p->next_higher->data)
p=p->next_higher;
(*head)->next_higher=p->next_higher;
p->next_higher=(*head);
}
(*head)= (*head)->next;
}
return start;
}
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;
}
/* Function to print linked list */
void printList(struct node *node)
{
while(node != NULL)
{
printf("%d ", node->data);
node = node->next_higher;
}
}
int main()
{
/* Start with the empty list */
struct node* head = NULL;
push(&head, 4);
push(&head, 6);
push(&head, 5);
push(&head, 1);
push(&head, 3);
head=setNextHigher(&head);
printList(head);
getchar();
}
Run Here https://ideone.com/fARV8
{
int data;
struct node *next;
struct node *next_larger;
}
initially next_larger of every node is point to NULL.
now write a c code which set all node's next_larger pointer.
where next_largest point to the next larger then its own value and largest value node's next_larger pointer points to NULL
i.e.
if LL is 3->1->5->6->4
then 3's next_larger points to 4
and 1's next_larger points to 3
and 5's next_larger points to 6
and 6's next_larger points to NULL
and 4's next_larger points to 5
#include
#include
struct node
{
int data;
struct node *next;
struct node *next_higher;
};
struct node* setNextHigher(struct node** head)
{
if(head==NULL)
return NULL;
struct node *start=*head;
(*head)=(*head)->next;
while((*head))
{
if((*head)->data
{
(*head)->next_higher=start;
start= (*head);
}
else
{
struct node *p=start;
while(p->next_higher&&(*head)->data>=p->next_higher->data)
p=p->next_higher;
(*head)->next_higher=p->next_higher;
p->next_higher=(*head);
}
(*head)= (*head)->next;
}
return start;
}
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;
}
/* Function to print linked list */
void printList(struct node *node)
{
while(node != NULL)
{
printf("%d ", node->data);
node = node->next_higher;
}
}
int main()
{
/* Start with the empty list */
struct node* head = NULL;
push(&head, 4);
push(&head, 6);
push(&head, 5);
push(&head, 1);
push(&head, 3);
head=setNextHigher(&head);
printList(head);
getchar();
}
Run Here https://ideone.com/fARV8
WAP to Solve Robot In The Maze
Pretend there is a robot that has to navigate a maze (N x M). The robot can only move down or right and the maze can contain walls. Write an algorithm to determine the number of paths the robot can take.
1st Approach No of Paths
(For clarity, we will solve this part assuming an X*Y Matrix)
Each path has (X-1)+(Y-1) steps. Imagine the following paths:
X X Y Y X (move right -> right -> down -> down -> right)
X Y X Y X (move right -> down -> right -> down -> right)
...& so on
Each path can be fully represented by the moves at which we move
right. That is, if I were to ask you which path you took, you could
simply say “I moved right on step 3 and 4.”
Since you must always move right X-1 times, and you have X-1 + Y-1
total steps, you have to pick X-1 times to move right out of X-1+Y-1
choices. Thus, there are C(X-1, X-1+Y-1) paths (e.g., X-1+Y-1 choose
X-1):
(X-1 + Y-1)! / ((X-1)! * (Y-1)!)..Hope This Equation Clear to Every1
which is nothing but C(2n-2,n-1) Catalan Number
2nd Approach
DP(Always Best)
A robot can take path (N,M) from either (N-1,M) or (N,M-1)
if N and M is 0, its the beginning so return 0.
if N or M is 0, we can get there in 1 path.
We call paths(N,M) with s[][] initialized to -1.
int paths(int i,int j)
{
if(!(i||j)) //means we either can go down or right path as only 1 is
zero
return 1;
if((i&&j))/// no path exist if both are zero
return 0;
if(s[i][j] != -1)
return s[i][j];
s[i][j] = paths(i-1,j) + paths(i,j-1);
return s[i][j];
}
Running C++ Code
#include
void PrintRobotPaths(std::string path, int row, int column, int totrows, int totcols)
{
if(column == totcols && row == totrows)
{
std::cout << path << std::endl;
return;
}
if(row == totrows)
{
std::string pc = path + " D";
PrintRobotPaths(pc, row, column+1, totrows, totcols);
return;
}
if(column == totcols)
{
std::string pr = path + " R";
PrintRobotPaths(pr, row+1, column, totrows, totcols);
return;
}
std::string pr = path + " R";
std::string pc = path + " D";
PrintRobotPaths(pr, row+1, column, totrows, totcols);
PrintRobotPaths(pc, row, column+1, totrows, totcols);
}
int main(int argc, char** argv)
{
int row=4;
int column=4;
std::string path;
PrintRobotPaths(path,1, 1, row, column);
return 0;
}
Run Here https://ideone.com/qq7dh
1st Approach No of Paths
(For clarity, we will solve this part assuming an X*Y Matrix)
Each path has (X-1)+(Y-1) steps. Imagine the following paths:
X X Y Y X (move right -> right -> down -> down -> right)
X Y X Y X (move right -> down -> right -> down -> right)
...& so on
Each path can be fully represented by the moves at which we move
right. That is, if I were to ask you which path you took, you could
simply say “I moved right on step 3 and 4.”
Since you must always move right X-1 times, and you have X-1 + Y-1
total steps, you have to pick X-1 times to move right out of X-1+Y-1
choices. Thus, there are C(X-1, X-1+Y-1) paths (e.g., X-1+Y-1 choose
X-1):
(X-1 + Y-1)! / ((X-1)! * (Y-1)!)..Hope This Equation Clear to Every1
which is nothing but C(2n-2,n-1) Catalan Number
2nd Approach
DP(Always Best)
A robot can take path (N,M) from either (N-1,M) or (N,M-1)
if N and M is 0, its the beginning so return 0.
if N or M is 0, we can get there in 1 path.
We call paths(N,M) with s[][] initialized to -1.
int paths(int i,int j)
{
if(!(i||j)) //means we either can go down or right path as only 1 is
zero
return 1;
if((i&&j))/// no path exist if both are zero
return 0;
if(s[i][j] != -1)
return s[i][j];
s[i][j] = paths(i-1,j) + paths(i,j-1);
return s[i][j];
}
Running C++ Code
#include
void PrintRobotPaths(std::string path, int row, int column, int totrows, int totcols)
{
if(column == totcols && row == totrows)
{
std::cout << path << std::endl;
return;
}
if(row == totrows)
{
std::string pc = path + " D";
PrintRobotPaths(pc, row, column+1, totrows, totcols);
return;
}
if(column == totcols)
{
std::string pr = path + " R";
PrintRobotPaths(pr, row+1, column, totrows, totcols);
return;
}
std::string pr = path + " R";
std::string pc = path + " D";
PrintRobotPaths(pr, row+1, column, totrows, totcols);
PrintRobotPaths(pc, row, column+1, totrows, totcols);
}
int main(int argc, char** argv)
{
int row=4;
int column=4;
std::string path;
PrintRobotPaths(path,1, 1, row, column);
return 0;
}
Run Here https://ideone.com/qq7dh
Monday, April 18, 2011
Iterative Solution of Binary Tree Traversal Inorder,Preorder,PostOrder
Most problems involving binary trees can be solved by using recursion. Recursion is inherent to trees. But, keep in mind that recursion has a memory overhead because of the additional stack space required for the recursive method calls. Sometime interviewers will ask to solve problems related to trees without using recursion. This can sometimes make the problem challenging. In this problem, even though we will not use recursion explicitly, we will use the Stack data structure that emulates what recursion does.
Inorder
Algo
1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then
a) Pop the top item from stack.
b) Print the popped item, set current = current->right
c) Go to step 3.
5) If current is NULL and stack is empty then we are done.
#include
#include
#define bool int
/* A binary tree tNode has data, pointer to left child
and a pointer to right child */
struct tNode
{
int data;
struct tNode* left;
struct tNode* right;
};
/* Structure of a stack node. Linked List implementation is used for
stack. A stack node contains a pointer to tree node and a pointer to
next stack node */
struct sNode
{
struct tNode *t;
struct sNode *next;
};
/* Stack related functions */
void push(struct sNode** top_ref, struct tNode *t);
struct tNode *pop(struct sNode** top_ref);
bool isEmpty(struct sNode *top);
/* Iterative function for inorder tree traversal */
void inOrder(struct tNode *root)
{
/* set current to root of binary tree */
struct tNode *current = root;
struct sNode *s = NULL; /* Initialize stack s */
bool done = 0;
while (!done)
{
/* Reach the left most tNode of the current tNode */
if(current != NULL)
{
/* place pointer to a tree node on the stack before traversing
the node's left subtree */
push(&s, current);
current = current->left;
}
/* backtrack from the empty subtree and visit the tNode
at the top of the stack; however, if the stack is empty,
you are done */
else
{
if (!isEmpty(s))
{
current = pop(&s);
printf("%d ", current->data);
/* we have visited the node and its left subtree.
Now, it's right subtree's turn */
current = current->right;
}
else
done = 1;
}
} /* end of while */
}
/* UTILITY FUNCTIONS */
/* Function to push an item to sNode*/
void push(struct sNode** top_ref, struct tNode *t)
{
/* allocate tNode */
struct sNode* new_tNode =
(struct sNode*) malloc(sizeof(struct sNode));
if(new_tNode == NULL)
{
printf("Stack Overflow \n");
getchar();
exit(0);
}
/* put in the data */
new_tNode->t = t;
/* link the old list off the new tNode */
new_tNode->next = (*top_ref);
/* move the head to point to the new tNode */
(*top_ref) = new_tNode;
}
/* The function returns true if stack is empty, otherwise false */
bool isEmpty(struct sNode *top)
{
return (top == NULL)? 1 : 0;
}
/* Function to pop an item from stack*/
struct tNode *pop(struct sNode** top_ref)
{
struct tNode *res;
struct sNode *top;
/*If sNode is empty then error */
if(isEmpty(*top_ref))
{
printf("Stack Underflow \n");
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->t;
*top_ref = top->next;
free(top);
return res;
}
}
/* Helper function that allocates a new tNode with the
given data and NULL left and right pointers. */
struct tNode* newtNode(int data)
{
struct tNode* tNode = (struct tNode*)
malloc(sizeof(struct tNode));
tNode->data = data;
tNode->left = NULL;
tNode->right = NULL;
return(tNode);
}
/* Driver program to test above functions*/
int main()
{
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
struct tNode *root = newtNode(1);
root->left = newtNode(2);
root->right = newtNode(3);
root->left->left = newtNode(4);
root->left->right = newtNode(5);
inOrder(root);
getchar();
return 0;
}
Run Here https://ideone.com/bgss3
Preorder Traversal
Algo
/**
non-recursive version of Pre-order traversal
void PreOrderNonRecur(NODE *root)
Algorithm:
create a stack
PUSH the root node of the tree into the stack
While the stack is not empty
POP a node
If the node is not NULL
Print the value of the node
PUSH the node's right child into the stack
PUSH the node's left child into the stack
*/
#include
#include
#define bool int
/* A binary tree tNode has data, pointer to left child
and a pointer to right child */
struct tNode
{
int data;
struct tNode* left;
struct tNode* right;
};
/* Structure of a stack node. Linked List implementation is used for
stack. A stack node contains a pointer to tree node and a pointer to
next stack node */
struct sNode
{
struct tNode *t;
struct sNode *next;
};
/* Stack related functions */
void push(struct sNode** top_ref, struct tNode *t);
struct tNode *pop(struct sNode** top_ref);
bool isEmpty(struct sNode *top);
/* Iterative function for preorder tree traversal */
void postOrder(struct tNode *root)
{
/* set current to root of binary tree */
struct tNode *current=root;
struct sNode *s = NULL; /* Initialize stack s */
push(&s,current);
while(!isEmpty(s))
{
current=pop(&s);
printf(" %d ", current->data);
push(&s,current->right);
push(&s,current->left);
}
}
/* UTILITY FUNCTIONS */
/* Function to push an item to sNode*/
void push(struct sNode** top_ref, struct tNode *t)
{
/* allocate tNode */
struct sNode* new_tNode =
(struct sNode*) malloc(sizeof(struct sNode));
if(new_tNode == NULL)
{
printf("Stack Overflow \n");
getchar();
exit(0);
}
/* put in the data */
new_tNode->t = t;
/* link the old list off the new tNode */
new_tNode->next = (*top_ref);
/* move the head to point to the new tNode */
(*top_ref) = new_tNode;
}
/* The function returns true if stack is empty, otherwise false */
bool isEmpty(struct sNode *top)
{
return (top == NULL)? 1 : 0;
}
/* Function to pop an item from stack*/
struct tNode *pop(struct sNode** top_ref)
{
struct tNode *res;
struct sNode *top;
/*If sNode is empty then error */
if(isEmpty(*top_ref))
{
printf("Stack Underflow \n");
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->t;
*top_ref = top->next;
free(top);
return res;
}
}
/* Helper function that allocates a new tNode with the
given data and NULL left and right pointers. */
struct tNode* newtNode(int data)
{
struct tNode* tNode = (struct tNode*)
malloc(sizeof(struct tNode));
tNode->data = data;
tNode->left = NULL;
tNode->right = NULL;
return(tNode);
}
/* Driver program to test above functions*/
int main()
{
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
struct tNode *root = newtNode(1);
root->left = newtNode(2);
root->right = newtNode(3);
root->left->left = newtNode(4);
root->left->right = newtNode(5);
postOrder(root);
getchar();
return 0;
}
run here https://ideone.com/YUPvS
PostOrder Traversal
Algo use Tow Stack child & Parent
* Push the root node to the child stack.
* while child stack is not empty
* Pop a node from the child stack, and push it to the parent stack.
* Push its left child followed by its right child to the child stack.
* end while
* Now the parent stack would have all the nodes ready to be traversed in post-order. Pop off the nodes from the parent stack one by one and you will have the post order traversal of the tree.
#include
#include
#define bool int
/* A binary tree tNode has data, pointer to left child
and a pointer to right child */
struct tNode
{
int data;
struct tNode* left;
struct tNode* right;
};
/* Structure of a stack node. Linked List implementation is used for
stack. A stack node contains a pointer to tree node and a pointer to
next stack node */
struct sNode
{
struct tNode *t;
struct sNode *next;
};
/* Stack related functions */
void push(struct sNode** top_ref, struct tNode *t);
struct tNode *pop(struct sNode** top_ref);
bool isEmpty(struct sNode *top);
/* Iterative function for postorder tree traversal */
void postOrder(struct tNode *root)
{
if(!root)
return;
/* set current to root of binary tree */
struct sNode *child,*parent = NULL; /* Initialize stack s */
push(&child,root);
while(!isEmpty(child))
{
struct tNode *current =pop(&child);
push(&parent,current);
if(current->left)
push(&child,current->left);
if(current->right)
push(&child,current->right);
}
while(!isEmpty(parent))
{
struct tNode *current= pop(&parent);
printf(" %d ",current->data);
}
}
/* UTILITY FUNCTIONS */
/* Function to push an item to sNode*/
void push(struct sNode** top_ref, struct tNode *t)
{
/* allocate tNode */
struct sNode* new_tNode =
(struct sNode*) malloc(sizeof(struct sNode));
if(new_tNode == NULL)
{
printf("Stack Overflow \n");
getchar();
exit(0);
}
/* put in the data */
new_tNode->t = t;
/* link the old list off the new tNode */
new_tNode->next = (*top_ref);
/* move the head to point to the new tNode */
(*top_ref) = new_tNode;
}
/* The function returns true if stack is empty, otherwise false */
bool isEmpty(struct sNode *top)
{
return (top == NULL)? 1 : 0;
}
/* Function to pop an item from stack*/
struct tNode *pop(struct sNode** top_ref)
{
struct tNode *res;
struct sNode *top;
/*If sNode is empty then error */
if(isEmpty(*top_ref))
{
printf("Stack Underflow \n");
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->t;
*top_ref = top->next;
free(top);
return res;
}
}
/* Helper function that allocates a new tNode with the
given data and NULL left and right pointers. */
struct tNode* newtNode(int data)
{
struct tNode* tNode = (struct tNode*)
malloc(sizeof(struct tNode));
tNode->data = data;
tNode->left = NULL;
tNode->right = NULL;
return(tNode);
}
/* Driver program to test above functions*/
int main()
{
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
struct tNode *root = newtNode(1);
root->left = newtNode(2);
root->right = newtNode(3);
root->left->left = newtNode(4);
root->left->right = newtNode(5);
root->right->left = newtNode(6);
root->right->right = newtNode(7);
postOrder(root);
getchar();
return 0;
}
Run here https://ideone.com/uFq33
Excellent Explanation of Postorder Using Single Stack
http://www.ihas1337code.com/2010/10/binary-tree-post-order-traversal.html
Inorder
Algo
1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then
a) Pop the top item from stack.
b) Print the popped item, set current = current->right
c) Go to step 3.
5) If current is NULL and stack is empty then we are done.
#include
#include
#define bool int
/* A binary tree tNode has data, pointer to left child
and a pointer to right child */
struct tNode
{
int data;
struct tNode* left;
struct tNode* right;
};
/* Structure of a stack node. Linked List implementation is used for
stack. A stack node contains a pointer to tree node and a pointer to
next stack node */
struct sNode
{
struct tNode *t;
struct sNode *next;
};
/* Stack related functions */
void push(struct sNode** top_ref, struct tNode *t);
struct tNode *pop(struct sNode** top_ref);
bool isEmpty(struct sNode *top);
/* Iterative function for inorder tree traversal */
void inOrder(struct tNode *root)
{
/* set current to root of binary tree */
struct tNode *current = root;
struct sNode *s = NULL; /* Initialize stack s */
bool done = 0;
while (!done)
{
/* Reach the left most tNode of the current tNode */
if(current != NULL)
{
/* place pointer to a tree node on the stack before traversing
the node's left subtree */
push(&s, current);
current = current->left;
}
/* backtrack from the empty subtree and visit the tNode
at the top of the stack; however, if the stack is empty,
you are done */
else
{
if (!isEmpty(s))
{
current = pop(&s);
printf("%d ", current->data);
/* we have visited the node and its left subtree.
Now, it's right subtree's turn */
current = current->right;
}
else
done = 1;
}
} /* end of while */
}
/* UTILITY FUNCTIONS */
/* Function to push an item to sNode*/
void push(struct sNode** top_ref, struct tNode *t)
{
/* allocate tNode */
struct sNode* new_tNode =
(struct sNode*) malloc(sizeof(struct sNode));
if(new_tNode == NULL)
{
printf("Stack Overflow \n");
getchar();
exit(0);
}
/* put in the data */
new_tNode->t = t;
/* link the old list off the new tNode */
new_tNode->next = (*top_ref);
/* move the head to point to the new tNode */
(*top_ref) = new_tNode;
}
/* The function returns true if stack is empty, otherwise false */
bool isEmpty(struct sNode *top)
{
return (top == NULL)? 1 : 0;
}
/* Function to pop an item from stack*/
struct tNode *pop(struct sNode** top_ref)
{
struct tNode *res;
struct sNode *top;
/*If sNode is empty then error */
if(isEmpty(*top_ref))
{
printf("Stack Underflow \n");
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->t;
*top_ref = top->next;
free(top);
return res;
}
}
/* Helper function that allocates a new tNode with the
given data and NULL left and right pointers. */
struct tNode* newtNode(int data)
{
struct tNode* tNode = (struct tNode*)
malloc(sizeof(struct tNode));
tNode->data = data;
tNode->left = NULL;
tNode->right = NULL;
return(tNode);
}
/* Driver program to test above functions*/
int main()
{
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
struct tNode *root = newtNode(1);
root->left = newtNode(2);
root->right = newtNode(3);
root->left->left = newtNode(4);
root->left->right = newtNode(5);
inOrder(root);
getchar();
return 0;
}
Run Here https://ideone.com/bgss3
Preorder Traversal
Algo
/**
non-recursive version of Pre-order traversal
void PreOrderNonRecur(NODE *root)
Algorithm:
create a stack
PUSH the root node of the tree into the stack
While the stack is not empty
POP a node
If the node is not NULL
Print the value of the node
PUSH the node's right child into the stack
PUSH the node's left child into the stack
*/
#include
#include
#define bool int
/* A binary tree tNode has data, pointer to left child
and a pointer to right child */
struct tNode
{
int data;
struct tNode* left;
struct tNode* right;
};
/* Structure of a stack node. Linked List implementation is used for
stack. A stack node contains a pointer to tree node and a pointer to
next stack node */
struct sNode
{
struct tNode *t;
struct sNode *next;
};
/* Stack related functions */
void push(struct sNode** top_ref, struct tNode *t);
struct tNode *pop(struct sNode** top_ref);
bool isEmpty(struct sNode *top);
/* Iterative function for preorder tree traversal */
void postOrder(struct tNode *root)
{
/* set current to root of binary tree */
struct tNode *current=root;
struct sNode *s = NULL; /* Initialize stack s */
push(&s,current);
while(!isEmpty(s))
{
current=pop(&s);
printf(" %d ", current->data);
push(&s,current->right);
push(&s,current->left);
}
}
/* UTILITY FUNCTIONS */
/* Function to push an item to sNode*/
void push(struct sNode** top_ref, struct tNode *t)
{
/* allocate tNode */
struct sNode* new_tNode =
(struct sNode*) malloc(sizeof(struct sNode));
if(new_tNode == NULL)
{
printf("Stack Overflow \n");
getchar();
exit(0);
}
/* put in the data */
new_tNode->t = t;
/* link the old list off the new tNode */
new_tNode->next = (*top_ref);
/* move the head to point to the new tNode */
(*top_ref) = new_tNode;
}
/* The function returns true if stack is empty, otherwise false */
bool isEmpty(struct sNode *top)
{
return (top == NULL)? 1 : 0;
}
/* Function to pop an item from stack*/
struct tNode *pop(struct sNode** top_ref)
{
struct tNode *res;
struct sNode *top;
/*If sNode is empty then error */
if(isEmpty(*top_ref))
{
printf("Stack Underflow \n");
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->t;
*top_ref = top->next;
free(top);
return res;
}
}
/* Helper function that allocates a new tNode with the
given data and NULL left and right pointers. */
struct tNode* newtNode(int data)
{
struct tNode* tNode = (struct tNode*)
malloc(sizeof(struct tNode));
tNode->data = data;
tNode->left = NULL;
tNode->right = NULL;
return(tNode);
}
/* Driver program to test above functions*/
int main()
{
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
struct tNode *root = newtNode(1);
root->left = newtNode(2);
root->right = newtNode(3);
root->left->left = newtNode(4);
root->left->right = newtNode(5);
postOrder(root);
getchar();
return 0;
}
run here https://ideone.com/YUPvS
PostOrder Traversal
Algo use Tow Stack child & Parent
* Push the root node to the child stack.
* while child stack is not empty
* Pop a node from the child stack, and push it to the parent stack.
* Push its left child followed by its right child to the child stack.
* end while
* Now the parent stack would have all the nodes ready to be traversed in post-order. Pop off the nodes from the parent stack one by one and you will have the post order traversal of the tree.
#include
#include
#define bool int
/* A binary tree tNode has data, pointer to left child
and a pointer to right child */
struct tNode
{
int data;
struct tNode* left;
struct tNode* right;
};
/* Structure of a stack node. Linked List implementation is used for
stack. A stack node contains a pointer to tree node and a pointer to
next stack node */
struct sNode
{
struct tNode *t;
struct sNode *next;
};
/* Stack related functions */
void push(struct sNode** top_ref, struct tNode *t);
struct tNode *pop(struct sNode** top_ref);
bool isEmpty(struct sNode *top);
/* Iterative function for postorder tree traversal */
void postOrder(struct tNode *root)
{
if(!root)
return;
/* set current to root of binary tree */
struct sNode *child,*parent = NULL; /* Initialize stack s */
push(&child,root);
while(!isEmpty(child))
{
struct tNode *current =pop(&child);
push(&parent,current);
if(current->left)
push(&child,current->left);
if(current->right)
push(&child,current->right);
}
while(!isEmpty(parent))
{
struct tNode *current= pop(&parent);
printf(" %d ",current->data);
}
}
/* UTILITY FUNCTIONS */
/* Function to push an item to sNode*/
void push(struct sNode** top_ref, struct tNode *t)
{
/* allocate tNode */
struct sNode* new_tNode =
(struct sNode*) malloc(sizeof(struct sNode));
if(new_tNode == NULL)
{
printf("Stack Overflow \n");
getchar();
exit(0);
}
/* put in the data */
new_tNode->t = t;
/* link the old list off the new tNode */
new_tNode->next = (*top_ref);
/* move the head to point to the new tNode */
(*top_ref) = new_tNode;
}
/* The function returns true if stack is empty, otherwise false */
bool isEmpty(struct sNode *top)
{
return (top == NULL)? 1 : 0;
}
/* Function to pop an item from stack*/
struct tNode *pop(struct sNode** top_ref)
{
struct tNode *res;
struct sNode *top;
/*If sNode is empty then error */
if(isEmpty(*top_ref))
{
printf("Stack Underflow \n");
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->t;
*top_ref = top->next;
free(top);
return res;
}
}
/* Helper function that allocates a new tNode with the
given data and NULL left and right pointers. */
struct tNode* newtNode(int data)
{
struct tNode* tNode = (struct tNode*)
malloc(sizeof(struct tNode));
tNode->data = data;
tNode->left = NULL;
tNode->right = NULL;
return(tNode);
}
/* Driver program to test above functions*/
int main()
{
/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
struct tNode *root = newtNode(1);
root->left = newtNode(2);
root->right = newtNode(3);
root->left->left = newtNode(4);
root->left->right = newtNode(5);
root->right->left = newtNode(6);
root->right->right = newtNode(7);
postOrder(root);
getchar();
return 0;
}
Run here https://ideone.com/uFq33
Excellent Explanation of Postorder Using Single Stack
http://www.ihas1337code.com/2010/10/binary-tree-post-order-traversal.html
Subscribe to:
Posts
(
Atom
)
