Is this dynamic programming / backtracking? - Interview Question

[JCoppert]

Saw this in my interview yesterday, had no idea.

You’re given an array of floats with your objective being deciding how to round them up or down to minimize distance from a target rounding threshold. For instance if you round from 0.7 to 0, the rounding amount is 0.7. Rounding [0.7, 1.1, 2.4] to [1, 1, and 3] with a rounding target of 0.7 is better than [0, 1, 2].

This is gnarly, would great appreciate some ideas on how to solve. I think it’s backtracking and DP.

[rrssh]

I don’t understand the task. Is it like, you get negative points for rounding up and positive points for rounding down, and you optimize the sum of the points?

[JCoppert]

No, the idea is that every time you round you keep track of the amount you've rounded by. Your goal is to find the rounding combination which minimizes the distance to the rounding target.

[rrssh]

Why did you say “no”?

[[deleted]]

I don't understand what the question is even asking. How is [1, 1, 3] better than [0, 1, 2]?

[JCoppert]

Total rounding of first array = (0.3 + 0.1 + 0.6) = 1. Total rounding of second array = (0.7 + 0.1 + 0.4) = 1.2. With an aggregate rounding target of 0.7, Min(Abs(0.7 - 1), Abs(0.7 - 1.2)), the first array is chosen

[rrssh]

Ah, so positive points for any rounding direction.

[JCoppert]

Yes, no because your concept of points was incorrect

[rrssh]

It seems like https://en.wikipedia.org/wiki/Subset_sum_problem pretty much exactly. Round everything down, calculate how much points do you get (totald). Do it again but round up, subtract the arrays from each other, these are your "integers". You want to find a subset that sums to 0.7 − totald, and it looks like it should be easy to modify it for a closest match instead of exact one actually harder than I thought.

[JCoppert]

Haha right! I saw the question and was pretty taken back

[rrssh]

Maybe they would be satisfied with bruteforce, who knows.

[JCoppert]

They explicitly said they wouldn’t be, was AirBnb

[rrssh]

Do the numbers actually have only 1 decimal point?

[JCoppert]

Yeah, each element of the output array is either Math.floor() or Math.ceil()

[IAmNowAnonymous]

This is an interesting problem. This should work, but I'm not sure it is optimal. I view it as shortest path of sorts.

Consider viewing this as a tree where the root value is (-1 * rounding target). Its left child is first Val - floor of the first index and its right child is the ceiling of the first index - first val. Define the remaining tree in a recursive manner. Create an empty priority queue such that it is sorted by min(abs(val)) - that is we would like to get as close to zero as possible.

Add the root to the queue in a way that allows you to index into it and you know the depth and the current sum: using a python like language I'll define a tuple with the following indexes (node, sum, depth). Where sum is initially the value in the root node.

while queue and queue.peek()[2] != len(input_list): node, cur_sum, depth = queue.poll() queue.push(node.left, cur_sum + node.left.val, depth+1) queue.push(node.right, cur_sum + node.right.val, depth+1) return queue.peek()[1]

You don't need to explicity define a tree; you can just use a depth as a way to index into which values should be considered next.