Interview Question
AccountantsCountry: India
#include "stdafx.h"
#include <math.h>
#include <iostream>
using namespace std;
#define STEPS 4
#define BUDGET 7
int _tmain(int argc, _TCHAR* argv[])
{
float p[STEPS + 1][BUDGET + 1]; // Probability that it worked on a particular step with a particular budget
int used[STEPS][BUDGET]; // machines used
float r[STEPS] = { .99f, .8f, .9f, .4f }; // Probability that a step works
int c[STEPS] = { 2, 2, 5, 2 }; // cost of a machine
int i, s;
for (s = 0; s <= BUDGET; s++) // for all amounts you spend
{
p[0][s] = 1.0f; // if you have not run any steps the prob is 1
}
for (i = 1; i <= STEPS; i++) // init the 0 spent colum
{
p[i][0] = p[i - 1][0] * r[i - 1];
}
for (i = 1; i <= STEPS; i++)
{
for (s = 1; s <= BUDGET; s++)
{
int nm = s / c[i - 1]; // number of extra machines we could get
float best = 0;
used[i - 1][s - 1] = 0;
for (int mi = 0; mi <= nm; mi++)
{
float sp = 1.0f - powf((1.0f - r[i - 1]), mi + 1); // step probability
int leftover = s - mi * c[i - 1];
float total_prob = p[i - 1][leftover] * sp; // probability so far
if (best < total_prob)
{
best = total_prob;
used[i - 1][s - 1] = mi; // set number of machines used at this stage
}
}
p[i][s] = best;
cout << used[i - 1][s - 1] << " " << best << endl;
}
cout << i << "---------------------------------------------------------------------" << endl;
}
int out[STEPS];
int left = BUDGET - 1; // need an offset becas used array index starts at 0
for (i = STEPS-1; i >= 0; i--) // get the result in reverse order
{
out[i] = used[i][left]; // save number of machines
int cost = used[i][left] * c[i]; //How much did they cost
left = left - cost; //how much do you have left
}
// Print the number of extra machines best employed for each step in the correct order
for (i = 0; i < STEPS; i++)
{
cout << out[i] << " ";
}
}
It looks like dynamic programming with either bottom up or memoization
- DR ADM June 10, 2017I get the following recurrence:
Let P be the probability of getting through i steps with a budget b
P(i, b)
C is a vector of machine costs
R is the vector of machine reliabilities
Let n be the number of extra machines you use to add to step i
P(i, b) = max( P(i-1, b - n * C[i]) * (1 – (1 – R[i]) * (n + 1))) for:
n = [0 to floor(b / C[i])] // from 0 to the largest number of such machines you could afford
Does this look right to you ?