Here is the interview question prompt, presented for reference.

On a given street, there's a bunch of houses and lamps nearby. It looks kind of like the following (H being houses, L being lamps):

L H L H H
0 1 2 3 4

We decide to represent this with two arrays: one being the positions of the houses, and the other the positions of the lamps. From the above example, the arrays would be:

houses = [1, 3, 4]
lamps = [0, 2]

With this knowledge, can you find out the minimum radius that the lamps would need to cover in order for every house to get access to light?

Here, the minimum radius would be 2-- the lamp at position 2 needs to cover not only house 3, but up to the house on position 4, so a 2 radius is required.

L H L H H
0 1 2 3 4

We can guarantee that there is at least one house and one lamp in every scenario. All lamps cover the same minimum radius.

Constraints

• Length of the given array <= 100000
• Values in the array ranges from 0 to 100000
• Expected time complexity : O(n^2)
• Expected space complexity : O(1)

You can see the full challenge with visuals at this link.