## Interview Question for Testing / Quality Assurances

Country: India

Comment hidden because of low score. Click to expand.
0
of 0 vote

An O(n^2) approach:

``````for(i=0;i<m;i++)
{
if(b[i]==0)
{
b[i]=flag;
break;

}
}
for(i=0;i<m;i++)
{
if(b[i]*b[i+1]>0)
{
for(j=i+1;j<m;j++)
{
if(b[j]*b[j+1]<0)
{
swap(b[j],b[j+1]);
i--;
break;
}
}
}
}

for(i=0;i<m;i++)
{
if(b[i]==flag)
{
b[i]=0;
break;

}
}``````

Comment hidden because of low score. Click to expand.
0

Sorry i need o(n) solution... how to edit this question .. m unable to see the edit option.?

Comment hidden because of low score. Click to expand.
0
of 0 vote

MISSING COSTRAINTS ARE O(N) AND NO EXTRA SPACE.

Comment hidden because of low score. Click to expand.
0

Which company? Phone interview? Are you sure the constraints were specifically stated by the interviewer?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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++;
}
}``````

Comment hidden because of low score. Click to expand.
0

Order is not maintained by your solution .... look closely ..

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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()) {
}
else {
swap(vector, i, lastodds.remove(lastodds.size() - 1).intValue());
}
}
}
if (vector[i] < 0) {
if (i % 2 == 1) {
continue;
}
else {
if (lastevens.isEmpty()) {
}
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));
}
};``````

Comment hidden because of low score. Click to expand.
0

no extra space .

Comment hidden because of low score. Click to expand.
0

is it in place

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

geeksforgeeks.org/rearrange-positive-and-negative-numbers-publish/

Comment hidden because of low score. Click to expand.
0

that link doesn't put the constraint "should preserve the order". Are you certain this constraint was asked by the interviewer? And he asked you to solve it in O(n)?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

Comment hidden because of low score. Click to expand.
0

-1 -2 -3 -4 5 6 7 -8 9 -10 -11 12
as a result you get
-1 5 -2 6 -4 7 -3 9 -8 12 -10 -11
Notice that -3 and -4 is interchanged.

Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution is O(n) and preserve the order also

public static void main (String[] args)
{
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) {
}
else {
}
}
array.clear();
System.out.println(firstpos);
if (firstpos) {
for(int i=0;i< (posarray.size() + negarray.size()); i++) {
if( i < posarray.size()) {
}
if( i < negarray.size()) {
}
}
}
else {
for(int i=0;i< (posarray.size() + negarray.size()); i++) {
if(i<negarray.size())
if(i<posarray.size())

}
}
System.out.println(array);
//System.out.println(newarray);
}

Comment hidden because of low score. Click to expand.
0

I wrote the basic stuff.. I can be further optimised to reduce memory.

Comment hidden because of low score. Click to expand.
0

It is not "in place"

Comment hidden because of low score. Click to expand.
0
of 0 vote

{{ 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;
}
}
}
} }}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

{
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]);
}
}
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

// precondition: array is sorted

public int[] arrange(int[] source)
{
int zeroOrFirstPos=0;
int shortSide=0;
int longSide=0;

// 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)
{
j++;
k++;
}

// since one side ran out, then just add the remaining numbers from the longer side to the end

}
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

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?

Comment hidden because of low score. Click to expand.
0

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``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.