Microsoft Interview Question for Interns


Team: idc
Country: India
Interview Type: Written Test




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

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,

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

- Vijay September 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- ss March 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
5
of 5 vote

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

- D3^!L September 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is a good Working O(n) Code

- Anonymous November 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- j.a.b. September 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- kaustubh deshmukh September 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

group them into sets of 2 from the end and print the decimal equivalents for each set.

- ashish September 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- ashish September 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Jack September 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1010101010 =22222(base 4) =682( Decimal)
In order to convert, we have to take group of 2 bits from the LSB and convert it to base 4. For example , 10 is converted to 2. So the result is 22222

- musfiqur September 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- m@}{ September 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Jayanta Mukherjee September 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ConvertBaseToFour(char *str, int size) {
	char *tail = str+size;
	int i = 0, j = 0, k = 0;
	
	while(tail!=str) {
		i = *tail-- - '0';
		j = *tail - '0';
		K = 2*i+j;
		*tail = (char)(((int)'0')+k);
		*(tail+1) = '\0';
		tail--;		

	}

	removeWhiteSpaces();
}

- Anonymous September 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous September 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

q' is not clear

- Anonymous September 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- avico81 September 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Amanda November 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- ss March 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- vic March 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous July 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Satya Raj October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

onestopinterviewprep.blogspot.com/2014/03/convert-number-from-base2-to-base4.html

- wELLWISHER March 26, 2014 | Flag Reply


Add a Comment
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.

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