Microsoft Interview Question
Country: United States
+1 please give ur algos only, anyone code from an algo.. so its algos what we should discuss not coding
1 correction in the previous action
find the numerator remove the decimal we will get the numerator
here .125 numerator is 125 if 22.36 then 2236
now find the denominator =10^(number of digit after decimal in numerator) here 10^3=1000
now find the HCF of numerator and denominator
here HCF of 125 and 1000 is 125
now divide the numerator and denominator by HCF
we get the answer
just want to make a comment for all approaches which are based on the following loop:
double e = 1.123, // number to convert
eps = 1e-17; // mantissa of dp number
int denom = 1;
while(e - (int)e > eps)
{
denom *= 10;
e *= 10;
printf("e: %f; denom: %d\n", e, denominator);
}
since 10 is not exactly representable by floating-point,
the above algorithm is supposed to run forever in some cases because with each multiplication by 10 we introduce a small
error to the mantissa.
for example, try the above loop with e = 1.000002
the output is going to be:
e: 10.000020; denom: 10
e: 100.000200; denom: 100
e: 1000.002000; denom: 1000
e: 10000.020000; denom: 10000
e: 100000.200000; denom: 100000
e: 1000002.000000; denom: 1000000
e: 10000020.000000; denom: 10000000
e: 100000200.000000; denom: 100000000
e: 1000002000.000000; denom: 1000000000
e: 10000020000.000002; denom: 1410065408
e: 100000200000.000015; denom: 1215752192
e: 1000002000000.000122; denom: -727379968
e: 10000020000000.001953; denom: 1316134912
e: 100000200000000.015625; denom: 276447232
e: 1000002000000000.125000; denom: -1530494976
e: 10000020000000002.000000; denom: 1874919424
e: 100000200000000016.000000; denom: 1569325056
e: 1000002000000000128.000000; denom: -1486618624
e: 10000020000000002048.000000; denom: -1981284352
e: 100000200000000016384.000000; denom: 1661992960
e: 1000002000000000196608.000000; denom: -559939584
e: 10000020000000001966080.000000; denom: -1304428544
e: 100000200000000023855104.000000; denom: -159383552
e: 1000002000000000272105472.000000; denom: -1593835520
e: 10000020000000002721054720.000000; denom: 1241513984
e: 100000200000000027210547200.000000; denom: -469762048
e: 1000002000000000237745733632.000000; denom: -402653184
e: 10000020000000002377457336320.000000; denom: 268435456
e: 100000200000000023774573363200.000000; denom: -1610612736
e: 1000002000000000272930105720832.000000; denom: 1073741824
e: 10000020000000003010776033918976.000000; denom: -2147483648
....
and thus never terminates
string void ConvertToRational(double n)
{
if (n == 0)
{
return "0";
}
int denominator = 1;
while ((n - (int)n) != 0)
{
n = n * 10;
denominator *= 10;
}
// Use Euclidean theorm to find gcd: en.wikipedia.org/wiki/Euclidean_algorithm
int numerator = (int)n;
if (denominator % numerator == 0)
{
return string.Format("1/{0}", denominator / numerator);
}
int i = numerator;
int j = denominator;
int diff = Math.Abs(i-j);
while ((i % diff != 0) || (j % diff != 0))
{
if (i > j)
{
i = diff;
}
else
{
j = diff;
}
diff = Math.Abs(i-j);
}
return string.Format("{0}/{1}", numerator/diff, denominator/diff);
}
"while ((n - (int)n) != 0)"
I think under some circumstances your alg can run
forever because exact comparison of floating-point numbers
is a common source of errors. This is even more true since
you multiply 'n' by 10 which is not a power-of-two
@Anonymous 1
I am not aware of radix implementation in C#. However can you explain how decimals can work with radix?
@Anonymous 2
n - (int) n will eventually reduce to 0 since we are multiplying n by 10. Normally I would have a > 0 condition but in this case it indeed will be equal once all the digits preceed the decimal.
@Ashish Kaila: that's right if we assume to have an fp number with
very large mantissa (e.g., BigFloat).
Remember that, in floating-point format, any number is stored
in scientific format, i.e.:
sign * mantissa * 2^{exponent + bias}
each multiplication by 10 introduces some small error and
these errors tend to accumulate. Thus, comparing two fp-numbers
for equality is, in many cases, meaningless. Just try to run your
algorithm for n = 1.000002
<pre lang="" line="1" title="CodeMonkey59447" class="run-this">import java.math.BigDecimal;
import java.util.Arrays;
public class DoubleToFraction
{
public static void main(String[] args)
{
double number = 314159265 / 358979323.0;
toFraction(number);
}
private static void toFraction(double number)
{
BigDecimal numerator = new BigDecimal(number);
int scale = numerator.scale();
numerator = numerator.movePointRight(scale);
BigDecimal denominator = new BigDecimal(10).pow(scale);
BigDecimal gcd = gcd(numerator, denominator);
numerator = numerator.divide(gcd);
denominator = denominator.divide(gcd);
System.out.println(numerator);
System.out.println(createFractionLine(numerator, denominator));
System.out.println(denominator);
}
private static BigDecimal gcd(BigDecimal num1, BigDecimal num2)
{
return (num2.equals(BigDecimal.ZERO)) ? num1 : gcd(num2, num1.remainder(num2));
}
private static String createFractionLine(BigDecimal numerator, BigDecimal denominator)
{
char[] chars = new char[Math.max(numerator.precision(), denominator.precision())];
Arrays.fill(chars, '—');
return new String(chars);
}
}</pre><pre title="CodeMonkey59447" input="yes">
</pre>
int GCD(int a, int b)
{
assert(a > 0);
assert(b > 0);
int m = a > b ? a : b;
int n = a > b ? b : a;
while(n != 0)
{
int temp = m % n;
m = n;
n = temp;
}
return m;
}
void ConvertDouble(double e)
{
const double diff = 1e-32;
bool flag = false;
if(e < 0)
{
e = -e;
flag = ture;
}
int denominator = 1;
while(e - (int)e) > diff)
{
denominator *= 10;
e *= 10;
}
int fraction = (int)e;
int gcd = GCD(denominator, fraction);
denominator /= gcd;
fraction /= gcd;
if(flag)
fraction = -fraction;
printf("%d/%d\n", fraction, denominator);
}
@ all cc users
- kamal November 15, 2011please give ur approach or algo first and then write the code(code is not required the people using the cc have enough potential to code).
my approach
find the numerator remove the decimal we will get the numerator
here .125 numerator is 125
now find the denominator =10^(number of digit in numerator) here 10^3=1000
now find the HCF of numerator and denominator
here HCF of 125 and 1000 is 125
now divide the numerator and denominator by HCF
we get the answer