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.

2 Likes

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
//