Bloomberg LP Interview Question
Software Engineer / Developersvoid FindRatio(double val, double tolerance, int* numerator, int* denominator) {
int sign = 0;
if (val < 0) {
sign = 1;
val = -val;
}
int p = val, q = 1, t;
double tol = (val*q - p) / q;
while (tol > tolerance || tol < -tolerance) {
t = q / (val * q - p);
p = p * t + q;
q = q * t;
tol = (val * q - p) / q;
}
if (q < 0 && p < 0) {
q = -q;
p = -p;
}
if (sign) {
q = -q;
}
*numerator = p;
*denominator = q;
}
Your while loop wont even executed once. because you are assigning p = val and q = 1. then tol becomes = (val*1-val)/1 = 0 and the condition becomes
while (0 > tolerance || 0 < -tolerance)
none of which will be write.
Honestly speaking it is hard to comprehend your code without the provision of comments.
int findRatio(double val, double tolerance, int &numerator, int &denominator)
{
int negative = 0;
if (val < 0)
{
negative = 1;
val *= -1;
}
numerator = 0;
denominator = 1;
double result = 0.0;
while (fabs(result-val) > tolerance)
{
if (result < val)
numerator++;
else
denominator++;
result = (double)numerator/(double)denominator;
}
if (negative)
numerator *= -1;
return 0;
}
I don't think while(fabs(result-val) > (tolerance * 2))
It is the difference between the desired value and the given value. For, the two values you considered 0.24 and 0.26, the desired value should be 0.25 and the difference of 0.24 and 0.26 with 0.25 will remain 0.01 thus no need to twice the tolerance. Please correct
This is Java version. Using BigDecimal since double has problems when comparing.
package test1;
import java.math.BigDecimal;
import java.math.RoundingMode;
public class Double2Ratio {
static class Ratio {
int numerator = 0, denominator = 0;
public void setNumerator(int numerator) {
this.numerator = numerator;
}
public void setDenominator(int denominator) {
this.denominator = denominator;
}
public int getNumerator() {
return numerator;
}
public int getDenominator() {
return denominator;
}
}
public static void main(String[] args) {
Ratio result = new Ratio();
BigDecimal val = new BigDecimal("0.25");
BigDecimal tolerance = new BigDecimal("0.01");
findRatio(val, tolerance, result);
System.out.println("The ratio of 0.25" + " is " + result.getNumerator() + "/" + result.getDenominator());
val = new BigDecimal("0.24");
findRatio(val, tolerance, result);
System.out.println("The ratio of 0.24" + " is " + result.getNumerator() + "/" + result.getDenominator());
val = new BigDecimal("0.3333333");
findRatio(val, tolerance, result);
System.out.println("The ratio of 0.33" + " is " + result.getNumerator() + "/" + result.getDenominator());
val = new BigDecimal("3.1415926");
findRatio(val, tolerance, result);
System.out.println("The ratio of 3.1415926" + " is " + result.getNumerator() + "/" + result.getDenominator());
}
private static void findRatio(BigDecimal val, BigDecimal tolerance, Ratio ratio)
{
boolean negative = false;
BigDecimal zero = new BigDecimal("0");
BigDecimal minusOne = new BigDecimal("-1");
if (val.compareTo(zero) < 0 )
{
negative = true;
val.multiply(minusOne);
}
int numerator = 0;
int denominator = 1;
BigDecimal result = zero;
BigDecimal abs = result.subtract(val).abs();
while (abs.compareTo(tolerance) > 0)
{
if (result.compareTo(val) < 0)
numerator++;
else
denominator++;
result = new BigDecimal(numerator).divide(new BigDecimal(denominator), 2, RoundingMode.HALF_EVEN);
abs = result.subtract(val).abs();
}
if (negative)
numerator *= -1;
ratio.setNumerator(numerator);
ratio.setDenominator(denominator);
}
}
The result:
The ratio of 0.25 is 1/4
The ratio of 0.24 is 1/4
The ratio of 0.33 is 1/3
The ratio of 3.1415926 is 22/7
You can always easily get the ratio when the denominator is 10^n, where n is determined by the precision
- Marian May 26, 2009Then you can divide by common denominators (in your example, you have 25/100, based on the precision, and the common denominator is 25, so you end up having 1/4).
To solve the 0.333 issue (you would want to have 1/3, not 333/1000), you can use ranges for the denominator, determined by the precision.
Instead of thinking about 333/1000 only, you think about 333/999, 333/1000 and 333/1001 (all three allowed by 0.001 precision), and pick the one that goes nicest - 333/999 = 1/3