## Microsoft Interview Question

Country: United States

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

@ all cc users
please 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

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

+1 please give ur algos only, anyone code from an algo.. so its algos what we should discuss not coding

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

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

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

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

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

Is it HCF or GCD?

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

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

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

Eek, use FLT_RADIX instead of base 10 (not sure what the C# (?) equivalent is).

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

"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

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

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

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

@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

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

@asm
Yes I ran my code for 1.000002 and it ran fine. We are not converting a fraction in decimal so there is no question of losing accuracy.

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

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

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

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

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

find reciprocal of number will give the denominator...that is... 1/0.125=8
So the number will be 1/8

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

I think its about finding common factors. Since denominator is decimal, only possible factors are 5 and 2

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

``````pair<int, int> convert(double n)
{
int dem = 1;
// some error is fine
while ( fabs(n - (int)n) >= 1e-9) {
n *= 10;
dem *= 10;
}
int num = (int) n;
int gcd = __gcd(num, dem);
return make_pair(num/gcd, dem/gcd);
}``````

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.