Amazon Interview Question: About the details, and interv... | Glassdoor

Amazon

## Interview Question

Software Development Engineer/Intern Interview Seattle, WA

# About the details, and interviewer will communicate with

you when you are typing.
Tags:
technical, algorithm

0

Division - Divide A/B - repeatedly subtract B from A, until A < B. At which time print the number of subtractions as the quotient. The left over value in B, is the remainder.

Anonymous on Nov 8, 2013
0

More efficient - http://www.prasannatech.net/2009/01/division-without-division-operator_24.html

Anonymous on Nov 8, 2013
0

For the sum case of digits try a binary search type approach:

Let S be the sum we are searching for

Sort the array - you can do this in n*Log(n) (see http://en.wikipedia.org/wiki/Sorting_algorithm)

Here is where the binary search idea comes in

Divide the sorted array into sub arrays A1 and A2. Take the mid elements of both sub arrays as pivots p1 and p2. This gives us 4 sub-sub arrays - In A1, we have the left of p1 as A11 to the right of p1 as A12. In A2, we have to the left of p2 as A21 and right of p2 as A22.

If p1 + p2 > S then we look in A12 and A13, A11 and A13 and A11 and A12
If p1 + p2 < S look in A12 and A14

Anonymous on Nov 8, 2013