## Amazon Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

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

Can I re-formulate the question as follow?

``````Question:
Given two numbers a,b, where a > b >= 1. Find the quotient n = a/b
without using the division operator, in log(n) time, with a precision of
k digits after the decimal point.``````

This can be done by GALLOP SEARCH:
First, init the quotient q as 1 then do repeated doubling until it overshoots the target quotient.

``````q = 1;
while (q*b < a) q *=2;``````

After this, we know the quotient is in between the range [q/2,q]
Now do binary search on this range [q/2,q]:

``````binSearch(a,b, st, ed):
mid = (st+ed)/2;
while(st < ed-1){
mid = (st+ed)/2;
if (mid *a <b){
st = mid;
} else ed = mid;
}
return mid;``````

The integer part of the quotient is:

``intPart = binSearch(a, b, q/2, q);``

The remainder is:

``remain = b - intPart*a;``

To find the k digits after decimal point, we k-time iteratively multiply the remain by 10, and do binary search in range [0,9];

``````for i = 1..k
remain *=10;
D[i]= binSearch(remain, b, 0, 9);
remain = b - a*D[i];``````

The final quotient is composed of the intPart and k digits after decimal point stored in array D.

Complexity: O(log n) + O( k*log(10) )

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

Change those [whatever]/2's with [whatever]>>1 :-P

EDIT: Nice solution BTW :-)

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

Why is your code using so many division operators when the question clearly states not to ?

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

Nicely done!
@Ram: The only division he is doing is /2, which can be done by the right shift operator

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

A little improvement over above code,

``````public class Division {

public int quotient(int a, int b){
int q = 1;

while(q*b<a)
q *=2;

return binSearch(q>>1, q, a, b);
}

public void divide(int a, int b){
int quotient = quotient(a, b);
System.out.println("Quotient: " + quotient);

int k = 5;
int d[] = new int[k];
int remainder = a - quotient * b;
for (int index = 0; index < 5; index++){
remainder *= 10;
d[index] = quotient(remainder, b);
remainder -= d[index] * b;
}

System.out.print("Digits: ");
for(int digit:d)
System.out.print(digit);
}

public int binSearch(int start, int end, int a, int b){
int mid = (start+end)>>1;
if (start == mid || mid == end)
return mid;

if (mid * b == a)
return mid;
else if (mid * b <a)
return binSearch(mid, end, a, b);
else
return binSearch(start, mid, a, b);
}

public static void main(String[] args) {
Division d = new Division();
d.divide(1023, 19);
}
}``````

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

My code would simply use a formula
#include<math.h>
#include<iostream.h>
#include<conio.h>
#include<math.h>
#include<stdio.h>
void main()
{
int a,b;
clrscr();
cout<<"Enter two numbers\n";
cin>>a>>b;
cout<<pow(10,(log10(a)-log10(b)));
getch();
}

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

+1000

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

This also will work:
a/b = b^(-1) * a

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

Amazing and clever! haha! :D

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

where n is ?

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

This Approach is good but the complexity might be n.

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

How about using shift operator (>>) for this operation as follows:

``````int a = 32;
int b = 2;
int mask = b / 2;
int result = a;
System.out
.println("Division result of a/b without using division operator is "
+ result);``````

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

/*Increment quotient by 2. when value crosses actual divident, then track from previous to actual */
private void findQDiv(int dividend, int divisor) {

int previous = 1, quotient=1, value=1;
while(true){
previous = quotient;
quotient += 2; //increment quotient by 2
value = quotient * divisor;
if(value>dividend){
value = previous * divisor;
while(previous<quotient && (dividend-value)>=divisor){
//Now the quotient is in range of previous and current
// increment previous one by one to fine right value
previous++;
value = previous * divisor;
}
quotient = previous;
break;
}else if(value==dividend){
break;
}
}
System.out.println(dividend + " / "+divisor +"="+quotient);

}

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

``````private void findQDiv(int dividend, int divisor) {

int previous = 1, quotient=1, value=1;
while(true){
previous = quotient;
quotient  += 2;			//increment quotient by 2
value = quotient * divisor;
if(value>dividend){
value = previous * divisor;
while(previous<quotient && (dividend-value)>=divisor){
//Now the quotient is in range of previous and current
// increment previous one by one to fine right value
previous++;
value = previous * divisor;
}
quotient = previous;
break;
}else if(value==dividend){
break;
}
}
System.out.println(dividend + " / "+divisor +"="+quotient);

}``````

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

``````void divide(int num,int denom)
{
if(denom==0)
return;
int q=0;
while(denom <= num)
{
denom = denom<<1;
}
{
denom = denom>>1;
if(num > denom)
{
num = num - denom;
}
}
printf("Quotient is %d and remainder is %d\n",q,num);
}``````

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

in java

``````public static double divide(int dividend, int divisor) throws Exception {
// a number cannot be divided by zero
if (divisor == 0)
throw new Exception();
// result is zero if the dividend is zero
if (dividend == 0)
return 0.0;

int quotient = 0;
int div2 = divisor * 2;
int test = dividend;
String decimal = "";

// subtract the dividen with the divisor x 2 or divisor
// we are using div2 to make this function O (log n)
while (test >= divisor) {
if (test >= div2) {
test -= div2;
quotient += 2;
} else if (test >= divisor) {
test -= divisor;
quotient++;
}
}

// decimal place
if (test != 0) {
// we don't want to be in an infinite loop
int counter = 0;
while (test != 0) {
test *= 10;

int remainder = 0;
// same code as above to have O (log n)
while (test >= divisor) {
if (test >= div2) {
test -= div2;
remainder += 2;
} else if (test >= divisor) {
test -= divisor;
remainder++;
}
}

decimal += remainder;

// break out of the loop
if (counter++ > 99)
break;
}
}

return Double.parseDouble(quotient + "." + decimal);
}``````

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

``````public class Division {

public static void main(String[] args) {
// 7.8/2.5

double dividend = -7.8;
double divisor = 2.5;

double converted_dividend = dividend;
double converted_divisor = divisor;

int k = 0;

if(dividend < 0)
{
converted_dividend = dividend * -1;
}
if(divisor < 0)
{
converted_divisor = divisor * -1;
}

double z = converted_dividend;

while(z >= converted_divisor ){
z = z - converted_divisor;
k++;
}

if( (dividend<0 && divisor>0) || (dividend>0 && divisor<0))
{
k = k*-1;
}

System.out.println("Quotient : "+ k);
System.out.println("Remainder : "+z);
}

}``````

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

``````public class MagicDivision {

public static void main(String[] args) {
new MagicDivision().doMagicDivision(21,3);
}

private void doMagicDivision(int n1, int n2){
int mul = 1;
int total =0;

while(true){
if((n1 - (n2*mul)) < 0) mul=1;
if(n1<n2){
break;
}
if((n1 - (n2*mul) == 1)) break;
n1 = (n1 - (n2*mul));
total = total+mul;
mul++;
}

System.out.println("Division : " + total);
}
}``````

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

``````my approach would be something:

problem:
69 / 4 = 17

69 - 4^1 = 65   : 1
65 - 4^2 = 57   : 2
57 - 4^3 = 45   : 3
45 - 4^4 = 29   : 4
29 - 4^5 = 9     : 5

now, 9 - 4^6 < 0
then
9 - 4^1  = 5     : 1

similarly,
5 - 4^2 < 0
then,
5 - 4^1 = 1      : 1
-------------------------------
ans          : 17

I'll then try to modify this algo!!``````

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

how does 17 fall out of all that?
also the ^ symbol usually stands for exponent, you are using it as multiply

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

This is pretty neat. Just use * instead of ^.

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

This could be code like such:

``````static int division (int a, int b ) {
int ans = 0, cntr = 1;
while (true) {
int t = a - (b * cntr);
if (t > 0) {
a = t; ans += cntr; cntr ++;
} else if( t < 0) {
cntr = 1;
} else {
ans += cntr;
break;
}
}

return ans;
}``````

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.