Amazon Interview Question for SDE-3s


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)

- Anonymous March 09, 2017 | Flag Reply
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.

- raz0r89 March 09, 2017 | Flag Reply
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

- Chris March 09, 2017 | Flag Reply
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;
  }
}

- petrov4feedly March 13, 2017 | 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