Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
I don't think this solution is right.
Try test convertBase(6,-3), it turns out to be 120 which 3 in decimal.
private static void convertBase(int decimalVal,int base){
if(base > 0 && decimalVal < 0){
System.out.println("not possible");
return;
}
StringBuffer buffer = new StringBuffer();
while (decimalVal != 0){
int result = decimalVal / base;
int remainder = decimalVal % base;
if(remainder < 0){
result++;
remainder = decimalVal - base * result;
}
decimalVal = result;
buffer.insert(0, remainder);
}
System.out.println(buffer);
}
If we simulate 2-3 digits we can see the pattern of generated numbers. The code follows from observing how the range of positive/negative numbers changes. Time O( log n ).
long convert(long n)
{
if(n == 0 || n == 1)
return n;
long res = 0, low, high, range;
long digits = required_digits(n, low, high, range);
while(digits--)
{
res <<= 1;
if(digits&1)
{
if( low <= n && n < low + range)
{
res |= 1;
n += range;
}
low += range;
}
else
{
if( high >= n && n > high - range)
{
res |= 1;
n -= range;
}
high -= range;
}
range>>=1;
}
return res;
}
long required_digits(long n, long& low, long& high, long& range)
{
long digit = 1;
range = 1, low = 0, high = 1;
while( low > n || n > high )
{
digit++;
range <<= 1;
if(digit&1)
high += range;
else
low -= range;
}
return digit;
}
See Negative_base on wikipedia
Algorithm is same as positive-base conversion(e.g. base 2) but if you get remainder as -ve, you need to add the mod of base(e.g. | -2 | = 2) to remainder to get it to become non-negative and also add 1 to the remaining value after division by base.
Compilable and running code:
// How to represent a number in base -2? (negative -2 base) eg 6 can be 11010 i.e. 16 -8 +0 -2 +0 = 6.
// When the num is +ve then we divide by (0-base) (here base if negative so 0-base is +ve) and save remainter by dividing num by (0-base) and after division num becomes 0-num
// when the num is -ve then we divide (0-(num+base)) by (0-base) and save remainder by dividing (0-(num+base)) by (0-base) and after division we put back sign for both num and base
// how remainder is saved:
#include <stdio.h>
int convertToNegativeBase(int num, int base, int *digits)
{
int i=0;
while(num != 0)
{
if(num > 0)
{
base = 0-base;
digits[i++] = num%base;
num = num/base;
num = 0-num;
}
else
{
num = 0-(num+base);
base = 0-base;
digits[i++] = num%base;
num = num/base;
}
base = 0-base;
}
return i;
}
int main()
{
int digits[100];
int i = 0;
int n = convertToNegativeBase(16,-2,digits);
while(n > 0)
{
printf("%d",digits[--n]);
}
}
Suppose you have a binary number 1101110. If we consider this as base -2, the difference is that the odd digits now represent a negative value. We simply need to convert the odd digits into base -2. Examples:
10=2^1 in binary and 110=2^2-2^1=2^1 in base -2
1000=2^3 in binary and 1100=2^4-2^3=2^3 in base -2
In general
2^n=2^{n+1}-2^n
and when n is odd, 2^{n+1} is even, hence positive in base -2. This allows us to rewrite an odd digit of a binary number ...0001000.... as ...0011000...
Therefore, to find the base -2 expansion of n, a simple solution to the problem would be:
1) Sum the odd powers of 2 until you obtain a number x > n.
2) Compute the `bit-wise and`
y = n & x
(as in C or C++)
3) Multiply y by 2 (aka bit-wise shift left) and then add to n:
z = (y << 1) + n
The binary expansion of z is the base -2 expansion of n.
What a headache, but I managed it. It returns an integer where it's bits correspond to the base -2 encoding, it does it in O(log(n)) where n is the position of the highes bit:
import math
def convert(x):
res = 0
while True:
sign = 1 if x >= 0 else -1
p = math.floor(math.log2(abs(x)))
if 2**p < abs(x):
p += 1
if (p % 2 == 0 and sign < 0) or (p % 2 == 1 and sign > 0):
res += 2**(p+1)
x = -(sign*(2**p) - x)
res += 2**p
if x == 0:
break
return res
Decimal can convert into base by divide and collecting the remainders,
For example:
Binary value of decimal 12
12 / 2 = 6 with remainder 0
6 / 2 = 3 with remainder 0
3/ 2 = 1 with remainder 1
1 / 2 = 0 with remainder 1
So the Binary value is 1100
Same formula can be applied to find Negative Base, but remember remainders have to be positive.
Like the sample found in wiki
Note, here -5/-3 = 2 with remainder 1 ,
If a/b = c with remainder d then bc + d = a , thus the c can be found like c = (a-d) / b
Let’s try to write Java method to calculate this.
convertBase(7,-2) = 11011
- welcometotalk November 25, 2013convertBase(6,-2) = 11010
convertBase(7,2) = 111
convertBase(6,2) = 110