patternMinor
Merging balls interview problem
Viewed 0 times
probleminterviewballsmerging
Problem
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)$.
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)$.
Solution
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)$.
$$
\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)$.
Context
StackExchange Computer Science Q#104374, answer score: 4
Revisions (0)
No revisions yet.