Google Interview Question for Software Engineers


Country: United States




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

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.

public static String convert(int n) {
        if (n == 0) {
            return "";
        }
        StringBuffer sb = new StringBuffer();

        while (n > 0) {
            if ((n & 1) == 1) {
                sb.append("A");
            } else {
                sb.append("B");
                n -= 1; 
            }
            n >>= 1;
        }

        return sb.reverse().toString();
    }

- JW March 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How did you come up with this solution? I see that it's working but I couldn't come up with a solution myself.

- ramon1080 March 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

ramon1080

Essentially, B = 2*2^i, and A = 1*2^i where i is the (i - 1)st digit.

A's are equal to 1s in binary, but B's need to be modified to fit with the bit shift right. To do this, you can just subtract 1 from the number before shifting it.

- Anonymous March 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Anonymous March 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please explain your code. I am unable to understand it.

- codeAddict March 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- Anonymous March 12, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

- sk11 March 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think you only want to subtract 1 from n in the B case.

n=4 yields BB whereas it should return AB

- Anonymous March 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Vijay March 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your code does not work when the input number is 127,8191..etc
please check again.

- mahaveer jangir March 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your code does not work when the input number is 127,8191..etc
please check again.

remove the float casting in below line and it will work fine.
int places = (int)((float) Math.log10(num+1)/Math.log10(2));

- mahinveer March 11, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- vs March 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- vs March 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution provided by vijay is not working when the input number is 127,8191,etc..
please check again.

- mahaveer jangir March 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A 1 1 1 1
B 2 10 2 10
AA 3 11 3 11
AB 4 100 6 110
AAA 5 101 5 101
AAB 6 110 10 1010

See the pattern?

If number input is odd, it is the previous odd input + 2, then convert to binary. If input is even, it is the preceding number * 2, then convert to binary

- Anonymous March 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Siddharth March 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous March 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- BH March 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Augustus March 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Augustus March 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- IAMASHIT March 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- IAMASHIT March 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- IAMASHIT March 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public String convert(int n) {
		if (n == 0) {
			return "";
		}
		int last = (n-1)%2;
		return convert((n-1)/2) + (char)('A' + last);
	}

- YH March 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public String convert(int n) {
		if (n == 0) {
			return "";
		}
		int last = (n-1)%2;
		return convert((n-1)/2) + (char)('A' + last);
	}

- YH March 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Recursion

public String convert(int n) {
		if (n == 0) {
			return "";
		}
		int last = (n-1)%2;
		return convert((n-1)/2) + (char)('A' + last);
	}

- yh March 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- GY March 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

A little bug

def convert(n):
    n=n+1
    i=0
    while (n>=(2**(i+1))):
        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="")

- GY March 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- ConsultTheOrb March 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- frankie March 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- AJ March 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- AJ March 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- AJ March 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- AJ March 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- AJ March 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- AJ March 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public void outputBinary(int n)
	{
		StringBuilder sb = new StringBuilder();

		while(n > 0)
		{
			if((n & 1) == 1)
			{
				sb.append("A");
				n = n>>1;
			}
			else
			{
				sb.append("B");
				n = n>>1;
				n-=1;
			}
		}
		System.out.println(sb.reverse().toString());

}

- Eric March 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this is question of uniform hashing function. It should not be limited to only to characters 'A' and 'B'

- Anonymous May 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Man, this problem is hard. Do they really ask this in the interviews ?

- hellohello October 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- hellohello October 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote
{{{ {{{while n {{{if n is of type 2n+1 then insert A in stack else insert B in stack }}} unwind stack and print }}} }}} - sk11 March 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

until number is 0
if number is of type 2n+1 then push A in stack
else push B in stack

at the last unwind and print stack.

- sk11 March 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- vs March 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I DNT KNOW

- SALMAN March 12, 2015 | 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