Monday, February 28, 2011

WAP to Find Maximum in Sliding Window of size W in an Unsorted Array or Integers.

A long array A[] is given to you. There is a sliding window of size w which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:
The array is [1 3 -1 -3 5 3 6 7], and w is 3.

Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7


Input: A long array A[], and a window width w
Output: An array B[], B[i] is the maximum value of from A[i] to A[i+w-1]
Requirement: Find a good optimal way to get B[i]

Solution: It Can Solved By Two Ways in This Question Data Structure Plays Important Role

The obvious solution with run time complexity of O(nw) is which is not efficient enough. Every time the window is moved, we have to search for the maximum from w elements in the window. where w is size of window & n is size of array

1st Method(Naive Approach)

Data Structure Used : Array
Algorithm: A.for all i=0 to n-w+1 (we should have at-least w elements in window)
B.for all j=i to i+w (keep incrementing windows size form left to right)
C find maximum inn each window & print it or put in array (Auxiliary)

#include

void printMaxInSlidingWindows(int a[],int n,int w)
{

int max=0;
int i=0,j=0;

for (i = 0; i {
max=a[i];

for (j=i; j {
if (a[j]>max)
{
max=a[j];

}



}
printf( " %d ", max);
}

}

int main()
{
int a[]={1,3,-1,-3,5,3,6,7};
printMaxInSlidingWindows(a,8,3);
}

TC O(nw)
SC O(1)
Run Here http://ideone.com/7o3Ta


2nd Method

Data Structure Used: Queue(More Efficient)
Algorithm Provided By Aakash (A Techie Who Run Blog on Coding,DS,Algorithms)

We need a data structure where we can store the candidates for maximum value in the window and discard the element, which are outside the boundary of window. For this, we need a data structure in which we can edit at both the ends, front and back. Deque is a perfect candidate for this problem.

We are trying to find a way in which, we need not search for maximum element among all in the window. We will make sure that the largest element in the window would always appear in the front of the queue.
While traversing the array in forward direction if we find a window where element A[i] > A[j] and i > j, we can surely say that A[j], will not be the maximum element for this and succeeding windows. So there is no need of storing j in the queue and we can discard A[j] forever.
For example, if the current queue has the elements: [4 13 9], and a new element in the window has the element 15. Now, we can empty the queue without considering elements 4, 13, and 9, and insert only element 15 into the queue.

Every time, we move to a new window, we will be getting a new element and leave an old element. We should take care of:
Popping elements outside the window from queue front.
Popping elements that are less than new element from the queue.
Push new element in the queue as per above discussion.

Note:Optimization Done In Done so that we can Find The Maximum of Each Window in O(1)

Here Is Tunning Code

import java.util.*;

class Maximumin_SlidingWindow
{

public static void main(String ar[])
{

Integer a[]=new Integer[]{1,3,-1,-3,5,3,6,7};
int w=3,i=0;
int size=a.length;
Integer b[]=new Integer[size-w+1];

maxSlidingWindow(a,size,w,b);

for(i=0;i System.out.println(b[i]);

}

static void maxSlidingWindow(Integer A[], int n, int w, Integer B[])
{
Integer ar[]=new Integer[1];
DequeQ=ar[0];

//Initilize deque Q for first window
for (int i = 0; i < w; i++)
{
while (!Q.isEmpty() && A[i] >= A[Q.peekLast()])
Q.pollLast();
Q.offerLast(i);
}

for (int i = w; i < n; i++)
{
B[i-w] = A[Q.peekFirst()];

//update Q for new window
while (!Q.isEmpty() && A[i] >= A[Q.peekLast()])
Q.pollLast();

//Pop older element outside window from Q
while (!Q.isEmpty() && Q.peekFirst() <= i-w)
Q.pollFirst();

//Insert current element in Q
Q.offerLast(i);
}
B[n-w] = A[Q.peekFirst()];
}

}

TC O(n)n Since Eacj Array Element is Inserted & deleted At-Most Once
SC O(1)
Run Here http://ideone.com/KLIpO
http://ideone.com/TftYg

Search an element in a sorted and pivoted array e.g Array is Rotated by some length K. Now you Have to Search Element in Complexity less then O(N)

Data Structure Used: Array

Hint : Find the pivot point, divide the array in two sub-arrays and call binary search. Thats It :)

Approach to Solve Problem:
Find the pivot point, divide the array in two sub-arrays and call binary search.The main idea for finding pivot is – for a sorted (in increasing order) and pivoted array, pivot element is the only only element for which next element to it is smaller than it. Using above criteria and binary search methodology we can get pivot element in O(logn) time

Input arr[] = {3, 4, 5, 1, 2}
Element to Search = 1
1) Find out pivot point and divide the array in two
sub-arrays. (pivot = 2) /*Index of 5*/
2) Now call binary search for one of the two sub-arrays.
(a) If element is greater than 0th element then
search in left array
(b) Else Search in right array
(1 will go in else as 1 < 0th element(3)) 3) If element is found in selected sub-array then return index Else return -1. Efficient Algorithm: 1. A Pivot Point is point around which array is rotated so 1st we need to find out its location/index. lets say it pivot. a. to find pivot point we use same idea of binary search & check if arr[mid]>a[mid+1] if true then return pivot=mid.
b else if arr[low]

int binarySearch(int arr[], int low, int high, int no)
{
if(high >= low)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/

if(no == arr[mid])
return mid;
if(no > arr[mid])
return binarySearch(arr, (mid + 1), high, no);
else
return binarySearch(arr, low, (mid -1), no);
}
/*Return -1 if element is not found*/
return -1;
}

/* Function to get pivot. For array 3, 4, 5, 6, 1, 2
it will return 3 e.g. position of pivoted element */
int findPivot(int arr[], int low, int high)
{
int mid = (low + (high-low))/2; /*low + (high - low)/2;*/
if(arr[mid] > arr[mid + 1])
return mid;
if(arr[low] > arr[mid])
return findPivot(arr, low, mid-1);
else
return findPivot(arr, mid + 1, high);
}

/* Searches an element no in a pivoted sorted array arrp[]
of size arr_size */
int pivotedBinarySearch(int arr[], int arr_size, int no)
{
int pivot = findPivot(arr, 0, arr_size-1);
if(arr[pivot] == no)
return pivot;
if(arr[0] <= no)
return binarySearch(arr, 0, pivot-1, no);
else
return binarySearch(arr, pivot+1, arr_size-1, no);
}


int main()
{
int arr[] = {3, 4, 5, 6, 7, 1, 2};
int n = 5;
printf("Index of the element is %d", pivotedBinarySearch(arr, 7, 5));
getchar();
return 0;
}

Time Complexity O(Logn)
Space Complexity O(1)
Run Here https://ideone.com/KMOvG

Convert Sorted Array to Balanced Binary Search Tree (BST)

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Solution:
If you would have to choose an array element to be the root of a balanced BST, which element would you pick? The root of a balanced BST should be the middle element from the sorted array.

You would pick the middle element from the sorted array in each iteration. You then create a node in the tree initialized with this element. After the element is chosen, what is left? Could you identify the sub-problems within the problem?

There are two arrays left — The one on its left and the one on its right. These two arrays are the sub-problems of the original problem, since both of them are sorted. Furthermore, they are subtrees of the current node’s left and right child.

The code below creates a balanced BST from the sorted array in O(N) time (N is the number of elements in the array). Compare how similar the code is to a binary search algorithm. Both are using the divide and conquer methodology.


BinaryTree* sortedArrayToBST(int arr[], int start, int end) {
if (start > end) return NULL;
// same as (start+end)/2, avoids overflow.
int mid = start + (end - start) / 2;
BinaryTree *node = new BinaryTree(arr[mid]);
node->left = sortedArrayToBST(arr, start, mid-1);
node->right = sortedArrayToBST(arr, mid+1, end);
return node;
}

BinaryTree* sortedArrayToBST(int arr[], int n) {
return sortedArrayToBST(arr, 0, n-1);
}

Design a stack that supports push, pop, and retrieving the minimum element in constant time. Can you do this?

I found that this question had been asked in Amazon and Bloomberg interviews.

Initially I thought of using an extra min-heap to store the elements. Although this enables us to retrieve the minimum element in O(1), push and pop operations both operates in O(lg N), where N is the total number of elements in the stack. Definitely not a desirable method.

How about recording the current minimum in the stack? This works until you pop current minimum off the stack, where you would have to update your next minimum, which takes O(N) time to examine all elements.

Assume you have an extra stack. What would you do with the extra stack?

Stack is a last in, first out (LIFO) data structure. It can be easily implemented either through an array or a linked list.


Solution:

1st Solution

You can implement this by having each node in the stack keep track of the minimum beneath
itself. Then, to find the min, you just look at what the top element thinks is the min.
When you push an element onto the stack, the element is given the current minimum. It sets its “local min” to be the min.

public class StackWithMin extends Stack {
public void push(int value) {
int newMin = Math.min(value, min());
super.push(new NodeWithMin(value, newMin));
}

public int min() {
if (this.isEmpty()) {
return Integer.MAX_VALUE;
} else {
return peek().min;
}
}
}
class NodeWithMin {
public int value;
public int min;
public NodeWithMin(int v, int min){
value = v;
this.min = min;
}
}
There’s just one issue with this: if we have a large stack, we waste a lot of space by keeping track of the min for every single element.


2nd solution


The solution is surprisingly simple and elegant — Use an extra stack to maintain the minimums. What does this mean?

* To retrieve the current minimum, just return the top element from minimum stack.
* Each time you perform a push operation, check if the pushed element is a new minimum. If it is, push it to the minimum stack too.
* When you perform a pop operation, check if the popped element is the same as the current minimum. If it is, pop it off the minimum stack too.


struct StackGetMin {
void push(int x) {
elements.push(x);
if (minStack.empty() || x <= minStack.top())
minStack.push(x);
}
bool pop() {
if (elements.empty()) return false;
if (elements.top() == minStack.top())
minStack.pop();
elements.pop();
return true;
}
bool getMin(int &min) {
if (minStack.empty()) {
return false;
} else {
min = minStack.top();
return true;
}
}
stack elements;
stack minStack;
};

Find Maximum Size BST in Binary Tree

#include
#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct BinaryTree
{
int data;
struct BinaryTree * left;
struct BinaryTree * right;
};


// Find the largest BST subtree in a binary tree.
// If the subtree is a BST, return total number of nodes.
// If the subtree is not a BST, -1 is returned.
int findLargestBSTSubtree(struct BinaryTree *p, int &min, int &max,int &maxNodes, struct BinaryTree* &largestBST)
{
if (!p) return 0;
bool isBST = true;
int leftNodes = findLargestBSTSubtree(p->left, min, max, maxNodes, largestBST);
int currMin = (leftNodes == 0) ? p->data : min;
if (leftNodes == -1 ||
(leftNodes != 0 && p->data <= max))
isBST = false;
int rightNodes = findLargestBSTSubtree(p->right, min, max, maxNodes, largestBST);
int currMax = (rightNodes == 0) ? p->data : max;
if (rightNodes == -1 ||
(rightNodes != 0 && p->data >= min))
isBST = false;
if (isBST) {
min = currMin;
max = currMax;
int totalNodes = leftNodes + rightNodes + 1;
if (totalNodes > maxNodes) {
maxNodes = totalNodes;
largestBST = p;
}
return totalNodes;
} else {
return -1; // This subtree is not a BST
}
}


/* Helper function that allocates a new node
with the given data and NULL left and right
pointers. */
struct BinaryTree* newNode(int data)
{
struct BinaryTree* node = (struct BinaryTree*)
malloc(sizeof(struct BinaryTree));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

struct BinaryTree* findLargestBST(struct BinaryTree *root) {
struct BinaryTree *largestBST = NULL;
int min=INT_MAX, max=INT_MIN;
int maxNodes = INT_MIN;
findLargestBSTSubtree(root, &min, &max, &maxNodes, &largestBST);
return largestBST;
}

void print(struct BinaryTree *root)
{
if(root==NULL)
return ;

print(root->left);
printf("%d ",root->data);
print(root->right);

}

int main()
{

struct BinaryTree* root = newnode(10);
root->left = newnode(5);
root->right = newnode(15);
root->left->left = newnode(1);
root->left->right = newnode(8);
root->right->right =newnode(7);

struct BinaryTree* tmp=findLargestBST(root);

print(tmp);
return 0;

}

Time Complexity O(n)

Print Ancestors of a given node in Binary Tree

#include
#include
#include

using namespace std;

/* 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;
};

/* If target is present in tree, then prints the ancestors
and returns true, otherwise returns false. */
bool printAncestors(struct node *root, int target)
{
/* base cases */
if ( root == NULL )
return false;

if ( root->data == target )
return true;

/* If target is present in either left or right,
then print this node */
if ( printAncestors(root->left, target) ||
printAncestors(root->right, target) )
{
cout<data<<" ";
return true;
}

/* Else return false */
return false;
}

/* 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);
}

/* Driver program to test above functions*/
int main()
{

/* Constructed the following binary tree
1
/ \
2 3
/ \
4 5
/
7
*/
struct node *root = newnode(1);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(4);
root->left->right = newnode(5);
root->left->left->left = newnode(7);

printAncestors(root, 7);

getchar();
return 0;
}

Output:
4 2 1

Time Complexity: O(n) where n is the number of nodes in the given Binary Tree.

WAP using recursion to Palindrom

/*
* isPalindrome.c
*
*/

#include
#include

int isPalindrome( char *str, int length )
{

if ( length < 1 )
{
return 1; /* no more chars to compare, its a palindrome */
}

if ( str[0] == str[length-1] ) /* Are the two ends same? */
{
return isPalindrome( str+1, length-2 ); /* continue checking */
}
else
{
return 0; /* comparison failed, not a palindrome */
}
}

void strToUpper( char *src )
{
/* convet to upper case any letter */
while( ( *src = toupper( *src ) ) != '\0' )
{
++src;
}
}

int main( void )
{
int result = 0;
char str[40];

result = isPalindrome( "jalaj", 7 ); /* recursive starts here */

if( result == 1 )
{
puts( "Its a palindrome string." );
}
else
{
puts( "Its not a palindrome string." );
}

getchar();
return 0;

}

WAP to Convert Number into Roman Number

#include

int ConvertToRomanNo(int number,int no,char ch);
int main()
{
int number=525;

printf("Roman number of" " %d " "is::",number);
number=ConvertToRomanNo(number,1000,'M');
number=ConvertToRomanNo(number,500,'D');
number=ConvertToRomanNo(number,100,'C');
number=ConvertToRomanNo(number,50,'L');
number=ConvertToRomanNo(number,10,'X');
number=ConvertToRomanNo(number,5,'V');
number=ConvertToRomanNo(number,1,'I');

return 0;
}

int ConvertToRomanNo(int number,int no,char ch)
{
int i,j;

if(number==9)
{
printf("IX");
return (number%9);
}
if(number==4)
{
printf("IV");
return (number%4);
}
j=number/no;
for(i=1;i<=j;i++)
{
printf("%c",ch);
}
return(number%no);
}

TC O(n)
SC o(1)
Run Here https://ideone.com/xvqDz

Given a function which generates a random integer in the range 1 to 7, write a function which generates a random integer in the range 1 to 10 uniformy

This has been asked in Google interview and Amazon interview, and appears quite often as one of the few probabilistic analysis questions. You should be familiar with the concept of expected value, as it could be extremely helpful in probabilistic analysis.

Basic Idea

In C++, rand() generates random integral number between 0 and 32K. Thus to generate a random number from 1 to 10, we write rand() % 10 + 1. As such, to generate a random number from integer a to integer b, we write rand() % (b - a + 1) + a.
The interviewer told you that you had a random generator from 0 to 1. It means floating-point number generator.
How to get the answer mathematically:
  1. Shift the question to a simple form such that the lower bound is 0.
  2. Scale the range by multiplication
  3. Re-shift to the required range.
For example: to generate R such that
a <= R <= b.  Apply rule 1, we get a-a <= R - a <= b-a 
                       0 <= R - a <= b - a.  
Think R - a as R1. How to generate R1 such that R1 has range from 0 to (b-a)?
R1 = rand(0, 1) * (b-a)   // by apply rule 2.
Now substitute R1 by R - a
R - a = rand(0,1) * (b-a)    ==>   R = a + rand(0,1) * (b-a)
==== 2nd question - without explanation ====
We have 1 <= R1 <= 5
==>   0 <= R1 - 1             <= 4
==>   0 <= (R1 - 1)/4         <= 1
==>   0 <= 6 * (R1 - 1)/4     <= 6
==>   1 <= 1 + 6 * (R1 - 1)/4 <= 7
Thus, Rand(1,7) = 1 + 6 * (rand(1,5) - 1) / 4



Hint:
Assume you could generate a random integer in the range 1 to 49. How would you generate a random integer in the range of 1 to 10? What would you do if the generated number is in the desired range? What if it’s not?

Solution:
This solution is based upon Rejection Sampling. The main idea is when you generate a number in the desired range, output that number immediately. If the number is out of the desired range, reject it and re-sample again. As each number in the desired range has the same probability of being chosen, a uniform distribution is produced.

Obviously, we have to run rand7() function at least twice, as there are not enough numbers in the range of 1 to 10. By running rand7() twice, we can get integers from 1 to 49 uniformly. Why?

1 2 3 4 5 6 7
1 1 2 3 4 5 6 7
2 8 9 10 1 2 3 4
3 5 6 7 8 9 10 1
4 2 3 4 5 6 7 8
5 9 10 1 2 3 4 5
6 6 7 8 9 10 * *
7 * * * * * * *

A table is used to illustrate the concept of rejection sampling. Calling rand7() twice will get us row and column index that corresponds to a unique position in the table above. Imagine that you are choosing a number randomly from the table above. If you hit a number, you return that number immediately. If you hit a *, you repeat the process again until you hit a number.

Since 49 is not a multiple of tens, we have to use rejection sampling. Our desired range is integers from 1 to 40, which we can return the answer immediately. If not (the integer falls between 41 to 49), we reject it and repeat the whole process again.


int rand10() {
int row, col, idx;
do {
row = rand7();
col = rand7();
idx = col + (row-1)*7;
} while (idx > 40);
return 1 + (idx-1)%10;
}

Now to calculate the expected value for the number of calls to rand7() function.

E(# calls to rand7) = 2 * (40/49) +
4 * (9/49) * (40/49) +
6 * (9/49)2 * (40/49) +
...


= ∑ 2k * (9/49)k-1 * (40/49)
k=1

= (80/49) / (1 - 9/49)2
= 2.45



Given an array conataing item a1a2a3a4 & b1b2b3b4 reaarange them such as a1b1a2b2a3b3a4b4 & so on

A Naive Attemt:

Algorithm

#include

void swap(char *c,char *p)
{
char tmp;
tmp=*c;
*c=*p;
*p=tmp;

}

int main (int argc, char const* argv[])
{
char str[] = "1234abcd";
int i,j;
int len = strlen(str)/2;
//swap str[len-1] and str[len] and so on
for ( i = 0; i < len-1; i += 1) { for ( j = len-1-i; j <= len+i; j += 2) { printf("i=%d j=%d c1=%c \t c2=%c \n",i,j,str[j],str[j+1]); swap(&str[j],&str[j+1]); } } printf("%s \n", str); return 0; } Time Complexity O(n^2) Space Complexity O(1) An Linear Time Inplace Algorithm Algorithm Step 1) Find an m such that 2m+1 = 3k <= 2n < 3k+1 Step 2) Right cyclic shift A[m+1 ... n+m] by m. Step 3) Foreach i = 0 to k - 1, considering only the Array[1...2m] start at 3i and 'follow the cycle'. Step 4) Recurse on A[2m+1...2n] Basic idea is as follows: If for each n, we can find an m (Step 1) for which we can easily do the 'following the cycle' algorithm, we can first shuffle some elements (Step 2), then do the algo for m (Step 3) and then recurse on the remaining elements (Step 4). 'following the cycle': element i1 goes to i2 which goes to i3 ... goes to finally back to i1. We can put the elements of this cycle in their right places by using just one extra location as follows: Store element i1 in the extra location. Look at what goes into i1. say X1. Store element in X1 in i1. Follow the cycle. Finally store i1 in is right position. #include
#include
#include


void Inshuffle(int *A, int N);
void follow_cycle(int *A, int N, int seed);
void cyclic_shift(int *A, int size, int distance);
void reverse(int *A, int size);
int Inverseof2(int M);


/***************************
Main Insuffle Algorithm.
Shuffle a1 a2 ..an b1 b2 ...bn
to
b1 a1 b2 a2 .... bn an

Parameters: A = the array
N = 2n, size of the array.

The permutation is given by
i -> 2i mod (N + 1)

We shuffle the array starting
from A[1] for easier coding.
****************************/

void Inshuffle(int *initialA, int initialN)
{

int m =1;
int i;
int power3 = 1;
int seed = 1;
int k = 1;
int n = initialN/2; //N is assumed to be even.
int *A = initialA;
int N = initialN;

while (N > 0){


//Reset Values.
m = 1;
i = 0;
power3 = 1;
seed = 1;
k = 1;
n = N/2;

//Step 1: Find an m such that 2m+1 is the largest power of 3 <= N+1 for (i = 0; i <= N+1; i ++){ if (3*power3 > N+1){
break;
}
power3 = 3*power3;
}
k = i;

m = (power3 - 1)/2;
//Step 2: Cyclic Right Shift A[m+1, n+m] by m
cyclic_shift(A+m+1,n,m);

// Step3: Do inshuffle of A[1....2m] by 'following cycle'.

for (i = 0 ; i < k; i ++) { follow_cycle(A,2*m,seed); seed = 3*seed; } // Step 4: Recurse on A[2m+1...,2n] //Could have made a recursive call here: //Inshuffle(A+2*m,2*(n-m)); // But to make it O(1) space, convert tail recursion to iteration and put in a while loop. A = A + 2*m; N = 2*(n-m); // Reset Values. } //End of while loop. } /**************************************** Follow the cycle starting at seed. For example: insuffle of 1 2 3 4 5 6 7 8 1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1
We follow this cycle in reverse order.
We look at 1. Save A[1].
Then look at what goes to 1, i.e 5 = 1*x
where x is inverse of 2.
Now fill A[1] with A[5].
Now look at what goes into A[5]. 7 = 5*x
(x is inverse of 2)
So fill A[5] with A[7].
And so on.
*****************************************/

void follow_cycle(int *A, int N, int seed)
{
int cur;
int inverse2 = Inverseof2(N+1);
int tmp;
int prev;

cur = (seed*inverse2 % (N+1));

tmp = A[seed];
prev = seed;
while (cur != seed){
A[prev] = A[cur];
prev = cur;
cur = (cur*inverse2 % (N+1));
}
A[prev] = tmp;
}
/*******************************
cyclic right shift an array by a given amount.
********************************/
void cyclic_shift(int *A, int sz, int k)
{
reverse(A,sz - k);
reverse(A+sz-k,k);
reverse(A,sz);
}

/******************************
reverse an array
*******************************/
void reverse(int *A, int sz)
{
int i;
int tmp;
for (i = 0; i < sz/2; i++)
{
tmp = A[i];
A[i] = A[sz-i-1];
A[sz-i-1] = tmp;
}
}

/***************************

find x such that 2x = 1 (mod M)
M is assumed to be an odd integer.
x = (M+1)/2
***************************/
int Inverseof2(int M)
{
return (M+1)/2;
}


int main()
{
int n;
int i;
int *A;
printf("Enter the value of n, (total size of array = 2n): ");
scanf("%d",&n);
A = (int *)malloc((2*n+1)*sizeof(int));
for (i = 0; i <= 2*n; i++){
A[i] = i;
}

Inshuffle(A,2*n);

printf("\n[");
for (i = 1; i <= 2*n; i ++){
printf(" %d",A[i]);
}
printf(" ]\n");
free(A);
return 1;
}

Time Complexity O(N)
Space Compleixty O(1)
Run Here https://ideone.com/2yLq1
A Great Source http://arxiv.org/PS_cache/arxiv/pdf/0805/0805.1598v1.pdf
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi board=riddles_cs;action=display;num=1094241218;

Saturday, February 26, 2011

WAP to do AutoCorrection of Word Using Trie

/*
ASSUMPTIONS:
All characters are case insensitive
ENHANCEMENTS:
Auto correction of word
Display all words in postorder

SAMPLE DATA: - ALGO, ALL, ALSO, ASSOC, TREE, TRIE

+--> [G] ---+--> [O]
|
+--> [L] ---+--> [L]
| |
+--> [A] ---+ +--> [S] ---+--> [O]
| |
| +--> [S] ---+--> [S] ---+--> [O] ---+--> [C]
[\0] ---+
| +--> [E] ---+--> [E]
| |
+--> [T] ---+--> [R] ---+
|
+--> [I] ---+--> [E]

*/

#include
#include

using namespace std;

class trie
{
private:
struct node
{
char character; // character of the node
bool eow; // indicates a complete word
int prefixes; // indicates how many words have the prefix
node* edge[26]; // references to all possible sons
}*root; // trie root node

void preorder_display(node *); // preorder display
void truncate_node(node *); // Deletes node and sub-nodes
void delete_node(node *); // Deletes node if prefixes is 1

public:
trie(); // constructor
~trie(); // destructor

void insert_word(char *); // to insert a word
void delete_word(char *); // to delete a word
bool search_word(char *); // to search a word

void display(); // display complete trie
};

trie::trie()
{
root = new node();
root->character = '\0';
root->prefixes = 0;
root->eow = false;
for(int i=0;i<26;i++)
{
root->edge[i] = NULL;
}
}

trie::~trie()
{
truncate_node(root);
}

void trie::truncate_node(node* n)
{
for(int i=0;i<26;i++)
{
if(n->edge[i] != NULL)
{
truncate_node(n->edge[i]);
}
}
delete n;
}

void trie::insert_word(char* s)
{
node *t = root;
while(*s != '\0')
{
int c = toupper(*s) - 'A';
if(t->edge[c] == NULL)
{
node* n = new node();
n->character = *s;
n->eow = false;
n->prefixes = 1;
for(int i=0;i<26;i++)
{
n->edge[i] = NULL;
}
t->edge[c] = n;
t = n;
}
else
{
t = t->edge[c];
t->prefixes++;
}
*s++;
}
t->eow = true;
}

bool trie::search_word(char* s)
{
node *t = root;
while(*s != '\0')
{
int c = toupper(*s) - 'A';
if(t->edge[c] == NULL)
{
return false;
}
else
{
t = t->edge[c];
}
*s++;
}
if(t->eow == true)
return true;
else
return false;
}

void trie::delete_word(char* s)
{
node* t = root;
while(*s != '\0')
{
int c = toupper(*s) - 'A';
if(t->edge[c] == NULL)
{
return;
}
else if(t->edge[c]->prefixes == 1)
{
truncate_node(t->edge[c]);
t->edge[c] = NULL;
return;
}
else
{
t = t->edge[c];
}
*s++;
}
}

void trie::display()
{
preorder_display(root);
}

void trie::preorder_display(node* t)
{
if(t == NULL)
return;

cout << "iterating :: " << t->character << " :: " << t->eow << " :: " << t->prefixes << endl;

for(int i=0;i<26;i++)
{
if(t->edge[i] != NULL)
preorder_display(t->edge[i]);
}
}



int main()
{
trie mytrie;
char *s[] = {"tree","trie","algo","assoc","all","also","ass"};
for(int i=0;i {
mytrie.insert_word(s[i]);
}

mytrie.display();

if(mytrie.search_word("all") == true) cout << "all exist" << endl;
else cout << "all do not exist" << endl;

mytrie.delete_word("all");

if(mytrie.search_word("all") == true) cout << "all exist" << endl;
else cout << "all do not exist" << endl;

mytrie.display();
}

Find the last person seated around in a circle program/puzzle

“n” people are seated around in a circle. At each step, the “m”th person is eliminated from the circle. The next iteration continues from the person next to the eliminated person. In the end, there will be only one person remaining. Given “n” and “m”, write a program to find out the person who will be remaining at the end.
int FindWinner(int n, int m)

package brainteasers;

public class FindWinner {
public static void main(String[] args) {
FindWinner finder = new FindWinner();
char winner = finder.findWinner(10,3);
System.out.println("\nAnd the winner is "+(char)(winner-32)+"!!");
}

private char findWinner(int n, int m){
char[] people = getPeople(n);
boolean[] eliminated = new boolean[n];
//always start from 1st person
int remainingGuys = n;
int current = 0;

while(remainingGuys>1){
int inkiPinki=0;

while( eliminated[current] || ++inkiPinki != m )
current = (current+1) % n;

eliminated[current] = true;
printStatus( eliminated, people );
remainingGuys--;

while(eliminated[(current+1)%n]){
current++;
}

current = (current+1)%n;
}

System.out.println();
return people[current];
}

private void printStatus(boolean[] eliminated, char[] people) {
System.out.println();
for(int i=0;i char output;
if(eliminated[i]){
output = people[i];
}else{
output = (char)(people[i] - 32);
}
System.out.print(output+" ");
}
}

private char[] getPeople(int n) {
char[] people = new char[n];
System.out.println("Participants are...");
for(int i=0;i people[i] = (char)(i+97);
System.out.print((char)(people[i]-32)+" ");
}
System.out.println();
return people;
}
}
/*
Participants are...
A B C D E F G H I J

A B c D E F G H I J
A B c D E f G H I J
A B c D E f G H i J
A b c D E f G H i J
A b c D E f g H i J
a b c D E f g H i J
a b c D E f g h i J
a b c D e f g h i J
a b c D e f g h i j

And the winner is D!!
*/

Find the last person seated around in a circle program/puzzle

“n” people are seated around in a circle. At each step, the “m”th person is eliminated from the circle. The next iteration continues from the person next to the eliminated person. In the end, there will be only one person remaining. Given “n” and “m”, write a program to find out the person who will be remaining at the end.
int FindWinner(int n, int m)

package brainteasers;

public class FindWinner {
public static void main(String[] args) {
FindWinner finder = new FindWinner();
char winner = finder.findWinner(10,3);
System.out.println("\nAnd the winner is "+(char)(winner-32)+"!!");
}

private char findWinner(int n, int m){
char[] people = getPeople(n);
boolean[] eliminated = new boolean[n];
//always start from 1st person
int remainingGuys = n;
int current = 0;

while(remainingGuys>1){
int inkiPinki=0;

while( eliminated[current] || ++inkiPinki != m )
current = (current+1) % n;

eliminated[current] = true;
printStatus( eliminated, people );
remainingGuys--;

while(eliminated[(current+1)%n]){
current++;
}

current = (current+1)%n;
}

System.out.println();
return people[current];
}

private void printStatus(boolean[] eliminated, char[] people) {
System.out.println();
for(int i=0;i char output;
if(eliminated[i]){
output = people[i];
}else{
output = (char)(people[i] - 32);
}
System.out.print(output+" ");
}
}

private char[] getPeople(int n) {
char[] people = new char[n];
System.out.println("Participants are...");
for(int i=0;i people[i] = (char)(i+97);
System.out.print((char)(people[i]-32)+" ");
}
System.out.println();
return people;
}
}
/*
Participants are...
A B C D E F G H I J

A B c D E F G H I J
A B c D E f G H I J
A B c D E f G H i J
A b c D E f G H i J
A b c D E f g H i J
a b c D E f g H i J
a b c D E f g h i J
a b c D e f g h i J
a b c D e f g h i j

And the winner is D!!
*/

Given an array of size n and a number X, you are supposed to find a pair of numbers that sums to X.

This problem is quite largely discussed and is very famous for its various ways to attack. This can be constrained in time and in space. The most primitive way of attacking this problem would yield an solution that runs in O(n2) time.
Let me define the problem clearly. Given an array of size n and a number X, you are supposed to find a pair of numbers that sums to X. Only one pair would be enough.
Lets see how we can find the solution for this in O(n) using a HashSet. Yes, HashSet is a costly data structure to use, but lets consider this primitive just due to the linear order it provides.


import java.util.HashSet;
import java.util.Set;

public class FindSumHashSet {
public static void main(String a[]){
FindSumHashSet sumFinder = new FindSumHashSet();
sumFinder.begin();
}

public void begin(){
int[] sampleArray = getRandomArray(20);
int randomSum = sampleArray[15] + sampleArray[10];
System.out.print("ARRAY : ");
for(int i:sampleArray){
System.out.print(i+" ");
}
System.out.println();
findPair(sampleArray,randomSum);
}

public void findPair(int[] sampleArray, int randomSum) {
Set sampleArraySet = new HashSet();
for(int i=0;i sampleArraySet.add(sampleArray[i]);
int valueToFind = randomSum - sampleArray[i];
if(sampleArraySet.contains(valueToFind)){
System.out.println("SUM : "+randomSum);
System.out.println("PAIR : "+valueToFind+","+sampleArray[i]);
break;
}
}
}

private int[] getRandomArray(int size) {
int[] randomArray = new int[size];
for(int i=0;i randomArray[i] = (int)(Math.random()*10);
}
return randomArray;
}
}
//SAMPLE OUTPUTS

//ARRAY : 7 3 6 4 3 4 7 7 5 1 4 6 2 4 1 7 5 8 9 7
//SUM : 11
//PAIR : 7,4

//ARRAY : 0 2 9 6 0 7 6 5 1 7 9 0 7 1 2 4 4 3 9 0
//SUM : 13
//PAIR : 6,7

Given a string, we should be able to print all the possible palindromes. Let me quickly give a brief example. For the following text : abccbab etc

package dsa.stringmanipulation;

/**
* Program to print all palindromes in a string
* @author Bragaadeesh
*/
public class FindAllPalindromes {
public static void main(String[] args){
FindAllPalindromes finder = new FindAllPalindromes();
finder.printAllPalindromes("abcddcbaABCDEDCBA");
}

public void printAllPalindromes(String inputText){
if(inputText==null){
System.out.println("Input cannot be null!");
return;
}
if(inputText.length()<=2){
System.out.println("Minimum three characters should be present");
}
//ODD Occuring Palindromes
int len = inputText.length();
for(int i=1;i for(int j=i-1,k=i+1;j>=0&&k if(inputText.charAt(j) == inputText.charAt(k)){
System.out.println(inputText.subSequence(j,k+1));
}else{
break;
}
}
}
//EVEN Occuring Palindromes
for(int i=1;i for(int j=i,k=i+1;j>=0&&k if(inputText.charAt(j) == inputText.charAt(k)){
System.out.println(inputText.subSequence(j,k+1));
}else{
break;
}
}
}

}
}
/*
Sample Output:
DED
CDEDC
BCDEDCB
ABCDEDCBA
dd
cddc
bcddcb
abcddcba
*/

WAP to Sort Stack In Ascending Order "InPlace"

Sorting can be performed with one more stack. The idea is to pull an item from the original stack and push it on the other stack. If pushing this item would violate the sort order of the new stack, we need to remove enough items from it so that it’s possible to push the new item. Since the items we removed are on the original stack, we’re back where we started. The algorithm is O(N^2) and appears below.

public static Stack sort(Stack s) \
{
Stack r = new Stack();
while(!s.isEmpty())
{
int tmp = s.pop();
while(!r.isEmpty() && r.peek() > tmp)
{
s.push(r.pop());
}
r.push(tmp);
}
return r;
}

WAP to Calculate Square Root of Number Efficiently

It Seems to easy but people don't take care of algo & precision so why most of them don't able to implement these method & its asked in mostly core companies interviews

This Method is Known as Square root approximation - Babylonian method

Explanation
The basic idea is that if x is an overestimate to the square root of a non-negative real number S then S/x, will be an underestimate and so the average of these two numbers may reasonably be expected to provide a better approximation

It proceeds as follows:

1. Begin with an arbitrary positive starting value x0 (the closer to the root, the better).
2. Let xn+1 be the average of xn and S / xn (using the arithmetic mean to approximate the geometric mean).
3. Repeat step 2 until the desired accuracy is achieved.



#include

#include

double sqroot(const double s)
{

double xn = s / 2.0;
double lastX = 0.0;

// Looping this way ensures we perform only as many calculations as necessary.
// Can be replaced with a static for loop if you really want to.
while(xn != lastX) {
lastX = xn;
xn = (xn + s/xn) / 2.0;
}

return xn;

}
int main()
{
printf( " %f ",sqroot(7));
}

Complexity is O(log2(n)) but if the closest 2^k number is found in constant time then complexity is O(log2log2(n))
TC O(logn)
SC O(1)
Run here http://codepad.org/jmmBxoZ4


2nd Method & Well Know Mostly Used Newton Rapson method

The Newton-Raphson method in one variable:

Given a function Æ’(x) and its derivative Æ’ '(x), we begin with a first guess x0 for a root of the function. Provided the function is reasonably well-behaved a better approximation x1 is

x(n+1)=x0-f(x0,num)/f'(x0)

#include

#include

float f(float x,int n)
{
return(x*x-n);
}

float df(float x)
{
return 2*x;
}

int main()
{
float x0=3,x1,e=0.0001,num=7;
int i;

printf("\n Newton Raphson's Method : To find Square Root");

x1=(x0)-((f(x0,num))/df(x0));
printf(" %f ", x1);
i=1;
while(fabs(f(x1,num))>e)
{
x0=x1;
x1=(x0)-((f(x0,num))/df(x0));

printf("\n prev root=%f Square root of %f is %.2f",x0,num,x1);

}
}

Source http://en.citizendium.org/wiki/Newton's_method#Computational_complexity

Using Newton's method as described above, the time complexity of calculating a root of a function f(x) with n-digit precision, provided that a good initial approximation is known, is O((\log n) F(n)) where F(n) is the cost of calculating f(x)/f'(x)\, with n-digit precision.

However, depending on your precision requirements, you can do better:

If f(x) can be evaluated with variable precision, the algorithm can be improved. Because of the "self-correcting" nature of Newton's method, meaning that it is unaffected by small perturbations once it has reached the stage of quadratic convergence, it is only necessary to use m-digit precision at a step where the approximation has m-digit accuracy. Hence, the first iteration can be performed with a precision twice as high as the accuracy of x_0, the second iteration with a precision four times as high, and so on. If the precision levels are chosen suitably, only the final iteration requires f(x)/f'(x)\, to be evaluated at full n-digit precision. Provided that F(n) grows superlinearly, which is the case in practice, the cost of finding a root is therefore only O(F(n)), with a constant factor close to unit

TC O(logn)
SC O(1)
Run Here h
http://codepad.org/mIrXDehk


Too Prove why ist log(n) you can try this simple example based on binary search 

import java.util.*;
public class SQRT
{
public static void main(String args[])
{
float n=7;
float y=sqrt(n);
System.out.println("sqrt is "+y);
}
static float sqrt(float n)
{
float low=0,high=n;
float mid=(low+high)/2;
while(Math.abs(mid*mid-n)>0.0000001)
{

if(mid*mid<n)
low=mid;
else if(mid*mid>n)
high=mid;
mid=(low+high)/2;

}

How to find a number of 10 digits (non repeated digits) which is a perfect square? perfect square examples: 9 (3x3) 16 (4x4) 25(5x)

class perfectSquare
{

/**
* @param args
*/

public static int check(long num)
{
int[] A={0,0,0,0,0,0,0,0,0,0};
int i;

while ( num != 0)
{
i=(int) (num%10);
if (A[i]==0)
{
A[i]=1;
num=num/10;

}
else
return 0;

}
return 1;
}


public static void main(String[] args) {
// TODO Auto-generated method stub

long b=(long) Math.sqrt(1023456789);
long bn= 9876543210L;
long e=(long) Math.sqrt(bn);
int count=0;

for (long j=b;j<=e;j++)
if(check((long)(j*j))!=0)
{
count++;
System.out.println((j*j));
}

System.out.println("count::"+count);


}

}


compilation info

input / output show all hide all
# 1

* upload with new input

You have reached a limit of free submissions this month.
You cannot send submissions this month anymore because of exceeding your monthly limit. Please recharge your account.
*
# 1: hide show edit 2 days 15 hours ago

result: Success time: 0.09s memory: 213440 kB returned value: 0
input: no
output:

1026753849
1042385796
1098524736
1237069584
1248703569
1278563049
1285437609
1382054976
1436789025
1503267984
1532487609
1547320896
1643897025
1827049536
1927385604
1937408256
2076351489
2081549376
2170348569
2386517904
2431870596
2435718609
2571098436
2913408576
3015986724
3074258916
3082914576
3089247561
3094251876
3195867024
3285697041
3412078569
3416987025
3428570916
3528716409
3719048256
3791480625
3827401956
3928657041
3964087521
3975428601
3985270641
4307821956
4308215769
4369871025
4392508176
4580176329
4728350169
4730825961
4832057169
5102673489
5273809641
5739426081
5783146209
5803697124
5982403716
6095237184
6154873209
6457890321
6471398025
6597013284
6714983025
7042398561
7165283904
7285134609
7351862049
7362154809
7408561329
7680594321
7854036129
7935068241
7946831025
7984316025
8014367529
8125940736
8127563409
8135679204
8326197504
8391476025
8503421796
8967143025
9054283716
9351276804
9560732841
9614783025
9761835204
9814072356
count::87

Prime Number Generation Using Sieve of Eratosthenes

public class prime_sieve
{


public static void main(String a[])
{

runEratosthenesSieve(100);

}

public static void runEratosthenesSieve(int upperBound) {

int upperBoundSquareRoot = (int) Math.sqrt(upperBound);

boolean[] isComposite = new boolean[upperBound + 1];

for (int m = 2; m <= upperBoundSquareRoot; m++) {

if (!isComposite[m]) {

System.out.print(m + " ");

for (int k = m * m; k <= upperBound; k += m)

isComposite[k] = true;

}

}

for (int m = upperBoundSquareRoot; m <= upperBound; m++)

if (!isComposite[m])

System.out.print(m + " ");

}


}

AP to implement Horner Rule

#include

double horner(double *coeffs, int s, double x)
{
int i;
double res = 0.0;

for(i=s-1; i >= 0; i--)
{
res = res * x + coeffs[i];
}
return res;
}


int main()
{
double coeffs[] = { -19.0, 7.0, -4.0, 6.0 };

printf("%5.1f\n", horner(coeffs, sizeof(coeffs)/sizeof(double), 3.0));
return 0;
}
W

WAP to implement Htoi Function (it Used to Convert Hexadecimal into Integer)

#include
#include
#include

void htoi(char *);

int main()
{
char *hex="0xFFFF";
htoi(hex);
return 0;
}

void htoi(char *hexstr)
{
char c;
int val=0,i;

int len=strlen(hexstr);
for(i=0;i{
c=*(hexstr+2); //pointer will points to F in case of 0xFFFF

if(c>='a' && c<='f')
{
val=val*16+(c-'a'+10);
}

else if(c>='A' && c<='F')
{
val=val*16+(c-'A'+10);
}

else
{

if(c>='0' && c<='9')
{
val=val*16+(c-'0');
}

}
printf("Val: %d \t ",val);
hexstr++;

}

printf("\n Val: %d ",val);
}

Friday, February 25, 2011

Given 3 sorted arrays Let x be an element of A, y of B, z of C.the distance b/w x,y,z =max(|x-y|,|y-z|,|z-x|) Find Touple With Minimum Distance

Given 3 sorted arrays (in ascending order). Let the arrays be A(of n1 length), B(of n2 length), C(of n3 length). Let x be an element of A, y of B, z of C. The distance between x, y and z is defined as the max(|x-y|,|y-z|,|z-x|). Find the tuple with the minimum distance?


#include
#include

#define min2(a,b) (a) < (b) ? (a) : (b)
#define min3(a,b,c) (a) < (b) ? min2(a,c) : min2(b,c)
#define max2(a,b) (a) > (b) ? (a) : (b)
#define max3(a,b,c) (a) > (b) ? max2(a,c) : max2(b,c)


typedef struct
{
int x, y, z;
}Tuple;


Tuple mindist(int a[], int b[], int c[], int m, int n, int l)
{
int i = 0;
int j = 0;
int k = 0;

int distance = INT_MAX;
Tuple out = {-1,-1,-1};


while(i < m && j < n && k < l)
{
//Find max (abs(a[i]-b[j]), abs(b[j]-c[k]), abs(a[i]-c[k])
//Advance minimum of a[i], b[j] and c[l]

int x = abs(a[i]-b[j]);
int y = abs(b[j]-c[k]);
int z = abs(a[i]-c[k]);

int d = max3(x,y,z);
if(d < distance)
{
distance = d;
out.x = i; out.y = j, out.z = k;
}

int min = min3(a[i], b[j], c[k]);

if(min == a[i])
i++;
else if(min == b[j])
j++;
else if(min == c[k])
k++;

}
return out;

}


int main()
{
int m=3, n=4, l=5;


int a[]={1,2,3};
int b[]={5,6,7,8};;
int c[]={10,11,12,13,14};

int i;

Tuple r = mindist(a,b,c,m,n,l);

printf("(%d,%d,%d)\n", r.x,r.y,r.z);
}

Given M-by-N matrix all the elements of the j-th row and k-th column to 0 if matrix[k][j] is 1

Suppose you have a (i.e. M rows and N columns), whose entries are all integers. Set all the elements of the j-th row and k-th column to 0 if matrix[k][j] is 1.

For instance, if the matrix is:

1 1 2 15
3 0 1 7
0 3 9 10
2 4 6 8

then, the result should be:

0 0 0 0
0 0 0 0
0 0 0 10
0 0 0 8



class matrix_ones
{


public static void setOnes(int[][] matrix)
{
int[] row = new int[matrix.length];
int[] column = new int[matrix[0].length];
// Store the row and column index with value 0
for (int i = 0; i < matrix.length; i++)
{
for (int j = 0; j < matrix[0].length;j++)
{

if (matrix[i][j] == 1)
{
row[i] = 1;
column[j] = 1;
}

}

}

// Set arr[i][j] to 0 if either row i or column j has a 0
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if ((row[i] == 1 || column[j] == 1)) {
matrix[i][j] = 0;
}
}
}
}


public static void main(String a[])
{
int ar[][]=new int[][]{
{1, 1 ,2 ,15},
{3 ,0 ,1 ,7},
{0, 3, 9, 10},
{2 ,4 ,6 ,8}

};


setOnes(ar);

for (int i = 0; i <4; i++)
{
for (int j = 0; j < 4;j++)
{

System.out.println(ar[i][j]);

}
System.out.println();


}

}


}

Thursday, February 24, 2011

WAP to reverse Stack inplace

You are not allowed to use loop constructs like while, for..etc, and you can only use the following ADT functions on Stack S:
isEmpty(S)
push(S)
pop(S)

Solution:
The idea of the solution is to hold all values in Function Call Stack until the stack becomes empty. When the stack becomes empty, insert all held items one by one at the bottom of the stack.

For example, let the input stack be

1 <-- top
2
3
4

First 4 is inserted at the bottom.
4 <-- top

Then 3 is inserted at the bottom
4 <-- top
3

Then 2 is inserted at the bottom
4 <-- top
3
2

Then 1 is inserted at the bottom
4 <-- top
3
2
1

So we need a function that inserts at the bottom of a stack using the above given basic stack function. //Below is a recursive function that inserts an element at the bottom of a stack.
?
void insertAtBottom(struct sNode** top_ref, int item)
{
int temp;
if(isEmpty(*top_ref))
{
push(top_ref, item);
}
else
{

/* Hold all items in Function Call Stack until we reach end of
the stack. When the stack becomes empty, the isEmpty(*top_ref)
becomes true, the above if part is executed and the item is
inserted at the bottom */
temp = pop(top_ref);
insertAtBottom(top_ref, item);

/* Once the item is inserted at the bottom, push all the
items held in Function Call Stack */
push(top_ref, temp);
}
}

//Below is the function that reverses the given stack using insertAtBottom()
?
void reverse(struct sNode** top_ref)
{
int temp;
if(!isEmpty(*top_ref))
{

/* Hold all items in Function Call Stack until we reach end of
the stack */
temp = pop(top_ref);
reverse(top_ref);

/* Insert all the items (held in Function Call Stack) one by one
from the bottom to top. Every item is inserted at the bottom */
insertAtBottom(top_ref, temp);
}
}

//Below is a complete running program for testing above functions.


#include
#include
#define bool int



/* structure of a stack node */
struct sNode
{
char data;
struct sNode *next;
};

/* Function Prototypes */
void push(struct sNode** top_ref, int new_data);
int pop(struct sNode** top_ref);
bool isEmpty(struct sNode* top);
void print(struct sNode* top);



void insertAtBottom(struct sNode** top_ref, int item)
{
int temp;
if(isEmpty(*top_ref))
{
printf(" yes : ");
push(top_ref, item);
}
else
{

/* Hold all items in Function Call Stack until we reach end of
the stack. When the stack becomes empty, the isEmpty(*top_ref)
becomes true, the above if part is executed and the item is
inserted at the bottom */
temp = pop(top_ref);
insertAtBottom(top_ref, item);

/* Once the item is inserted at the bottom, push all the
items held in Function Call Stack */
push(top_ref, temp);
}
}


void reverse(struct sNode** top_ref)
{
int temp;
if(!isEmpty(*top_ref))
{

/* Hold all items in Function Call Stack until we reach end of
the stack */
temp = pop(top_ref);
printf(" %d ", temp);
reverse(top_ref);

/* Insert all the items (held in Function Call Stack) one by one
from the bottom to top. Every item is inserted at the bottom */
insertAtBottom(top_ref, temp);
}
}

/* Driveer program to test above functions */
int main()
{
struct sNode *s = NULL;
push(&s, 4);
push(&s, 3);
push(&s, 2);
push(&s, 1);

printf("\n Original Stack ");
print(s);
reverse(&s);
printf("\n Reversed Stack ");
print(s);
getchar();
}

/* Function to check if the stack is empty */
bool isEmpty(struct sNode* top)
{
return (top == NULL)? 1 : 0;
}

/* 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)
{
char 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;
}
}

/* Functrion to pront a linked list */
void print(struct sNode* top)
{
printf("\n");
while(top != NULL)
{
printf(" %d ", top->data);
top = top->next;
}
}


/*

void reverse(stack s){
if(empty(s)){
return ;
}
func(s);
k=s.pop();
reverse(s);
push(&s,k);
}

void func(stack s){
if(empty(s)){
return ;
}
k=s.pop();
if(!empty(s)){
temp=s.pop();
push(&s,k);
push(&s,temp);
}
else{
push(&s,k);
}
}

*/

Run Here https://ideone.com/pCoDm
Source Geesk4Geeks

Given an array and an integer k, find the maximum for each and every contiguous sub array of size k.

Sample Input :
1 2 3 1 4 5 2 3 6
3 [ value of k ]

Sample Output :
3
3
4
5
5
5
6



#include

using namespace std;

int max(int a[],int r,int pos)
{
int m=a[pos];
int i=0;
for(i=pos+1;i {
if(a[i]>m)
{
m=a[i];
}

}

return m;
}
void maxi(int a[],int r,int pos)
{
int m;

if(pos > 10-r ) return ;
m=max(a,3,pos);
cout< maxi(a,r,pos+1);
}
int main()
{
int a[]={1, 2, 3 ,1 ,4 ,5 ,2 ,3 ,6};

int pos=0;

maxi(a,3,pos);


return 1;
}

Given a tree and a sum, return true if there is a path from the root down to a leaf, such that adding up all the values along the path equals the

#include
#include
#define bool int

/* 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;
};

/*
Given a tree and a sum, return true if there is a path from the root
down to a leaf, such that adding up all the values along the path
equals the given sum.

Strategy: subtract the node value from the sum when recurring down,
and check to see if the sum is 0 when you run out of tree.
*/
bool hasPathSum(struct node* node, int sum)
{
/* return true if we run out of tree and sum==0 */
if (node == NULL)
{
return(sum == 0);
}
else
{
/* otherwise check both subtrees */
int subSum = sum - node->data;
return(hasPathSum(node->left, subSum) ||
hasPathSum(node->right, subSum));
}
}

/* UTILITY FUNCTIONS */
/* 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);
}

/* Driver program to test above functions*/
int main()
{

int sum = 21;

/* Constructed binary tree is
10
/ \
8 2
/ \ /
3 5 2
*/
struct node *root = newnode(10);
root->left = newnode(8);
root->right = newnode(2);
root->left->left = newnode(3);
root->left->right = newnode(5);
root->right->left = newnode(2);

if(hasPathSum(root, sum))
printf("There is a root-to-leaf path with sum %d", sum);
else
printf("There is no root-to-leaf path with sum %d", sum);

getchar();
return 0;
}

WAP to Convert Zig Zag level order Traversal of Tree to Doubly Linked List

Method 1 using 2-Stack--Need Modification RunTime Error But Logic is 100% Correct

#include
#include

/* Structure for Tree */
struct node
{
struct node* left;
struct node* right;
int data;
};

/* structure of a stack node */
struct sNode
{
struct node *t;
struct sNode *next;
};

/* Helper function that allocates a new tNode with the
given data and NULL left and right pointers. */
struct node* newtNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}


/* UTILITY FUNCTIONS */
/* Function to push an item to sNode*/
void push(struct sNode** top_ref, struct node *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 node *pop(struct sNode** top_ref)
{
struct node *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;
}
}

void Insert(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;

/* since we are adding at the begining,
prev is always NULL */
new_node->left= NULL;

/* link the old list off the new node */
new_node->right= (*head_ref);

/* change prev of head node to new node */
if((*head_ref) != NULL)
(*head_ref)->left= new_node ;

/* move the head to point to the new node */
(*head_ref) = new_node;
}

void Spiral(struct node* root)
{
struct node *head;//for DLL
struct sNode *node1;
struct sNode *node2;
struct node *temp;


if(root == NULL)
return;

push(&node1,root);


while(!isEmpty(node1) && !isEmpty(node2))
{

while(!isEmpty(node1))
{
temp = pop(&node1);
Insert(&head,temp->data);
push(&node2,temp->right);
push(&node2,temp->left);
}
//temp=NULL;

while(!isEmpty(node2))
{
temp = pop(&node2);
Insert(&head,temp->data);
push(&node1,temp -> left);
push(&node1,temp -> right);
}

}

}

/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct node* node)
{
if (node == NULL)
return;

/* first recur on left child */
printInorder(node->left);

/* then print the data of node */
printf("%d ", node->data);

/* now recur on right child */
printInorder(node->right);
}

/* Utility function to print a linked list */
void printList(struct node* head)
{
while(head!=NULL)
{
printf("%d ",head->data);
head=head->right;
}
printf("\n");
}

/* Driver function to test above functions */
int main()
{
struct node *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);

Spiral(root);
printList(root);

getchar();
}

TC O(n)
Sc (2n) if Stack Space is considered else O(1)
Run Here https://ideone.com/cyPM5

Method 2 Using Recursion(Bottom Up Tree Traversal)


#include
#include

struct node
{
struct node *left;
struct node *right;
int data;

};

struct node *rslt;//Global structure pointer..it point to head of doubly linked list


int height(struct node* head)
{

if(head==NULL)
return 0;

if(head->left==NULL && head->right==NULL)
return 0;

int lh=height(head->left);
int rh=height(head->right);

return lh>rh?(lh+1):(rh+1);

}

struct node* appnd(struct node *a,struct node *b)
{
if(a==NULL)return b;
if(b==NULL)return a;

struct node* result=a;
while(a->left!=NULL)
a=a->left;

a->left=b;
b->right=a;

b->left=NULL;

return result;

}

void printGivenLevel(struct node* head,int level,int ltr)
{
if(head==NULL)
return;

if(level==0)
{
appnd(rslt, head);
rslt = head;
}

if(level>0)
{

if(ltr)
{
printGivenLevel(head->left,level-1,ltr);
printGivenLevel(head->right,level-1,ltr);
}
else
{
printGivenLevel(head->right,level-1,ltr);
printGivenLevel(head->left,level-1,ltr);

}
}

}

void printGivenOrder(struct node* head)
{

int i=0;
int ltr=0;

for(i=height(head); i >= 0; i--)
{

printGivenLevel(head,i,ltr);
ltr=~ltr;
}

}

struct node* NewNode(int data)
{
struct node* tmp=(struct node *)malloc(sizeof(struct node));
tmp->data=data;
tmp->left=NULL;
tmp->right=NULL;
return tmp;

}

void printList(struct node* node)
{
struct node* current=node;
while(current)
{
printf("%d ----> ",current->data);
current=current->right;
}


}

int main()
{
struct node* start=NULL;

start=NewNode(1);
start->left=NewNode(2);
start->right=NewNode(3);
start->left->left=NewNode(4);
start->left->right=NewNode(5);
start->right->left=NewNode(6);
start->right->right=NewNode(7);

printGivenOrder(start);

printList(rslt);

return 0;

}
TC O(n^2)....need Modification..??
Sc O(1)
Run Here https://ideone.com/y9Ssb

WAP for Sorting Doubly Linked List

/* Program to reverse a doubly linked list */
#include
#include

/* a node of the doubly linked list */
struct node
{
int data;
struct node *next;
struct node *prev;
};


/* UTILITY FUNCTIONS */
/* Function to insert a node at the beginging of the Doubly Linked List */
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;

/* since we are adding at the begining,
prev is always NULL */
new_node->prev = NULL;

/* link the old list off the new node */
new_node->next = (*head_ref);

/* change prev of head node to new node */
if((*head_ref) != NULL)
(*head_ref)->prev = new_node ;

/* move the head to point to the new node */
(*head_ref) = new_node;
}


struct node* SortedMerge(struct node* a, struct node* b)
{
struct node* result = NULL;

/* Base cases */
if (a == NULL)
return(b);
else if (b==NULL)
return(a);

/* Pick either a or b, and recur */
if (a->data <= b->data)
{
result = a;
result->next = SortedMerge(a->next, b);
}
else
{
result = b;
result->next = SortedMerge(a, b->next);
}
return(result);
}

int Length(struct node* head)
{
int count = 0;
struct node* current = head;
while (current != NULL)
{
count++;
current=current->next;
}
return(count);
}
// to split list in to two equal part using lenth function
void FrontBackSplit(struct node* source,struct node** frontRef, struct node** backRef)
{
int len = Length(source);
int i;
struct node* current = source;

if (len < 2) {
*frontRef = source;
*backRef = NULL;
}
else {
int hopCount = (len-1)/2; //(figured these with a few drawings)
for (i = 0; icurrent = current->next;
}
// Now cut at current
*frontRef = source;
*backRef = current->next;
current->next = NULL;
}
}


/* sorts the linked list by changing next pointers (not data) */
void MergeSort(struct node** headRef)
{
struct node* head = *headRef;
struct node* a;
struct node* b;

/* Base case -- length 0 or 1 */
if ((head == NULL) || (head->next == NULL))
{
return;
}

/* Split head into 'a' and 'b' sublists */
FrontBackSplit(head, &a, &b);

/* Recursively sort the sublists */
MergeSort(&a);
MergeSort(&b);

/* answer = merge the two sorted lists together */
*headRef = SortedMerge(a, b);
}




/* Function to print nodes in a given doubly linked list
This function is same as printList() of singly linked lsit */

void printList(struct node *node)
{
while(node!=NULL)
{
printf("%d ", node->data);
node = node->next;
}
}

/* Drier program to test above functions*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;

/* Let us create a sorted linked list to test the functions
Created linked list will be 10->8->4->2 */
push(&head, 3);
push(&head, 1);
push(&head, 2);
push(&head, 2);
push(&head, 1);
push(&head, 3);
push(&head, 1);
push(&head, 2);
push(&head, 2);

printf("\n Original Linked list ");
printList(head);

MergeSort(&head);


printf("\nsorted Doubly Linked list ");
printList(head);


getchar();
}


Run Here https://ideone.com/dESuB

Wednesday, February 23, 2011

WAP tp print Combination of given string

#include
#include
#include

void mycombination(char const * const s, int l, int *arr, int index, int start, int d)
{
int i,j;
if (index >= d)
return ;
for (j = start ; j < l ; j++)
{
arr[index] = j;
if (index == d-1)
{
for (i=0;i putchar('\n');
}
else
mycomb_ultrabad(s,l,arr,index+1,j+1,d);
}
return ;
}

int main()
{
int i,d;
char s[4]={'a','v','i'};
d = strlen(s);
int arr[d+1];
for (i=0;i {
mycomb_ultrabad(s, d, arr,0,0,d-i);
}
return 0;
}

WAP to Swap Two NIbble in Byte

struct nibbles
{
int lnibble:4;
int unibble:4;
};
union swap
{
char byte;
struct nibbles nb;
};
int main()
{
union swap sw;
int temp;
sw.byte=0x12;
printf("Before swap:%x\n",sw.byte);
temp=sw.nb.lnibble;
sw.nb.lnibble=sw.nb.unibble;
sw.nb.unibble=temp;
printf("After swap:%x",sw.byte);
}

Given a integer matrix of size m*n. We need to find a sub matrix with the largest sum.

#include
using namespace std;

#define MAX(a, b) (a>b ? a : b)
#define MIN(a, b) (a>b ? b : a)
int const maxn = 102;
int map[maxn][maxn], sum[maxn][maxn];
int n;

int read()
{
int i, j;
if(cin >> n)
{
for(i=1;i<=n;++i)
{
sum[i][0] = 0;
for(j=1;j<=n;++j)
{
cin >> map[i][j];
sum[i][j] = map[i][j] + sum[i][j-1];
}
}
return 1;
}
return 0;
}

void solve()
{
int i, j, k, sub_row, max[maxn], min[maxn], best;
best = 0;
for(i=1;i<=n;++i)
{
for(j=i;j<=n;++j)
{
sub_row = 0;
max[0] = 0;
min[0] = 100000;
for(k=1;k<=n;++k)
{
sub_row = sum[k][j] - sum[k][i];
max[k] = MAX(max[k-1], sub_row);
min[k] = MIN(min[k-1], sub_row);
}
best = MAX(max[n] - min[n], best);
}
}

cout << best << endl;
/*for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
cout << map[i][j] << " " << endl;*/
}

int main()
{
while(read()) solve();
return 0;
}

WAP for Square Matrix Rotation by 90 Degree

Method 1 (Using auxiliary Space of matrix size)

void rotate (Matrix m)
{
Matrix temp;
for(int i=0;i for(int j=0;j temp[i][j]=m[SIZE-j-1][i];

for(int i=0;i for(int j=0;j m[i][j]= temp [i][j];

}

void print (Matrix a)
{
for(int i=0;i {
for(int j=0;j cout< cout< }
cout<

}
This is the before and after output
/*Original square matrix:
11 22 33
44 55 66
77 88 99

Matrix now rotated 90
77 44 11
88 55 22
99 66 33*/

Time Complexity O(m*n)
Space Complexity O(n)




2nd Method In Place Matrix Rotation (Will Work Only For Square Matrix)

void rotate_matrix_90degree(int **m, int n)
{
int i, j;

// first mirror the matrix along the diagonal line.
for (i = 0; i < n; i++)
{
for (j = i + 1; j < n; j++)
{
int tmp = m[i][j];
m[i][j] = m[j][i];
m[j][i] = tmp;
}
}

// mirror the matrix horizontally. for Left Rotation
// and mirror the matrix vertically for right rotation

for (i = 0; i < n / 2; i++)
{
for (j = 0; j < n; j++)
{
int tmp = m[j][i];
m[j][i] = m[j][n - i - 1];
m[j][n - i - 1] = tmp;
}
}
}

Time Complexity O(m*n)
Space Complexity O(1)

Please write comment if you find any thing wrong in this code or anything
missing

Write a program to add two long positive numbers (each represented by linked lists).

mynode *long_add(mynode *h1, mynode *h2, mynode *h3)
{
mynode *c, *c1, *c2;
int sum, carry, digit;

carry = 0;
c1 = h1->next;
c2 = h2->next;

while(c1 != h1 && c2 != h2)
{
sum = c1->value + c2->value + carry;
digit = sum % 10;
carry = sum / 10;

h3 = insertNode(digit, h3);

c1 = c1->next;
c2 = c2->next;
}

if(c1 != h1)
{
c = c1;
h = h1;
}
else
{
c = c2;
h = h2;
}

while(c != h)
{
sum = c->value + carry;
digit = sum % 10;
carry = sum / 10;
h3 = insertNode(digit, h3);
c = c->next;
}

if(carry==1)
{
h3 = insertNode(carry, h3);
}

return(h3);
}

WAP for Converting integer in to string it means you have to implement your own itoa function

I used to function here after storing string in to char* we have to reverse it to get desired output

#include
#include


void reverse(char *str,int len) {
int i=0;
char ch;
for(i=0;i<=(len-1)/2;i++) {
ch=str[i];
str[i]=str[len-1-i];
str[len-1-i]=ch;
}
}


char* itoa(int number) {
char *str=malloc(sizeof(char)*20);
int negFlag=0,pos=0;
if(number<0) {
negFlag=1;
number=-number;
}
while(number>0) {
str[pos++]='0'+number%10;
number=number/10;
}
if(negFlag) {
str[pos++]='-';
}
str[pos]='\0';
reverse(str,pos);
return str;
}


int main() {
printf("reverse %d : %s ",-543,itoa(-543));
printf("reverse %d : %s ",54,itoa(54));
printf("reverse %d : %s ",5,itoa(5));
}

WAP for Converting String in to Integer it means you have to implement your own atoi function

so Here we Go its Simple Logic

#include

int main(int argc, char* argv[])
{
printf("\n%d\n", myatoi("1998"));
getch();
return(0);
}

int myatoi(const char *string)
{
int i;
i=0;
while(*string)
{
i=(i<<3) + (i<<1) + (*string - '0');
string++;

//i am using left shift which is equals to multiply by pow(2,n) & shifting is fast then multiplication
// Don't increment i!

}
return(i);
}

Run Herehttps://ideone.com/XUKdL

Tuesday, February 22, 2011

Given a list of numbers and a number x, find two numbers in the list such that product of those 2 numbers is equal to x

import java.util.*;

class twonummulti_equalto_x
{

public static void main(String[] args)
{

int x = 21;
int[] arr = {4, 7, 3, 2, 4, 7, 6, 5, 2};

Set set = new HashSet ();
for (int i=0; i{
set.add(arr[i]);
}

Iterator itr = set.iterator();

while (itr.hasNext())
{
int i = itr.next();
int div = x/i;
int mod = x%i;
if (mod==0 && set.contains(div))
{
System.out.println(i+"x"+div+"="+x);
}

}

}


}

Find common sequence that is out of order between two given strings in Java

/*
Given two strings, find the longest common sequence that is out of order. Initially it was royally confusing to me what the question meant, but I was able to come up with a solution. Please see the following program implemented in Java. The sample inputs and outputs have been provided at the end.
*/
Hashing is Most Efficient Solution

import java.util.LinkedHashMap;
import java.util.Map;

public class Sequence {
public static void main(String[] args) {
Sequence seq = new Sequence();
String str1 = "a111b3455yy";
String str2 = "byy115789";
System.out.println("Input1: "+str1);
System.out.println("Input2: "+str2);
String solution = seq.findCommonSequnce(str1, str2);
System.out.println("Output: "+solution);
}

public String findCommonSequnce(String str1, String str2){
if(str1==null || str2==null){
return "";
}
if(str1.length() == 0 || str2.length() == 0){
return "";
}
//parse first String store the frequency of characters
//in a hashmap
Map firstStringMap = frequencyMap(str1);

StringBuilder output = new StringBuilder();

for(int i=0;i int count = 0;
if(firstStringMap.containsKey(str2.charAt(i)) && (count=firstStringMap.get(str2.charAt(i)))>0){
output.append(str2.charAt(i));
firstStringMap.put(str2.charAt(i), --count);
}
}

return output.toString();
}

/**
* Returns a map with character as the key and its occurence as the value
* @param str
* @return
*/
private Map frequencyMap(String str) {
Map freqMap = new LinkedHashMap();
for(int i=0;i Integer count = freqMap.get(str.charAt(i));
if(count==null){//means the frequency is yet to stored
freqMap.put(str.charAt(i), 1);
}else{
freqMap.put(str.charAt(i), ++count);
}
}
return freqMap;
}
}

//SAMPLE OUTPUTS
//Input1: a111b3455yy
//Input2: byy115789
//Output: byy115

Given a square matrix, write a program to print the items in zig zag diagonal order.

if Give Matrix is

1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

So the output expected for the above example is,

1 -> 2 -> 6 -> 3 -> 7 -> 11 -> 4 -> 8 -> 12 -> 16 -> 5 -> 9 -> 13 -> 17 -> 21 -> 10 -> 14 -> 18 -> 22 -> 15 -> 19 -> 23 -> 20 -> 24 -> 25

Solution:

This program is a bit tricky and is very hard to solve immediately when asked in an interview. People who try to attack problems involving matrices always think they need at least two loops to arrive at the solution. But the surprise here is the problem can be solved in just a single loop with a very simple logic.




#include
using namespace std;

#define MAX 5

int main(){
int a[MAX][MAX] =
{{ 1, 2, 3, 4, 5},
{ 6, 7, 8, 9,10},
{11,12,13,14,15},
{16,17,18,19,20},
{21,22,23,24,25}};
int i=0,j=0;
while(i cout << a[i][j] << " -> ";
if(i==MAX-1){
i = j+1; j = MAX-1;
}
else if(j==0){
j = i+1; i = 0;
}
else{
i++; j--;
}
}
cout << endl;

return 0;
}

WAP for Quick Sort Algorithm

Data Structure used:Array

Algorithm:Divide & Conquer
1. Phase:Partition O(N) Time
2. Phase: Divide the array in two part Recursively & call partition function until we are run out of array O(nlogn)

Recursive Function Looks Like T(n)=2*T(n/2)+O(n)

Working Code:
public class QuickSort
{

public static int SIZE = 1000000;

public int[] sort(int[] input) {
quickSort(input, 0, input.length-1);
return input;
}

public static void main(String args[]){
int[] a = new int[SIZE];
for(int i=0;i pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}
return i;
}
}
//Time taken to sort a million elements : 156 milliseconds

Time Complexity O(nlogn)
Space Complexity O(logn)
Run Here http://ideone.com/clone/ClBCZ

Complexity Analysis ( More Focus on Space )

very Few of us Know & are abale to come up space compelxity of quick sort if asked during the interview isn't it ?

Quicksort has a space complexity of O(logn), even in the worst case, when it is carefully implemented such that

* in-place partitioning is used. This requires O(1).
* After partitioning, the partition with the fewest elements is (recursively) sorted first, requiring at most O(logn) space. Then the other partition is sorted using tail-recursion or iteration.

The version of quicksort with in-place partitioning uses only constant additional space before making any recursive call. However, if it has made O(logn) nested recursive calls, it needs to store a constant amount of information from each of them. Since the best case makes at most O(logn) nested recursive calls, it uses O(logn) space. The worst case makes O(n) nested recursive calls, and so needs O(n) space.

However, if we consider sorting arbitrarily large lists, we have to keep in mind that our variables like left and right can no longer be considered to occupy constant space; it takes O(logn) bits to index into a list of n items. Because we have variables like this in every stack frame, in reality quicksort requires O(log2n) bits of space in the best and average case and O(nlogn) space in the worst case. This isn't too terrible, though, since if the list contains mostly distinct elements, the list itself will also occupy O(nlogn) bits of space.