Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
#!/usr/bin/env python3
def negabase(number, base):
if 0 == number:
return '0'
digits = list()
while 0 != number:
number, remainder = divmod(number, base)
if remainder < 0:
# N == b*q + (b - b) + r == b*(q + 1) + (r - b)
number, remainder = number + 1, remainder - base
digits.append(str(remainder))
return ''.join(digits[::-1]) if len(digits) else '0'
def solution(number):
return negabase(number, -2)
assert solution(-15) =='110001'
assert solution(10) == '11110'
assert solution(-5) == '1111'
package dir;
class result {
int reminder;
int result;
public result(int reminder, int result) {
this.reminder = reminder;
this.result = result;
}
public result() {
}
}
public class NewClass {
public NewClass() {
int num = 13;
int div = -2;
StringBuilder sb=new StringBuilder();
while (Math.abs(num) >0) {
result r = divide(num, div);
num = r.result;
//print(r);
sb.append(r.reminder);
}
sb.reverse();
System.out.println(sb);
}
void print(result r) {
System.out.println("result " + r.result + " reminder = " + r.reminder);
}
result divide(int num, int div) {
result r = new result();
//r.result = num % div;
int count = 0;
int reminder = 0;
if (num == 0 || div == 0) {
r.reminder = 0;
r.result = 0;
}
if (num > 0) {
if (div > 0) {
//later
} else {
while (num >= -div) {
num = num + div;
count++;
}
r.result = -count;
}
} else {
if (div > 0) {
//later
} else {
// both are negative
while (num < 0) {
num = num - div;
count++;
}
r.result = count;
}
}
r.reminder = num;
return r;
}
public static void main(String[] args) {
new NewClass();
}
}
It is very similar to transforming into 2-base but tricky case is when reminder is negative.
- hawkap January 10, 2016we just have to convert negative reminder into non-negative:
a=b*c + r, so if r <0 then we can do a=b*c + r +b-b=b*(c+1) + (r-b)
in our case b=-2