Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
Why is your code using so many division operators when the question clearly states not to ?
Nicely done!
@Ram: The only division he is doing is /2, which can be done by the right shift operator
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);
}
}
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();
}
/*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);
}
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);
}
void divide(int num,int denom)
{
if(denom==0)
return;
int mask=1;
int q=0;
while(denom <= num)
{
denom = denom<<1;
mask = mask<<1;
}
while(mask > 1)
{
mask = mask>>1;
denom = denom>>1;
if(num > denom)
{
num = num - denom;
q = q|mask;
}
}
printf("Quotient is %d and remainder is %d\n",q,num);
}
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);
}
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);
}
}
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);
}
}
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!!
how does 17 fall out of all that?
also the ^ symbol usually stands for exponent, you are using it as multiply
Can I re-formulate the question as follow?
This can be done by GALLOP SEARCH:
First, init the quotient q as 1 then do repeated doubling until it overshoots the target quotient.
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:
The remainder is:
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];
The final quotient is composed of the intPart and k digits after decimal point stored in array D.
- ninhnnsoc April 22, 2014Complexity: O(log n) + O( k*log(10) )