Epic Systems Interview Question
Software Engineer / DevelopersHere is the Java Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Example1 {
public Example1(){
}
private void cashRegister(){
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter total cost....\n");
try {
double cost= cost = Float.parseFloat(br.readLine());
System.out.println("Enter total paid...\n");
double paid= Float.parseFloat(br.readLine());
if( paid>=cost){
double balance = paid-cost;
if(balance >=5){
int fives= (int) (balance/5);
balance = balance - 5*fives;
System.out.println("Give.$FIVES X "+fives);
}
if(balance >=1){
int ones= (int) (balance/1);
balance = balance - 1*ones;
System.out.println("Give.$ONES X "+ones);
}
if(balance >=0.25){
int quarters= (int) (balance/0.25);
balance = balance - 0.25*quarters;
System.out.println("Give.$QUARTERS X "+quarters);
}
if(balance >=0.10){
int quarters= (int) (balance/0.10);
balance = balance - 0.10*quarters;
System.out.println("Give.$DIMES X "+quarters);
}
if(balance >=0.05){
int nickels= (int) (balance/0.05);
balance = balance - 0.05*nickels;
System.out.println("Give.$NICKELS X "+nickels);
}
if(balance >=0.01){
int pennies= (int) Math.round(balance/0.01);
balance = balance - 0.01*pennies;
System.out.println("Give.$PENNIES X "+pennies);
}
}
} catch (NumberFormatException | IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
public static void main(String[] args0){
new Example1().cashRegister();
}
}
import java.util.Arrays;
public class ChangeBreakDown {
public static void main(String[] args) {
casher(10.25, 2000.0);
}
public static int units[] = { 10000, 5000, 1000, 500, 100, 25, 10, 5, 1 };
public static String unitsname[] = { "$100", "$50", "$20" };
public static void casher(double Worth, double Paid) {
int counter[] = new int[units.length];
int worthcents = (int) (Worth * 100);
int paidcents = (int) (Paid * 100);
int left = paidcents - worthcents;
int index = 0;
while (left > 0) {
counter[index] = left / units[index];
left = left % units[index];
index++;
}
System.out.println(Arrays.toString(units));
System.out.println(Arrays.toString(counter));
}
}
Enter total amnt
scanf("%f", actual);
Enter given amnt
scanf("%f", given);
if(given == actual)
{
printf("0");
}
else
{
float diff = given - actual;
while(diff > 0)
{
if(diff / 100 > 0)
{
printf("%d 100s", diff/100);
diff = diff%100;
break;
}
else if(diff/20 > 0)
{
printf("%d 20s", diff/20);
diff = diff % 20;
break;
}
else if(diff/10 > 0)
{
printf("%d 10s", diff/10);
diff = diff % 10;
break;
}
else if(diff/5 > 0)
{
printf("%d 5s", diff/5);
diff = diff % 5;
break;
}
else if(diff/1 > 0)
{
printf("%d 1s", diff/1);
diff = diff % 1;
break;
}
else if(diff/0.25 > 0)
{
printf("%d Quarters", diff/0.25);
diff = diff % 0.25;
break;
}
else if(diff/0.10 > 0)
{
printf("%d Dimes", diff/0.10);
diff = diff % 0.10;
break;
}
else if(diff/0.05 > 0)
{
printf("%d 5 cents", diff/0.05);
diff = diff % 0.05;
break;
}
else if(diff/0.01 > 0)
{
printf("%d cents", diff/0.01);
diff = diff % 0.01;
break;
}
}
}
#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
int pamt,intdiff,nten,nfiv,none,val,nten1,nfiv1;
float aamt,floatdiff,val1;
printf("\nPaid amount");
scanf("%d",&pamt);
printf("\nactual amount");
scanf("%f",&aamt);
intdiff=pamt-ceil(aamt);
floatdiff=(pamt-intdiff)-aamt;
cout<<intdiff;
cout<<endl<<floatdiff;
val=intdiff;
//chck if its divisible by 10
if(val/10>=0)
nten=val/10;
else
nten=0;
val=val-(nten*10);
//chck if its divisible by 5
if(val/5>=0)
nfiv=val/5;
else
nfiv=0;
val=val-(nfiv*5);
none=val;
val=val-none;//val will be zero
printf("\nno of ten dollar bucks=%d",nten);
printf("\nno of five dollar bucks=%d",nfiv);
printf("\nno of one dollar bucks=%d",none);
val1=floatdiff;
//chck if its divisible by 10
if(val1/0.1>0)
nten1=val1/0.1;
else
nten1=0;
val1=val1-(nten1*0.1);
//chck if its divisible by 5
if(val1/0.05>0)
nfiv1=val1/0.05;
else
nfiv1=0;
val1=val1-(nfiv1*0.05);
printf("\nno of ten cents=%d",nten1);
printf("\nno of five cents=%d",nfiv1);
system("PAUSE");
return 0;
}
<pre lang="" line="1" title="CodeMonkey93322" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));
String s;
while (!(s=r.readLine()).startsWith("42")) System.out.println(s);
}
}
</pre><pre title="CodeMonkey93322" input="yes">
</pre>
C++ code
#include<iostream>
using namespace std;
void notes(int);
void change(int );
int main()
{
double cost,payment;
cout<< "Cost of the product/meal :";
cin>>cost;
cout<<"How much did customer pay :";
cin>>payment;
double x = payment - cost;
if(x<0)
{
cout<<"Wrong inputs,Please try again"<<endl;
return 0;
}
int remainder = ( x - floor(x) ) *100;
int p = floor(x);
notes(p);
change(remainder);
return 0;
}
void change( int remainder )
{
if( remainder/25 != 0 )
{
cout<<"Quartes required :"<<remainder/25<<endl;
remainder = remainder%25;
}
if( remainder/10 !=0)
{
cout<<"Dimes required :"<<remainder/10<<endl;
remainder = remainder%10;
}
if( remainder/5 !=0)
{
cout<<"Five cents required :"<<remainder/5<<endl;
remainder = remainder%5;
}
if( remainder/1 !=0)
cout<<"Nickles required :"<<remainder/1<<endl;
}
void notes( int bills)
{
if(bills/20!=0)
{
cout<<"20 dollar bills required : "<<bills/20<<endl;
bills =bills%20;
}
if(bills/5!=0)
{
cout<<"5 dollar bills required : "<<bills/5<<endl;
bills=bills%5;
}
if(bills/1!=0)
cout<<"1 dollar bills required : "<<bills/1<<endl;
}
Here is the Java Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Example1 {
public Example1(){
}
private void cashRegister(){
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter total cost....\n");
try {
double cost= cost = Float.parseFloat(br.readLine());
System.out.println("Enter total paid...\n");
double paid= Float.parseFloat(br.readLine());
if( paid>=cost){
double balance = paid-cost;
if(balance >=5){
int fives= (int) (balance/5);
balance = balance - 5*fives;
System.out.println("Give.$FIVES X "+fives);
}
if(balance >=1){
int ones= (int) (balance/1);
balance = balance - 1*ones;
System.out.println("Give.$ONES X "+ones);
}
if(balance >=0.25){
int quarters= (int) (balance/0.25);
balance = balance - 0.25*quarters;
System.out.println("Give.$QUARTERS X "+quarters);
}
if(balance >=0.10){
int quarters= (int) (balance/0.10);
balance = balance - 0.10*quarters;
System.out.println("Give.$DIMES X "+quarters);
}
if(balance >=0.05){
int nickels= (int) (balance/0.05);
balance = balance - 0.05*nickels;
System.out.println("Give.$NICKELS X "+nickels);
}
if(balance >=0.01){
int pennies= (int) Math.round(balance/0.01);
balance = balance - 0.01*pennies;
System.out.println("Give.$PENNIES X "+pennies);
}
}
} catch (NumberFormatException | IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
public static void main(String[] args0){
new Example1().cashRegister();
}
}
public class CashChange {
// Assume sorted
private static final double[] denominations = { 20.0, 10.0, 5.0, 1.0, .5, .25,
.1, .05, .01 };
public static void main(String[] args) {
double amount = 25.39;
for (double denom : denominations) {
if (denom > amount) {
continue;
}
while (amount > 0 && denom < amount ) {
int num = (int) Math.floor(amount/denom);
System.out.println(num + " * " + denom);
amount -= (num * denom);
}
}
}
}
seems no one mentions this...if cost=29.21 paid=100 balance=71.789999999999 in some machines. you should deal with this. try BigDecimal for java.
import java.util.Scanner;
public class CashRegister
{
public static Double actual, bill;
public static int balance, notes, i =0;
public static void main(String[] args)
{
System.out.println("Please enter actual cost in $");
Scanner br = new Scanner(System.in);
actual = br.nextDouble();
System.out.println("Please enter customer's bill value in $");
Scanner br1 = new Scanner(System.in);
bill = br1.nextDouble();
System.out.println("Total balance is " + "$"+(bill-actual));
actual = actual*100;
bill = bill*100;
balance = (int) (bill-actual);
System.out.println("Denomination is");
if(balance/2000 >0)
{
balance(2000);
}
else if(balance/1000>0)
{
balance(1000);
}
else if((balance/500) > 0)
{
balance(500);
}
else if(balance/100 >0)
{
balance(100);
}
else if(balance/25 >0)
{
balance(25);
}
else if(balance/10>0)
{
balance(10);
}
else if(balance/5 >0)
{
balance(5);
}
else System.out.println(balance +" - 1cents");
}
public static void balance(int amt)
{
while(balance>=5)
{
notes = balance/amt;
balance = balance%amt;
if(amt==2000)
{
System.out.println(notes+" - "+ (amt/100)+"Dollars");
amt =1000;
}
else if(amt == 1000)
{
System.out.println(notes+" - "+ (amt/100)+"Dollars");
amt =500;
}
else if(amt == 500)
{
System.out.println(notes+" - "+ (amt/100)+"Dollars");
amt = 100;
}
else if(amt == 100)
{
System.out.println(notes+" - "+ (amt/100)+"Dollars");
amt = 25;
}
else if(amt == 25)
{
System.out.println(notes+" - "+ amt+"cents");
amt = 10;
}
else if(amt ==10)
{
if(notes!=0) System.out.println(notes+" - "+ amt+"cents");
amt = 5;
}
else if(amt ==5) System.out.println(notes+" - "+ amt+"cents");
}
if (balance!=0) System.out.println(balance+" - 1cents");
}
}
Just one quick reminder, you know there are 2 dollar bills and half dollar coin, which means the optimal solution for the question is actually not 1 five 4 ones and 3 quarters, but 1 quarter, 1 half dollar, 2 two dollar bills and 1 five dollar bill.
Greedy is definitely recommended for coin change problem using american coin system. But general problems need regular DP. A bottom DP solution is as follow (with traceback)
vector<int> minCoin(vector<int> base, int total) {
sort(base.begin(), base.end());
vector<int> rec(total+1, 0);
vector<int> coin(total + 1, 0);
for (int i = 1; i <= total; ++i) {
int localMin = INT_MAX-1;
int candcoin = 0;
for (auto cand : base) {
if (i - cand < 0) continue;
if (rec[i - cand] + 1 < localMin) {
candcoin = cand;
localMin = rec[i - cand] + 1;
}
}
rec[i] = localMin;
coin[i] = candcoin;
}
if (rec[total] == INT_MAX - 1) return vector<int>();
vector<int> ret;
while (total) {
ret.push_back(coin[total]);
total -= coin[total];
}
return ret;
}
Playable version at
ideone.com/GfxnF8
Tried with Java
- rohith.sankarraman September 09, 2011import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class AAC {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter total cost");
try {
double cost = Double.parseDouble(br.readLine());
System.out.println("Enter the amount paid");
double amount = Double.parseDouble(br.readLine());
double ret = amount - cost;
int one = 0, five = 0, ten = 0, quart = 0, quarter = 0, nickel = 0, dime = 0, cent = 0;
while(true){
System.out.println(ret);
if(ret >= 10){
ten++;
ret -=10;
}
else if(ret >= 5){
five++;
ret -= 5;
}
else if(ret>=1){
one++;
ret -= 1;
}
else if(ret >= 0.25){
quarter++;
ret -= 0.25;
}
else if(ret>=0.10){
dime++;
ret -=0.10;
}
else if(ret>=0.05){
nickel++;
ret -= 0.05;
}
else if(ret>=0.01){
cent++;
ret -= 0.01;
}
if(ret <= (double)0){
break;
}
}
System.out.println("Tens = "+ten+" Five = "+five+" One = "+one+" Quarter = "+quarter+" dime = "+dime+" nickel = "+nickel+" cent = "+cent);
} catch (NumberFormatException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}