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;

		}
	}

- Anonymous October 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Rahul Sharma October 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Rahul Sharma October 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous October 15, 2013 | Flag
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++;
	}
}

- wwwwwwking October 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Rahul Sharma October 15, 2013 | Flag
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()) {
                        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));
     } 
 };

- Arnab Guin October 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

no extra space .

- Rahul Sharma October 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

is it in place

- mahanta.tapas October 15, 2013 | Flag
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;
}

- mahanta.tapas October 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- xyz October 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)?

- Anonymous October 17, 2013 | Flag
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;
}
}

}

- Girvar October 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your code does not preserve order of elements. For example, when you start with an array:
-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.

- luc October 16, 2013 | Flag
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)
{
// 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);
}

- Anonymous October 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- -Rishabh Agarwal October 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is not "in place"

- laperla October 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- lidia November 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- lidiam November 21, 2013 | Flag Reply
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;

- sayak January 15, 2014 | Flag Reply
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;

- saha January 15, 2014 | Flag Reply
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]);
}
}
}


}

- Avinash kumar singh January 20, 2014 | Flag Reply
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;
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;
}

- nobody June 10, 2014 | Flag Reply
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

- laperla October 15, 2013 | Flag Reply
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?

- Murali Mohan October 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- laperla October 16, 2013 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More