Write Algorithm – interview question

[Singleton]

Percentage of trading in bank between 8:00 to 12:00 is as follows.
8:01 - 9:00 20% [i.e each minute is 1/3 %]
9:01 - 10:00 40% [i.e each minute is 2/3 %]
10:01 - 11:00 30% [i.e each minute is 1/2 %]
11:01 - 12:00 10% [i.e each minute is 1/6 %]
--------------------------------------------------------------------------
Total 100%

Now write an algorithm which will take start time and end time and calculates the % of trading done.
For example:-trading between 8:45 – 9:00 is 15 * 1/3 = 5%
Trading between 8:45 – 11:30 is
15 * 1/3 + 40 + 30 + 30* 1/6 = 80%

I couldn’t said answer then and there, But said my approach as follows.
First I will write a function wich will take start time and end time forms an array as follows [8:45, 9:00, 10:00, 11:00, 11:10]
Then I will write a recursive function will traverse through this array and calculates the total percentages!!!
They are no takers .. any solutions…

[wendigo100]

What was wrong with that?

[Singleton]

they expected more simple one

[AtW]

Christ, is it what they pay stupid money for working in Banks?

-------------------------------------------------------
8:01 - 9:00 20% [i.e each minute is 1/3 %]
9:01 - 10:00 40% [i.e each minute is 2/3 %]
10:01 - 11:00 30% [i.e each minute is 1/2 %]
11:01 - 12:00 10% [i.e each minute is 1/6 %]
-------------------------------------------------------

1) you need simple function - CalcTradingRatio that accepts the following arguements:

a) %-tage of trading in given period
b) period start time, ie 8:01
c) period end time, ie 9:00
d) current time: this can be
d1) INSIDE period - in this case you calculation and return fraction of parameter a)
d2) BEFORE period starts (ie smaller then b) - return 0
d3) AFTER period ends - return full value a)

2) macro function that calls 1) for all periods:

string sCurTime="8:55";
int iTradingDone=0;

iTradingDone+=CalcTradingRatio("20","8:01","9:00", sCurTime);
iTradingDone+=CalcTradingRatio("40","9:01","10:00" ,sCurTime);
iTradingDone+=CalcTradingRatio("30","10:01","11:00 ",sCurTime);
iTradingDone+=CalcTradingRatio("10","11:01","12:00 ",sCurTime);

--

There done - pretty simple.

A faster way however is to split all periods into minutes and calculate cumulative trading done up to any given minute - put it all into array, then in order to calculate trading done in any given time you just calculate number of minutes from 8:00am and just look up trading value in array - this is very fast as pre-computation is needed only once.

Can't see ANY need for recursion here.

[RSoles]

For example:-trading between 8:45 – 9:00 is 15 * 1/3 = 5%
Trading between 8:45 – 11:30 is
15 * 1/3 + 40 + 30 + 30* 1/6 = 80%

Err, isn't the example above the algorithm you need?

One golden rule of recursion:-

"Never use recursion"

Computers' resources are finite, recursion's appetite for resources isn't.

[Rebecca Loos]

no need to external functions:


IF $EndTime between 8 and 9 THEN
$tradeperc = 100 * (1/3) * ($EndTime - 8)
ELSEIF $EndTime between 9 and 10 THEN
$tradeperc = 20 + 100 * (2/3) * ($EndTime - 9)
ELSEIF $EndTime between 10 and 11 THEN
$tradeperc = 60 + 100 * (1/2) * ($EndTime - 10)
ELSEIF $EndTime between 11 and 12 THEN
$tradeperc = 90 + 100 * (1/6) * ($EndTime - 11)
END IF

IF $StartTime between 8 and 9 THEN
$tradeperc = $tradeperc - 100 * (1/3) * ($Starttime - 8)
ELSEIF $StartTime between 9 and 10 THEN
$tradeperc = $tradeperc - (100 * (2/3) * ($StartTime - 9) + 20)
ELSEIF $StartTime between 10 and 11 THEN
$tradeperc = $tradeperc - (100 * (1/2) * ($StartTime - 10) + 60)
ELSEIF $StartTime between 11 and 12 THEN
$tradeperc = $tradeperc - (100 * (1/6) * ($StartTime - 11) + 90)
END IF

Assuming $StartTime < $EndTime, check not made here...

[AtW]

no need to external functions:

Compare your code with mine:

iTradingDone+=CalcTradingRatio("20","8:01","9:00", sCurTime);
iTradingDone+=CalcTradingRatio("40","9:01","10:00" ,sCurTime);
iTradingDone+=CalcTradingRatio("30","10:01","11:00 ",sCurTime);
iTradingDone+=CalcTradingRatio("10","11:01","12:00 ",sCurTime);

Now which one is clearer and which one is more maintainable? Who is likely to make mistake -- you with great many IFs, or me with few?

Modern compiles will inline small functions - the fact that its "external" is of no consequence to performance, but for the sake of readability and reliability it makes sense to keep these things external rather than develop spagetting code like the one you shown -- if you made mistake in some of the ratios then I would not be able to see it from your code, its just a mess.

[Singleton]

no need to external functions:


IF $EndTime between 8 and 9 THEN
$tradeperc = 100 * (1/3) * ($EndTime - 8)
ELSEIF $EndTime between 9 and 10 THEN
$tradeperc = 20 + 100 * (2/3) * ($EndTime - 9)
ELSEIF $EndTime between 10 and 11 THEN
$tradeperc = 60 + 100 * (1/2) * ($EndTime - 10)
ELSEIF $EndTime between 11 and 12 THEN
$tradeperc = 90 + 100 * (1/6) * ($EndTime - 11)
END IF

IF $StartTime between 8 and 9 THEN
$tradeperc = $tradeperc - 100 * (1/3) * ($Starttime - 8)
ELSEIF $StartTime between 9 and 10 THEN
$tradeperc = $tradeperc - (100 * (2/3) * ($StartTime - 9) + 20)
ELSEIF $StartTime between 10 and 11 THEN
$tradeperc = $tradeperc - (100 * (1/2) * ($StartTime - 10) + 60)
ELSEIF $StartTime between 11 and 12 THEN
$tradeperc = $tradeperc - (100 * (1/6) * ($StartTime - 11) + 90)
END IF

Assuming $StartTime < $EndTime, check not made here...

WoW!! I really like that solution ..

[Singleton]

Christ, is it what they pay stupid money for working in Banks?

-------------------------------------------------------
8:01 - 9:00 20% [i.e each minute is 1/3 %]
9:01 - 10:00 40% [i.e each minute is 2/3 %]
10:01 - 11:00 30% [i.e each minute is 1/2 %]
11:01 - 12:00 10% [i.e each minute is 1/6 %]
-------------------------------------------------------

1) you need simple function - CalcTradingRatio that accepts the following arguements:

a) %-tage of trading in given period
b) period start time, ie 8:01
c) period end time, ie 9:00
d) current time: this can be
d1) INSIDE period - in this case you calculation and return fraction of parameter a)
d2) BEFORE period starts (ie smaller then b) - return 0
d3) AFTER period ends - return full value a)

2) macro function that calls 1) for all periods:

string sCurTime="8:55";
int iTradingDone=0;

iTradingDone+=CalcTradingRatio("20","8:01","9:00", sCurTime);
iTradingDone+=CalcTradingRatio("40","9:01","10:00" ,sCurTime);
iTradingDone+=CalcTradingRatio("30","10:01","11:00 ",sCurTime);
iTradingDone+=CalcTradingRatio("10","11:01","12:00 ",sCurTime);

--

There done - pretty simple.

A faster way however is to split all periods into minutes and calculate cumulative trading done up to any given minute - put it all into array, then in order to calculate trading done in any given time you just calculate number of minutes from 8:00am and just look up trading value in array - this is very fast as pre-computation is needed only once.

Can't see ANY need for recursion here.

Sorry, I didn't get that one .. lets say start time is 8:15 and end time is 10:50 tell me how your solution works?

[Rebecca Loos]

AtW, I agree your solution is more elegant than mine

But I wrote it in one single block on the grounds that the bank rejected a solution with an external function call