Persistent Systems Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
check this for the test case
i/p : 011111
1) left = 0 , right =5
2) enters while loop
{
left ++ ; (left=1)
right--; (right=4)
arr[left] = 0; // this statement gives wrong result
}
check this if i am wrong.....
}
a small correction will work out
if(arr[left] > a[right])
{
arr[left]=0;
arr[right]=1;
}
Above Solution is wrong,
public static void sortZeroOne(int[] data) {
if (data == null || data.length==1){
return;
}
int left = 0;
int right = data.length-1;
while (left<right) {
while (data[left]==0){
left++;
}
while (data[right]==1){
right--;
}
if (left < right) {
data[left]=0;
data[right]=1;
left++;
right--;
}
}
}
Please check this code...
#include<stdio.h>
main(){
int a[] = {0,1,0,1,0,1,0,1,0,1};
int i=0,j,size=0;
size = sizeof(a)/sizeof(int);
for(j=1;j<size;j++){
if(a[i] == 1 && a[j] == 0){
a[i] = 0;
a[j] = 1;
}
if(a[i] == 1 && a[j] == 1)
continue;
i++;
}
for(j=0;j<size;j++)
printf("%d",a[j]);
printf("\n");
}
//cur initialised to starting of array
//n is the no. of elements
//initial state is set to 0 and signifies whether till now any 1 is encountered or not
//once state is changed to 1 and we get any 0 then we bubble it
cur=0;
while(cur<n)
{
if((state==0)&&(a[cur]==1))
state=1;
else if((state==1)&&(a[cur]==0))
{
for(i=cur;(i>=0)&&(a[i-1]==1);i--)
a[i-1]^=a[i]^=a[i-1]=a[i-1]^a[i]; //swapping the elements
}
cur++;
}
// Since the array consists of only 0's and 1's,
1. Initialize two pointers: j = 0, k = array.length - 1;
2. while(j < k) {
if (a[k] < a[j] { // if '0' < '1', swap, for automatic sorting
a[k] = 1;
a[j] = 0;
k--; // point to next swap candidate from right ('0')
}
// if a[k] = '1', a[k] is a swap candidate, if no swap is done for this a[k], we're done with sorting entire array
// If a[j) is 0, it's sorted already, just point to next swap candidate from left ('1')
j++;
}
}
well this can be done in O(len).
following is my implementation
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
int T;scanf("%d",&T);
while(T--) {
char arr[1000];
scanf("%s",arr);
int len=strlen(arr);int one,zero;
for(int j=0; j< len;j++) {
if(arr[j]=='0') zero++;
if(arr[j] == '1') one++;
}
int p1=0,p2=len-1,tmp;tmp=len;
while(1) {
for(int j=p1;j<len;j++) if(arr[j] == '1') {p1=j;break;} else zero--;
arr[p1]='0';zero--;
for(int j=p2;j>=0;j--) if(arr[j]=='0') {p2=j;break;} else one--;
arr[p2]='1';one--;
if(one <=0 || zero <=0) break;
}
printf("%s",arr);
}
return 0;
}
well this can be done in O(len).
following is my implementation
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
int T;scanf("%d",&T);
while(T--) {
char arr[1000];
scanf("%s",arr);
int len=strlen(arr);int one,zero;
for(int j=0; j< len;j++) {
if(arr[j]=='0') zero++;
if(arr[j] == '1') one++;
}
int p1=0,p2=len-1,tmp;tmp=len;
while(1) {
for(int j=p1;j<len;j++) if(arr[j] == '1') {p1=j;break;} else zero--;
arr[p1]='0';zero--;
for(int j=p2;j>=0;j--) if(arr[j]=='0') {p2=j;break;} else one--;
arr[p2]='1';one--;
if(one <=0 || zero <=0) break;
}
printf("%s",arr);
}
return 0;
}
#include"conio.h"
#include"iostream"
using namespace std;
int main()
{
int a[15]= {0,1,0,0,1,0,1,1,1,0,1};
int i,j=0;
int temp;
for(i=0;i<11;i++)
{
if(a[i]>a[i+1])
{
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
i=0;
}
}
for(i=0;i<11;i++)
cout<<a[i];
getch();
}
Wrong Solution... You are passing 5 0's. while printing the array after processing.. its printing 6 0's.
Check you answer before posting it, why you are wasting others time.
#include<iostream>
using namespace std;
void inplace( int *A , int size )
{
//00010111
int l = 0 ,h=size;
while( l < h )
{
if( A[l] == 0 )
l++;
if( A[h] == 1 )
h--;
if( A[l]== 1 && A[h] == 0 )
{
A[l] = A[l] ^ A[h];
A[h] = A[l] ^ A[h];
A[l] = A[l] ^ A[h];
l++;
h--;
}
}
for( int i=0; i < size ; i++ )
{
cout << A[i];
}
}
int main()
{
int Ar[] = {0,1,1,1,1,0,0,0,0,1};
inplace( Ar , 10 );
return 0;
}
int[] arr = {0,0,1,0,1,1,0,1,1,1,0,1,0,0,0,1};
System.out.println("Orginal Array : ");
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+", ");
}
for(int i=0;i<arr.length;i++){
for(int j=i;j<arr.length;j++){
if(arr[i]> arr[j]){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
System.out.println();
System.out.println("Sorted Array : ");
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+", ");
}
}
int[] arr = {0,0,1,0,1,1,0,1,1,1,0,1,0,0,0,1};
System.out.println("Orginal Array : ");
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+", ");
}
for(int i=0;i<arr.length;i++){
for(int j=i;j<arr.length;j++){
if(arr[i]> arr[j]){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
System.out.println();
System.out.println("Sorted Array : ");
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+", ");
}
}
- Dev February 20, 2012