Epic Systems Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Written Test
public class IrreducibleFraction
{
public static String getIrreducibleFraction(double num)
{
int n = (int) (num * 10000);
int d = 10000;
// get greatest common divisior
int gcd = getGCD(n, d);
return ((n / gcd) + "/" + (d / gcd));
}
private static int getGCD(int a, int b)
{
if (a == 0)
return b;
while (a != b)
{
if (a > b)
a = a - b;
else if (b > a)
b = b - a;
else
return a;
}
return a;
}
public static void main(String args[])
{
System.out.println(getIrreducibleFraction(0.1));
}
}
public class Fractions {
public static void main(String[] args) {
double num= 0.45;
String[] s= (""+num).split("\\.");
int pow=s[1].length();
int a = (int) Math.pow(10, pow);
int b = Integer.parseInt(s[1]);
int hcf= gcd(a,b);
//System.out.println(hcf);
System.out.println(b/hcf +"/"+ a/hcf);
}
static int gcd(int a, int b){
int t;
while(b>0){
t=b;
b=a%b;
a=t;
}
return a;
}
}
Thanks for this question, I went back and reviewed GCD. :)
With GCD, this problem is quite simple. There is another hard problem: repeated decimal to fraction(medium), and fraction to repeated decimal(hard).
Code for this problem:
int gcd(int a, int b) { // make sure a > b
if (!(a%b)) return b;
return gcd(b, a%b);
}
pair<int, int> getIrreducibleFraction(double num) {
int denominator = 10000;
int numerator = denominator * num;
int cd;
cd = gcd(numerator, denominator);
numerator /= cd;
denominator /= cd;
return make_pair(numerator, denominator);
}
public String GetFraction(String deci){
if(deci==null||deci.length()<3||deci>length()>6) throw new IllegalArgumentException(“empty input”);
int deciNum = 0;
int denominator = 1;
if(deci.charAt(0) != ‘0’) throw new IllegalArgumentException(“false format”);
if(deci.charAt(1) != ‘.’) throw new IllegalArgumentException(“false format”);
for(int i=2; i<deci.length(); i++){
if(deci.charAt(i)<’0’&&deci.charAt(i)>’9’) throw new IllegalArgument(“false format”);
deciNum = deciNum * 10 + (int) (deci.charAt(i)-’0’);
denominator *= 10;
}
//devide by 2s
while(denominator%2==0&&deciNum%2==0){
deciNum /= 2;
denominator /= 2;
}
//devide by 5s
while(denominator%5==0&&deciNum%5==0){
deciNum /= 5;
denominator /= 5;
}
return new String(Integer.toString(deciNum)+”/”+Integer.toString(denominator));
}
public class Fraction {
public static void main(String[] args) {
// TODO Auto-generated method stub
double num = 0.325;
int bn = (int)(num * 10000);
//System.out.print(bn);
int great_d = getGreatestDivisor(bn,10000);
System.out.print(bn/great_d+"/"+10000/great_d);
}
public static int getGreatestDivisor(int a, int b){
if(a == 0){
return b;
}
else{
int great_d = 1;
for(int n = 1; n < a/2; n++){
if(a%n==0 && b%n==0){
great_d = n;
}
}
return great_d;
}
}
}
private static String convertToFraction(Integer numerator, Integer deno) {
Integer sqrt=(int) Math.floor(Math.sqrt(numerator));
int i=2;
for(;i<=sqrt;i++){
if(numerator%i==0&&deno%i==0)
return convertToFraction(numerator/i, deno/i);
}
if(i==sqrt+1)
return numerator+"/"+deno;
else
return "No result";
}
Pythonic Solution for generic fractional number
import math
#euclid method to find GCD
def gcd(a,b):
if b == 0 :
return a
return gcd(b, a%b)
def findIrrFrac(frac):
num = frac.split(".")[1]
den = int(math.pow(10,len(num)))
num = int(num)
gcdVal = gcd(num,den)
while(gcdVal!=1):
num /= gcdVal
den /= gcdVal
gcdVal = gcd(num,den)
print str(num)+"/"+str(den)
if __name__ == "__main__":
frac = "0.35"
findIrrFrac(frac)
package EPIC;
public class Decimal2Fraction {
public static void decimal2fraction(double input, int numbits){
int numerator;
int denominator = 1;
for (int i = 0; i < numbits; i++) {
denominator *= 10;
}
numerator = (int) (denominator * input);
int GCD = EuclideanAlgorithm(numerator, denominator);
numerator /= GCD;
denominator /= GCD;
System.out.println(numerator + " / " + denominator);
}
public static int EuclideanAlgorithm(int a, int b){
while(a != b){
if (a > b) {
a -= b;
}else{
b -= a;
}
}
return a;
}
public static void main(String[] args) {
decimal2fraction(0.35, 4);
}
}
import java.util.ArrayList;
import java.util.Scanner;
public class Prime {
private static ArrayList<Integer> findPrims(int n) {
ArrayList<Integer> primes = new ArrayList<Integer>();
boolean[] notPrime = new boolean[n + 1];
notPrime[0] = notPrime[1] = true;
for (int i = 2; i < notPrime.length; i++) {
if (notPrime[i] == false) {
primes.add(i);
for (int j = i * i; j < notPrime.length; j += i) {
notPrime[j] = true;
}
}
}
return primes;
}
private static int[] primeFactors(ArrayList<Integer> primes, int n) {
int[] powers = new int[primes.size()];
int c = 0;
while (n != 1) {
while (n % primes.get(c) == 0) {
n /= primes.get(c);
powers[c]++;
}
c++;
}
return powers;
}
private static void get() {
Scanner scan = new Scanner(System.in);
String s = scan.next().substring(2);
while (s.length() < 4)
s += "0";
int num = Integer.parseInt(s);
ArrayList<Integer> primes = findPrims(10000);
int[] p10000 = primeFactors(primes, 10000);
int[] pNum = primeFactors(primes, num);
int numerator = 1, dunmerator = 1;
for (int i = 0; i < p10000.length; i++) {
int min = Math.min(p10000[i], pNum[i]);
p10000[i] -= min;
pNum[i] -= min;
numerator *= Math.pow(primes.get(i), pNum[i]);
dunmerator *= Math.pow(primes.get(i), p10000[i]);
}
System.out.println(numerator + "/" + dunmerator);
}
public static void main(String[] args) {
get();
}
}
public class IrreduciableNumber {
public static void main(String[] args) {
int a= 35, b=100;
BigInteger n = BigInteger.valueOf(a);
BigInteger d = BigInteger.valueOf(b);
BigInteger gcd = n.gcd(d);
System.out.println(gcd);
int num1 = a/gcd.intValue();
System.out.println(num1);
int num2 = b/gcd.intValue();
System.out.println(num2);
System.out.println(num1 + "/"+ num2);
}
X = input();
- ninhnnsoc April 25, 2014Y = 10000;
X = X*Y;
Z = Greatest_Common_Divisor_Of (X, Y);
return X/Z . "/" . Y/Z;