#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <queue>
using namespace std;
/*Let the Current window size be K.
10 Elements and 4 is size of the window
Input : 10 3
1 5 2 6 4 8 6 2 3 5
Output: 5 6 6 8 8 8 6 5
*/
int a[1000];
int q[1000];
vector<int> ans;
int main()
{ //Front of queue is the side where we enter new element.
//back is the side from which we remove old element.
//Here basically a doubly ended queue is implemented using
//simple array and two pointers pointing to the back and
//front respectively. :-)
int n, k;
int front1 = -1, back1 = 0;
cin >> n >> k;
for(int i = 0; i < n; i++)
cin >> a[i];
for(int i = 0; i < n; i++){
while(front1 >= back1 && q[front1] < a[i]) //While atleast 1 element is present and
//current element is greater then front
//of queue, remove from front.
front1--;
q[++front1] = a[i]; //Add new element to front.
if(i >= k && q[back1] == a[i-k]) //If current element is equal to element
//at the back, remove front the back.
back1++;
if(i >= k -1) //Print after iterating k-1 times
cout << q[back1] << endl;
// for(int j = back1; j <= front1; j++) //Can be used to print current status of queue
// cout << q[j] << " " ;
// cout << endl;
}
}
Swap the nth and the mth node in a linked list
0In this case n = 2 and m = 4.
Please give a linked list of size > 4. Corner cases are not handled. Only the main swapping part is handled.
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef struct node{
int data;
node *next;
};
node *allocate(){
node *ptr = (node *)malloc(sizeof(node));
ptr -> next = NULL;
return ptr;
}
node *f(){
int x;
cin >> x;
if(x == -1)
return NULL;
node *head = allocate();
head ->data = x;
head ->next = f();
return head;
}
int main()
{
cout << "Enter items of list:-\nType -1 to exit.\n";
node *head;
head = NULL;
head = f();
node *temp = head;
while(temp!= NULL)
cout << temp->data << " ", temp = temp->next;
node *ptr2, *ptr4;
temp = head;
for(int i = 0; i < 4; i++){
if(i == 0)
ptr2 = temp;
else if(i == 2)
ptr4 = temp;
temp = temp -> next;
}
// cout << ptr2->data << " " << ptr4->data << endl;
temp = (ptr2->next) -> next;
ptr2->next->next = ptr4->next->next;
ptr4->next->next = temp;
temp = ptr2->next;
ptr2->next = ptr4->next;
ptr4->next = temp;
cout << endl;
temp = head;
// system ("pause");
while(temp!= NULL)
cout << temp->data << " ", temp = temp->next;
return 0;
}
Reverse every K nodes in a linked list.
0In this example k = 4 (initialized at the beginning of main function. Change according to needs.)
original list – 1 2 3 4 5 6 7 8 9 10
final list – 4 3 2 1 8 7 6 5 10 9
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef struct node{
int data;
node *next;
};
node *allocate(){
node *ptr = (node *)malloc(sizeof(node));
ptr -> next = NULL;
return ptr;
}
node *f(){
int x;
cin >> x;
if(x == -1)
return NULL;
node *head = allocate();
head ->data = x;
head ->next = f();
return head;
}
node *rev(node *head){
if(head == NULL || head->next == NULL)
return head;
node *A = head;
node *B = head -> next;
node *C = head;
A->next = B->next;
A = B;
B -> next = C;
head = B;
head -> next -> next = rev(head ->next ->next);
return B;
}
int main()
{
cout << "Enter items of list:-\nType -1 to exit.\n";
node *head;
head = NULL;
head = f();
node *temp = head;
cout << "The original list is\n";
while(temp!= NULL)
cout << temp->data << " ", temp = temp->next;
head = rev(head);
cout << endl;
temp = head;
cout << "The pairwise reversed list is\n";
while(temp!= NULL)
cout << temp->data << " ", temp = temp->next;
return 0;
}
Reverse a linked list in pairs
0
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef struct node{
int data;
node *next;
};
node *allocate(){
node *ptr = (node *)malloc(sizeof(node));
ptr -> next = NULL;
return ptr;
}
node *f(){
int x;
cin >> x;
if(x == -1)
return NULL;
node *head = allocate();
head ->data = x;
head ->next = f();
return head;
}
node *rev(node *head){
if(head == NULL || head->next == NULL)
return head;
node *A = head;
node *B = head -> next;
node *C = head;
A->next = B->next;
A = B;
B -> next = C;
head = B;
head -> next -> next = rev(head ->next ->next);
return B;
}
int main()
{
cout << "Enter items of list:-\nType -1 to exit.\n";
node *head;
head = NULL;
head = f();
node *temp = head;
cout << "The original list is\n";
while(temp!= NULL)
cout << temp->data << " ", temp = temp->next;
head = rev(head);
cout << endl;
temp = head;
cout << "The pairwise reversed list is\n";
while(temp!= NULL)
cout << temp->data << " ", temp = temp->next;
return 0;
}
Reverse a linked list
0
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef struct node{
int data;
node *next;
};
node *allocate(){
node *ptr = (node *)malloc(sizeof(node));
ptr -> next = NULL;
return ptr;
}
node *f(){
int x;
cin >> x;
if(x == -1)
return NULL;
node *head = allocate();
head ->data = x;
head ->next = f();
return head;
}
node *rev(node **curr, node *last){
if((*curr)->next == NULL){
(*curr)->next = last;
return (*curr);
}
node *temp = rev(&((*curr)->next), *curr);
if(last != NULL)
(*curr)->next = last;
else
(*curr)->next = NULL;
return temp;
}
int main()
{
cout << "Enter items of list:-\nType -1 to exit.\n";
node *head;
head = NULL;
head = f();
node *temp = head;
cout << "old list is \n";
while(temp!= NULL)
cout << temp->data << " ", temp = temp->next;
head = rev(&head, NULL);
cout << endl;
temp = head;
cout << "New list is \n";
while(temp!= NULL)
cout << temp->data << " ", temp = temp->next;
return 0;
}
Linked list Implementation with a return type of node*
0
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef struct node{
int data;
node *next;
};
node *allocate(){
node *ptr = (node *)malloc(sizeof(node));
ptr -> next = NULL;
return ptr;
}
node *f(){
int x;
cin >> x;
if(x == -1)
return NULL;
node *head = allocate();
head ->data = x;
head ->next = f(); //Point the next pointer to the next node
//whose address is returned recursively.
return head; //return the pointer to the current node
}
int main()
{
cout << "Enter items of list:-\nType -1 to exit.\n";
node *head;
head = NULL;
head = f();
while(head!= NULL)
cout << head->data << " ", head = head->next;
return 0;
}
A simple linked list implementation with no return type and no global pointers.
0
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <utility>
using namespace std;
typedef struct node{
int data;
node *next;
};
node * alloc(){ //allocate and return the new allocated memory of type node
node *ptr = (node*)malloc(sizeof(node));
ptr -> next = NULL;
ptr -> data = 0;
}
void f(node **head){
int x;
cin >> x;
if(x == -1) //no more data
return ;
*head = alloc(); //allocate new memory
(*head)->data = x;
f(&((*head)->next)); //pass the next pointer of current node to be used recursively.
}
int main()
{
cout << "Enter items of list:-\nType -1 to finish.\n";
node *head = NULL;
f(&head);
while(head != NULL)
cout << head->data << " ", head = head->next;
}
Reverse a stack without any other data structure !!
0Yes, the question is simple. Reverse a stack without using any other any other data structure.
But this one is really a very good question. You need to think a lot to answer this correctly. If you hear this question for the first time in the interview, then i am pretty sure that if you are not a extraordinarily good, you can’t answer this question. So, here is how the solution goes.
Make two functions:-
1. The first function reverse is to pick the top element from the current stack.
2. The second function is to insert the element a to the last of the current stack.
So at first we put the 2nd element at last position. then the third element, and so on…
Thus finally we get a reversed stack. Hope the code helps you.
The sieve of Eratosthenes !!
0The ancient Greek mathematician Eratosthenes suggested the following algorithm for finding all primes that not exceeding a given number n. Let us take an array S of length n and fill it with figures one (mark them as uncrossed). Now we will consistently see the elements of S [k], starting with k = 2. If S [k] = 1, then fill in with zeros (cross out or sow) all subsequent table cells, which numbers are multiple of k. As result is an array in which cells contain 1 if and only if the number of cell is a prime number.
A lot of time could be saved by noting that a composite number is less than n, at least one of the divisors does not exceed , the sowing process sufficiently to finish on . This is the Sieve of Eratosthenes animation, taken from Wikipedia
Click on the image to get an idea of what is happening. The animation says it all.
S = [];
S[1] = 0; // 1- not a prime number
/ / fill it with figures one
for(k=2; k<=n; k++)
S[k]=1;
for(k=2; k*k<=n; k++){
/ / if k is a simple (not crossed out)
if(S[k]==1){
/ / then we cross out multiples of k
for(l=k*k; l<=n; l+=k){
S[l]=0;
}
}
}
return S;
}
The Two pointer Algorithm !!
2A very easy but really effective algorithm..
I will try to describe this method on example of a problem.
Given two arrays (A and B) sorted in ascending order, and an integer x. we need to find i and j, such that a[i] + b[j] is equal to X.
i and j our pointers, at first step i points to the first element of a, and j points to the last element of b.
i = 0; j = b.size() – 1;
move first pointer one by one through the array a, and decrease position of the second pointer if needed.
Here we are checking if a[i] +b[j] = X. If so, then write the answer. When this is not true, then if a[i] + b[j] > X, then decrease j (if j > 0), because what we need must be at a position less than current position of j or more than current position of i.
Now Take the example of this problem.
Consider problem 190D – Non-Secret Cypher. The stupid solution goes over all subarrays and checks whether it’s good or not. Now we notice that if subarray is ‘good’, then all its superarrays is ‘good’ too. Let’s go over all left borders x (1 ≤ x ≤ N) and for each of them find rx. rx is a minimal number such that subarray x… rx is good. Obviously, all subarrays which starts at x and ends after rx is good.
If you notice that r1 ≤ r2 ≤ … ≤ rN, you can use ‘two pointers’ method. The first pointer is x and the second one is rx. When you move the first one right, the second one can only move right too. No matter how many operations you perform in one step, algo’s running time is O(n), because each of pointers makes ≤ N steps.
Now, try this problem by your own:-
Q> Given n numbers, find pairs with difference x.
Hint: First sort then apply the algo you have just learnt.
If you still can’t understand, then comment below..
ilovealgorithms 