Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
March 2, 2018 - 12:00 PM mock interview discussion about the algorithm.
/*
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.