Oracle Labs247 Interview Question
Quality Assurance Engineers Site Reliability EngineersTeam: 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.
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);
}
}
}
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
Why don't we count all the number of 1's or 0's then create a seperate array with these datas.
#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;
}
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);
}
}
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
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--;
}
}
}
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;
}
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]+" ");
}
}
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--;
}
}
}
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));
}
}
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));
}
}
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;
}
Sum all the N elements, then overwrite the array :)
- Anurag Kumar July 25, 2012