#Google OA

1 messages · Page 1 of 1 (latest)

strange fox
#

A smarter option would be to first sort the heights then setting moveCost = min(movCost, addCost+deleteCost)

#

moving should almost always be preferred - because its two move in one
So, we need to figure out

  1. when we cannot use move - and if cumulative delete operations or addition operation are cheaper
  2. How to move a bunch of blocks at once
#

Adding a bunch of block or subtracting a bunch of blocks is super easy

#

For addition

  • find max val - and then calculate maxHeight-column height for every row and add them up - now we have the total number of blocks we need to add and can multiply it by our addCost
#

Subtraction is similarly easy

  • Find min column - then subtract the min column from every other column and calculate the total number of blocks needed to be deleted - now just multiply our answer with the delete cost
#

So,
If we can know when using move is no longer feasible - we can find either the last addAllStep or the deleteAllStep to calcualte our answer in O(n)

#

At-least that's what I am thinking so far

toxic hamlet
#

I see

#

I just read the LC problem and it seems they tackled the question by finding a target height to meet - the median of the array

toxic hamlet
strange fox
#

so imagine we have [1,2,3,4,4]
subtract maxHeight from each row we get [3,2,1,0,0] - which are the number of blocks we need to add to each column to make everything equal using only add

#

so if sum them up 3+2+1=6 and multiply it by our addCost

#

we get the cost it will take to equalize the array in one O(n) step

#

Although that won't necessarily be the best way - since we have both delete and addition
Then we can just cut till the median

#

So on one side of the median u would use the addition operation and on the one side u would use the delete operation - this would be optimal when delete and add cost the same

strange fox
#

So, if addition and deletion are comparable in cost then we can calculate the percentile to find Xth percentile and then delete all elements left of our partition and add to all elements to the right
So, the simple only add case is when we are looking at the 0th percentile or then total min - which means we only need to add
If both cost are equal then we just need to use the 100th percentile or the total max
If both cost are equal we will use the 50th percentile or the median

#

We still need to figure out how to calculate the percentile - but again - most of the time we would prefer to use the move operation - this addition or subtraction step - is our last step

#

Actually, wait if we calculate the average then I can calculate bigger then the rounded average and use it calculate the number blocks I need to move

#

That tells us how many blocks we can move in one move operation

#

[2,11,16,28,36,47,53,54]
average = 30.875 ~= 31
[29,20,15,3,-5,-16,-22,-23] sum=1 -
so we need one more
block to equalize the row

#

So, now we have to consider which is cheaper
to either add one more block e.g 1*addCost
or, (n-1)* deleteCost

#

now which ever one is cheaper we would do that operation to finish our operation

#

I am going to try and see if I can see a reason the approach has to work - or figure out where it doesn't

#

Okay got it, imagine we want to find an integer x so that if we subtract x from each element we want the cumulative sum to be as close to 0

  • whether we want to err on the side of positive or negative 0 will depend on the addCost and deleteCost value - but for now let's just imagine our goal is to get as close as possible
    Well if we subtract the exact average from every element we get 0
    Average*number of elements = sum of elements => sum of elements - (Average*number of element) = 0
#

Okay, so current algorithm the problem breaks down into 4 cases

  1. find ceiling of average and do our moveAll
    • try addAll to finish equalizing
    • try subtractAll to finish equalizing
  2. find floor of average and do our moveAll
    • try addAll to finish equalizing
    • try subtractAll to finish equalizing
      The min of the four possibility must be our answer
toxic hamlet
#

great break down of the probelm ,just went through it

#

it appears there's some proof on why median works

#

instead of mean

#

im not going to attempt it yet because i have another interview coming up that requires more frontend skills but will try to tackle implementation next week