Interview Question
Country: India
Interview Type: Phone Interview
Implementation in C#, in place, O(n)
void Convert(char[] input)
{
if (input == null)
return;
int zeroCount = 0;
int oneCount = 0;
for (int i = 0; i < input.Length; i++)
{
if (input[i] == '0')
{
zeroCount++;
}
else if (input[i] == '1')
{
oneCount++;
}
else
{
throw new ApplicationException("invalid string format");
}
}
for (int i = 0; i < input.Length; i++)
{
if (zeroCount != 0)
{
input[i] = '0';
zeroCount--;
}
else if (oneCount != 0)
{
input[i] = '1';
oneCount--;
}
}
Console.WriteLine(new string(input));
}
Just use a single traversal, which is even more effective than element counting followed by generating a new sequence:
char *pstart, *pend;
while (pstart < pend){
while (*pstart == '0')
++pstart;
while (*pend == '1')
--pend;
char tmp = *pstart;
*pstart = *pend;
*pend = tmp;
++pstart;
--pend;
}
we can optimize it to
char *pstart, *pend;
while (pstart < pend)
{
// if both pointers pointing to expected value then increment the pstart and decrement the pend
if ( *pstart == '0' && *pend == '1')
{
pstart++;
pend++;
}
elseif(*pstart == 1) // if this condition satiesfy, it means we need to swap the values of pstart and pend
//and also increment & decrement the pointers respectively
{
*pstart = 0;
*pend = 1;
pstart++;
pend++;
}
else // here need to decrement the pointer of pend
{
pend++;
}
}
// correcting the mistakes
char *pstart, *pend;
while (pstart < pend)
{
// if both pointers pointing to expected value then increment the pstart and decrement the pend
if ( *pstart == '0' && *pend == '1')
{
pstart++;
pend--;
}
elseif(*pstart == 1) // if this condition satiesfy, it means we need to swap the values of pstart and pend
//and also increment & decrement the pointers respectively
{
*pstart = 0;
*pend = 1;
pstart++;
pend--;
}
else // here need to decrement the pointer of pend
{
pend--;
}
}
more concisely
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool IsZero(char c)
{
return c == '0';
}
int main()
{
string s = "01101100111010010101001100010";
if (s.empty())
return 0;
cout << s << endl;
partition(s.begin(), s.end(), IsZero);
cout << s << endl;
}
public class Convertion {
public static void main(String[] args) {
String actual= "01011011001";
StringBuffer actualZero=new StringBuffer();
StringBuffer actualOnes=new StringBuffer();
int actuallen=actual.length();
for (int i = 0; i < actuallen; i++) {
char chTemp=actual.charAt(i);
if(chTemp=='0')
{
actualZero.append(chTemp);
}else if(actual.charAt(i)=='1')
{
actualOnes.append(chTemp);
}
}
/***Appending ones with zeros*****/
actualZero.append(actualOnes);
System.out.println(actualZero);
}
}
Finally See the answer
int main()
{
char *abc = "01011011001";
vector<char> def;
int zero = 0;
while(*abc != NULL)
{
if(*abc == '0')
{def.push_back(48);
abc++;}
else
{abc++;zero++;}
}
while(zero!=0)
{def.push_back(49);zero--;}
for (unsigned n=0; n<def.size(); ++n) {
cout << def.at( n ) ;//<< " ";
//printf("%c", def.at( n ));
}
cout <<"\n";
system("pause");
return 0;
}
#include <iostream>
/// Complexity O(n). Traverse through the string exchanging subsequent 0's with first 1's.
using namespace std;
#define one '1'
#define zero '0'
StringOrder::StringOrder(string str)
{
int posFirst =0, posNext=0;
//Point to 1st '1'
posFirst = str.find(one);
if(posFirst <0)
{
cout << "no 1's in the string ";
return;
}
//point to 1st '0' beyond 1
posNext = str.find(zero,posFirst+1);
while(posNext >= 0)
{
//Exchange
str.replace(posFirst,1,1,zero);
str.replace(posNext,1,1,one);
//continue traversing to the end
posFirst = posFirst+1;
posNext = str.find(zero,posNext+1);
}
cout << "Final string : :" << str;
}
This problem is very similar to segregation of even and odd numbers from an array
#include<stdio.h>
int main()
{
int i,n,left,right,temp;
printf("Enter the no. of elements\n");
scanf("%d",&n);
int a[n];
printf("Enter the elements of an array\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\nSegregate array elements into '0' and '1'\n");
left=0;
right=n-1;
while(left<right)
{
while(a[left]==1 && left<right)
left++;
while(a[right]==0 && left<right)
right--;
if(left<right)
{
temp=a[left];
a[left++]=a[right];
a[right--]=temp;
}
}
printf("Array elements after segregation are :::\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
getch();
return 0;
}
Make a tree with left node contains 0's and right node contains 1's .Traverse the tree in-order..
#include<stdio.h>
#include<string.h>
#include <malloc.h>
struct Tree
{
char data;
struct Tree *Left;
struct Tree *Right;
};
void InorderTraverse(Tree* root)
{
Tree* Tnode = NULL;
if(root == NULL)
{
return;
}
InorderTraverse(root->Left);
printf("%c",root->data);
InorderTraverse(root->Right);
}
Tree* MakeTree(Tree *root, char byte)
{
if(root == NULL)
{
root = (Tree*)malloc(sizeof(Tree));
root->data = byte;
root->Left = NULL;
root->Right = NULL;
return root;
}
else
{
if(byte == '0')
{
root->Left = MakeTree(root->Left, byte);
}
else if(byte == '1')
{
root->Right = MakeTree(root->Right, byte);
}
return root;
}
}
int main()
{
char inputstring[100];
Tree *root = NULL;
printf("\nEnter the string\n");
scanf("%s", inputstring);
int len = strlen(inputstring);
for(int i =0;i<len;i++)
{
root = MakeTree(root, inputstring[i]);
}
InorderTraverse(root);
}
#include "stdio.h"
int main(int argc, char* argv[])
{
char str[] = "001110110100001110101010101010101010101111010101010110010101";
int i = sizeof(str)-1;
int k = i-1;
printf("\n%s",str);
for(int j=0;j<i;)
{
if(str[j] != '0')
{
if(str[j] != str[k])
{
char tempch;
tempch = str[j];
str[j] = str[k];
str[k] = tempch;
}
}
else
j++;
if(str[k] != '0')
k--;
if(j>k)
break;
}
printf("\n%s",str);
return 0;
}
In java.
import java.io.*;
class careercup
{
public static void main(String args[])throws IOException
{
String a="";
String b="";
InputStreamReader isr=new InputStreamReader(System.in);
BufferedReader in=new BufferedReader(isr);
System.out.println("Enter the string");
String s=in.readLine();
for(int i=0;i<s.length();i++)
{
if(s.charAt(i)=='0')
a+=s.charAt(i);
else
b+=s.charAt(i);
}
System.out.print(a);
System.out.println(b);
}
}
int* change(int a[], int l){
int s=0;
int end=l-1;
while(s<end){
if(a[s]==1 && a[end]==0){
a[s]=0;
a[end]=1;
s++;end--;
}
else if(a[s]==0 && a[end]==0){
s++;
}
else if(a[s]==1 && a[end]==1){
end--;
}
else{
s++;
end--;
}
}
return a;
}
int main(){
int a[]={0,1,0,1,1,0,1,1,0,0,1};
int *b=change(a,11);
for(int i=0; i<11; i++){
cout<<b[i];
}
int aa;
cin>>aa;
return 0;
}
#include <iostream>
using namespace std;
void convert_fun(char *str)
{
if(str == NULL)
return;
int n = strlen(str);
int first_one = 0;
int i = 0;
for(i=0; i<n; i++)
if(str[i] == '0') {
str[i] = '1';
str[first_one++] = '0';
}
}
int main()
{
char s[] = "0101110001";
cout << s << endl;
convert_fun(s);
cout << s << endl;
}
Wow, those are some really complex solutions,but the last one is close. Just don't need the strlen for a null terminated string.
#include <iostream>
using namespace std;
void arrange(char* pStr)
{
if (!pStr) return;
char* pOneStr = pStr;
while (*pStr)
{
if (*pStr++ == '0')
{
*pOneStr++ = '0';
}
}
while (*pOneStr)
{
*pOneStr++ = '1';
}
}
int main()
{
char* pStr = (char*)malloc(40);
strcpy(pStr, "00110000001");
cout << pStr << '\n';
arrange(pStr);
cout << pStr;
return 0;
}
{
#include<iostream>
#include<string>
using namespace std;
int main()
{
char str1="01011011001";
sort(str1.begin(),str1.end());
cout<<str1<<endl;
return 0;
}
#include<iostream>
#include<string>
using namespace std;
int main()
{
char str1="01011011001";
sort(str1.begin(),str1.end());
cout<<str1<<endl;
return 0;
}
1.get the length of the string
- Anonymous November 30, 20122.count the number of 0 or 1,
3. then generate a new string
O(n)