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 |

- pirate August 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 votes

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

- coding.arya August 03, 2013 | Flag
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
		 * 11. leading zeros
		 */
		
		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"));
	}

}

- jacl August 08, 2013 | Flag
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......

- Devank Agarwal August 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Whats the logic behind ? Could you explain that?

- Noob August 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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 |

- Cheng Q. September 04, 2013 | Flag
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;
}

- Peter August 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Right to left not taken care of.

- KannarKK August 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- ss September 27, 2013 | Flag
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);
        }

- Rich August 14, 2013 | Flag Reply
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;
}

- avikodak August 20, 2013 | Flag Reply
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);
}

- Anubhav August 22, 2013 | Flag Reply
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);

	}

}

- bhadu407 October 01, 2013 | Flag Reply
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);
	}

- Anand November 03, 2013 | Flag Reply
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

- sumitgaur.iiita January 13, 2017 | 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