Microsoft Interview Question
InternsTeam: idc
Country: India
Interview Type: Written Test
class base2_convert_it_into_string_with_base4 {
public static void main(String[] args) {
String s = "101010101";
if(s.length()%2==1){
s='0'+s;
}
StringBuffer sb = new StringBuffer();
for(int i = 0;i<s.length()-1;i=i+2){
if(s.charAt(i)=='0'&& s.charAt(i+1)=='0'){
sb.append('0') ;
}
if(s.charAt(i)=='1'&& s.charAt(i+1)=='0'){
sb.append('2') ;
}
if(s.charAt(i)=='0'&& s.charAt(i+1)=='1'){
sb.append('1') ;
}
if(s.charAt(i)=='1'&& s.charAt(i+1)=='1'){
sb.append('3') ;
}
//System.out.println(sb.toString());
}
System.out.println(sb.toString());
}
}
#include<stdio.h>
#include<string.h>
main()
{
int i,l,k;
char s[20];
printf("Enter a base 2 number : ");
gets(s);
l=strlen(s);
k=i=(l%2==0)?0:1;
while(i<l)
{
if(s[i]=='0' && s[i+1]=='0')
s[k++]='0';
else if(s[i]=='0' && s[i+1]=='1')
s[k++]='1';
else if(s[i]=='1'&& s[i+1]=='0')
s[k++]='2';
else
s[k++]='3';
i+=2;
}
s[k]=NULL;
printf("The base 4 string is : ");
puts(s);
}
#include<iostream>
#include<malloc.h>
#include<string.h>
using namespace std;
main()
{
char *a= new char[20];
cout<<"Enter string \n";
cin >>a;
cout<<"\n\n";
int len =strlen(a);
int i;
if(len%2 ==0) {
for(i=0;i< len ;i+=2){
cout<<((a[i]-'0')*2+(a[i+1]-'0'));
}
}
else{
cout<<a[0];
for(i=1;i< len ;i+=2){
cout<<((a[i]-'0')*2+(a[i+1]-'0'));
}
}
cout<<"\n";
}
No this is wrong. this program gives wrong input fot input "6", it prints just 6 instead of 12. here is new version (with input limitations) :-P
#include<stdio.h>
#include<stdlib.h>
void main(){
int i;
char *str, buff[100];
str="6";
i = atoi(str);
itoa(i,buff,4); //specify here base i.e. 4
printf("%s",buff);
}
#include<stdio.h>
#include<conio.h>
#include<string.h>
#define MAX 20
typedef struct stack
{
int data[MAX];
int top;
}stack;
void push(stack*, int );
int pop(stack*);
int empty(stack*);
void initialise(stack*);
int atoi(char);
void main()
{
char arr[MAX];
stack S;
int first, second, i, num, l;
printf("Enter the string:");
scanf("%s", arr);
initialise(&S);
l=strlen(arr);
while(l>0)
{
second=atoi(arr[l-1]);
if(l!=1)
first=atoi(arr[l-2]);
else
first=0;
num=(2*first)+second;
printf("%d\n",num);
push(&S, num);
l=l-2;
}
while(!empty(&S))
{
i=pop(&S);
printf("%d",i);
}
}
void initialise(stack *S)
{S->top=-1;
}
void push(stack *S, int num)
{
S->top=S->top+1;
S->data[S->top]=num;
}
int pop(stack *S)
{
int k=S->data[S->top];
S->top=S->top-1;
return k;
}
int empty(stack *S)
{
if(S->top==-1)
return 1;
return 0;
}
int atoi(char c)
{
if(c=='0')
return 0;
return 1;
}
static public char[] convert(final char[] array) {
for (int pairIter = array.length - 1, insertIter = array.length - 1;
insertIter >= 0; insertIter--) {
if (pairIter >= 1) {
array[insertIter] = (char) (((array[pairIter] - '0') +
(2 * (array[pairIter - 1] - '0'))) + '0');
pairIter -= 2;
} else if (pairIter == 0) {
array[insertIter] = array[pairIter];
pairIter--;
} else {
array[insertIter] = '0';
}
}
return array;
}
---
System.out.println(new String(ConvertBinaryToBase4.convert(
"1010101010".toCharArray())));
System.out.println(new String(ConvertBinaryToBase4.convert(
"1011101011".toCharArray())));
System.out.println(new String(ConvertBinaryToBase4.convert(
"0000000000".toCharArray())));
System.out.println(new String(ConvertBinaryToBase4.convert(
"1111111111".toCharArray())));
System.out.println(new String(ConvertBinaryToBase4.convert(
"111111111".toCharArray())));
0000022222
0000023223
0000000000
0000033333
000013333
public String toBase4(String str){
if( str == null ){
throw new IllegalArgumentException("NULL string passed");
}
if( str.trim().equals("") ){
throw new IllegalArgumentException("EMPTY string passed");
}
char[] buf = str.toCharArray();
int length = 0;
int index = 0;
// odd length; add leading zero
if( (buf.length & 1) == 1 ){
buf[length++] = base2CharToBase4('0', buf[0]);
++index;
}
else {
buf[length++] = base2CharToBase4(buf[0], buf[1]);
index += 2;
}
while( index < buf.length ){
buf[length++] = base2CharToBase4(buf[index], buf[index+1]);
index += 2;
}
return new String(buf, 0, length);
}
final static char[] BASE4_CHARS = new char[]{'0', '1', '2', '3'};
char base2CharToBase4(char first, char second){
int base4CharsIndex = 2 * (first - '0') + (second - '0');
if( base4CharsIndex > BASE4_CHARS.length ){
throw new IllegalArgumentException("Can't convert to base4 string: '" + first + second + "'");
}
return BASE4_CHARS[base4CharsIndex];
}
#include<stdio.h>
#include<malloc.h>
int main(int argc, char* argv[])
{
char* binary = argv[1];
int length = 0;
int number = 0;
while(binary[length]!='\0')
{
number = number*2 + (binary[length++] - '0');
printf("\n number = %d", number);
}
char* base4 = malloc(length+1 * sizeof(char));
int i=0;
for(i=0; i < length;i++)
{
base4[i] = '0';
}
base4[length] = '\0';
for(i=length -1; i >-1; i--)
{
int remainder = number % 4;
base4[i] = (char) ('0' + remainder);
number /= 4;
}
printf("\nBase4 = %s", base4);
}
static public void convert(string str)
{
{
int i = 0;
if ((str.Length % 2) == 1)
{
Console.Write(int.Parse(str[i++].ToString()));
}
bool second = false;
int acc = 0;
while (i < str.Length)
{
int temp = int.Parse(str[i++].ToString());
if (second)
{
acc = 2 * acc + temp;
Console.Write(acc);
}
else
{
acc = temp;
}
second = !second;
}
Console.WriteLine();
}
}
Ignore the toCharArray part. It's just a convenience.
/**
* 1. Replace every second char with the base4 digit of the pair (i.e. '100011' => '120013')
* 2. Move all base4 digits to the right (i.e. '120013' => '120203')
* 3. Pad left half with zeros (i.e. '120203' => '000203')
* @param str
* @return
*/
public static char[] getBase4(String str){
if(str.length() % 2 == 1)
str = "0" + str;
char[] c = str.toCharArray();
for(int i = c.length - 2; i>=0; i-=2)
c[i+1] = (char)(((int)(c[i] - '0')*2) + ((int)(c[i+1]-'0')) + '0');
for(int i = 0; i < c.length/2; i++)
c[c.length - 1 - i] = c[c.length - 1 - i*2];
for(int i = 0; i < c.length/2; i++)
c[i] = '0';
return c;
}
static inline int
charToInt
( char value )
{
return value - '0';
}
static inline char
intToChar
( int value )
{
return value + '0';
}
char *
binaryToBase4
( char * string )
{
if( nullptr == string ){
throw std::invalid_argument("The argument cannot be null");
}
int length = strlen( string );
int i = (0 == length % 2) ? 0 : 1 ;
int j = i;
for(; i < length; j++, i += 2){
// parentheses are needed due to the low precedence of the <<
// operator
string[j] = charToInt(string[i+1]) + (charToInt(string[i]) << 1);
string[j] = intToChar( string[j] );
}
string[j] = '\0';
return string;
}
class base2_convert_it_into_string_with_base4 {
public static void main(String[] args) {
//given s string "1010101010" in base2
// convert it into string with base4.not use extra space....
String s = "101010101";
if(s.length()%2==1){
s='0'+s;
}
//s.charAt(index)
// String sr[] = s.split(s, 2);
StringBuffer sb = new StringBuffer();
for(int i = 0;i<s.length()-1;i=i+2){
if(s.charAt(i)=='0'&& s.charAt(i+1)=='0'){
sb.append('0') ;
}
if(s.charAt(i)=='1'&& s.charAt(i+1)=='0'){
sb.append('2') ;
}
if(s.charAt(i)=='0'&& s.charAt(i+1)=='1'){
sb.append('1') ;
}
if(s.charAt(i)=='1'&& s.charAt(i+1)=='1'){
sb.append('3') ;
}
//System.out.println(sb.toString());
}
System.out.println(sb.toString());
}
}
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int convert(char *str)
{
int sum=0,i,j,k;
while(*str)
{
i=*str-'0';
j=*(str+1)-'0';
if(*(str+1)=='\0')
j=0;
k=i*1+j*2;
sum=k+sum*10;
str=str+2;
}
return sum;
}
int main()
{
char *s="110011";
int k;
k=convert(strrev(s));
printf("%d",k);
return 0;
}
string base2_to_base4(const string& str)
{
string result;
for(int i = str.length() - 1; i >= 0; i = i - 2)
{
string pair = (i == 0)? "0" : str[i - 1];
pair += str[i];
string append;
if(pair == "00") { append = "0"; }
else if (pair == "01") { append = "1"; }
else if (pair == "10") { append = "2"; }
else if (pair == "11") { append = "3"; }
else { return "-1"; }
result = append + result;
}
return result;
}
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
int strLen(char *str)
{
if(*str)
return 1+strLen(str+1);
else
return 0;
}
void base_four(char *str,int len)
{
char *base;
base=(char *)malloc(sizeof(char)*1);
if(len%2!=0)
*base++=*str++;
while(*str)
{
if(*str=='0' && *(str+1)=='0')
{
*base++='0';
}
if(*str=='0' && *(str+1)=='1')
{
*base++='1';
}
if(*str=='1' && *(str+1)=='0')
{
*base++='2';
}
if(*str=='1' && *(str+1)=='1')
{
*base++='3';
}
str+=2;
}
*base='\0';
base=base-(len/2+len%2);
puts("\nTetral value is :");
puts(base);
}
void main()
{
char *str;
int size;
printf("Enter size of binary number :");
scanf("%d",&size);
str=(char *)malloc(sizeof(char)*size);
printf("Enter binary number :");
fflush(stdin);
gets(str);
base_four(str,strLen(str));
getch();
}
If we are using base 4, we have 4 digits 0,1,2 and 3. So if we have to represent 4 then it will be "10", 5 will be "11", 6 will be 12 and so on. So, 2 digits in base 2 can be represented by 1 digit in base 4. So,
- Vijay September 09, 2012base 2 => base 4
00 = > 0
01=> 1
10=>2
11=>3
So by grouping the string into groups of 2 and then substituting them with the above conversion we will get the solution. So 1001 will be (10 = 2 and 01 = 1) 21 is base 4.
We need to consider the case when we have odd length string. In that case we need to consider it as two bit string with 0 as the MSB.