Oracle Labs247 Interview Question Quality Assurance Engineers Site Reliability Engineers
0of 0 votes1.sort array {0,1,1,0,1,0,1,0,0,1,1,1,0} of binary numbers in O(n) time complexity using property of binary numbers.(no counting here)
Team: GGN
Country: India
Interview Type: In-Person
/* 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;
}
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.
what's the logic here ? did not understand what you are storing at some location...Thanks.
Why don't we count all the number of 1's or 0's then create a seperate array with these datas.
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 .
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'.
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
#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);
}
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;
}
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;
}
}
}
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));
}
}}
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));
}
can you explain me this XOR thing ? what actually is achieved by using it,and how actually it is better than swapping.
Thank you!
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
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.
Ok yeah got it thanks.So,is bit wise XOR faster than usual swapping we generally perform.
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;
}
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.
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
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);
}
}
}
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;
}
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]);
}
}
}
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]+" ");
}
}
//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;
}
Sum all the N elements, then overwrite the array :)
- Anurag Kumar on July 25, 2012 Edit | Flag Replyint 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; }