Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
I think you mean to say keep track of remainder and when it repeat. that the point the decimal also begin to repeat.
I gave the same solution.
Being a Tester, I tried hard finding error in this solution and I consider it my failure to find any problem in this.
-1: I haven't tested your code for correctness (and it might well be correct), but there's some bad stuff going on in here. There are some major performance killers:
- Use of operations like soFar += "0". This is terrible practice because it recopies the entire string every time you do that. See kaioa DOT com/node/59 for one explanation
- Unnecessary use of recursion for something that easily could have been done with iteration. This is particularly bad given that the maximum height of the recursive call stack is order O(B).
- More complex code logic and more checks than necessary. For example the decimal point could have been added once prior to entering the recursion so that all the associated checks aren't done every time you call divide().
Because of how you manage your strings, your algo will be at worst O(B^2) instead of being O(B).
your solution will give wrong output for example 2.
what if its not getting repeated from 1st digit after the decimal
I am not sure about that. can you please explain the logic in words.
Also can it handle 22/700 or 22/70000
For 22/700 Ans should be 0.03(142857)
again modified the code.. check the link again..
thank you for giving the counter test case :)
Try This:
•1/97 = 0.01030927 83505154 63917525 77319587 62886597 93814432 98969072 16494845 36082474 22680412 37113402 06185567 ; 96 repeating digits
Actually I mean to say that approach is not correct. you can't find in this way. I thought a lot on this approach. I could not able to find out any crack in this way.
In this case 0 and many degits are repeated few times.
Only one way I can think of.
first go on deviding the number by number by denominator * 2 and then check for pattern.
@Sanjay:
if you seen the decimal value should not repeat, then 225/1000 give only 0.(2)
the task is the decimal PATTERN should not be repeated.. not decimal VALUE..
you are seeing for the first decimal quotient not to repeat..
but i seen first remainder not to repeat..
because 10/7 and 11/7 both give quotient 1..
my answer for 1/97 is
0.01(030927835051546391752577319587628865979381443298969072164948453608247422680412371134020618556701)
as there are 97 possible remainders.. these number of decimal points.. when you try to go further.. the pattern in the bracket will be repeated..
@Cobra Answer for 1/97 should be 0.(010309278350515463917525773195876288659793814432989690721649484536082474226804123711340206185567).
Answer for 127775 / 50000 should be definitely 2.5555
any decimal term repeats in a division only when the same remainder
is divided again e.g. 115/99 = 1.161616... 16 are being repeated because
160 and 610 are being divided by 99 again and again
the solution would be to keep track of the reminder if it repeats at any
point stop right there.
here is the java code
public String division(int dividend, int divisor){
StringBuilder quotient = new StringBuilder();
quotient.append(dividend/divisor);
int remainder = dividend%divisor;
if(remainder==0)
return quotient.toString();
//add the decimal part
quotient.append(".");
//take a hashset to check for repeating remainders
Set<Integer> remainders = new HashSet<Integer>();
while(remainder!=0 && remainders.add(remainder)==true){
dividend = remainder*10;
quotient.append(dividend/divisor);
remainder = dividend%divisor;
}
return quotient.toString();
}
package amazon;
import java.util.ArrayList;
public class Divide_A_B {
public static String divide_A_B(int A,int B){
String results="";
if(A%B==0){
results=String.valueOf(A/B);
return results;
}
ArrayList<String> map=new ArrayList<String>();
int begin_maybe=0;
if(A>B){
results=String.valueOf(A/B)+".";
begin_maybe=results.length();
A=(A%B);
}
else{
results="0.";
begin_maybe=2;
}
while(A!=0){
int hasIndex=checkWhetherHasReturnIndex(map,String.valueOf(A));
if(hasIndex!=-1){
results=results.substring(0,begin_maybe+hasIndex)+"("+
results.substring(begin_maybe+hasIndex,results.length())+")";
break;
}
map.add(String.valueOf(A));
A=A*10;
results+=String.valueOf(A/B);
A=(A%B);
}
return results;
}
public static int checkWhetherHasReturnIndex(ArrayList<String> map,String obj){
for(int i=0;i!=map.size();i++){
if(map.get(i).equals(obj)){
return i;
}
}
return -1;
}
public static void main(String[] args) {
System.out.println(divide_A_B(4,8));
System.out.println(divide_A_B(9,5));
System.out.println(divide_A_B(2,10000));
System.out.println(divide_A_B(22,7));
}
}
public static string divide(int num0, int den0)
{
if (den0 == 0) return "Error";
var retval = new StringBuilder();
var remainders = new HashSet<int>();
int num = num0;
int den = den0;
int rem = num % den;
int quot = num / den;
retval.Append(String.Format("{0}.", quot));
while (rem != 0 )
{
num = rem * 10;
quot = num / den;
rem = num % den;
if (remainders.Contains(rem)) break;
if (rem == num)
{
rem *= 10;
}
else
{
remainders.Add(rem);
}
retval.Append(quot);
}
return retval.ToString();
}
225/1000 => 2250/1000 => 1000+1000 => 2250 - 2000 => 2*1000 + 250/1000 => 2*1000 (quotient is 2).
250/1000 => 2500/1000 => 2*1000 + 500/1000
500/1000 => 5000/1000 => 5*1000
=> 0.2 + 0.02 + 0.005 = 0.225
22/7 => 7*3 + 1/7 => 7*3 + (10/7)/10 =>
3 + (1+3/7)/10 =>
3 + (1+(30/7)/10)/10 =>
3 + (1+(4+2/7)/10)/10 =>
3 + (1+(4+(2+6/7)/10)/10)/10 =>
=> 3 + 0.1 + 0.04 + 0.002 + ... =>
=> 3.142...
Have the func input a max depth, from which to round up or down.
public static String division(int A, int B, int precision){
if(B == 0) throw new IllegalArgumentException();
if(A == 0) return "0";
StringBuilder sb = new StringBuilder();
sb.append(A / B).append(".");
A = (A % B) * 10;
for(int i = 0; i < precision; i++){
if(A == 0) return sb.toString();
if(A < B){
sb.append("0");
A *= 10;
}else{
int val = A / B;
A = (A % B)*10;
sb.append(val);
}
}
return sb.toString();
}
public static String division(int A, int B, int precision){
if(B == 0) throw new IllegalArgumentException();
if(A == 0) return "0";
StringBuilder sb = new StringBuilder();
sb.append(A / B).append(".");
A = (A % B) * 10;
for(int i = 0; i < precision; i++){
if(A == 0) return sb.toString();
if(A < B){
sb.append("0");
A *= 10;
}else{
int val = A / B;
A = (A % B)*10;
sb.append(val);
}
}
return sb.toString();
}
one solution is to first try dividing the numbers, like 2/5 , if q == 0, then multiply num by 10 until num is some perfect number and remainder is 0. In case of recurring, we need to find and match pattern in remainder.
Here is the algorithm divide(A,B)
1. if A>B , Just add A/B to the soFar String and call the divide(A%B,B)
2. if A<B A = A*10 and add "." to the soFar String if it does NOT already have it. Now if A is still less than B keep multiplying A by 10 while(A<B) for each multiplication now we need to append a "0" to soFar String
3. In step 2 we will add A in Hashtable and store the length of soFar, This is to make sure when we see this again in future we will stop the execution and return the Result.
I know Hard to explain in words so below is the Working/Tested Code
- loveCoding August 08, 2012