Oracle Labs247 Interview Question 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 7 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;
}

- Anurag Kumar on July 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

awesome logic :)

- Subrahmanyam on April 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

supper..:)

- ishwar on May 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Mika on September 13, 2013 | Flag
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;
}

- niraj.nijju on June 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Code zapper on June 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 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.

- Anon on July 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sujita on July 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sujita on July 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

thats gud...

- dig on July 19, 2012 | Flag
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 .

- A. on June 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 Dittakavi on June 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on June 30, 2012 | Flag
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.

- lucifer on June 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Siva Krishna on June 30, 2012 | Flag
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);
}

- ming on June 29, 2012 | Flag Reply
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 ?

- Barney on June 30, 2012 | Flag Reply
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;
}

- poxzlm on July 01, 2012 | Flag Reply
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]);


}

- codez on July 01, 2012 | Flag Reply
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;
}

}
}

- shivam on July 01, 2012 | Flag Reply
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

- niraj.nijju on July 06, 2012 | Flag Reply
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));

}
}}

- vishalgupta2008 on July 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on July 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sujita on July 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Vishal on July 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sujita on July 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Vishal on July 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sujita on July 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Pradeep on July 22, 2012 | Flag
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.

- kiruba on July 06, 2012 | Flag Reply
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

- Aashish on July 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- mk on October 02, 2013 | Flag
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);
}

}
}

- Ganesh Khakare on July 07, 2012 | Flag Reply
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)

- maheshwar on July 07, 2012 | Flag Reply
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

- ethioer on July 08, 2012 | Flag Reply
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");
}

- Anonymous on August 03, 2012 | Flag Reply
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;
    }

- Veeru on September 13, 2012 | Flag Reply
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]);
}
}
}

- raghava.javvaji on September 21, 2012 | Flag Reply
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

- ROHIT on October 09, 2012 | Flag Reply
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]+" ");
	}

}

- bumbu89 on October 10, 2012 | Flag Reply
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;
}

- Anonymous on November 03, 2012 | Flag Reply
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++;
}
}
}
}

- Anonymous on February 17, 2013 | Flag Reply
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);
		}
}

- Kanha on August 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Enter n :
6
Read n numbers
0 0 1 0 1 0

--
output

0
0
1
0
1
0

Check for above case its failing

- mk on October 02, 2013 | Flag
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

- Parthipan on February 13, 2014 | Flag Reply
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]
    }
}

- kinshuk.ram on May 07, 2014 | Flag Reply
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--;
                }
            }   
        }

- GURUNATH NAVALE on May 22, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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