Amazon Interview Question
SDE-3sCountry: United States
Interview Type: In-Person
def remainder(binarystring, k):
r = 0
for c in binarystring:
r *= 2
if c == '1': r += 1
r %= k
return r
assume the large number is represented as a string "11" with the MSB first
assume further the divisor (k) is represented as integer
even if python is capable of nearly unlimitted sized integers, the
remainder operation is implemented manualy
just implement the manual (paper-style) division algorith but only keep remainder this is O(n) runetime and O(1) space where n is the number of bits I assume this is the best conceivable runtime since I can't imagine how to calculate a remainder withouth touching each bit. how ever, there might be a more optimized version, using fewer divisions.
complete python code
def remainder(binarystring, k):
r = 0
for c in binarystring:
r *= 2
if c == '1': r += 1
r %= k
return r
print(remainder("11", 3)) # 3%3 = 0
print(remainder("111", 3)) # 7%3 = 1
print(remainder("101", 3)) # 5%3 = 2
print(remainder("1111", 3)) #15%3 = 0
print(remainder("10000", 3)) #16%3 = 1
print(remainder("10001", 3)) #17%3 = 2
print(remainder("10010", 3)) #18%3 = 0
print(remainder("100010111100", 3)) #2236%3 = 1
class Main {
public static void main(String[] args) {
BigInteger num = new BigInteger("9620680364645634331845386726262609206982068206820281340810801411111793759");
String s = num.toString(2);
System.out.println(s);
for (int i = 2; i <= 999; i++) {
String str1 = num.mod(new BigInteger(Integer.toString(i))).toString();
String str2 = "" + mod(s, i);
if (!str1.equals(str2)) {
System.out.println(i + ":\t" + str1 + "\t" + str2);
}
}
}
private static int mod(String num, int k) {
final long maxValModK = (1L<<62) % k;
int times = 0;
int pos = num.length()-1;
int res = 0;
while (pos >= 0) {
long factor = 1;
long x = 0;
while (pos >= 0 && factor != 1L<<62) {
if (num.charAt(pos--) == '1') {
x |= factor;
}
factor <<= 1;
}
x %= k;
for (int i = 0; i < times; i++) {
x = (x * maxValModK) % k;
}
res += x;
res %= k;
times++;
}
return res;
}
}
For case of divided by 3:
- Anonymous March 09, 2017(1). Divide the binary stream in groups of size 4.
(2). For each group, find its decimal value and corresponding remainder. Say the remainder is r1.
(3). Find remainder for the next group. say it is r2.
(4). The remainder of these two groups would be (r1+r2)%3.
(5). Use this remainder ((r1+r2)%3) as if it is the remainder as described in (2).
(6) Repeat (3), (4), (5)