## Amazon Interview Question for SDE-3s

• 1
of 1 vote

Country: United States
Interview Type: In-Person

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

For case of divided by 3:

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

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

The solution can be written as (ak * 10 ^ k + .... a0) % 3 = [ak * (9,,,9 + 1) + ... + a0] % 3 = [ak + a(k - 1) + ... + a0] % 3. So we just need to add all digits of decimal of the binary number and then use the sum to module 3. Saw a similar problem in leetcode.

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

``````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``````

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

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

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

Implement the binary divisibility rule for 3
if it is divisible, then 0 is remainder
else find the sum = 1+stream, using iteration since the stream is long
then test again using the divisibility rule,
if it is divisible then remainder is 1, else the remainder is 2

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.

### 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.