Amazon Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

subtracting is not very efficient if the divisor much smaller than the dividend
you can adapt the binary search for this problem,e.g:

// computes a = b*q + r with 0 <= r < b
void divide(unsigned a, unsigned b, unsigned& quo, unsigned& rem) {
    // suppose numbers are positive
    if(a < b) {
        quo = 0; rem = a;
        return;   
    }
    quo = 1;
    while(quo*b*2 <= a) {
         quo *= 2;
    }
    // here it holds that: quo*b <= a < quo*b*2
    if(quo * b == a) {
        rem = 0;
        return;
    }

    unsigned ql = quo, qr = quo*2, mid;
    while(1) {
        mid = (ql + qr) / 2;
        if(mid*b <= a && a < (mid+1)*b)
            break;
        if(mid*b < a) {
            ql = mid+1;
        } else {
            qr = mid;
        }
    }
    quo = mid, rem = a - quo * b;
}

int main() {
    unsigned a = 2556721331, b = 13, q, r;
    printf("correct: %d %d\n", a / b, a % b);
    divide(a, b, q, r);
    printf("test: quo: %d; rem: %d\n", q, r);
    return 1;
}

- pavel.em October 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

static int div(int tempdividend, int tempdivisor){
		if(tempdividend == tempdivisor) return 1;
		if(tempdividend < tempdivisor) return 0;
		int lo = 2;
		int hi = tempdividend;
		while(lo <= hi){
			int mid = (lo + hi)/2;
			if(mid * tempdivisor <= tempdividend && ( mid+1 )* tempdivisor >tempdividend)
				return mid;
			if(mid * tempdivisor > tempdividend)
				hi = mid-1;
			else if(mid * tempdivisor < tempdividend)
				lo = mid+1;
		}
		
		return -1;
	}

- nmc January 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@asm - the question does not allow division operator in the solution.

- melchior October 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

well, that's division by 2 )) can be replaced by bitshifts

- pavel.em October 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int givequotient (int dividend, int divisor)
{
   int i = 0;
   while (dividend > divisor)
   {
      dividend -= divisor;
      i++;
   }
   return i;
}

- Anonymous October 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

correction :

while (dividend >= divisor)

- Anonymous October 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int divide(int dividend,int divisor){
      int quo=0,tmpquo=1;
      while(dividend >= divisor ){
            tmpquo=1;
            while(tmpquo*divisor*2<=dividend) tmpquo*=2;
            quo+=tmpquo;
            dividend-=(divisor*tmpquo);
       }
       return quo;
}

- Vikash Kesarwani October 31, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Well the division operation is equal to subtracting the dividend from divisor till the result is less than divisor. The no of times this subtraction is done gives the quotient while the last no gives us remainder.

For eq: 8 / 3 = 8 - 3 -3 = 2 Quotient = 2, Remainder - 2.

- Anonymous November 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why can't we do the below:

Int Quotient Divide(Int Dividend, int Divisor ) {
Int i = 1;
while (true) {
if (Dividend < Divisor * i) {
return i;
} else {
i++;
}
}
}

- MP November 28, 2011 | 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