## Interview Question

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
5
of 5 vote

1.get the length of the string
2.count the number of 0 or 1,
3. then generate a new string
O(n)

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

I a modify merge sort is better is n log n, more efficiency.

Comment hidden because of low score. Click to expand.
4
of 4 vote

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

}

Comment hidden because of low score. Click to expand.
0

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

}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

}

Comment hidden because of low score. Click to expand.
0

What about *pstart = 0 && *pend == 0 case? I think your code skips that case.

Comment hidden because of low score. Click to expand.
0

See my complete implementation at:

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

Void convert(char number[])
{
Int i,s=0,n,m;
n=strlen(number);
for(i=0 ;i<n ;i++)
S=s+numner[i]-’0’;
m=n-1-s;
for(j=0 ; j<m ; j++)
if(j<i)
number[j]=0;
else
number[j]=1;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Void convert(char number[])
{
Int i,s=0,n,m;
n=strlen(number);
for(i=0 ;i<n ;i++)
S=s+numner[i]-’0’;
m=n-1-s;
for(j=0 ; j<m ; j++)
if(j<i)
number[j]=0;
else
number[j]=1;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a sorting algorithm such a Quick Sort and sort the string. Time complexity O(nlgn), with n being the length of the string.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

All u need to do is take even char and convert to integer and push it to a multimap. Ull have a started map like u needed

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

It's an interesting approach, but completely misses the point of "as efficiently as possible."

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

In java.

``````import java.io.*;
class careercup
{
public static void main(String args[])throws IOException
{
String a="";
String b="";
System.out.println("Enter the string");
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);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] cleanInput (int[] input) {
int end=input.length-1;
for(int i=0;i<=end;i++) {
if(input[i]==1) {
if(input[end]==0) {
input[i]=0;
input[end]=1;
end--;
} else {
end--;
i--;
}
}
}
for(int i=0;i<input.length;i++) {
System.out.print(input[i]);
}
return input;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Name:

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

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### 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.

### 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.

### 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.