## Accolite software Interview Question

• 0

Country: United States
Interview Type: In-Person

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

``````function sort01(array) {
if (!array || array.length < 2) {
return;
}

var firstNonZeroIndex = null;
var index = 0;

while(index < array.length) {
if (array[index] === 1 && firstNonZeroIndex === null) {
firstNonZeroIndex = index;
}

if (array[index] === 0 && firstNonZeroIndex !== null) {
[array[index], array[firstNonZeroIndex]] = [array[firstNonZeroIndex], array[index]];
firstNonZeroIndex++;
}

index++;
}
}

var a = [1,0,0,0,1,1,1,0,0,0,0,1,1,1,0,0,0];
sort01(a);
console.log(a);``````

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

Use partition function of Quicksort, easy-peasy.

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

``````public static void main(String[] args) {
int arr[] = { 0, 1, 1, 1, 1, 0, 0, 1 };
for (int i = 0, j = arr.length - 1; i < j; i++, j--) {
if (arr[i] > arr[j]) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
//print the arr
for (int i : arr) {
System.out.println(i);
}
}``````

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

The requirements for
1. O(n)
2. In place sort
3. preserve order (stable)
are a stingy combination.

All common sorting algorithms takes O(nlogn):
-Quicksort can sort in-place, but its partitioning function is not stable (does preserve element order), and it's not O(n)
-Mergesort can sort in-place, and preserve order (stable), but is not O(n)
-Bubble sort sort in-place, but O(n^2)

Radix sort is possibly the only sub-O(nlogn) algorithm. It runs O(wn) where w is the length of word (in this problem where elements are either 1 or 0, w=1). It also preserves order, but does not sort in place (it creates bucket).

None of the solution offered so far satisfy the 3 requirements simultaneously. I think interviewer is looking for RadixSort, which gives O(n) and stable order preservation. But I doubt he meant in-place (otherwise, creating buckets during RadixSort cost extra space)

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

O(n) runtime. the basic concept is to keep swapping at the beginning of the array where the 0's are untill that is filled.

``````def stable_sort(array):
j_start = 0
for a in array:
if a == 0:
j_start += 1

i_start = 0
j_end = j_start

while i_start != j_start:
for i in range(i_start, j_start):
if array[i] != 0:
array[j_end], array[i] = array[i], array[j_end]
j_end += 1
else:
i_start += 1

return array``````

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

The basic concept is to move out the 1's from the area that the 0's will occupy. By always swapping into the bucket where the 0's will occupy, you can preserve the order.

here's an example of a run through the algorithm:

1a 1b 1c 1d 0a 0b 1e 1f
j_start = 2
j_end = 2
i_start = 0

i=0, j_end=2
1c 1b 1a 1d 0a 0b 1e 1f

i=1, j_end=3
1c 1d 1a 1b 0a 0b 1e 1f

i=0, j_end=4, i_start = 1
0a 1d 1a 1b 1c 0b 1e 1f

i=1, j_end=5, i_start = 2
0a 0b 1a 1b 1c 1d 1e 1f

i_start == j_start so stop.

``````def stable_sort(array):
j_start = 0
for a in array:
if a == 0:
j_start += 1

i_start = 0
j_end = j_start

while i_start != j_start:
for i in range(i_start, j_start):
if array[i] != 0:
array[j_end], array[i] = array[i], array[j_end]
j_end += 1
else:
i_start += 1

return array``````

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

What does it mean "While sorting you are not allowed to change the original ordering of same element" - do you mean sort must be stable?
So you want stable in-place partition? Sorry, but that doesn't sound like an interview question.
citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.5554

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

``````void swap(vector<int>& arr, int one_pos, int zero_pos)
{
int tmp = arr[one_pos];
arr[one_pos] = arr[zero_pos];
arr[zero] = tmp;
}

void sortInPlace(vector<int>& arr)
{
int zero_pos = arr.size()-1;
for (int i = arr.size()-1; i>=0; i--)
{
if (arr[i] == 0 && arr[zero_pos]!=0)
zero_pos = i;
else if (arr[i] == 1 && arr[zero_pos] == 0)
{
swap(arr, i, zero_pos);
zero_pos--;
}
}
}``````

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

``````If the sort starts from the end, it can keep the 0s and 1s in their original order. That means the last 1 should be at the end and the first 0 should be at the beginning. Here is the function.

void swap(vector<int>& arr, int one_pos, int zero_pos)
{
int tmp = arr[one_pos];
arr[one_pos] = arr[zero_pos];
arr[zero_pos] = tmp;
}

void sortInPlace(vector<int>& arr)
{
int zero_pos = arr.size()-1;
for (int i = arr.size()-1; i>=0; i--)
{
if (arr[i] == 0 && arr[zero_pos]!=0)
zero_pos = i;
else if (arr[i] == 1 && arr[zero_pos] == 0)
{
swap(arr, i, zero_pos);
zero_pos--;
}
}
}``````

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

``print stable_sort([1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0])``

[0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0]

next time, test your code before you post

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

Instead of using two pointers, start and end which will modify the order, use start and middle so the order is preserved

``````int[] preservedSort(int[] array)
{
if (array == null || array.length() == 0)
return array;
int start = array;
int middle = array.length() / 2 ;
while(start < array.length() && middle < array.length())
{
if (array[start] > array[middle])
{
swap(array[start], array[middle]);
start++; middle++;
}
if (array[start] == 0)	start++;
if (array[middle] == 1) middle++;
}

return array;
}``````

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

``````public static int[] SortOsAnd1sInPlaceO_n(int[] n)
{
int i=0, j=n.Length-1;
while(i < j)
{
if(n[i] > n[j])
{
int temp = n[j];
n[j] = n[i];
n[i] = temp;
i++;
j--;
}
else if(n[i] < n[j])
{
i++;
j--;
}
else
{
i++;
}
}
return n;
}``````

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

@emb and all, this question becomes a lot easier if you consider that using extra space is permitted. Why anybody would want an in-place sorting while allowing extra space is beyong me, though... but a solution that fulfills all the requirements is much easier to find that way. I say this because I think many people here implicitly assume no extra space is permitted.

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

while(start < end)
{
while(arr[start] ==0)
start++;
while(arr[end]== 1)
end++;
swap(start,end);
}

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

int arr[] = { 0, 1, 1, 1, 1, 0, 0, 1 };
int x =arr.length;
for (int i = 0; i < arr.length/2; i++) {
if(arr[i]>arr[x-1]){
int temp = arr[x-1];
arr[x-1] = arr[i];
arr[i] = temp;
}
x--;
}
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}

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

int arr[] = { 0, 1, 1, 1, 1, 0, 0, 1 };
int x =arr.length;
for (int i = 0; i < arr.length/2; i++) {
if(arr[i]>arr[x-1]){
int temp = arr[x-1];
arr[x-1] = arr[i];
arr[i] = temp;
}
x--;
}
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}

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

Can't we just count the number of zeroes as 'x' and set the initial 'x' elements as 0 and the rest as 1. It will run in O(n) time.

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.