Puzzle for interview

there is an infinite line.you are standing at a particular point you can either move 1 step forward or 1 step backward.you have to search for an object in that infinite line.your object can be in any direction. Give optimal algorithm.


You got to have some hueristic search somewhere or some more constraints. Otherwise, no hope I guess.

From zero; move to 1 then towards -1 then 2 then -2 then 3 and so on…

Move to 1

Move to -1

Move to 2

Move to -2

Move to 4

Move to -4

Move to 8

Move to -8

and so on, until you find your item.

@mseghal That approach is pretty slow. If the item si at 10 you wil do a lot of steps. The number of steps is roughly proportional to |X|^2 where X is the position of the point on the Ox line (you can rotate the line to match the Ox). A better algorithm works as follows:

From 0 go 1 step forward, 2 backward, 4 forward, 8 backward, … and so on. You’ll do at most 4|X| steps to find the object which is the best complexity you could achieve because its O(|X|) and you can not do better than that.

1 Like

even second type of binary search is possible. Move to 1, -2, 4, -8, 16 etc. But I’m not sure which gives you less steps and I’m too lazy to count it :slight_smile:

From what i can see my approach is a little better on average versus yours. (by some small percentange about 10%).

yes it’s possible. But these two approaches are only one, you should try at first.

So i did a small benchmark. Both algorithms for N up to 100.000 calculating the average ratio (number of steps divided by |X| where X is the position).

For 1 million mine is 5.4089 and yours is 5.21163 and that seems to be the real ratio as |X| grows. Yours also does better for up until a few thousands where mine becomes better for up until 200.000.

But these doesn’t measures spikes so I also calculated it with the quadratic mean(adding the squared ratios and extracted the square root in the end) and the same with the power of 3.

For quadratic sums I have : 5.6757 and you have 5.4667.

For powers of 3 I have 5.9285 and you have 5.712. From this we can infer that your solution is better in practice as the limit goes to infinity. Sorry for presuming otherwise.

1 Like