Interview Question
Testing / Quality AssurancesCountry: India
So, we can arrange all elements in order negative left and positive right like a step of quick sort, and then rearrange the left part and right part..
void swap(int &a, int &b)
{
int tmp = a;
a = b;
b = tmp;
}
void ReArrange(int *src, int length)
{
int i = -1;
int j = 0;
for (j = 0; j < length; ++j)
{
if (src[j] < 0)
{
i++;
swap(src[i], src[j]);
}
}
j = ++i;
i = 0;
int posStart = j;
while (j < length && i < j && src[i] < 0)
{
swap(src[i], src[j]);
i += 2;
j++;
}
}
Looks like an O(n) solution. We keep two arrays to track the indices where positive and negative elements occur. The last index is removed to preserve the order.
import java.util.Arrays;
import java.lang.Integer;
import java.util.ArrayList;
import java.util.List;
class Rearrange {
static Integer [] values = { 2,9,-2,8,8,-9 };
static List<Integer> lastevens = new ArrayList<Integer> ();
static List<Integer> lastodds = new ArrayList<Integer> ();
public static void swap(Integer [] vector, int i , int j) {
int tmp = vector[i];
vector[i] = vector[j];
vector[j] = tmp;
}
public static void rearrange (Integer [] vector) {
for (int i = 0; i < vector.length; i++) {
if (vector[i] >= 0) {
if (i % 2 == 0) {
continue;
}
else {
if (lastodds.isEmpty()) {
lastevens.add(i);
}
else {
swap(vector, i, lastodds.remove(lastodds.size() - 1).intValue());
}
}
}
if (vector[i] < 0) {
if (i % 2 == 1) {
continue;
}
else {
if (lastevens.isEmpty()) {
lastodds.add(i);
}
else {
swap(vector, i, lastevens.remove(lastevens.size() - 1).intValue());
}
}
}
}
}
public static void main(String [] args) {
System.out.printf("Orig array = %s", Arrays.toString(values));
rearrange(values);
System.out.printf("Re array = %s", Arrays.toString(values));
}
};
O(n^2) approach
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>
using namespace std;
void swap(int *a,int *b)
{
int c=*a;
*a=*b;
*b=c;
}
int main()
{
cout<<" enter no of elements \n";
int num,n,save_index;
int flag;
cin>>num;
vector<int>a;
while(num--)
{
cin>>n;
a.push_back(n);
}
flag= a[0]>0 ? 1 :-1;
for(int i=1;i<a.size();i++)
{
if((flag*a[i])>0)
{
save_index=i;
for(unsigned int j=i+1;j<a.size();j++)
if((flag*a[j])<0)
{
swap(&a[save_index],&a[j]);
break;
}
}
flag= a[i]>0 ? 1:-1;
}
for(int i=0;i<a.size();i++)
cout<<a[i]<<" ";
cout<<endl;
}
for(int i =0; i < a.length-1; i++) {
if(a[i] * a[i+1] > 0) {
for (int j = i+1; j < a.length; j++) {
if(a[i] * a[j] < 0) {
temp1 = a[j];
a[j] = a[i+1] ;
a[i+1] = temp1 ;
temp = j;
break ;
}
}
} else {
if (temp > 0 && i + 1 != temp) {
temp1 = a[i+1];
a[i+1] = a[temp] ;
a[temp] = temp1 ;
temp = -1;
}
}
}
My solution is O(n) and preserve the order also
public static void main (String[] args)
{
// your code goes here
int negative = 0;
int positive = 0;
boolean firstpos = false;
ArrayList<Integer> array = new ArrayList<Integer>(Arrays.asList(-2,-9,-2,8,8,-9));
ArrayList<Integer> posarray = new ArrayList<Integer>();
ArrayList<Integer> negarray = new ArrayList<Integer>();
System.out.println(array);
for(int i=0; i<array.size(); i++) {
if(array.get(i) >= 0 && i == 0) {
System.out.println("first pos:" + array.get(i));
firstpos = true;
}
if(array.get(i) >= 0) {
posarray.add(array.get(i));
}
else {
negarray.add(array.get(i));
}
}
array.clear();
System.out.println(firstpos);
if (firstpos) {
for(int i=0;i< (posarray.size() + negarray.size()); i++) {
if( i < posarray.size()) {
array.add(posarray.get(i));
}
if( i < negarray.size()) {
array.add(negarray.get(i));
}
}
}
else {
for(int i=0;i< (posarray.size() + negarray.size()); i++) {
if(i<negarray.size())
array.add(negarray.get(i));
if(i<posarray.size())
array.add(posarray.get(i));
}
}
System.out.println(array);
//System.out.println(newarray);
}
How about this:
{{ protected void rearrangeArrayPreserveOrder(ArrayList<Integer> inputArray) {
boolean swapped = false;
if (inputArray == null || inputArray.size() < 3) {
return;
}
for (int i = 0; i < inputArray.size() - 1; i++) {
if (inputArray.get(i) > 0) {
if (inputArray.get(i + 1) > 0) {
//int x = inputArray.get(i + 1);
for (int j = i + 1; j < inputArray.size(); j++) {
if (inputArray.get(j) < 0){
int y = inputArray.get(j);
for (int k = j - 1; k > i; k--) {
inputArray.set(k + 1, inputArray.get(k));
}
inputArray.set(i + 1, y);
swapped = true;
}
if (swapped)
break;
}
swapped = false;
}
} else if (inputArray.get(i) < 0) {
if (inputArray.get(i + 1) < 0) {
//int x = inputArray.get(i + 1);
for (int j = i + 1; j < inputArray.size(); j++) {
if (inputArray.get(j) > 0) {
int y = inputArray.get(j);
for (int k = j - 1; k > i; k--) {
inputArray.set(k + 1, inputArray.get(k));
}
inputArray.set(i + 1, y);
swapped = true;
}
if (swapped)
break;
}
swapped = false;
}
}
}
} }}
How about this:
{{ protected void rearrangeArrayPreserveOrder(ArrayList<Integer> inputArray) {
boolean swapped = false;
if (inputArray == null || inputArray.size() < 3) {
return;
}
for (int i = 0; i < inputArray.size() - 1; i++) {
if (inputArray.get(i) > 0) {
if (inputArray.get(i + 1) > 0) {
for (int j = i + 1; j < inputArray.size(); j++) {
if (inputArray.get(j) < 0){
int y = inputArray.get(j);
for (int k = j - 1; k > i; k--) {
inputArray.set(k + 1, inputArray.get(k));
}
inputArray.set(i + 1, y);
swapped = true;
}
if (swapped)
break;
}
swapped = false;
}
} else if (inputArray.get(i) < 0) {
if (inputArray.get(i + 1) < 0) {
for (int j = i + 1; j < inputArray.size(); j++) {
if (inputArray.get(j) > 0) {
int y = inputArray.get(j);
for (int k = j - 1; k > i; k--) {
inputArray.set(k + 1, inputArray.get(k));
}
inputArray.set(i + 1, y);
swapped = true;
}
if (swapped)
break;
}
swapped = false;
}
}
}
} }}
The code can be refactored to remove duplicate lines.
O(n) solution and I used Perl.
=for comment
Given an array consisting of both positive and negative numbers,
rearrange the elements such that positive and negative numbers are
placed alternatively, constraints are that it should be in-place and
order of elements should not change.
=cut
use strict;
use Data::Dumper;
my (@arr, @positives, @negatives, $no, $temp, $flag, $limit);
@arr = (1,-5,2,-4,6,-19,89);
foreach $no(@arr){
if($no > 0){
push(@positives, $no);
}else{
push(@negatives,$no);
}
}
@arr = ();
# Print the positives
# print Dumper @positives;
# Print the negatives
# print Dumper @negatives;
# Find the length of positives
my $len_positive = scalar @positives;
# Find the length of negatives
my $len_negative = scalar @negatives;
# Find the smallest array
if($len_positive < $len_negative){
$limit = $len_positive;
$flag = 1;
}else{
$limit = $len_negative;
$flag = 2;
}
foreach(my $i=0; $i< $limit; $i++){
push(@arr, $positives[$i]);
push(@arr, $negatives[$i]);
}
if($len_positive != $len_negative){
if($flag == 1) {
push(@arr,@negatives[$limit..$len_negative-1]);
}else{
push(@arr,@positives[$limit..$len_positive-1]);
}
}
print Dumper @arr;
The below solution is O(n) and I used Perl.
use strict;
use Data::Dumper;
my (@arr, @positives, @negatives, $no, $temp, $flag, $limit);
@arr = (1,-5,2,-4,6,-19,89);
foreach $no(@arr){
if($no > 0){
push(@positives, $no);
}else{
push(@negatives,$no);
}
}
@arr = ();
# Print the positives
# print Dumper @positives;
# Print the negatives
# print Dumper @negatives;
# Find the length of positives
my $len_positive = scalar @positives;
# Find the length of negatives
my $len_negative = scalar @negatives;
# Find the smallest array
if($len_positive < $len_negative){
$limit = $len_positive;
$flag = 1;
}else{
$limit = $len_negative;
$flag = 2;
}
foreach(my $i=0; $i< $limit; $i++){
push(@arr, $positives[$i]);
push(@arr, $negatives[$i]);
}
if($len_positive != $len_negative){
if($flag == 1) {
push(@arr,@negatives[$limit..$len_negative-1]);
}else{
push(@arr,@positives[$limit..$len_positive-1]);
}
}
print Dumper @arr;
{
public class Rearrangingnum {
public Rearrangingnum() {
}
/**
* @param args
*/
public static void main(String[] args)throws IOException {
//Sample input array
int a[]={-10,-20,40,67,6,-3,-22,34,61};
//printing the input array
System.out.println(" \n Intial array is ");
for(int i=0;i<a.length;i++)//order O(n)
System.out.print("\t"+a[i]);
//Declaring tow arrays for getting positive numbers and negative numbers
int pos[]=new int[a.length];
int neg[]=new int[a.length];
int j=0,k=0;
String start="";
//Loop to separate positive and negative numbers
//order is O(n)+O(n)
for(int i=0;i<a.length;i++){
if(a[i]<0 )
{
neg[j]=a[i];
j++;
if(i==0)
start="neg";
}
if(a[i]>0){
pos[k]=a[i];
k++;
if(i==0)
start="pos";
}
}
//Printing the positive and negative arrays
System.out.println(" \n Positive array is ");
for(int i=0;i<pos.length;i++){
System.out.print("\t"+pos[i]);
}
System.out.println(" \n Negative array is ");
for(int i=0;i<neg.length;i++){
System.out.print("\t"+neg[i]);
}
//Merging the positive array and negative array as per given constraints
int l=0,m=0;
for(int i=0;i<a.length-3;i=i+2){
if(start.equals("pos")){
if(l<pos.length)
{a[i]=pos[l];
l++;
}
{if(m<neg.length)
a[i+1]=neg[m];
m++;
}
}
if(start.equals("neg")){
if(l<neg.length)
{a[i]=neg[l];
l++;
}
{if(m<pos.length)
a[i+1]=pos[m];
m++;
}
}
}
System.out.println(" \n Array is \n");
for(int i=0;i<a.length;i++){
System.out.print("\t"+a[i]);
}
}
}
}
// precondition: array is sorted
public int[] arrange(int[] source)
{
int zeroOrFirstPos=0;
int shortSide=0;
int longSide=0;
int[] answer = new int[source.Length];
// find the mid point to divide the positive and negative side of the array O(n)
for (int i=0; i< source.length; i++){
if (source[i]<0)
{
zeroOrFirstPos++;
}
else {
break;
}
}
// find the maximum number of iteration by determine the larger of both positive side and negative side
if (zeroOrFirstPos>Math.Round(Decimal(source.Length/2)))
{
longSide = zeroOrFirstPos;
shortSide = source.Length-zeroOrFirstPos;
} else {
shortSide = zeroOrFirstPos;
longSide = source.Length-zeroOrFirstPos;
}
// reconstructing the array with alternating positive and negative O(n)
for (int i=0, j=0, k=1; i<longSide;i++)
{
// join the two side of the array alternately until one of the side run out
if (i<shortSide)
{
answer[i+j]=source[i];
answer[i+k]=source[i+zeroOrFirstPos];
j++;
k++;
}
// since one side ran out, then just add the remaining numbers from the longer side to the end
answer[i+j];
}
return answer;
}
The trick is to _move_ the next element to its place in the array, not to swap. Such an operation is also known as splice. I wrote it in python. I'd argue, it is O(N) even though the iterator i sometimes decreases a bit. The good news is that every splice we do fixes two elements simultaneously.
def is_odd (num):
return num % 2 > 0
def is_even (num):
return not is_odd(num)
def rearrange (a):
good_i = -1
i=0
while (i<len(a)):
v = a[i]
if ( is_odd(good_i) and v<0 or is_even(good_i) and v>=0 ):
if (i != good_i+1):
a[i:i+1] = []
a[good_i+1:good_i+1] = [v]
i = good_i = good_i+1
i+=1
return a
print rearrange([1,2,3])
print rearrange([-1,-2,-3])
print rearrange([1,2,3,-1,-2,-3])
print rearrange([1,2,-1,-2,-3,3])
print rearrange([-1,-2,-3,1,2,3])
print rearrange([-1,1,-2,2,-3,3])
print rearrange([1,-1,2,-2,3,-3])
print rearrange([-1,1,-2,2,-3,3,4,5,6])
print rearrange([-1,1,-2,2,-3,3,-4,-5,-6])
Enjoy
In your _move_ trick, the shift(which is nothing but repeated swaps) is implicit. You have certainly got tricked yourself into thinking that it is O(n) and you almost got me tricked into thinking that you are correct, and therefore a -1 from me.
The mere fact that array is mapped to contiguous memory locations in hardware implies that you cannot 'splice' it. Shifting, which is accomplished either by repeated swaps or repeated copying of elements to adjacent locations, is the way to go. Just because python/perl provides you splicing operation as an easy abstraction does not mean that the complexity of a single splice operation is O(1). Did you really check the internals of your interpreter?
What a wicked answer, Erasmus, thank you very much! I stand corrected,
plead guilty as charged and offer a reimbursement. You're right that
splice is not O(1), neither in perl nor in python. To preserve the
contiguous memory locations, I offer to run an equivalent chain of swaps
whenever the iterator i hits a number that must be moved to the left.
Here is the improved rearrange function:
def rearrange (a):
good_i = -1
i=0
while (i<len(a)):
v = a[i]
if ( is_odd(good_i) and v<0 or is_even(good_i) and v>=0 ):
if (i != good_i+1):
for j in range(i,good_i+1,-1):
a[j]=a[j-1]
a[good_i+1] = v
i = good_i = good_i+1
i+=1
return a
An O(n^2) approach:
- Anonymous October 14, 2013