Google Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
So you do not count digits left to decimal ?
It says first N digits of rational no
So 42.1673 and N = 2 should return 42 and not 42.16
42.1673 N = 1 must be 4 and N=3 must be 42.1
So you do not count digits left to decimal ?
It says first N digits of rational no
So 42.1673 and N = 2 should return 42 and not 42.16
42.1673 N = 1 must be 4 and N=3 must be 42.1
Whoops, my mistake JW. From the expected result of the problem statement your solution is correct.
"the result should be "1.66666". N=2: 1.66"
Your code prints out complete garbage.
Say you had 5/3. Then you get the first digit right : 1. However 5%3=2*10=20/5=4. This is clearly not correct since you would get 1.4 not 1.6 as needed.
What you should do is multiply numerator by numdigits, divide by denom, then place the "." as needed.
#include <stdio.h>
void print_ndigit(int d, int n, int count) {
int curr = d % n;
for (int i=0;i<count;++i) {
curr *=10;
printf("%d ", curr/n);
curr = curr % n;
}
printf("\n");
}
int main() {
print_ndigit(3227,555,6);
return 0;
}
class GetNDigitOfRationalNumber {
public double solution(int numerator, int denominator, int num) throws ArithmeticException{
double out = 0;
double temp = (float) numerator/denominator;
out = (int)(temp * Math.pow(10, num));
return (float) (out/Math.pow(10, num));
}
private String getOutput(int numerator, int denominator, int num) throws ArithmeticException{
String str = "";
int pre = (numerator/denominator + "").length();
double temp = (float) numerator/denominator;
str = str+temp;
System.out.println(str.substring(0,num+pre+1));
return str;
}
public double solution2(int numerator, int denominator, int num) throws ArithmeticException{
return Double.parseDouble(getOutput(numerator, denominator, num));
}
}
class GetNDigitOfRationalNumber {
public double solution(int numerator, int denominator, int num) throws ArithmeticException{
double out = 0;
double temp = (float) numerator/denominator;
out = (int)(temp * Math.pow(10, num));
return (float) (out/Math.pow(10, num));
}
private String getOutput(int numerator, int denominator, int num) throws ArithmeticException{
String str = "";
int pre = (numerator/denominator + "").length();
double temp = (float) numerator/denominator;
str = str+temp;
System.out.println(str.substring(0,num+pre+1));
return str;
}
public double solution2(int numerator, int denominator, int num) throws ArithmeticException{
return Double.parseDouble(getOutput(numerator, denominator, num));
}
}
public void formatRational(int numerator, int denominator, int N) {
String format = "%." + (N + 1) + "f";
String value = String.format(format, (numerator / (float)denominator));
int index = value.indexOf(".");
System.out.println(value.substring(0, index + 1) + value.substring(index + 1, index + 1 + N));
}
public void formatRational(int numerator, int denominator, int N) {
String format = "%." + (N + 1) + "f";
String value = String.format(format, (numerator / (float)denominator));
int index = value.indexOf(".");
System.out.println(value.substring(0, index + 1) + value.substring(index + 1, index + 1 + N));
}
void PrintNDigits(uint32_t num, uint32_t den, uint32_t max){
if (den == 0){
printf("Error");
}
else
{
// get integer of dividing 2 numbers
printf("%d.", num / den);
for (uint32_t i = 0; i < max && (num%den > 0); i++){
uint32_t val = num%den;
num = val * 10;
printf("%d", num / den);
}
}
printf("\n");
}
void PrintNDigits(uint32_t num, uint32_t den, uint32_t max){
if (den == 0){
printf("Error");
}
else
{
// get integer of dividing 2 numbers
printf("%d.", num / den);
for (uint32_t i = 0; i < max && (num%den > 0); i++){
uint32_t val = num%den;
num = val * 10;
printf("%d", num / den);
}
}
printf("\n");
}
string IntegerDivide(int num, int den, int n)
{
if (num == MINI && den == -1) throw overflow_error("result overflowed");
ll x = num, y = den; int sign = (x >> 31) == (y >> 31) ? 1 : -1;
x = abs(x); y = abs(y);
string integer = to_string(x / y * sign), decimal;
unordered_map<int, int> st; x %= y;
while (x != 0 && st.count(x) == 0 && decimal.size() < n)
{
st[x] = decimal.size(); x *= 10; decimal += to_string(x / y); x %= y;
}
if (x == 0)
{
decimal += string(n - decimal.size(), '0');
}
else if (st.count(x) != 0)
{
string tmp = decimal.substr(st[x]);
while (decimal.size() < n) decimal += tmp;
}
while (decimal.size() > n) decimal.pop_back();
return decimal.empty() ? integer : integer + "." + decimal;
}
public static void printRational(int a, int b, int n) {
String output = "";
int div, mod, currA, currB, i;
i = div = mod = 0;
currA = a;
currB = b;
output += (a/b)+".";
for (;i < n; i++) {
mod = currA % currB;
mod *= 10;
while (mod < currB) {
mod *= 10;
output += "0";
i++;
}
output += mod/currB+"";
currA = mod;
}
System.out.println(output);
}
#! /usr/bin/ruby
# Write a function which, given two integers (a numerator and a denominator),
# print the first N digits of a rational number. For example, for 5 / 3 with
# N=5, the result should be "1.66666". N=2: 1.66
numer = ARGV[0].to_i
denom = ARGV[1].to_i
digits = ARGV[2].to_i
def div(numer, denom, digits)
s = (numer / denom).to_s + "."
digits.times do |i|
numer %= denom
numer *= 10
s << (numer / denom).to_s
end
s
end
puts "Rational #{numer}/#{denom} => #{div numer, denom, digits}"
# vim:ts=2:sw=2:et:tw=120
#include <string>
#include <sstream>
using namespace std;
string div(int num, int den, int N) {
stringstream ss;
if (den == 0) return ss.str();
ss << num / den;
if (N == 0) return ss.str();
ss << ".";
int r = num % den;
for (; N > 0; --N) {
r *= 10;
if (r < den) {
ss << "0";
} else {
ss << r / den;
r = r % den;
}
}
return ss.str();
}
int main()
{
for (;;) {
int num;
std::cout << "Numerator: "; cin >> num;
int den;
std::cout << "Denominator: "; cin >> den;
int N;
std::cout << "N: "; cin >> N;
std::cout << "Result: " << div(num, den, N) << "\n";
}
}
private static String GetNDigitsOfRationalNum(int numer, int denom, int digits)
{
string valStr = (numer / (double)denom).ToString();
string integerPart, decimalPart;
int deci = valStr.IndexOf(".");
integerPart = valStr.Substring(0, deci);
decimalPart = valStr.Substring(deci + 1, digits + 1);
return integerPart + "." + decimalPart;
}
public static void printSizedDivision(int numerator, int divisor, int digits){
StringBuilder line = new Stringbuilder();
line.append(numerator / divisor);
line.append('.');
numerator %= divisor;
while(numerator > 0 && digits > 0){
numerator *= 10;
line.append(numerator / divisor);
numerator %= divisor;
digits--;
}
System.out.println(line.toString());
}
#include<stdio.h>
#include<conio.h>
int main()
{
int a,b,count=0,n,rem,cons1;
float count2=0.1,cons;
printf("enter the value of a and b:=>");
scanf("%d%d",&a,&b);
printf(" enter the value of N:=> ");
scanf("%d",&n);
while(n>0)
{
if(count==0)
{
cons=a/b;
rem=a%b;
count++;
}
cons1=(rem*10)/b;
cons=cons+cons1*count2;
rem=(rem*10)%b;
count2=count2*0.1;
n--;
}
printf("%f",cons);
return 0;
}
This is a trivial question:
{{
public class DivisionPrint {
public static void print(int num, int denom, int n) {
if (denom == 0) {
throw new RuntimeException("denom cannot be zero ...");
}
double result = (double) num / denom;
int res = (int) result;
String output = res + ".";
double precision = result - (double) res;
int fp = (int)(precision * Math.pow(10, n));
output += fp + "";
System.out.println(output);
}
public static void main(String[] args) {
DivisionPrint.print(5, 3, 5);
DivisionPrint.print(5, 3, 2);
}
}
}}
public void printNDigitsOfRationalNumber(int numerator, int denominator, int digits) {
String stringRep = (numerator / (double) denominator) + "";
int dotIndex = stringRep.indexOf(".");
String output = stringRep.substring(0, dotIndex);
for (int i = dotIndex, j = 0; i < stringRep.length() && j <= digits; i++, j++) {
output += stringRep.charAt(i);
}
System.out.println("Output: " + output);
}
package fraction generator;
import java.util.Scanner;
public class JavaApplication19 {
public static void main(String[] args) {
int nume,denume,n,temp_res,res1,i,rem;
float temp2,temp3,res;
System.out.println("enter numerator ,denominator ,and limit");
Scanner in=new Scanner(System.in);
nume=in.nextInt();
denume=in.nextInt();
n=in.nextInt();
res1=nume/denume;
res=res1;
rem=(nume%denume)*10;
for(i=1;i<=n;i++)
{
temp_res=rem/denume;
temp2=(float) Math.pow(0.1,i);
temp3=temp_res*temp2;
res=res+temp3;
rem=(rem%denume)*10;
}
System.out.println(res);
}
}
package fraction generator;
import java.util.Scanner;
public class JavaApplication19 {
public static void main(String[] args) {
int nume,denume,n,temp_res,res1,i,rem;
float temp2,temp3,res;
System.out.println("enter numerator ,denominator ,and limit");
Scanner in=new Scanner(System.in);
nume=in.nextInt();
denume=in.nextInt();
n=in.nextInt();
res1=nume/denume;
res=res1;
rem=(nume%denume)*10;
for(i=1;i<=n;i++)
{
temp_res=rem/denume;
temp2=(float) Math.pow(0.1,i);
temp3=temp_res*temp2;
res=res+temp3;
rem=(rem%denume)*10;
}
System.out.println(res);
}
}
Takes care of the sign, and just print the needed digits.
public string Division(int numerator, int denominator, int presicion)
{
if (denominator == 0)
throw new DivideByZeroException();
StringBuilder sb = new StringBuilder();
// The division takes care of the sign -
sb.Append(numerator / denominator);
numerator = Math.Abs(numerator);
denominator = Math.Abs(denominator);
numerator = (numerator % denominator) * 10;
if (numerator == 0)
return sb.ToString();
sb.Append('.');
while(presicion > 0 && numerator != 0)
{
sb.Append(numerator / denominator);
numerator = (numerator % denominator) * 10;
presicion--;
}
return sb.ToString();
}
Considere the sign and just print the needed digits.
public string Division(int numerator, int denominator, int presicion)
{
if (denominator == 0)
throw new DivideByZeroException();
StringBuilder sb = new StringBuilder();
// The division takes care of the sign -
sb.Append(numerator / denominator);
numerator = Math.Abs(numerator);
denominator = Math.Abs(denominator);
numerator = (numerator % denominator) * 10;
if (numerator == 0)
return sb.ToString();
sb.Append('.');
while(presicion > 0 && numerator != 0)
{
sb.Append(numerator / denominator);
numerator = (numerator % denominator) * 10;
presicion--;
}
return sb.ToString();
}
int abs(int n)
{
return (n < 0) ? -n : n;
}
void printFirstN(int N, int num, int denom)
{
cout<<num/denom<<".";
int count = 0;
int remainder = (num%denom)*10;
while(count < N)
{
cout<<abs(remainder/denom);
remainder = (remainder%denom)*10;
count++;
}
cout<<endl;
}
int main()
{
printFirstN(5,-5,3);
printFirstN(5,5,3);
printFirstN(2,-5,3);
return 0;
}
Approach:
Construct each digit of the result one at a time, most to least significant. You'll find long division does exactly this - dividing numerator into denominator and multiplying the denominator by 10 every time. Simply repeat this for however many decimal places you want.
- JW May 13, 2015