Reverse a stack without any other data structure !!

Yes, 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 !!

The 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 !!

A 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..

A Summary of Time Complexity of Most Common Sorting Algos !!

A few lines about the purpose of this blog !!

The best results are achieved by using the right amount of effort in the right place at the right time. And this right amount is usually less than we think we need. Faster learning is the knowledge of where to give the apropriate effort.
The key to success is sometimes using the right opportunity at the right time.

Open your eyes, your key to success is out here. If you need to mush up the most important algos for any coding interview in a very short time and a very simple way, this is the perfect blog for you..
This blog is specially for CSE/IT B.Tech students from any college in India.

I believe in sharing of knowledge. This is my earnest effort to let you know what i know and share my experiences with you. I hope and i am quiet sure that this will help you guys a lot.