Merging balls interview problem

Question

Here is an interview problem about balls rolling towards buckets from Sprinklr Interview Experience at GeekforGeeks.

You are given $n$ balls on the table and all the balls are rolling towards the one end of the table with velocities $V_1, V_2, \dots, V_n$ and there is a bucket placed at that end. The distance of the ball with velocity $V_i$ from the end of the table where the bucket is placed is $D_i$. It is given that when two balls collide, both balls merge into each other and move with the velocity of the ball nearer to the bucket. So, at last, you have two tell the number of the balls which will fall into the bucket.

Here is what I am doing. First, I insert one extra ball in the array with zero velocity and distance zero. That is, I am inserting the bucket as a ball. We will find how many balls are getting merged with last ball.

Find a pair of adjacent balls which have the smallest value of $T = \frac{D_i - D_{i+1}}{V_i - V_{i+1}}$ and $V_i > V_{i+1}$ and remove ball with velocity $V_i$, that is, the first ball in the pair. Now for each remaining ball, reduce its distance by its velocity times $T$, and continue doing this process.

The number of time we will choose the bucket as the second ballwill be the final answer.

Can anyone suggest a better approach? My approach has time complexity of $O(n^2)$.

Answer 1

Keep all the values $\frac{D_i - D_{i+1}}{V_i - V_{i+1}}$ in a min-heap. At each step, remove the minimum value, say $T = \frac{D_i - D_{i+1}}{V_i - V_{i+1}}$. We would first like to update all unaffected pairs, using $D'_j = D_j - TV_j$. The affect this has on the ratios is $$ \frac{D'_j - D'_{j+1}}{V_j - V_{j+1}} = \frac{D_j - TV_j - D_{j+1} + TV_{j+1}}{V_j - V_{j+1}} = \frac{D_j - D_{j+1}}{V_j - V_{j+1}} - T. $$ In other words, their relative order does not change. However, the removed ball $i$ does affect one of the other ratios: instead of $\frac{D_{i-1}-D_i}{V_{i-1}-V_i}$ we now have $\frac{D_{i-1}-D_{i+1}}{V_{i-1}-V_{i+1}}$. So we remove the former and insert the latter instead.

Constructing the min-heap in the beginning takes time $O(n\log n)$. Afterwards, we perform $O(n)$ operations on the min-heap, each of which runs in $O(\log n)$, and so the total running time is $O(n\log n)$.

Answer 2

Calculate a time value for each ball ($D_i/V_i$). Assume bucket is on the right. Find the ball with largest time value, say ball $i$. Then all balls to the left of ball $i$ will merge into ball $i$ before they fall into the bucket. Remove those balls, and repeat the step until no more balls. I don't think it is linear time.

Answer 3

Not sure if I understand this right. My understanding is this: If the ball furthest away would move at incredibly high speed so it can catch up with all the other balls, then it will collide with all of them and only one ball would fall into the bucket.

If this is right, then the problem is easy: Calculate the time when each ball would drop into the net if there were no other balls. Find the ball that would drop earliest and remove all balls that started out ahead of it, that is one drop. Then as long as there are other balls, find again the ball that would drop earliest and remove all balls that started ahead of it.

I think this can be done in linear time if the balls are sorted by distance: For each ball, calculate the drop time. Go through the balls one by one. For each ball, as long as it arrives earlier at the net than the ball starting before it, remove the ball before it, and you will be left with k balls that arrive in ascending order.