Amazon Interview Question Software Engineer / Developers


Country: India
Interview Type: Phone Interview


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

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

public static String divideIterative(int A, int B) {
		StringBuffer soFar = new StringBuffer("");
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		if (A == 0)
			return soFar.toString();
		while (A != 0) {
			if (A >= B) {
				soFar.append(A / B);
				A = A % B;
			} else {
				if (soFar.indexOf(".") == -1) {
					if (soFar.length() > 0)
						soFar.append(".");
					else
						soFar.append("0.");
				}

				if (map.containsKey(A)) {
					int index = (Integer) map.get(A);
					return soFar.substring(0, index) + "("
							+ soFar.substring(index) + ")";
				} else {
					map.put(A, soFar.length());
				}

				A = A * 10;
				while (A < B) {
					A = A * 10;
					soFar.append("0");
				}
			}

		}
		return soFar.toString();
	}

- loveCoding on August 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Sanjay Kumar on August 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You got it right Sanjay

- loveCoding on August 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Being a Tester, I tried hard finding error in this solution and I consider it my failure to find any problem in this.

- PAPA on August 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree this is most complete solution

- Ben on August 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

-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).

- eugene.yarovoi on August 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 4 vote

ideone.com/btABe

- cobra on August 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

your solution will give wrong output for example 2.

what if its not getting repeated from 1st digit after the decimal

- Sanjay Kumar on August 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thank you for the finding the mistake.. now changed the code. check the same link

- cobra on August 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Sanjay Kumar on August 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

again modified the code.. check the link again..
thank you for giving the counter test case :)

- cobra on August 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Sanjay Kumar on August 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Only one way I can think of.
first go on deviding the number by number by denominator * 2 and then check for pattern.

- Sanjay Kumar on August 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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 on August 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what 127775 / 50000 should give??
2.(5)
or 2.5555 ??

- cobra on August 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Cobra Answer for 1/97 should be 0.(010309278350515463917525773195876288659793814432989690721649484536082474226804123711340206185567).

Answer for 127775 / 50000 should be definitely 2.5555

- loveCoding on August 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Cobra why are you making it so complex. See Manan's solution its much better and handles all cases with ease.

- Ben on August 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous on August 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}

- Chengyun Zuo on August 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- larry on August 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Jack on August 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();

}

- Jakub on August 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Jakub on August 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- nitin on August 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

that is the point. how to do it.

- Sanjay Kumar on August 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

check for 10/3 ..

- cobra on August 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey guys, what exactly is wrong with this approach? (casting to floats)

- Anonymous on August 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The issue is that the poster didn't read the problem.

- eugene.yarovoi on August 10, 2012 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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