## Amazon Interview Question for SDE-2s

Team: AWS Infrastructure Planning, Analysis and Optimization
Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
6
of 8 vote

Since interviewer has constraint of not using division operator and hinted you to use binary search
we can use multiplication and then apply binary search
the Idea is
suppose a/b=c
=> a=b*c
now we need to apply binary search on c
followig c code will do the work
since abs function does not work for float I have implemented my own

``````float absolute(float a)
{
return a>0 ? a:-a;
}
float divide(int a,int b)
{
float high=INT_MAX,low=0,tolerence=1e-4;
int factor=1;
if( a*b < 0 )     /*for handling negative cases*/
factor=-1;
a=abs(a);
b=abs(b);
do
{
float mid=low +(high-low)/2;
float product=b*mid;
if(absolute (product - a) < tolerence)
return mid*factor;
if(product < a)
low = mid;
else
high=mid;
}while(absolute(high-low) > 1e-3);
return low*factor;
}``````

Comment hidden because of low score. Click to expand.
6

do not use / operator. So float mid=low +(high-low)/2 will become float mid=low +(high-low) >> 1 ;

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

since the inputs are integers, you don't need to search {0,INT_MAX} it is sufficient to search {0,a}

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

Double the divisor everytime until it is greater than numerator.Keep track of the doubling. Apply this recursively until the subtraction is less than divisor.
E.g.
40/3-> 40/6->40/12->40/24 : Keep track of doubling: 2 power 3 = 8
16/3 - > 16/6->16/12: Keep track of doubling 2 Power 2 = 4
4/3-> 1 Stop here because 1 less than 3: Keep track of doubling i.e. 2 power of zero: 1

8 + 4 +1 =13 factor remainder = 1

Comment hidden because of low score. Click to expand.
3

This can be further improved. In the second step, you can start from 12(largest doubled value which is less than 16) onwards and not from 3 again.

40/3-> 40/6->40/12->40/24 : Keep track of doubling: 2 power 3 = 8
16/12: Keep track of doubling 2 Power 2 = 4
4/3-> 1 Stop here because 1 less than 3: Keep track of doubling i.e. 2 power of zero: 1
Total steps: 5

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

You don't automatically know which of your intermediate results would be the relevant number for the recursive call. You would have to iterate over them to check, or check at each iteration of the doubling whether the result has been precomputed and substitute it.

That "optimization" doesn't change the algorithmic efficiency unless the computation of an intermediate result is greater than O(1), which it isn't (multiplication of 2 numbers is O(1)). In a different problem your suggestion may be right, but not here. Your original solution appears correct.

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

Complexity : O(logn) where n= max(number of bits in divisor, number of bits of dividend)

``````//division of two integers without using '/' symbol

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>

using namespace std;

int division(int,int);
int wrapper_division(int,int);

int divisor, dividend, _remainder;

int wrapper_division(int t_dividend, int t_divisor)
{
int quotient= division(abs(t_dividend), abs(t_divisor));

if(_remainder!=0)
{
if(t_dividend < 0 && t_divisor > 0)
{
_remainder++;
return -(quotient+1);
}

else if(t_dividend > 0 && t_divisor < 0)
{
_remainder= -(abs(t_divisor)-_remainder);
return -(quotient+1);
}

else if(t_dividend < 0 && t_divisor < 0)
{
_remainder= -_remainder;
return quotient;
}

else
return quotient;
}

if(t_divisor<0 || t_dividend<0)
return -quotient;

return quotient;

}

int division(int t_dividend, int t_divisor)
{
int quotient = 1;

if(t_divisor==0)
{
cout<<"DIVISION BY ZERO NOT POSSIBLE"<<endl;
exit(1);
}

if (t_divisor==t_dividend)
{
_remainder=0;
return 1;
}

else if(t_dividend < t_divisor)
{
_remainder = t_dividend;
return 0;
}

while(t_divisor <= t_dividend)
{
t_divisor <<= 1;
quotient <<= 1;
}

t_divisor >>= 1;
quotient >>= 1;

quotient = quotient + division( abs(t_dividend - t_divisor), abs(divisor));

return quotient;

}

//Unit test
int main(void)
{
dividend= 10, divisor= 3;
int quotient= wrapper_division(dividend, divisor);
assert(quotient==3 && _remainder ==1);
cout<<"Test 1 passed..."<<endl;
cout<<"quotient: "<<quotient<<" _remainder: "<<_remainder<<endl;

dividend= -10, divisor= 3;
quotient= wrapper_division(dividend, divisor);
assert(quotient==-4 && _remainder ==2);
cout<<"Test 2 passed..."<<endl;
cout<<"quotient: "<<quotient<<" _remainder: "<<_remainder<<endl;

dividend= 10, divisor= -3;
quotient= wrapper_division(dividend, divisor);
assert(quotient==-4 && _remainder == -2);
cout<<"Test 3 passed..."<<endl;
cout<<"quotient: "<<quotient<<" _remainder: "<<_remainder<<endl;

dividend= -10, divisor= -3;
quotient= wrapper_division(dividend, divisor);
assert(quotient==3 && _remainder == -1);
cout<<"Test 4 passed..."<<endl;
cout<<"quotient: "<<quotient<<" _remainder: "<<_remainder<<endl;

}``````

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

Did using bit operations.

``````private int DivideManual(int a, int b)
{
if (b == 0) throw new Exception("Diving by zero");
if (a == 0) return 0;
if (a < b) return 0;
if (a == b) return 1;

int m = 0;
int n = 0;
while (a >> m++ > 0) ;
while (b >> n++ > 0) ;
var c = a >> (m - n);
int d = 0;
if (c >= b)
{
c -= b;
d++;
}
for (int i = m - n - 1; i >= 0; i--)
{
c = (c << 1) + (a >> i) - ((a >> (i + 1)) << 1);
d = d << 1;
if (c >= b)
{
c -= b;
d++;
}
}
return d;
}``````

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

@vladimir.grebennikov: possible to explain the logic?

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

Code (c#) for the solution provided above. This takes care of cases for -ve number division.

``````public int DivideWODivisionOp(int dividend, int divisor)
{
bool negativebitSet = ((dividend < 0 || divisor < 0) && !(dividend < 0 && divisor < 0));
dividend = Math.Abs(dividend);
divisor = Math.Abs(divisor);
List<int> powOf2List = new List<int>();
int count = 0;
while (dividend >= divisor * Math.Pow(2, count))
{
count++;
}
count--;
if (count < 0)
return 0;

int quotient = (int)Math.Pow(2, count);
int[] pow2ValuesOfDivisor = powOf2List.ToArray();
int valRemaining = dividend - pow2ValuesOfDivisor[count];
int temp = count;
while (valRemaining >= divisor)
{
temp = returnLowestIndexWithBS(valRemaining, pow2ValuesOfDivisor, 0, count);
if (temp != -1)
{
quotient += (int)Math.Pow(2, temp);
valRemaining = valRemaining - powOf2List[temp];
}
}
if (negativebitSet)
return quotient - 2 * quotient;

return quotient;
}

private int returnLowestIndexWithBS(int value, int[] input, int start, int end)
{
if (end >= start && input != null && input.Length >= end)
{
if (value == input[start])
return start;
if (value == input[end])
return end;

if (start == end - 1 && value >= input[start])
{
if (value != input[end])
return start;
else
return end;
}

if (value < input[start])
return -1;
else if (value > input[end])
return end;

int mid = (start + end) / 2;
if (value > input[mid])
return returnLowestIndexWithBS(value, input, mid + 1, end);
else if (value == input[mid])
return mid;
else
return returnLowestIndexWithBS(value, input, start, mid);
}
return -1;
}``````

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

``````public int divide(int dividend, int divisor) {
if (divisor == 0)
throw new IllegalArgumentException();
long p = Math.abs((long)dividend);
long q = Math.abs((long)divisor);
int result = 0;
for (int bit = Integer.SIZE - 1 ; bit >= 0 && p >= q ; bit--){
if (p >= (q << bit)){
p -= q << bit;
result |= 1 << bit;
}
}
boolean isPositive = (dividend < 0 && divisor < 0)||( dividend > 0 && divisor > 0);
if (result < 0){
//in general the result can't be negative, but in case of overflowing whe should handle it.
return isPositive ? Integer.MAX_VALUE : Integer.MIN_VALUE;
}
return isPositive ? result : -result;
}``````

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

@GK: possible to explain the logic?

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

since this is a question of dividing two integers, I dont think we need to worry about float values.

``````def quickSearch(start, end, num, div):

mid = (start+end) >> 1
if mid*div < num and (mid+1)*div > num:
return mid
elif mid*div > num:
return quickSearch(start, mid, num, div)
else:
return quickSearch(mid, end, num, div)

def divideNoDivisor(num, div):
if div == 0:
raise IOError("divisor cannot be 0")
if num == 0:
return 0
negFlag = False
if (num > 0 and div < 0) or (num < 0 and div > 0):
negFlag = True

num = abs(num)
div = abs(div)

quot = quickSearch(0, num, num, div)

if negFlag:
quot = -1*quot

return quot``````

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

How about using modulus then multiple subtraction

so
Input int Dividend, int Divisor
Find Dividend/Divisor

``````void Divide (int Dividend, int Divisor, int* Answer, int* Remainder)
{
int i=0;
int temp=std::numeric_limits<int>::max();;
Remainder = Dividend % Divisor;

while (temp > Remainder)
{
temp=Dividend-Divisor;
i++;
}
}``````

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

``````void(int dividend, int divisor, int* answer, int* remainder)
{
if( divisor != 0)
{
negate=1;
if (dividend<0 || divisor<0) negate=-1;
dividend = abs(dividend);
divisor= abs(divisor);
int i=0
temp=std::numeric_limits<int>::max();
remainder=dividend%divisor;
while( temp>remainder )
{
temp=dividend-divisor;
i++;
}
}
else
{

}``````

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

``````void Divide(int dividend, int divisor, int* answer, int* remainder)
{
if( divisor != 0)
{
int neg=1;
if (dividend<0 || divisor<0) neg=-1;
dividend = abs(dividend);
divisor= abs(divisor);
int i=0;

*remainder=dividend%divisor;

while( dividend>*remainder )
{
dividend=dividend-divisor;
i++;
}
}
else
{
*remainder=NULL;
}
}

int main()
{
int a=11;
int b=5;
int ans=NULL;
int rem=NULL;
Divide(a,b,&ans,&rem);
if (ans != NULL || rem != NULL)
cout << "Ans= " << ans << " Rem= " << rem <<endl;
}``````

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

Returns result and remainder.
Time Complexity : O(logn)

``````public static int[] lognDivide(int i, int j) {
if (j == 0) throw new IllegalArgumentException();
if (i == 0) return new int[]{0, 0};
if (i < j) return new int[]{0, j};
int result = 0;
int remainder = i;
int multiplier = 1;
while (remainder >= j) {
int k = remainder - j * multiplier;
if (k >=0) {
result += multiplier;
remainder = k;
multiplier = multiplier * 2;
} else {
multiplier = 1;
}
}
return new int[]{result, remainder};
}``````

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

Why not do

``exp(log(dividend)-log(divisor))``

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.