Google Interview Question
Software EngineersCountry: United States
How did you come up with this solution? I see that it's working but I couldn't come up with a solution myself.
void printAB(int value){
int nDigit = ceil(log2(value/2.0+1.0));
int temp = value - (pow(2,nDigit)-1);
int i;
printf("%d : ", value);
for (i=nDigit-1; i>=0; i--){
printf("%c", (temp>>i & 1) ? 'B' : 'A');
}
printf("\n");
}
codeAddict//
First.. need to find a pattern.
1-letter string : 2^1
2-letter string : 2^2
3-letter string : 2^3..
...
k-letter string : 2^k..
Thus... if the input is $n$, the length of output string is ceil(log2(n/2+1)).
example:
n=1 -> ceil(log2(1/2+1)) = ceil(log2(3/2)) = 1.
n=2 -> ceil(log2(2/2+1)) = ceil(log2(2)) = 1.
n=3 -> ceil(log2(3/2+1)) = ceil(log2(5/2)) = 2.
...
Now.. the next observation is that...
when 1 <= n <= 2, the string is binary expression of n-(2-1). ('A' for 0, 'B' for 1)
when 3<= n <= 6, the string is binary expression of n-(2^2-1).
when 7<= n <= 14, the string is binary expression of n-(2^3-1).
...
In the code.. "nDigit" is the length of output string..
and.. "temp" is the value which will be used to generate the binary expression.
The for-loop is just printing the binary expression of 'temp' using 'A' and 'B' instead of 0 and 1.
while (n)
{
if num is of type 2n+1 then insert A in stack
else insert B in stack
n = (n-1)/2;
}
unwind stack and print;
public static void main(String args[]) {
for(String arg : args) {
int num = Integer.parseInt(arg);
int places = (int)((float) Math.log10(num+1)/Math.log10(2));
int highest = (int)Math.pow(2, places) - 1;
char output[] = new char[places];
int itr = places-1;
int diff = num - highest;
while(diff != 0) {
int bal = diff%2 ;
diff /= 2 ;
if(bal == 1)
output[itr--] = 'B';
else
output[itr--] = 'A' ;
}
while(itr >= 0)
output[itr--] = 'A';
System.out.println( arg + " --- " + disp(output) );
}
// 1 -> A 2-> B
static void NumberToString(int number)
{
if (number <= 0)
{
return;
}
int start = 0;
int end = 0;
int i = 0;
while (i <= number / 2)
{
if (number >= start && number <= end)
{
break;
}
++i;
int numOfElem = (int)Math.Pow(2, i);
start = end + 1;
end += numOfElem;
}
for (int j = i; j > 0; --j)
{
int mid = (start + end) / 2;
if (number <= mid)
{
Console.Write('A');
end = mid;
}
else
{
Console.Write('B');
start = mid + 1;
}
}
}
// 1 -> A 2-> B
static void NumberToString(int number)
{
if (number <= 0)
{
return;
}
int start = 0;
int end = 0;
int i = 0;
while (i <= number / 2)
{
if (number >= start && number <= end)
{
break;
}
++i;
int numOfElem = (int)Math.Pow(2, i);
start = end + 1;
end += numOfElem;
}
for (int j = i; j > 0; --j)
{
int mid = (start + end) / 2;
if (number <= mid)
{
Console.Write('A');
end = mid;
}
else
{
Console.Write('B');
start = mid + 1;
}
}
}
Working Java solution.
public class ABRepresentation {
public static String getABrepresentation(int n) {
// find the # of digits in n + 1
int x = n + 1;
int nDigits = 0;
while (x != 0) {
x /= 2;
nDigits++;
}
int y = n + 1 - (1 << (nDigits - 1));
// create the String representation of the (nDigits - 1)
// least significant bits of y, with A/B instead of 0/1
StringBuilder repr = new StringBuilder();
int mask = 1 << (nDigits - 2);
while (mask != 0) {
if ((mask & y) == 0)
repr.append('A');
else
repr.append('B');
mask >>= 1;
}
return repr.toString();
}
public static void main(String[] args) {
for (int i = 1; i <= 15; i++) {
System.out.println(i + " - " + getABrepresentation(i));
}
}
}
#include<iostream>
#include <math.h>
int main()
{
int num; //9
std::cin >> num;
int exp = floor(log2(num+1)); // 3
int baseNum = pow(2,exp) - 1; // 7
int diff = num - baseNum; //9 - 7 = 2
for (int i = exp-1; i >= 0; i--)
{
int bit = (diff & (1<<i));
char s = bit ? 'B' : 'A';
std::cout << s;
}
std::cout << std::endl;
}
private static string getAB(int n)
{
if (n < 1)
return null;
int m = n;
int digs = 0;
int d = 2;
while (m > 0)
{
m -= d;
d *= 2;
digs++;
}
char[] str = new char[digs];
m = n;
int idx = digs - 1;
for (int i = 0; i < digs; i++)
{
int seq = 2 << i;
int mid = seq >> 1;
int r = m % seq;
if ((r > 0) && (r <= mid))
str[idx] = 'A';
else
str[idx] = 'B';
m = m - seq;
idx--;
}
return new string(str);
}
//A is 0, B is 1. You just increase the input number by 1 and change it to the 0-1 (A-B) string, and remove the first character.
I write the code on the white broad, possibly some bugs.
string getString(int number) {
char ch;
if (number%2 == 0) {
ch = ‘A’
}
else {
ch = ‘B’
}
if (number/2 == 0) {
return ch;
}
string mStr = getString(number/2);
return mStr+ch;
}
string ans = getString(input+1);
ans = ans.substr(1, ans.length()-1);
//A is 0, B is 1. You just increase the input number by 1 and change it to the 0-1 (A-B) string, and remove the first character.
I write the code on the white broad, possibly some bugs.
string getString(int number) {
char ch;
if (number%2 == 0) {
ch = ‘A’
}
else {
ch = ‘B’
}
if (number/2 == 0) {
return ch;
}
string mStr = getString(number/2);
return mStr+ch;
}
string ans = getString(input+1);
ans = ans.substr(1, ans.length()-1);
//A is 0, B is 1. You just increase the input number by 1 and change it to the 0-1 (A-B) string, and remove the first character.
I write the code on the white broad, possibly some bugs.
string getString(int number) {
char ch;
if (number%2 == 0) {
ch = ‘A’
}
else {
ch = ‘B’
}
if (number/2 == 0) {
return ch;
}
string mStr = getString(number/2);
return mStr+ch;
}
string ans = getString(input+1);
ans = ans.substr(1, ans.length()-1);
A is 0, B is 1. You just increase the input number by 1 and change it to the 0-1 (A-B) string, and remove the first character.
I write the code on the white broad, possibly some bugs.
string getString(int number) {
char ch;
if (number%2 == 0) {
ch = ‘A’
}
else {
ch = ‘B’
}
if (number/2 == 0) {
return ch;
}
string mStr = getString(number/2);
return mStr+ch;
}
string ans = getString(input+1);
ans = ans.substr(1, ans.length()-1);
Python 3
def convert(n):
n=n+1
i=0
while (n>(2**i)):
i+=1
while (i>0):
n=n%2**i
i-=1
let = n//2**i
if let == 1:
print("B", end="")
else:
print("A", end="")
if __name__ == "__main__":
for k in range(16):
print (k, end =": ")
convert(k)
print()
A verbose, but simple ripple-carry implementation:
class LetterString
{
public static void nextInSequence(StringBuffer s)
{
int i = s.length() - 1;
boolean carry = true;
while (carry && i >= 0) {
if (s.charAt(i) == 'A') {
s.setCharAt(i, 'B');
carry = false;
} else { // B
s.setCharAt(i, 'A');
}
i--;
}
if (carry) {
s.insert(0, 'A');
}
}
public static String countTo(int n)
{
if (n <= 0) {
return "";
}
StringBuffer s = new StringBuffer();
for (int i = 0; i < n; i++) {
nextInSequence(s);
}
return s.toString();
}
public static void main(String[] args)
{
for (int i = 0; i <= 20; i++) {
System.out.println(i + " : " + countTo(i));
}
}
}
If you want to use math operations/functions other than bit manipulation you could do this:
void print_ab(int input){
int output_length = floor(log(input + 1)/log(2));
int dividend = (input+1)-pow(2, output_length);
int divisor = pow(2, output_length-1);
for(; divisor>0; divisor/=2){
if(dividend/divisor==0){
printf("A");
}else{
printf("B");
dividend%= divisor;
}
}
printf("\n");
}
This will only work for input >= 1.
I compiled this on Manjaro with the following: gcc printing_ab_output.c -lm.
Here is a working Java Solution:
String getString(int n)
{
if (n == 0)
return "";
if (n == 1)
return "A";
if (n == 2)
return "B";
final String constant[] = {"A","B"};
Stack<ArrayList<String>> ll = new Stack<ArrayList<String>>();
ArrayList<String> temp = new ArrayList<String>();
temp.add("A");
temp.add("B");
ll.add(temp);
while (n > 2)
{
ArrayList<String> tempList = new ArrayList<String>();
for(String prefix: constant)
{
String []priorStrings = new String[1];
for(String str: ll.peek().toArray(priorStrings))
{
String result = prefix+str;
n--;
if(n <=2)
return result;
tempList.add(result);
}
}
ll.add(tempList);
}
return "";
}
Here is a java working code:
String getString(int n)
{
if (n == 0)
return "";
if (n == 1)
return "A";
if (n == 2)
return "B";
final String constant[] = {"A","B"};
Stack<ArrayList<String>> ll = new Stack<ArrayList<String>>();
ArrayList<String> temp = new ArrayList<String>();
temp.add("A");
temp.add("B");
ll.add(temp);
while (n > 2)
{
ArrayList<String> tempList = new ArrayList<String>();
for(String prefix: constant)
{
String []priorStrings = new String[1];
for(String str: ll.peek().toArray(priorStrings))
{
String result = prefix+str;
n--;
if(n <=2)
return result;
tempList.add(result);
}
}
ll.add(tempList);
}
return "";
}
Here is a working Java Code :
static String getString(int n)
if (n <= 0)
return "";
final String constant[] = {"A","B"};
Stack<ArrayList<String>> ll = new Stack<ArrayList<String>>();
// add a empty list
ll.add(new ArrayList<String>());
while (n > 0)
{
ArrayList<String> tempList = new ArrayList<String>();
for(String prefix: constant)
{
for(String str: ll.peek().toArray(new String[1]))
{
String result = str != null ? prefix+str : prefix;
n--;
if(n <= 0)
return result;
tempList.add(result);
}
}
ll.add(tempList);
}
// match not found
return "";
Here is a working Java code :
static String getString(int n)
if (n <= 0)
return "";
final String constant[] = {"A","B"};
Stack<ArrayList<String>> ll = new Stack<ArrayList<String>>();
// add a empty list
ll.add(new ArrayList<String>());
while (n > 0)
{
ArrayList<String> tempList = new ArrayList<String>();
for(String prefix: constant)
{
for(String str: ll.peek().toArray(new String[1]))
{
String result = str != null ? prefix+str : prefix;
n--;
if(n <= 0)
return result;
tempList.add(result);
}
}
ll.add(tempList);
}
// match not found
return "";
}
Here is a working Java code :
static String getString(int n)
{
if (n <= 0)
return "";
final String constant[] = {"A","B"};
Stack<ArrayList<String>> ll = new Stack<ArrayList<String>>();
// add a empty list
ll.add(new ArrayList<String>());
while (n > 0)
{
ArrayList<String> tempList = new ArrayList<String>();
for(String prefix: constant)
{
for(String str: ll.peek().toArray(new String[1]))
{
String result = str != null ? prefix+str : prefix;
n--;
if(n <= 0)
return result;
tempList.add(result);
}
}
ll.add(tempList);
}
// match not found
return "";
}
static String getString(int n)
{
if (n <= 0)
return "";
final String constant[] = {"A","B"};
Stack<ArrayList<String>> ll = new Stack<ArrayList<String>>();
// add a empty list
ll.add(new ArrayList<String>());
while (n > 0)
{
ArrayList<String> tempList = new ArrayList<String>();
for(String prefix: constant)
{
for(String str: ll.peek().toArray(new String[1]))
{
String result = str != null ? prefix+str : prefix;
n--;
if(n <= 0)
return result;
tempList.add(result);
}
}
ll.add(tempList);
}
// match not found
return "";
}
This is hard to solve in 30 mins. Took me about 2 hours or so.
The key insight here is that there is no "zero" value in this representation.
Otherwise, it is similar to a binary representation.
A = 1 and B = 2
And value (0 counted from right) is 2^i times the value of A or B at that location.
Now, in order to deal with there being no zeros, first find the largest number represented with only A's that is smaller than the given number.
Example: for 13 that value is "AAA".
After than take the remaining value 13 - AAA = 13 - 7 = 6.
Now, take the binary representation of 6 which is "110" and for each occurance of 1, replace A with B. i.e "AAA" becomes "BBA".
class Solution {
public static String reverse(String str){
return new StringBuilder(str).reverse().toString();
}
public static String sequence(int num){
//baseNum is just a value corresponding to series of A's
int baseNum = 1;
int length = 1;
while((baseNum << 1) + 1 <= num){
baseNum = (baseNum << 1) + 1;
length += 1;
}
int remaining = num - baseNum;
String remainingStr = Integer.toString(remaining,2);
String remRev = reverse(remainingStr);
String res = "";
for(int i = 0; i < length; i++){
boolean second = (i < remRev.length()
&& remRev.charAt(i) == '1');
res += (second ? "B" : "A");
}
return reverse(res);
}
public static void main(String[] args) {
System.out.println( sequence(12) );
}
}
// 1 -> A 2-> B
static void NumberToString(int number)
{
if (number <= 0)
{
return;
}
int start = 0;
int end = 0;
int i = 0;
while (i <= number / 2)
{
if (number >= start && number <= end)
{
break;
}
++i;
int numOfElem = (int)Math.Pow(2, i);
start = end + 1;
end += numOfElem;
}
for (int j = i; j > 0; --j)
{
int mid = (start + end) / 2;
if (number <= mid)
{
Console.Write('A');
end = mid;
}
else
{
Console.Write('B');
start = mid + 1;
}
}
}
This is almost like converting the number's binary to A's and B's where A is 1 and B is 0, except with the twist of also subtracting 1 when a 0 is encountered.
- JW March 12, 2015