Microsoft Interview Question
Software Engineer / DevelopersCountry: United States
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"));
}
}
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......
// 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;
}
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);
}
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;
}
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);
}
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);
}
}
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);
}
Group each pair of binary bits gives base4.
- pirate August 02, 2013example:
base2: | 11 | 01 | 01 | 10 |
base4: | 3 | 1 | 1 | 2 |