google logo
Google· L4 SWE3

Google L4 SWE3

Posted
8 Apr 2025
385 reads

Summary

I was asked a challenging optimization problem about ice cream sellers and kids, requiring finding a minimum range for sellers to cover all kids. I initially provided an O(nklog(max-min)) solution and later thought of an O(nlogK) improvement.

How it went

There are K ice cream sellers who need to distribute ice creams to the kids of Ice-Town. Ice-Town can be represented as the x-axis where kids are standing at different x coordinates, which are given to you. A seller can only serve kids which are in his range, for example, if a seller is placed at X and his range is E then all kids in the range [X−E, X+E] can get ice creams from them. All the sellers have an equal range E.

Since the sellers are lazy so they want you to find the minimum range E such that all the kids in Ice-Town can get ice creams.

Both the sellers and children coordinates are given in arrays as input.

Answer:

Sort the seller and binary search on the min, max of the children coordinates as range.

Final complexity of my answer came out to be O(nklog(max-min)). The interviewer said the factor k could be improved.

After the interview I though of nlogK solution. For a given kid, you find the closest seller using binary search. If the kid’s coordinate exactly matches a seller, then the distance is 0. Otherwise, the binary search returns a negative insertion point indicating where the kid’s coordinate would be inserted; then you compare the seller immediately to the left and to the right of that insertion point.

Questions asked (1)

  1. 01

    Minimum Range to Cover All Kids with K Sellers

    Data Structures & Algorithms

    There are K ice cream sellers who need to distribute ice creams to the kids of Ice-Town. Ice-Town can be represented as the x-axis where kids are standing at different x coordinates, which are given to you. A seller can only serve kids which are in his range, for example, if a seller is placed at X and his range is E then all kids in the range [X−E, X+E] can get ice creams from them. All the sellers have an equal range E.

    Since the sellers are lazy so they want you to find the minimum range E such that all the kids in Ice-Town can get ice creams.

    Both the sellers and children coordinates are given in arrays as input.

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Google recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!