## Oracle Labs247 Interview Question for Quality Assurance Engineers Site Reliability Engineers

Team: GGN
Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
7
of 9 vote

Sum all the N elements, then overwrite the array :)

``````int main() {
int arr[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1};
int N = sizeof arr / sizeof *arr; /* 18 */
int sum = 0;
int ndx;
for (ndx=0; ndx<N; ndx++) sum += arr[ndx];
for (ndx=0; ndx<N-sum; ndx++) arr[ndx] = 0;
for (ndx=N-sum; ndx<N; ndx++) arr[ndx] = 1;
}``````

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

awesome logic :)

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

supper..:)

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

The challenge states no counting. Isn't doing a sum on all array elements a count?

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

#include <stdio.h>
int main()
{
int a[] = {0, 1,0,1,0,1, 0, 1, 0,1, 0, 1};
int ct=0, i =0;

for (i=0; i< (sizeof(a)/sizeof(int)) ; i++)
{
if (a[i])
{
if(!a[ct])
{
a[ct]= a[i];
a[i] = 0;
}
ct++;
}
}
return 0;
}

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

``````/*  sort an array a[n] containing 0s and 1s with time complexity n and you cant use more than 1 data structure
(you cant use more than 1 array)... the interviewer gave me good 10min to write the code  */

//      Working Code  ||  TIME: O(n)  ||   Space : O(1)

#include<stdio.h>
int main()
{
int A[20],i,j,n,temp;
printf("Enter n :");
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&A[i]);
printf("\n--");
i=0;
j=n-1;
while(i<j)
{
while(A[i]==0)
i++;
while(A[j]==1)
j--;
if(i<j)
{
temp=A[i];
A[i]=A[j];
A[j]=temp;
i++; j--;
}
}// end of while
printf("\n");
for(i=0;i<n;i++)
printf("%d ",A[i]);
printf("\n");
return 0;
}``````

Comment hidden because of low score. Click to expand.
-2

Hey how is this O(N)?? this is O(N^2)

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

@Code zapper.......Two nested while loops doesn't always means n^2 complexity :)

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

start with two pointers, one pointing at the start, other at the end.

value1 value2 newvalue1 newvalue2
0 0 0 0
0 1 0 1
1 1 1 1
1 0 0 1

from the table, the newvalue1 has to be the AND operation of the two values and the newvalue2 has to be the OR operation of the two values.

increment the first pointer only if newvalue1 is 0
decrement the last pointer only if newvalue2 is 1

do this till the two pointers meet/cross each other.

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

what's the logic here ? did not understand what you are storing at some location...Thanks.

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

Bhai aapka logic kaam nhn kar rha..pata nhn and or se kya karna chahte ho ??

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

thats gud...

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

this is the code for that:

``````public class Sort {

public static void main(String[] args) {
int[] in = new int[]{1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1};
int i = 0;
int j = in.length-1;
while(i<j){
int bi = (in[i]&in[j]);
int bj = (in[i]|in[j]);
in[i]=bi;
in[j]=bj;
if(bi==0) i++;
if(bj==1) j--;
}
for(int y: in){
System.out.print(y);
}

}``````

}

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

take two variable left and right to store the 1st and last element of the array. start scanning from left to right whenever there is a 1 scan the array from right to left till the right variable is greater than left var or you find a 0.. break if left > right and swap the element at right location with element at left location keep doing until left > right .

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

How about counting the number of zeroes?. If the size of the array is 'n' and if you have 'p' zeroes, fill in the first 'p' elements with a '0' and the next n-p elements with a '1'.

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

pavan your solution is cool, even though this problem can be solved by using partition method of quick sort, but as it is a very special case where elements are only 0 or 1, hence we can just count number of 0 m and 1 n in one pass and then in another pass set first m elements to 0 and next n elements to 1. However we have to have two for loops in this case even though order will be same O(N) but partition is more efficient

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

Why don't we count all the number of 1's or 0's then create a seperate array with these datas.

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

Already given that more than one array can't be used.

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

``````#include<iostream>

using namespace std;

void swap(int *a, int *b)
{
int *tmp = a;
*a = *b;
*b = *a;
}
void arrangeOneZeroInArray(int m[], int length)
{
int high = length - 1;
int low = 0;
if(!m || 1 == length)
return;
while(low < high)
{
if(m[low] == 1 && m[high] == 0)
{
swap(m[low], m[high]);
low++;
high--;
}
while(0 == m[low])
low++;
while(1 == m[high])
high--;

}
for(int i = 0; i < length; i++)
cout<<m[i]<<" ";
}
void main()
{
int a[] = {1,0,1,0,1,1,1,0,1};
int length = sizeof(a)/sizeof(int);
arrangeOneZeroInArray(a, length);
}``````

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

Do we have to use stable sort ? or just do the sorting ?

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

2 pivots patition:

``````#include <iostream>
using namespace std;

void swap(int& x, int& y) {
if(&x == &y)
return;
x = x ^ y;
y = x ^ y;
x = x ^ y;
}

void threePartition(int* a, int n) {
int i = -1, j = n, k = 0;
while(k < j) {
if(k == 8 && j == 9) {
cout << "point" << endl;
}
if(a[k] == 0) {
i++;
swap(a[i], a[k]);
k++;
} else if (a[k] == 2){
j--;
swap(a[j], a[k]);
} else {
k++;
}
}

}

int main() {
int a[] = {1, 2, 0, 2, 1, 0, 0, 2, 2, 1, 1, 0};
int n = sizeof(a) / sizeof(a[0]);
cout << n << endl;
threePartition(a, n);
for(int i = 0; i < n; i++) {
cout << a[i] << " ";
}
cout << endl;
return 0;
}``````

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

``````int main()
{
int p,q,n=10,a[100];
for(int i=0;i<n;i++) scanf("%d",&a[i]);
p=0;
q=n-1;

while(p<q)
{
while(a[p]!=1)
{
p++;
}

while(a[q]!=0)
{
q--;
}
if(p<q)
{
a[p]=0;
a[q]=1;
}
p++;
q--;

}

for(int i=0;i<n;i++) printf("%d ",a[i]);

}``````

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

public class Zero_Ones {
int a[]={1,1,0,1,1,0,1,0,1,0};
int n=a.length;
int i;
int temp;
public static void main(String[] args) {
new Zero_Ones().go();
}

public void go(){

for(i=0;i<n; i++){
if(a[i]>0){
if(a[i]>a[i+1]){
temp=a[i+1];
a[i+1]=a[i];
a[i]=temp;
}
else{
reuse();
}
}

else{
if(a[i]<a[i+1]){
reuse();
}
}
}

for(int j=0; j<a.length;j++){
System.out.print(a[j]);
}

}

public void reuse(){
temp=a[i+1];
a[i+1]=a[n-1];
a[n-1]=temp;
if(a[i+1]==1){
n=n-1;
i=i-1;
}
else{
i=i-1;
}

}
}

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

codes-to-problem.blogspot.in/2012/07/sort-array-containing-0s-and-1s-with.html

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

Just wrote a code in eclipse. Please comment if need to improve.

{{
public static void sortArray( byte[] input )
{
for( int i = 0, j = input.length - 1; i < j ; )
{
if( input[i] == 1 )
{
if( input[j] == 0 )
{
input[i] = 0;
input[j] = 1;
i++;
}

j--;
}
else
{
i++;
}

}
System.out.println(Arrays.toString(input));

}
}}

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

Missed one thing in previous program. had to use property of binary numbers. So a small change in above code. Using bitwise XOR to swap the value

``````public static void sortArray( byte[] input )
{
for( int i = 0, j = input.length - 1; i < j ; )
{
if( input[i] == 1 )
{
if( input[j] == 0 )
{
input[i] ^= 1;
input[j] ^= 1;
i++;
}

j--;
}
else
{
i++;
}

}
System.out.println(Arrays.toString(input));
}``````

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

can you explain me this XOR thing ? what actually is achieved by using it,and how actually it is better than swapping.
Thank you!

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

If you do bitwise XOR then it is same as swapping the bit.
0 ^ 1 = 1
1 ^ 1 = 0

As question statement asked to use property of binary numbers so just changed swapping logic with XOR

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

how is this swapping here ?
input[i] ^= 1;
input[j] ^= 1;
something wrong I guess.

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

I am swapping only when input[i]=1 and input[j]=0.

``````if( input[i] == 1 )
{
if( input[j] == 0 )
{
input[i] ^= 1;
input[j] ^= 1;
i++;
}

j--;
}``````

After swapping i want that input[i] should become 0 and input[j] should become 1. hence bitwise XOR can do this. You can try this in Eclipse. I tried and it works.

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

Ok yeah got it thanks.So,is bit wise XOR faster than usual swapping we generally perform.

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

``````private static void sortBinary(int arr[]){

int leftptr=0;
int rightptr=arr.length-1;

for(int i=0; i<arr.length; i++){
boolean moved=false;
if(leftptr>=rightptr){
break;
}
if(arr[leftptr]==0){
leftptr++;
moved = true;
}
if(arr[rightptr]==1){
rightptr--;
moved = true;
}

//if both left and right pointers didn't moved, then swap it
if(!moved)
swap(arr,leftptr,rightptr);
}
}

private static void swap(int arr[],int leftptr, int rightptr){
arr[leftptr]^=1;
arr[rightptr]^=1;
}``````

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

This may look like counting and will only work if the size of the input array is lesser than the max integer size.

``````int[] a = new int[]{0,1,1,0,1,0,1,0,0,1,1,1,0};
int el = 1;
for(int i=0;i<a.length;i++){
el=el<<a[i];
}
System.out.println(Integer.toBinaryString(el-1));
//You could append 0s in front which could be computed  from the array length.``````

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

As the array contains only binary 0 & 1. Use OR & AND operators to swap[Not exactly swap].

``````void sort(int *arr,int size)
{
int l=0,or,and,h;
h=size-1;
while(l<h)
{
while(arr[l]==0)
l++;
while(arr[h]==1)
h--;
if(l<h)
{
or=arr[l]|arr[h];
and=arr[l]&arr[h];
arr[l]=and;
arr[h]=or;
l++;h--;
}
}
for(l=0;l<size;l++)
printf("%d ",arr[l]);
}``````

ideone.com/6FEU5

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

Below lines also give the same results
A[i] = A[i]^A[j];
A[j] = A[i]^A[j];
A[i] = A[i]^A[j];

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

public class BinaryArray {
public static void main(String[] args) {
int[] array = {0,1,0,1,0,1,0,1,0,1,0};
int l= 0, r= array.length-1;

while(true){
while(l< array.length && array[l] != 1){
l++;
}
while(r>=0 && array[r] != 0){
r--;
}
if(l < r){
array[l] = 0;
array[r] = 1;
}
else
break;
}

for (int i : array) {
System.out.println(i);
}

}
}

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

int main()
{
int i,j;
int a[13] ={0,1,1,0,1,0,1,0,0,1,1,1,0};
int *p,*q;
p=a;
q=a+12;
for(;p<q;)
{
if(*p!=0)
*p=0;
p++;
if(*q!=1)
*q=1;
q--;
}
for(i=0;i<13;i++)
printf("%d",a[i]);

Time complexity: o(n)

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

1. if the current value is 1, throw its index to queue
2. if you got 0 then pop the value from the queue to see the index and swap the current with the one you get from the queue

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

#include<stdio.h>
#include<string.h>
void main()
{
int a[]={0,1,1,0,1,0,1,0,0,1,1,1,0};
int i,n,j;
j=0;
n=13;
for(i=0;i<n;i++)
{
if((a[i] == 0))
a[j++]=a[i];
}
for(i=j;i<n;i++)
{
a[j++]=1;
}
printf("\n");
for(i=0;i<n;i++)
printf(" %d ",a[i]);
printf("\n");
}

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

Best optimized code:
1. travers the given array
2. If an element is 1 count ones and make it 0 at the index.
3. Do this until end of the array.
4. Then traverse from end of the array in reversed order and put 1 until number of ones.count.

``````public void sortArray(int[] arr)
{
int countOnes =0;
for(int i=0;i<arr.length;i++)
{
if(arr[i] == 1)
{
countOnes++;
arr[i]=0;
}
}

for(int i=arr.length-1;i>= countOnes; i--)
arr[i] = 1;
}``````

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

public class SortBinaryArray
{
//Imagine 0 - false , 1 - true
public static void main(String args[])
{
boolean[] bool = new boolean[]{false,true,true,false,true,false,true,false,false,true,true,true,false};
int k =0;
int j =1;
for(int i=0;i<bool.length;i++)
{
if(!bool[i])
{
bool[k++] = false;
}
else
{
int index = bool.length-j++;
if(index > k)
{
bool[index] = true;
}
}
}
for(int i=0;i<bool.length;i++)
{
System.out.println(bool[i]);
}
}
}

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

if we take 2 counter 1 for zero and one for 1 ...this can be done in one itration nw fill the array by zero upto zero counter -1 nd then remaing by one.....how it? with o(n) complexity

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

``````public class Sort
{

/**
* @param args
*/
public static void main(String[] args)
{
// TODO Auto-generated method stub
int[] arr = {0,1,0,0,0,1,0,0,1,1};
// arr={0,1,0,0,0,1,0,0,1,1};
int len=arr.length;
int i,j=0;
i=0;
j=len-1;
int temp;
while(i<=j)
{
if(arr[i]==0 && arr[j]==1)
{
i++;
j--;
}
else if(arr[i]==0 && arr[j]==0)
{
i++;
}
else if(arr[i]==1 && arr[j]==0)
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
i++;
j--;
}
else
{
j--;
}
}

for(i=0;i<arr.length;i++)
System.out.println(arr[i]+" ");
}

}``````

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

//sort an array of 0s and 1s in O(n)
#include<stdio.h>

int main() {
int a[10] = {1, 0, 1, 0, 0, 0, 1, 1, 1, 0};
int p = -1, q;
for(q = 0; q < 10; q++) {
if(p > -1 && a[q] == 0) {
a[q] = a[p] ^ a[q];
a[p] = a[p] ^ a[q];
p++;
} else if(p == -1 && a[q] == 1) {
p = q;
}
}
for(q = 0; q < 10; q++)
printf("%d\n", a[q]);
return 0;
}

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

public static void sortBinaryArray(int[] A, int s, int e)
{
while(s < e)
{
if (A[s] > A[e])
{
swap(A, s, e);
s++;
e--;
}
else if (A[s] < A[e])
{
e--;
}
else
{
if(A[s] == 1)
{
e--;
}
else
{
s++;
}
}
}
}

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

``````public class SortBinaryNumber{
public static void main(String[] args) throws Exception
{
int[] a={1,0,1,1,0,1,0,1,0,0,1,1,1,0};
int count=0;
for(int i=0;i<a.length;i++)
{
if(a[i]==0)
{
a[count++]=0;
a[i]=1;
}
}
for(int aa: a)
System.out.print(aa);
}
}``````

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

Enter n :
6
0 0 1 0 1 0

--
output

0
0
1
0
1
0

Check for above case its failing

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

public class Sort{

public static void main(String[] args){
int a[]={0,1,1,0,1,0,1,0,0,1,1,1,0};
sort(a);
for(int i : a){
System.out.print(i+" ");
}

}

public static void sort(int[] arr){

int d = arr.length-1;
int s = 0;

while(true){
while(d>=0){
if(arr[d]==0) break;
d--;
}
while(s<=arr.length-1){
if(arr[s]==1) break;
s++;
}

if(d<s) break;
swap(arr,s,d);

}

}

public static void swap(int[] arr,int leftptr , int rightptr){
arr[leftptr]^=1;
arr[rightptr]^=1;
}

}
less than O(N) complexity

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

Here is the partition logic as pointed by others as well(from k2code.blogspot.in/2010/04/sorting-binary-array.html):

``````low = 0;
high = arr.length - 1;

while (low < high) {
while (arr[low] == 0) {
low ++;
}
while (arr[high] == 1) {
high --;
}
if (low < low ) {
swap arr[low], arr[high]
}
}``````

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

I have used C#.net to solve the problem.

``````public static void Sort01( ref int[] arr)
{
int Left = 0, Right = arr.GetLength(0)-1;

while(Left<Right)
{
if(arr[Left]==0)
Left++;
else if(arr[Right]==1)
Right--;
else
{
arr[Left]=arr[Left]+arr[Right];
arr[Right] = arr[Left] - arr[Right];
arr[Left] = arr[Left] - arr[Right];
Left++;
Right--;
}
}
}``````

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

This is not Exactly Sorting But Arranging All 1s and 0s accordingly, No Extra Space, Can be done in a Linear Time.

``````#include <stdio.h>
int main()
{
int a[] = {0, 1,0,1,0,1, 0, 1, 0,1, 0, 1};
int ct=0, i =0;

for (i=0;i< (sizeof(a)/sizeof(int)); i++)
{
if (a[i])
{
if(!a[ct])
{
a[ct]= a[i];
a[i] = 0;
}
ct++;
}
}
return 0;
}``````

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

Please tell me if this solution is ok or not?

``````public void sortArray(int arr[])
{

int p1 = 0 ;
int p2 = 0;
while(arr[p2] !=1)
p2++;
for( ;p1<arr.length;p1++)
{
if( arr[p1] ==0 &&  p1>p2)
{
arr[p1] = 1;
arr[p2]=0;
p2++;
}
}
}``````

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

``````public static void sortBinary() {
int a[]={0,1,1,0,1,0,1,0,0,1,1,1,0};
int temp,i=0,j=0;

for (j = 0; j < a.length; j++) {
if(a[i]==1 && a[j]==0) //10
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
i++;
}
else if(a[i]==0)  //00 01
{
i++;
}

}

for (int j2 = 0; j2 < a.length; j2++) {
System.out.print(a[j2]+" ");
}``````

}

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

public static void sortBinary(int[] arr){
int i=0, j = arr.length -1;
while(i <= j){
if( (arr[i]==0) && (arr[j] ==1)){
i++; j--;
}
else if( (arr[i]==1) && (arr[j]==0)){
arr[i]=0;
arr[j]=1;
i++;j--;
}
else if((arr[i]==0) && (arr[j]==0)){
i++;
}
else if((arr[i]==1) && (arr[j]==1)){
j--;
}
}
}

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

``````import java.*;
import java.util.*;

class testQ {
public static void main(String args[]) throws Exception{
int[] arr = { 1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1};
String str = Arrays.toString(arr);
int k = str.length() - str.replace("0","").length();
for( int i = 0;i<arr.length;i++){
arr[i] = ((i>=k) ? 1 : 0);
}
System.out.println(Arrays.toString(arr));
}
}``````

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

``````import java.*;
import java.util.*;

class testQ {
public static void main(String args[]) throws Exception{
int[] arr = { 1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1};
String str = Arrays.toString(arr);
int k = str.length() - str.replace("0","").length();
for( int i = 0;i<arr.length;i++){
arr[i] = ((i>=k) ? 1 : 0);
}
System.out.println(Arrays.toString(arr));
}
}``````

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

Simple soln. O(n)

``````public static void main(String[] args){
int[] arr = {0,1,1,0,1,0,1,0,0,1,1,1,0};
sort(arr);
for(int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
}

public static void sort(int[] arr){

int i = 0;
int j = arr.length-1;

while(i <= j){

while(arr[i] == 0)
i++;

while(arr[j] == 1)
j--;

if(i < j){
swap(arr, i, j);
i++;
j--;
}
}
}

public static void swap(int[] arr, int i, int j){
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}``````

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.