3
$\begingroup$

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)$.

$\endgroup$
  • 1
    $\begingroup$ By the way, I (strongly) recommend that you do not follow those problems even if you are only interested in the companies selected. It might not be stated correctly. It does not come with an online judge that you can submit solutions and check result. It does not have a support forum or discussion board. Of course, it is up to you to choose. $\endgroup$ – Apass.Jack Feb 14 at 21:30
  • 1
    $\begingroup$ Have you read the minimal scholarly requirements? I edited the question to show that those references should be included in the question. People and search engines are not expected to read the comments. $\endgroup$ – Apass.Jack Feb 14 at 21:42
3
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ How would a self-balancing tree help? $\endgroup$ – Yuval Filmus Feb 15 at 9:34
  • 1
    $\begingroup$ Keep an array of pointers to all entries, and maintain it during the heap operations. $\endgroup$ – Yuval Filmus Feb 15 at 9:42
  • $\begingroup$ You said, remove the former and insert the latter, But finding latter will be O(n) time complexity. $\endgroup$ – Manoharsinh Rana Feb 15 at 18:42
  • 1
    $\begingroup$ @ManoharsinhRana Maintain a doubly linked list of surviving balls. $\endgroup$ – Yuval Filmus Feb 16 at 2:35
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In your first example, with the furthest-away ball at incredibly high speed, it would slow down to the speed of the first ball it collides with. $\endgroup$ – j_random_hacker Feb 17 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.