Stack
Problem - 1: Reverse a Stack in place:void PercolateUp()
{
Element a,b;
if(IsEmpty())
return;
a = Pop();
if(IsEmpty())
{
Push(a);
return;
}
Percolate();
b = Pop();
Push(a);
Push(b);
}
void Reverse()
{
Element a;
if(IsEmpty())
return;
PercolateUp();
a = Pop();
Reverse();
Push(a);
}
{
Element a,b;
if(IsEmpty())
return;
a = Pop();
if(IsEmpty())
{
Push(a);
return;
}
Percolate();
b = Pop();
Push(a);
Push(b);
}
void Reverse()
{
Element a;
if(IsEmpty())
return;
PercolateUp();
a = Pop();
Reverse();
Push(a);
}
Queue
Problem - 1: Implement circular queues
/*class Queue {
public:
Queue() {
cout << "Inside Queue()" << endl;
_front = 0;
_rear = 0;
}
int push(int data);
int pop();
bool isEmpty();
bool isFull();
~Queue() {
cout << "Inside ~Queue()" << endl;
}
private:
static const int _size = 10;
int _data[_size];
int _front;
int _rear;
};
int Queue::push(int data){
if(!isFull()) {
_rear = (_rear + 1) % _size;
_data[_rear] = data;
cout << "Queue::pushed: "<< _data[_rear] << endl;
return 0;
} else {
cout << "Over Flow!" << endl;
return -1;
}
}
int Queue::pop() {
if(!isEmpty()) {
_front = (_front + 1) % _size;
cout << "Queue::poped: "<< _data[_front] << endl;
return _data[_front];
} else {
cout << "Under Flow!" << endl;
return -1;
}
}
bool Queue::isEmpty() {
if (_front == _rear)
return 1;
else
return 0;
}
bool Queue::isFull() {
if ((_rear+1) % _size == _front)
return 1;
else
return 0;
}
/*class Queue {
public:
Queue() {
cout << "Inside Queue()" << endl;
_front = 0;
_rear = 0;
}
int push(int data);
int pop();
bool isEmpty();
bool isFull();
~Queue() {
cout << "Inside ~Queue()" << endl;
}
private:
static const int _size = 10;
int _data[_size];
int _front;
int _rear;
};
int Queue::push(int data){
if(!isFull()) {
_rear = (_rear + 1) % _size;
_data[_rear] = data;
cout << "Queue::pushed: "<< _data[_rear] << endl;
return 0;
} else {
cout << "Over Flow!" << endl;
return -1;
}
}
int Queue::pop() {
if(!isEmpty()) {
_front = (_front + 1) % _size;
cout << "Queue::poped: "<< _data[_front] << endl;
return _data[_front];
} else {
cout << "Under Flow!" << endl;
return -1;
}
}
bool Queue::isEmpty() {
if (_front == _rear)
return 1;
else
return 0;
}
bool Queue::isFull() {
if ((_rear+1) % _size == _front)
return 1;
else
return 0;
}
Link-List
Problem - 1: Return Nth the node from the end of the linked list in one pass.
Space complexity : O(1), constantProblem - 2: Reverse a singly linked list
Space complexity : O(1), constant
Approach 2 Recursive reverse
List recursiveReverse(List L)
{
List first, rest;
if(!L)
return NULL;
first = L;
rest = L->next;
if(!rest)
return NULL;
rest = recursiveReverse(rest);
first->next->next = first;
first->next = NULL;
L=rest;
return L;
}
Time complexity : O( n )
Space complexity : O(1), constant
Approach 3 Iterative version with only one variable
Swap (Node* A, Node* B)
{
A = (node *) ((unsigned long) A ^(unsigned long) B);
B= (node *) ((unsigned long) A ^(unsigned long) B);
A =(node *) ((unsigned long) A ^ (unsigned long) B);
}
Space complexity : O(1), constant
Problem - 3: Delete a node in single non circular linked list
Space complexity : O(1), constant
Problem - 4: Implement "Merge Sort" for "Link List"?
line merge_sort (line list1)
{
if (list1 == NULL || list1.next == NULL)
return list1;
line list2 = split (list1);
list1 = merge_sort (list1);
list2 = merge_sort (list2);
return merge (list1, list2);
}
line split (line list1)
{
if (list1 == NULL)
return list1;
if (list1.next == NULL)
return list1.next;
line list2 = list1.next;
list1.next = list2.next;
list2.next = split (list2.next);
return list2;
}
line merge (line list1, line list2)
{
if (&list1 == NULL)
return list2;
if (list2 == NULL)
return list1;
if (list1.data < list2.data)
{
list1.next = merge (list1.next, list2);
return list1;
}
else
{
list2.next = merge (list1, list2.next);
return list2;
}
}Time complexity : O(n log n )
Space complexity : O(1), constant
Problem - 5: There are two singly linked lists l1 and l2 representing polynomials in X. we have to find difference b/w lists l1-l2. lists are in orders of descending powers.
constraints: no extra space i.e. O(1) space O(m+n) time complexity m and n and nodes in the lists.
struct node{
int coeff;
int power;
node *next;
};
Subtract (Poly* A, Poly* B)
Problem - 6: Evaluate a polynomial
typedef struct node
{
float cf;
float px;
float py;
struct node *next;
}mynode;
float evaluate(mynode *head, float x, float y)
{
float x,y,sum;
sum = 0;
mynode *poly;
for(poly = head->next; poly != head; poly = poly->next)
{
sum = sum + poly->cf * pow(x, poly->px) * pow(y, poly->py);
}
return(sum);
}
Problem - 7: There are two link list...having a common tail...i.e they are in a Y shape...find the point of intersection in O(n) time and constant extra space.
1) Take 2 pointers. ptr1 and ptr2
2) Start moving towards tail.
3) As soon as one of pointer reaches last node, start counter.
4) When the next pointer also reaches last node, stop counter.
5) Now you know, what is difference in length of two list.
6) Initialize the two pointers again with the two linked lists heads.
7) move the pointer with longer linked list by counter number of nodes, so that now the lengths are equal for both.
8) start moving both pointers now and as soon as they hit the same node, it is the intersection.
Problem - 8: Detect and remove loop in link list
1. Loop Detection: Take two pointers Fast and Slow (Slow jumps one step at a time while Fast two step)
While (Fast != NULL)
if(Fast == Slow)
return true;
else
fast = fast->next->next
slow = slow->next
return false;
2. Loop Length: After detecting loop stop one pointer and increment other pointer by 1 step untill
Loop
if (fast == slow)
break;
else
slow++
LoopLength++
EndLoop
3. Loop Position: You can find out loop start position also.
Fast = Slow = Start
Fast += LoopLenght
Loop
If Fast != Slow
Fast++;
Slow++
EndLoop
4. Loop Removal:Fast and Slow Both are pointing to the start of loop position.
Loop
if(Slow == Fast->next)
break;
Fast = Fast->next; Fast->next = NULL;
Problem - 9: Return Nth the node from the end of the linked list in one pass.
Node * GetNthNode ( Node* Head , int NthNode )
{
Node * pNthNode = NULL;
Node * pTempNode = NULL;
int nCurrentElement = 0;
for ( pTempNode = Head; pTempNode != NULL; pTempNode = pTempNode->pNext )
{
nCurrentElement++;
if ( nCurrentElement - NthNode == 0 )
{
pNthNode = Head;
}
else
if ( nCurrentElement - NthNode > 0)
{
pNthNode = pNthNode ->pNext;
}
}
if (pNthNode )
{
return pNthNode;
}
else
return NULL;
}
Time complexity : O( n )Space complexity : O(1), constantProblem - 2: Reverse a singly linked list
Approach 1 - Iterative version with three variable
Node* ReverseList( Node ** List )
{
Node *temp1 = *List;
Node * temp2 = NULL;
Node * temp3 = NULL;
while ( temp1 )
{
*List = temp1; //set the head to last node
temp2= temp1->pNext; // save the next ptr in temp2
temp1->pNext = temp3; // change next to privous
temp3 = temp1;
temp1 = temp2;
}
return *List;
}
Time complexity : O( n )Space complexity : O(1), constant
Approach 2 Recursive reverse
List recursiveReverse(List L)
{
List first, rest;
if(!L)
return NULL;
first = L;
rest = L->next;
if(!rest)
return NULL;
rest = recursiveReverse(rest);
first->next->next = first;
first->next = NULL;
L=rest;
return L;
}
Time complexity : O( n )
Space complexity : O(1), constant
Approach 3 Iterative version with only one variable
Swap (Node* A, Node* B)
{
A = (node *) ((unsigned long) A ^(unsigned long) B);
B= (node *) ((unsigned long) A ^(unsigned long) B);
A =(node *) ((unsigned long) A ^ (unsigned long) B);
}
void reverse (node* head)
{
node *temp=NULL;
while(true)
{
if(head->next==NULL)
{
head->next=temp;
break;
}
Swap(head->next, temp);
Swap(head, temp);
}
}
Time complexity : O( n ){
node *temp=NULL;
while(true)
{
if(head->next==NULL)
{
head->next=temp;
break;
}
Swap(head->next, temp);
Swap(head, temp);
}
}
Space complexity : O(1), constant
Problem - 3: Delete a node in single non circular linked list
void deleteNode(node *n)
{
if(n == NULL)
return;
p = NULL;
if(n->next == NULL)
{
while(n->next != NULL)
{
p = n;
n = n->next;
}
}
else
{
p = n->next
n->data = p->data;
n->next = p->next;
}
delete p;
}
Time complexity : Avg O(1 ), worst case O(n)Space complexity : O(1), constant
Problem - 4: Implement "Merge Sort" for "Link List"?
line merge_sort (line list1)
{
if (list1 == NULL || list1.next == NULL)
return list1;
line list2 = split (list1);
list1 = merge_sort (list1);
list2 = merge_sort (list2);
return merge (list1, list2);
}
line split (line list1)
{
if (list1 == NULL)
return list1;
if (list1.next == NULL)
return list1.next;
line list2 = list1.next;
list1.next = list2.next;
list2.next = split (list2.next);
return list2;
}
line merge (line list1, line list2)
{
if (&list1 == NULL)
return list2;
if (list2 == NULL)
return list1;
if (list1.data < list2.data)
{
list1.next = merge (list1.next, list2);
return list1;
}
else
{
list2.next = merge (list1, list2.next);
return list2;
}
}Time complexity : O(n log n )
Space complexity : O(1), constant
Problem - 5: There are two singly linked lists l1 and l2 representing polynomials in X. we have to find difference b/w lists l1-l2. lists are in orders of descending powers.
constraints: no extra space i.e. O(1) space O(m+n) time complexity m and n and nodes in the lists.
struct node{
int coeff;
int power;
node *next;
};
Subtract (Poly* A, Poly* B)
{
while (A && B)
{
poly * r = new poly ();
if (A->C > B->C)
{
r->c = A->C;
r->P = A->P;
AddLL(r);
A = A->Next;
}
else if (A->C < B->C)
{
r->c = B->C;
r->P = B->P;
AddLL(r);
B = B->Next;
}
else
{
r->c = A->C - B->C;
r->P = A->P;
AddLL(r);
B = B->Next;
A = A->Next;
}
}
while (A || B)
{
poly * r = new poly ();
if(A != NULL)
{
r->c = B->C;
r->P = B->P;
AddLL(r);
B = B->Next;
}
else
{
r->c = A->C;
r->P = A->P;
AddLL(r);
A = A->Next;
}
}
}
while (A && B)
{
poly * r = new poly ();
if (A->C > B->C)
{
r->c = A->C;
r->P = A->P;
AddLL(r);
A = A->Next;
}
else if (A->C < B->C)
{
r->c = B->C;
r->P = B->P;
AddLL(r);
B = B->Next;
}
else
{
r->c = A->C - B->C;
r->P = A->P;
AddLL(r);
B = B->Next;
A = A->Next;
}
}
while (A || B)
{
poly * r = new poly ();
if(A != NULL)
{
r->c = B->C;
r->P = B->P;
AddLL(r);
B = B->Next;
}
else
{
r->c = A->C;
r->P = A->P;
AddLL(r);
A = A->Next;
}
}
}
Problem - 6: Evaluate a polynomial
typedef struct node
{
float cf;
float px;
float py;
struct node *next;
}mynode;
float evaluate(mynode *head, float x, float y)
{
float x,y,sum;
sum = 0;
mynode *poly;
for(poly = head->next; poly != head; poly = poly->next)
{
sum = sum + poly->cf * pow(x, poly->px) * pow(y, poly->py);
}
return(sum);
}
Problem - 7: There are two link list...having a common tail...i.e they are in a Y shape...find the point of intersection in O(n) time and constant extra space.
1) Take 2 pointers. ptr1 and ptr2
2) Start moving towards tail.
3) As soon as one of pointer reaches last node, start counter.
4) When the next pointer also reaches last node, stop counter.
5) Now you know, what is difference in length of two list.
6) Initialize the two pointers again with the two linked lists heads.
7) move the pointer with longer linked list by counter number of nodes, so that now the lengths are equal for both.
8) start moving both pointers now and as soon as they hit the same node, it is the intersection.
Problem - 8: Detect and remove loop in link list
1. Loop Detection: Take two pointers Fast and Slow (Slow jumps one step at a time while Fast two step)
While (Fast != NULL)
if(Fast == Slow)
return true;
else
fast = fast->next->next
slow = slow->next
return false;
2. Loop Length: After detecting loop stop one pointer and increment other pointer by 1 step untill
Loop
if (fast == slow)
break;
else
slow++
LoopLength++
EndLoop
3. Loop Position: You can find out loop start position also.
Fast = Slow = Start
Fast += LoopLenght
Loop
If Fast != Slow
Fast++;
Slow++
EndLoop
4. Loop Removal:Fast and Slow Both are pointing to the start of loop position.
Loop
if(Slow == Fast->next)
break;
Fast = Fast->next; Fast->next = NULL;
Problem - 9: Return Nth the node from the end of the linked list in one pass.
Node * GetNthNode ( Node* Head , int NthNode )
{
Node * pNthNode = NULL;
Node * pTempNode = NULL;
int nCurrentElement = 0;
for ( pTempNode = Head; pTempNode != NULL; pTempNode = pTempNode->pNext )
{
nCurrentElement++;
if ( nCurrentElement - NthNode == 0 )
{
pNthNode = Head;
}
else
if ( nCurrentElement - NthNode > 0)
{
pNthNode = pNthNode ->pNext;
}
}
if (pNthNode )
{
return pNthNode;
}
else
return NULL;
}
Your blog explained clearly about the recent talks in the industry. For Software Courses:
ReplyDeleteSEO Training in Chennai
JAVA Training in Chennai
Big Data Training in Chennai
Selenium Training in Chennai
German Classes in chennai
DOT NET Training in Chennai
Qtp training in Chennai
Qtp training in T Nagar
ReplyDeleteThe strategy you have posted on this technology helped me to get into the next level and had lot of information in it. The angular js programming language is very popular which are most widely used.
Dot Net Training in Chennai | Dot Net Training in anna nagar | Dot Net Training in omr | Dot Net Training in porur | Dot Net Training in tambaram | Dot Net Training in velachery
This comment has been removed by the author.
ReplyDelete