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;