Amazon Interview Question Software Analysts
Country: India
Interview Type: Written Test
The question is asking not to use an additional array. However assuming we can use additional data structures other than array, this approach seems to be the most appropriate way to solve the problem.
@Apostle ... It's not mentioned that you cannot use any extra space. And I think if you have to solve the problem in linear time then there is no choice except using O(n) extra space.
But if a linked list had been given then we could possibly solve the problem in O(n) time using O(1) space.
@EOF says, "There is no choice except using O(n) space, to solve in linear time". This is WRONG.
It is possible to do this in linear time and O(1) space. Hard, but not impossible.
We can do it in O(1) space.
simply take two variable say
next_negative
next positive
now traverse the array from start , if any position you found any value at wrong position, store that in appropriate variable. and update the index with proper value.
you need to traverse the array with two variable one for positive and other for negative.
if something wrong plzz correct me .
#include<stdio.h>
#include<conio.h>
int main()
{
int i,j,k,l,temp,n;
int arr[]={1,-2,3,-4,-5,-6,-7,8,9,4,10,11,12};
int length=sizeof(arr)/sizeof(arr[0]);
for(i=0;i<length;i++)
{
if(i%2==0)
{
if(arr[i]>0)
;
else{
j=i;
while(arr[j]<0 && j<length)
j++;
if(j>=length)
;
else
{
temp=arr[j];
for(k=j;k>i;k--)
arr[k]=arr[k-1];
arr[i]=temp;
}
}
}
if(i%2!=0)
{
if(arr[i]<0)
;
else{
j=i;
while(arr[j]>0 && j<length)
j++;
if(j>=length)
;
else
{
temp=arr[j];
for(k=j;k>i;k--)
arr[k]=arr[k-1];
arr[i]=temp;
}
}
}
}
for(i=0;i<length;i++)
printf("%d ",arr[i]);
getch();
return 0;
}
#include <iostream>
using namespace std;
void change(int*, int);
int main() {
int a[] = {1, -2, 3, -4, -5, -6, -7, 8, 9, 4, 10, 11, 12};
int len = sizeof(a)/sizeof(int);
change(a, len);
return 0;
}
void change(int *arr, int len) {
int pos_num = 0;
int neg_num = 0;
for (int i = 0; i < len; i++)
if (arr[i] > 0)
pos_num++;
else
neg_num++;
int count = (pos_num < neg_num) ? pos_num : neg_num;
bool isPos = (pos_num < neg_num) ? true : false;
int i = 0;
int index = 0;
while (i < count && index < len) {
if (index % 2 == 0) {
if (arr[index] < 0) {
int position = index+1;
while (arr[position] < 0 && position < len)
position++;
while (position > index) {
int temp = arr[position];
arr[position] = arr[position-1];
arr[position-1] = temp;
position--;
}
}
index++;
if (isPos)
i++;
} else {
if (arr[index] > 0) {
int position = index+1;
while (arr[position] > 0 && position < len)
position++;
while (position > index) {
int temp = arr[position];
arr[position] = arr[position-1];
arr[position-1] = temp;
position--;
}
}
index++;
if (!isPos)
i++;
}
}
for(int i = 0; i < len; i++)
cout << arr[i] << ", ";
cout << endl;
}
My Algorithm: Time O(N) -- Idea: totally use 4 pointers to forsee the next 2 positive nos, and next 2 neg nos.. we can save those 4 values in temp variables -- curr_pos, next_pos, curr_neg, next_neg (i.e, marked by 4 pointers -- cur_pos_ptr, next_pos_ptr, cur_neg_ptr, next_neg_ptr respectively).. pls let me know your thoughts on this...
Then we can simply overwrite the original array (as these pointers will always be at an advanced index location.. so no extra space..
Full algo--
// Set up the pos & neg pointers the first time (Ex. start from -1 index loc, and figure out these...)
index=0
cur_pos_ptr=next_pos_ptr=cur_neg_ptr=next_neg_ptr=index-1
while(++cur_pos_ptr <0); curr_pos_num=a[cur_pos_ptr];
next_pos_ptr=cur_pos_ptr;
while(++nex_pos_ptr <0); nex_pos_num=a[nex_pos_ptr];
//Similarly find the (cur_neg_ptr & nex_neg_ptr) -- and hence, the 2 next nos..just a reverse of the above logic.. use > instead of < ...
#EOA = End of array
Excuse me for confusing variable names...
Step 2:
while(cur_pos_ptr != EOA && cur_neg_ptr != EOA){
a[index++]=cur_pos_num;
cur_pos_ptr=nex_pos_ptr; cur_pos_num=next_pos_num;
while(++nex_pos_ptr <0);
if(nex_pos_ptr ! = EOA) next_pos_num = a[nex_pos_ptr]
a[index++] = cur_neg_num;
cur_neg_ptr=nex_neg_ptr; cur_neg_num=nex_neg_num;
while(++nex_neg_ptr);
if(nex_neg_ptr ! = EOA) nex_neg_num = a[nex_neg_ptr];
}
if(cur_pos_ptr == EOA)
while(cur_neg_ptr ! = EOA) a[index++] = a[cur_neg_ptr++];
return;
if(cur_neg_ptr == EOA)
while(cur_pos_ptr ! = EOA) a[index++] = a[cur_pos_ptr++];
return;
Here it is in Java. The trick for me was determining exactly under what conditions the algorithm is done with no further work to do. That helped me simplify the corner cases.
package org.foo.alg;
import java.util.Arrays;
public class PosNegArrayShuffle {
public static void main(String[] args) {
int[] ar = {1, -2, 3, -4, -5, -6, -7, 8, 9, 4, 10, 11, 12};
int i = 0, k = 0;
int tempval = 0;
System.out.println("Was: " + Arrays.toString(ar));
// Iterate through the array, trying to fill the kth spot with next appropriate value
// if there is no appropriate value that should go in the spot, then we're done
for (k = 0; k < ar.length; k++) {
// Is the value currently in the array "good"?
boolean even = (k % 2 == 0);
if ((even && (ar[k] > 0)) || (!even && ar[k] < 0)) {
continue;
} // else find the next value that's appropriate for the spot
else {
i = k + 1;
if (even) { // find spot of next positive number
while (i < ar.length && ar[i] < 1) {
i++;
}
} else { // find spot of next negative
while (i < ar.length && ar[i] > 1) {
i++;
}
}
// did we go to far? If so, then we're done
if (i >= ar.length) {
break;
}
// if we haven't gone past the end...
// save that number temporarily
tempval = ar[i];
// shuffle the array values from k to i to the right
for (int z = i; z > k; z--) {
ar[z] = ar[z - 1];
}
// fill the kth spot with our saved value
ar[k] = tempval;
}
}
System.out.print("Now: " + Arrays.toString(ar));
}
}
This is just an idea:
1.Have 2 pointers say A and B. A traverses till it finds a positive number and B traverses till it finds a negative number.
2.Keep traversing them and store intermediate numbers in a temporary array. If either A or B reaches the end first, fill the temporary array with the rest of the elements that the other pointer traverses.
3.Return temporary array.
If we want to do it in place, then we have to shift the elements,And my solution's time complexity is O(n*n)
public class sortArray {
public static void main(String[] args){
int array[] = {1,-2,3,-4,-5,-6,-7,8,9,4,10,11,12};
for(int i : array){
System.out.print(i + " ");
}
System.out.println();
sortMethod(array);
for(int i : array){
System.out.print(i + " ");
}
}
public static void sortMethod(int array[]){
if(array == null){
return;
}
int positiveIndex = 0;
int negativeIndex = 0;
while(positiveIndex < array.length && negativeIndex < array.length){
positiveIndex = findNextOddPositive(array, positiveIndex);
if(positiveIndex == -1){
break;
}
negativeIndex = findNextNegatveEven(array, negativeIndex);
if(negativeIndex == -1){
break;
}
if(positiveIndex > negativeIndex){
int firstPostive = findFirstPostive(array, negativeIndex);
if(firstPostive == -1){
break;
}
shiftArray(array, negativeIndex, firstPostive);
}
else{
int firstNegative = findFirstNegative(array, positiveIndex);
if(firstNegative == -1){
break;
}
shiftArray(array, positiveIndex, firstNegative);
}
}
return ;
}
public static int findFirstPostive(int array[], int index){
while(index < array.length){
if(array[index] >= 0){
return index;
}
index++;
}
return -1;
}
public static int findFirstNegative(int array[], int index){
while(index < array.length){
if(array[index] < 0){
return index;
}
index++;
}
return -1;
}
public static void shiftArray(int array[], int start, int end){
if(start > end || array == null){
return;
}
int temp = array[end];
for(int i = end; i > start; i--){
array[i] = array[i - 1];
}
array[start] = temp;
}
public static int findNextOddPositive(int array[], int index){
if(array == null){
return -1;
}
while(index >= 0 && index < array.length){
if(array[index] < 0 || (array[index] >= 0 && (index % 2) == 0)){
index++;
}
else{
return index;
}
}
return -1;
}
public static int findNextNegatveEven(int array[], int index){
if(array == null){
return -1;
}
while(index >= 0 && index < array.length){
if(array[index] >= 0 || (array[index] < 0 && (index % 2) == 1)){
index++;
}
else{
return index;
}
}
return -1;
}
}
public class PositiveNegitive {
public PositiveNegitive() {
super();
}
public static void main(String[] args) {
PositiveNegitive positiveNegitive = new PositiveNegitive();
int[] a = {1,-2,3,-4,-5,-6,-7,8,9,4,10,11,12};
for(int x:a) {
System.out.print(x+"\t");
}
System.out.println("\n");
int i = 0, j = 0;
while (i < a.length-1) {
j = i + 1;
if (i % 2 != 0) {
if (a[i] > 0) {
while (j<a.length && a[j] > 0) {
j++;
}
if(j > a.length-1) break;
swap(a, i, j);
}
}
else {
if(a[i] < 0) {
while (j<a.length && a[j] < 0) {
j++;
}
if(j > a.length-1) break;
swap(a, i, j);
}
}
i++;
}
for(int x:a) {
System.out.print(x+"\t");
}
}
public static void swap(int[] a, int i, int j) {
int t = 0;
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
My approach to in-place ordering is to look for next out of place element of the opposite sign and swap it with the current element (which is out of place too).
ideone handle: Pamj0Y
#include<stdio.h>
int next(int a,int x[],int n,int sign)
{
int i;
for(i=a+1;i<n;i++)
{
if(x[i]*sign>0)
return i;
}
return -1;
}
void swap(int x[],int a,int b)
{
int temp=x[a];
x[a]=x[b];
x[b]=temp;
}
void ord_inplace(int x[],int n)
{
int idx,i;
for(i=0;i<n;i++)
{
if(i%2 && x[i]>0)
{idx=next(i,x,n,-1);if(idx==-1)break;swap(x,i,idx);}
else if(i%2==0 && x[i]<0)
{idx=next(i,x,n,1);if(idx==-1)break;swap(x,i,idx);}
}
}
int main()
{
int x[]={1,-2,3,-4,-5,-6,-7,8,9,4,10,11,12} ;
int i;
ord_inplace(x,13);
for(i=0;i<13;i++)
printf("%d ",x[i]);
return 0;
}
Just an Idea,Traverse the input from left to right 0th position should be a positive the next element 1st position should be negetive,the first position where this rule is violated,simply pick that element and search for the nearest appropriate alternative(up this point all the other elements would be of the same kind),replace that element with the appropriate on and shift all the other elements to the right.this way as you go along you are setting the elements in order once you reach the end you are done
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication2
{
enum ReplacementType { Skip, PositiveReplacement, NegativeReplacement };
class Program
{
static void swap(int[] arr, int currentPosition, int swapPosition )
{
// store the value that we will be replacing it with.
// 'it' refers to the value at the current position/index
int replacement = arr[swapPosition];
/*
* First iteration, e.g, swapping -5 with 8
* The loop belows covers the following elements:
* -5(current position), -6, -7, 8(swap position)
* --------------------------
* | loop |
* |----------|
* 1|-2|3|-4|-5|-6|-7|8|9|..
*
* -----------------------------
*/
for (int k = swapPosition; k > currentPosition; k--)
{
// starting at '8', move back and switch values like so:
// 1. -5 -6 -7 -7
// 2. -5 -6 -6 -7
// 3. -5 -5 -6 -7
arr[k] = arr[k - 1];
}
// finally
// 8 -5 -6 -7
arr[currentPosition] = replacement;
}
static ReplacementType NeedsReplacing(int[] arr, int position)
{
// value is positive but position is odd
if (arr[position] > 0 && (position % 2 != 0))
return ReplacementType.NegativeReplacement;
// value is negative but position even
if (arr[position] < 0 && (position % 2 == 0))
return ReplacementType.PositiveReplacement;
return ReplacementType.Skip;
}
static void Main(string[] args)
{
int[] input = new int[] { 1, -2, 3, -4, -5, -6, -7, 8, 9, 4, 10, 11, 12 };
for (int i = 0; i < input.Length; i++)
{
if (NeedsReplacing(input, i) != ReplacementType.Skip)
{
for (int j = (i + 1); j < input.Length; j++)
{
// even position, so it must be replaced with the next +ve number
if (NeedsReplacing(input, i) == ReplacementType.PositiveReplacement)
{
// find the first positive number
if (input[j] >= 0)
{
swap(input, i, j);
break;
}
}
if( NeedsReplacing(input, i) == ReplacementType.NegativeReplacement)
{
// find the first negative number
if (input[j] < 0)
{
swap(input, i, j);
break;
}
}
}
}
}
// Show output array to console
for (int i = 0; i < input.Length; i++)
{
Console.Write("{0} ", input[i]);
}
Console.ReadLine();
}
}
}
Is this a good solution for the question?
#include <iostream>
using namespace std;
int main()
{
int a[]={3,-2,-1,-24,4,5,-66,49,50},i,pos,temp,flag=0;
for(i=0;i<8;i++)
if((i%2==0 && a[i]>0)||(i%2!=0 && a[i]<0)) {
flag=!flag;
if(flag) pos=i;
else {
temp=a[pos];
a[pos]=a[i];
a[i]=temp;
}
}
for(i=0;i<8;i++)
cout<<a[i]<<endl;
return 0;
}
Is this a good solution?
#include <iostream>
using namespace std;
int main()
{
int a[]={3,-2,-1,-24,4,5,-66,49,50},i,pos,temp,flag=0;
for(i=0;i<8;i++)
if((i%2==0 && a[i]>0)||(i%2!=0 && a[i]<0)) {
flag=!flag;
if(flag) pos=i;
else {
temp=a[pos];
a[pos]=a[i];
a[i]=temp;
}
}
for(i=0;i<8;i++)
cout<<a[i]<<endl;
return 0;
}
public class ArrangeArray {
static int[] arr = { 1, -2, -3, -4, -5, -6, -8, -9, 4 };
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
for (int i = 0; i < arr.length; i++) {
if (i % 2 == 0) {
if (arr[i] < 0)
swap(i, nextIdx(i));
}
if (i % 2 != 0) {
if (arr[i] > 0)
swap(i, nextIdx(i));
}
}
for (int j = 0; j < arr.length; j++)
System.out.print(arr[j]);
}
private static void swap(int src, int dest) {
int temp = 0;
temp = arr[dest];
arr[dest] = arr[src];
arr[src] = temp;
}
private static int nextIdx(int startIdx) {
if (startIdx % 2 == 0) {
for (int j = startIdx; j < arr.length; j++) {
if (arr[j] > 0)
return j;
}
}
if (startIdx % 2 != 0) {
for (int j = startIdx; j < arr.length; j++) {
if (arr[j] < 0)
return j;
}
}
return startIdx;
}
}
static void Main(string[] args)
{
int[] sampleArray = { 1, -2, 3, -4, -5, -6, -7, 8, 9, 4, 10, 11, 12 };
int temp;
for (int i = 0; i < sampleArray.Length; i++)
{
if (i % 2 == 0)
{
if (sampleArray[i] < 0)
{
temp = sampleArray[i];
for (int j = i; j < sampleArray.Length; j++)
{
if (sampleArray[j] > 0)
{
sampleArray[i] = sampleArray[j];
sampleArray[j] = temp;
break;
}
}
}
}
}
foreach (var i in sampleArray)
{
Console.Write(i + ",");
}
Console.ReadLine();
}
public static void Arrange(int[] arr)
{
int pos = 0;
int neg = 0;
for (int i = 0; i < arr.length; i ++) {
if (i%2 == 0) {
for (pos = max(pos, i); i < arr.length; i ++) {
if (arr[pos] > 0) break;
}
if (pos >= arr.length) break; // all remaining numbers are negative, exit
if (pos != i) {
swap(arr, pos, i);
pos ++;
}
} else {
for (neg = max (neg, i); i < arr.length; i ++) {
if (arr[neg] < 0) break;
}
if (neg >= arr.length) break;
if (neg != i) {
swap (arr, neg, i);
neg ++;
}
}
}
}
correction...
public static void Arrange(int[] arr)
{
int pos = 0;
int neg = 0;
for (int i = 0; i < arr.length; i ++) {
if (i%2 == 0) {
for (pos = max(pos, i); pos < arr.length; pos ++) {
if (arr[pos] > 0) break;
}
if (pos >= arr.length) break; // all remaining numbers are negative, exit
if (pos != i) {
swap(arr, pos, i);
pos ++;
}
} else {
for (neg = max (neg, i); neg < arr.length; neg ++) {
if (arr[neg] < 0) break;
}
if (neg >= arr.length) break;
if (neg != i) {
swap (arr, neg, i);
neg ++;
}
}
}
}
#include<stdio.h>
int main()
{
int a[]={1,-2,3,-4,-5,-6,-7,8,9,4,10,11,12};
//pi is positive integers iterator, ni is negative integers iterator
int i=0,ni=0,pi=0,temp,prevpi,prevni,length=(sizeof(a)/sizeof(a[0]));
while(i< (sizeof(a)/sizeof(a[0])))
{
if(i%2 && a[i]>=0)
{
ni=i+1;
while(a[ni]>=0 && ni <length)
{
ni++;
}
if(ni==length)
break;
temp=a[i];
a[i]=a[ni];
pi=ni-1;prevpi=ni;
while(pi!=i){
if(a[pi]>=0)
{
a[prevpi]=a[pi];
prevpi=pi;
}
pi--;
}
a[pi+1]=temp;
}
if(!(i%2) && a[i]<0)
{
pi=i+1;
while(a[pi]<0 && pi < length)
{
pi++;
}
if(pi==length)
break;
temp=a[i];
a[i]=a[pi];
ni=pi-1;prevni=pi;
while(ni!=i){
if(a[ni]<0)
{
a[prevni] =a[ni];
prevni=ni;
}
ni--;
}
a[ni+1]=temp;
}
i++;
}
for(i=0;i<sizeof(a)/sizeof(a[0]);i++)
printf(" %d ",a[i]);
return 0;
}
package Maxwindow;
public class AlternatePosNegVal {
public static void main(String[] args)
{
Integer a[] = {1,-2,3,-4,-5,-6,-7,8,9,4,10,11,12};
int temp = 0;
int i,j=0;
for(i=0;i<a.length;i++)
{
if(i%2 == 0){
if(a[i]>=0);
else{
j=i;
while((a[j]<0) && j<a.length)
{
j++;
}
temp = a[i];
a[i]=a[j];
a[j]=temp;
j++;
}
}}
for(int k=0;k<a.length;k++)
System.out.println(a[k]);
}
public AlternatePosNegVal() {
super();
}
}
package Maxwindow;
public class AlternatePosNegVal {
public static void main(String[] args)
{
Integer a[] = {1,-2,3,-4,-5,-6,-7,8,9,4,10,11,12};
int temp = 0;
int i,j=0;
for(i=0;i<a.length;i++)
{
if(i%2 == 0){
if(a[i]>=0);
else{
j=i;
while((a[j]<0) && j<a.length)
{
j++;
}
temp = a[i];
a[i]=a[j];
a[j]=temp;
j++;
}
}}
for(int k=0;k<a.length;k++)
System.out.println(a[k]);
}
public AlternatePosNegVal() {
super();
}
}
Assuming 'a' is the array and 'n' is the size of 'a', we can get result in the following manner :
1. Start from index 0.
2. Check if for (index % 2 == 0), then a[index] > 0; if yes, then continue.
3. Check if for (index % 2 != 0), then a[index] < 0; if yes, then continue.
4. if for (index % 2 == 0) a[index] < 0; then add a[index] to QUEUE_NEG and continue in search of a +ve number (say, found_pos) and mark found index (found_index - position of found_pos) as EMPTY.
5. When found, do a[index] = found_pos.
6. If for (index % 2 != 0) a[index] > 0; then add a[index] to QUEUE_POS and continue in search of a -ve number (say, found_neg) and mark found index (found_index - position of found_neg) as EMPTY.
7. When found, do a[index] = found_neg.
8. If for (index % 2 == 0), a[index] = EMPTY, then do a[index] = QUEUE_POS.pop().
9. If for(index % 2 != 0), a[index] = EMPTY, then do a[index] = QUEUE_NEG.pop().
Advantage over the approach to having 2 QUEUEs from the start is that both QUEUE_POS and QUEUE_NEG may not store all the elements in average case, although in worst case it would be the same as the approach of having 2 QUEUEs from the start with positive and negative numbers separated out by scanning the array although with the approach described here, there would be no scanning and QUEUE will grow dynamically.
None of the posted solutions appear to solve the problem with all of the following constraints:
O(n) time
O(1) space
maintain original order of positive and negative sequences
And after studying the problem, I do not think it is possible to solve it and satisfy all these constraints. In any case, here are solutions where one of the constraints is relaxed.
public class PositiveNegativeSort {
// Use an auxiliary array. Maintain 2 pointers into input array. Copy elements from input array to aux array.
// Maintains original order of positive and negative sequences.
// O(n) time, O(n) space
int sort1(int a[]) {
int b[] = new int[a.length];
int pos = 0;
int neg = 0;
int iterations = 0;
for (int i = 0; i < a.length; ++i) {
++iterations;
if (i % 2 == 0) {
for (; pos < a.length && a[pos] < 0; ++pos, ++iterations);
if (pos < a.length) {
b[i] = a[pos++];
}
else {
b[i] = a[neg++];
}
}
else {
for (; neg < a.length && a[neg] >= 0; ++neg, ++iterations);
if (neg < a.length) {
b[i] = a[neg++];
}
else {
b[i] = a[pos++];
}
}
}
System.arraycopy(b, 0, a, 0, a.length);
iterations += a.length;
return iterations;
}
// Iterate over array and swap invalid elements with valid elements.
// Does NOT maintain original order of positive and negative sequences.
// O(n) time, O(1) space.
int sort2(int a[]) {
int iterations = 0;
int nextPositive = 0;
int nextNegative = 0;
for (int i = 0; i < a.length; ++i) {
++iterations;
for ( ; nextPositive < a.length && (nextPositive <= i || a[nextPositive] < 0); ++nextPositive, ++iterations);
for ( ; nextNegative < a.length && (nextNegative <= i || a[nextNegative] >= 0); ++nextNegative, ++iterations);
if (a[i] >= 0) {
if (i % 2 != 0 && nextNegative < a.length) {
swap(a, i, nextNegative);
}
}
else {
if (i % 2 == 0 && nextPositive < a.length) {
swap(a, i, nextPositive);
}
}
}
return iterations;
}
// Iterate over array and select correct element for each position. Shift subsequent elements right to maintain original order.
// Maintains original order of positive and negative sequences.
// O(n^2) time, O(1) space.
int sort3(int a[]) {
int iterations = 0;
int nextPositive = 0;
int nextNegative = 0;
for (int i = 0; i < a.length; ++i) {
++iterations;
for ( ; nextPositive < a.length && (nextPositive <= i || a[nextPositive] < 0); ++nextPositive, ++iterations);
for ( ; nextNegative < a.length && (nextNegative <= i || a[nextNegative] >= 0); ++nextNegative, ++iterations);
if (a[i] >= 0) {
if (i % 2 != 0 && nextNegative < a.length) {
a[i] = shift(a, i, nextNegative);
iterations += nextNegative - i;
}
}
else {
if (i % 2 == 0 && nextPositive < a.length) {
a[i] = shift(a, i, nextPositive);
iterations += nextPositive - i;
}
}
}
return iterations;
}
// O(1)
void swap(int a[], int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
// O(j-i)
int shift(int a[], int i, int j) {
int next = a[i];
for (; i < j; ++i) {
int tmp = a[i+1];
a[i+1] = next;
next = tmp;
}
return next;
}
@Test
public void testSort11() {
int[] a = {1, -2, 3, -4, -5, -6, -7, 8, 9, 4, 10, 11, 12};
int iterations = sort1(a);
System.out.println("sort11: iterations=" + iterations);
Assert.assertArrayEquals(new int[] {1,-2,3,-4,8,-5,9,-6,4,-7,10,11,12}, a);
}
@Test
public void testSort12() {
int[] a = {-1, -2, -3, -4, -5, -6, 1, -7 ,2, 3, 4, 5, 6, 7};
int iterations = sort1(a);
System.out.println("sort12: iterations=" + iterations);
Assert.assertArrayEquals(new int[] {1,-1,2,-2,3,-3,4,-4,5,-5,6,-6,7,-7}, a);
}
@Test
public void test13() {
int a[] = new int[64];
for (int i = 0; i < a.length / 2; ++i) {
a[i] = -i - 1;
}
for (int i = a.length / 2; i < a.length; ++i) {
a[i] = i - a.length / 2 + 1;
}
int iterations = sort1(a);
System.out.println("sort13: iterations=" + iterations);
check(a);
}
@Test
public void testSort21() {
int[] a = {1, -2, 3, -4, -5, -6, -7, 8, 9, 4, 10, 11, 12};
int iterations = sort2(a);
System.out.println("sort21: iterations=" + iterations);
Assert.assertArrayEquals(new int[] {1, -2, 3, -4, 8, -6, 9, -5, 4, -7, 10, 11, 12}, a);
}
@Test
public void testSort22() {
int[] a = {-1, -2, -3, -4, -5, -6, 1, -7 ,2, 3, 4, 5, 6, 7};
int iterations = sort2(a);
System.out.println("sort22: iterations=" + iterations);
Assert.assertArrayEquals(new int[] {1, -2, 2, -4, 3, -6, 4, -7, 5, -5, 6, -3, 7, -1}, a);
}
@Test
public void testSort23() {
int[] a = {-1, 1, -2, 2, -3, 3, -4, 4 ,-5, 5, -6, 6, -7, 7};
int iterations = sort2(a);
System.out.println("sort24: iterations=" + iterations);
Assert.assertArrayEquals(new int[] {1, -1, 2, -2, 3, -3, 4, -4, 5, -5, 6, -6, 7, -7}, a);
}
@Test
public void test24() {
int a[] = new int[64];
for (int i = 0; i < a.length / 2; ++i) {
a[i] = -i - 1;
}
for (int i = a.length / 2; i < a.length; ++i) {
a[i] = i - a.length / 2 + 1;
}
int iterations = sort2(a);
System.out.println("sort23: iterations=" + iterations);
check(a);
}
@Test
public void testSort31() {
int[] a = {1, -2, 3, -4, -5, -6, -7, 8, 9, 4, 10, 11, 12};
int iterations = sort3(a);
System.out.println("sort31: iterations=" + iterations);
Assert.assertArrayEquals(new int[] {1,-2,3,-4,8,-5,9,-6,4,-7,10,11,12}, a);
}
@Test
public void testSort32() {
int[] a = {-1, -2, -3, -4, -5, -6, 1, -7 ,2, 3, 4, 5, 6, 7};
int iterations = sort3(a);
System.out.println("sort32: iterations=" + iterations);
Assert.assertArrayEquals(new int[] {1,-1,2,-2,3,-3,4,-4,5,-5,6,-6,7,-7}, a);
}
@Test
public void test33() {
int a[] = new int[64];
for (int i = 0; i < a.length / 2; ++i) {
a[i] = -i - 1;
}
for (int i = a.length / 2; i < a.length; ++i) {
a[i] = i - a.length / 2 + 1;
}
int iterations = sort3(a);
System.out.println("sort33: iterations=" + iterations);
check(a);
}
void check(int a[]) {
for (int i = 0; i < a.length; ++i) {
Assert.assertTrue((i % 2 == 0 && a[i] >= 0) || (i % 2 !=0 && a[i] < 0));
}
}
}
python
#Given an array, with positive and negative integers, arrange it in such a way that, positive numbers occupy even positions and negative numbers occupy odd position. All the remaining extra positive or negative integers should be stored at the end of the array. Remember, the elements of the array should remain in the same order.
#EG: Input array {1,-2,3,-4,-5,-6,-7,8,9,4,10,11,12}
#output array {1,-2,3,-4,8,-5,9,-6,4,-7,10,11,12}
def pos_neg_sort(inarray):
retlist = []
poscount = 0
negcount = 1
for x in range(len(inarray)*2):
retlist.append(0)
for val in inarray:
if val > 0:
retlist[poscount]=val
poscount+=2
if val < 0:
retlist[negcount]=val
negcount+=2
retlist2=[]
for val in retlist:
if val != 0:
retlist2.append(val)
return retlist2
inarray = [1,-2,3,-4,-5,-6,-7,8,9,4,10,11,12]
outarray = pos_neg_sort(inarray)
if outarray == [1,-2,3,-4,8,-5,9,-6,4,-7,10,11,12]:
print "Success!"
else:
print "Failure!"
print outarray
Use insertion sort approach to preserve the order. Traverse the array ,check the positions and signs.say i. Pickup the index (j) and value of the suitable number a[j] to be inserted and shift the successive elements i+1 towards right till j.
void rearrange(int *arr, int count)
{
for (int i = 0; i < count - 1; i++)
{
bool fFound = false;
for (int j = i; j < count; j ++)
{
if ((arr[j] > 0) == (i%2==0))
{
if (i != j) swap(arr, i, j);
fFound = true;
}
}
if (!fFound) break;
}
}
Take two queues
- pirate August 12, 20131) In first scan put all +ve's in one queue and -ve's in other queue.
2) In second scan Dequeue alternatively.
3) If any queue is empty Dequeue other queue until empty.
Time complexity O(n)