Amazon Interview Question
SDE-2sTeam: AWS Infrastructure Planning, Analysis and Optimization
Country: United States
Interview Type: In-Person
do not use / operator. So float mid=low +(high-low)/2 will become float mid=low +(high-low) >> 1 ;
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
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
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.
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;
}
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;
}
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))
{
powOf2List.Add(divisor * (int)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;
}
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;
}
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
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++;
}
Answer=i;
}
How about using modulus and the multiple subtractions instead
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++;
}
answer=i*negate;
}
else
{
}
Actually sorry like this instead
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++;
}
*answer=i*neg;
}
else
{
*answer=NULL;
*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;
}
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};
}
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
- Abhay December 14, 2014