March 2, 2018 - 12:00 PM mock interview discussion about the algorithm.

NewBudgetCut_Analysis_Discussion

/*
Julia gave out her analysis to solve the problem as an interviewer:

2 50 100  120 1000 
------------------> search range for cap value 
if cap > 2 -> cap > 2, 50*4 => 200 cap < 50, dont register 50
  188/4 = 47 
if cap > 50 -> cap >= 50 -> prefixSum = 2, 188/ 4 = 47 < 50 , cap
  then what is my cap value -> 
  using dynamic programming, prefix sum 
  prefix sum -> consumption -> 2, budget 190, how much available for rest of array?
    190 - 2 = 188, 
  5 - 1 = 4
if cap > 100

The peer worked on his analysis based on average value, time complexity: O(N)
The analysis has a bug inside and could not solve the problem. 

// [2,4,100,50,120,1000] - 194
double x = newBudget / grantsArray.Count();
190/5 = 38  O(1) , < - average value may not be cap value, cap 47 
4<38, 2<38 .. 
all elements less than 38 -> le[2,4] = 6, 194-6 = 188, 

newCount = count(newgrantsarry) - count(le) .... O(1)
188/4 = 47  O(1)

cap = 47;
O(n)

MergeSort - O(n logn)
  
// [3,47,47,47,47]  cap = 46.75 , new budget