## Microsoft Interview Question for Software Engineer / Developers

Country: United States

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

Group each pair of binary bits gives base4.

example:
base2: | 11 | 01 | 01 | 10 |
base4: | 3 | 1 | 1 | 2 |

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

Correct but start that grouping from right to left...

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

Agree with above.

Giving an actual code below which uses String to represent both base2 and base4 numbers. Given this implementation, a clarification can be raised for leading zeros (if they need to be printed or not).

``````package base2tobase4;

public class Main {

public static boolean isValidInput(String b2) {
// Check if null/empty
if (b2 == null || b2.isEmpty()) {
return false;
}

// Check if all characters are just 1s and 0s
int b2Length = b2.length();
for (int i = 0; i < b2Length; i++) {
if (b2.charAt(i) != '1' && b2.charAt(i) != '0') {
return false;
}
}

return true;
}

public static String convertB2toB4(String b2) {
if (!isValidInput(b2)) {
// Invalid input
return null;
}

// Do the conversion
// The idea is to group the bits into two's since the binary representation of a base4 number is 2 bits.
// (actually, other powers of 2 follows. e.g. 3 bits for base8, 4 bits for base16, 5 bits for base 32, etc.)
StringBuilder result = new StringBuilder();
int b2Length = b2.length();
for (int i = b2Length - 1; i >=0; i = i - 2) {
int currNumber = 0;
// First bit
if (b2.charAt(i) == '1') {
currNumber++;
}
// Second bit
if (i > 0 && b2.charAt(i - 1) == '1') {
currNumber += 2;
}
// Convert the resulting number to String
result.append(String.valueOf(currNumber));
}

// Reverse the string since we processed from right to left
return result.reverse().toString();
}

public static void main(String[] args) {

/*
* Test cases
* 1. Null input - invalid case
* 2. Empty String - invalid case
* 3. Invalid binary number - invalid case
* 4. 1 bit binary number (0) - normal case
* 5. 1 bit binary number (1) - normal case
* 6. 2 bit binary number (10) - normal case
* 7. 2 bit binary number (11) - normal case
* 8. n bit binary number - normal case
* 9. binary number with even number of bits - normal case to test the loop
* 10. binary number with odd number of bits - normal case to test the loop specifically the i - 1 part
*/

System.out.println("1. " + convertB2toB4(null));
System.out.println("2. " + convertB2toB4(""));
System.out.println("3. " + convertB2toB4("1234"));
System.out.println("4. " + convertB2toB4("0"));
System.out.println("5. " + convertB2toB4("1"));
System.out.println("6. " + convertB2toB4("10"));
System.out.println("7. " + convertB2toB4("11"));
System.out.println("8. " + convertB2toB4("11101101110011"));
System.out.println("9. " + convertB2toB4("1111"));
System.out.println("10. " + convertB2toB4("11111"));
System.out.println("11. " + convertB2toB4("0000000000111111"));
}

}``````

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

by multiplying bits by
1st bit by 1
2nd bit by 2
3rd bit by 10
4th by 20
5th by 100
then 200
1000......

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

Whats the logic behind ? Could you explain that?

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

@Noob
A simple trick to convert base 2 integer to base 4 integer.
Do it on this example and u will then know:
base2: | 11 | 01 | 01 | 10 |
base4: | 3 | 1 | 1 | 2 |

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

``````// Interview specific questions
// Convert 2-base integer string to 4-base integer string
// A: Use grouping, because 2, 4, 8, 16 are very GOOD numbers :-)
// NOTE:
//   1. No overflow detection;
//   2. No invalid char/digit detection;
string Convert2_4(const string& s)
{
// Construct the map
map<string, string> map24;
map24["0"] = "0";
map24["1"] = "1";
map24["00"] = "0";
map24["01"] = "1";
map24["10"] = "2";
map24["11"] = "3";

string r;

// Group two digits by two
int len = s.length();
int start = 0;
if (len % 2)
{
r += map24[s.substr(0, 1)];
start = 1;
}

for (int i = start; i < len; i += 2)
{
r += map24[s.substr(i, 2)];
}

return r;
}``````

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

Right to left not taken care of.

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

@KannarKK - since the case when length is odd, is taken care of separately, right to left and left to right is literally same of remaining even length string

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

``````static void Base2To4(byte[] base2)
{
int pos = base2.Length - 1;
int base4 = 0;
int positionPower = 10;

while (pos >= 0)
{
if (base2[pos] > 1) throw new InvalidOperationException();

int value = base2[pos] == 0 ? 0 : 1;
if (pos > 0)
{
if (base2[pos - 1] > 1) throw new InvalidOperationException();
value += base2[pos - 1] == 0 ? 0 : 2;
}
if (base4 == 0)
base4 = value;
else
{
base4 += value * positionPower;
positionPower *= 10;
}

pos -= 2;
}

Console.WriteLine(base4);
}``````

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

Algo 1:
---------
Convert binary to decimal and then from decimal to base 4 number

``````int ConvertBase2NumberToBase4(long userInput){
int decimalNumber,numberInBase4;
int lastDigit;
int multiply = 1;
while(userInput){
lastDigit = userInput % 10;
userInput /= 10;
decimalNumber += (lastDigit * multiply);
multiply *= 2;
}
while(decimalNumber < 4){
lastDigit = userInput %4;
userInput /= 4;
numberInBase4 = (numberInBase4 *10) + lastDigit;
}
return numberInBase4;
}``````

2) Club two two digit and find the equivalent in base 4

``````int ConvertBase2NumberToBase4Merging2Digits(long userInput){
int lastTwoDigits,cummulativeSum,numberInBase4 = 0;
while(userInput){
lastTwoDigits = userInput % 100;
cummulativeSum = lastTwoDigits%10;
lastTwoDigits /= 10;
cummulativeSum = 2 * (lastTwoDigits %10);
numberInBase4 = numberInBase4 << 3 + numberInBase4 << 1 + cummulativeSum;
userInput /= 100;
}
return numberInBase4;
}``````

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

Using property of grouping and converting, this is a simple solution to the problem with complexity O(n)

public static void convertTobase4(String s)
{
String base4Number = "";
if(s.length() % 2 !=0 )
{
s = "0"+s;
}

for (int i = 0; i < s.length(); i=i+2)
{
if(s.substring(i, i+2).equals("00"))
{
base4Number =base4Number + "0";
}
if(s.substring(i, i+2).equals("01"))
{
base4Number =base4Number + "1";
}
if(s.substring(i, i+2).equals("10"))
{
base4Number =base4Number + "2";
}
if(s.substring(i, i+2).equals("11"))
{
base4Number =base4Number + "3";
}
}

System.out.println(base4Number);
}

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

``````public class Base2_4 {

static void stringBaseChange(char[] arr, int len) {
char ch1;
char ch2 = 0;
boolean flag = false;
if (len <= 0)
return;
if (len == 1) {
ch1 = arr[len - 1];
flag = true;
} else {
ch1 = arr[len - 1];
ch2 = arr[len - 2];
stringBaseChange(arr, len - 2);
}

if (ch2 == '0' && flag == false) {

if (ch1 == '0')
System.out.print("" + 0);
else
System.out.print("" + 1);
} else if (ch2 == '1' && flag == false) {

if (ch1 == '0')
System.out.print("" + 2);
else
System.out.print("" + 3);
}else{
System.out.print("" + ch1);
}

}

public static void main(String[] args) {
char []arr = {'1','1','0','0','1','1','1'};
stringBaseChange(arr,7);

}``````

}

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

``````public static void printBase4(String str) {
int n = str.length();
if(n % 2 == 1) {
System.out.println("Not Possible");
}
int i;
String out = "";
for(i = n - 1; i >= 0 ; i = i-2) {
char ch1 = str.charAt(i);
char ch2 = str.charAt(i-1);
int o;
if(ch1 == '0') {
if(ch2 == '0') {
o = 0;
} else {
o = 2;
}
} else {
if(ch2 == '0') {
o = 1;
}else {
o = 3;
}
}
out = "" + o + out;
}
System.out.println(out);
}``````

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

``````def convert(n):
res=''
for j in range(len(n) - 1, -1, -2):
if j==0:
res=str(int(n[j]))+res
else:
res = str(int(n[j-1] + n[j],2)) + res

return res``````

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.