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

- Abhay December 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
6
of 6 votes

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

- jaks December 23, 2014 | Flag
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}

- Omri.Bashari May 05, 2015 | Flag
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

- naren December 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
3
of 3 votes

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

- naren December 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- csmith932 December 13, 2014 | Flag
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;


}

- SKD December 16, 2014 | Flag Reply
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;
        }

- vladimir.grebennikov December 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@vladimir.grebennikov: possible to explain the logic?

- aka[1] December 25, 2014 | Flag
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))
            {
                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;
        }

- ad December 13, 2014 | Flag Reply
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;
    }

- GK December 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@GK: possible to explain the logic?

- aka[1] December 25, 2014 | Flag
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

- Adi December 25, 2014 | Flag Reply
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++;
   }
   Answer=i;
}

- Tikky April 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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
	{
		
}

- tikky7 April 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- tikky7 April 30, 2015 | Flag
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};
    }

- praneeth.gayam May 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why not do

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

- Falak November 03, 2015 | 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