Google L4 SWE3

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.