Question:
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 an optimal solution
My approach:
Go 1 step forward, 2 step back ward
Go 2 step forward, 4 step back ward and so on
Complexity:
Lets say the required object is at point n.
Total number of steps:
3 + 6 + 9 + .... n
= 3(1 + 2 + 3 ... n)
= O(n^2)
Is there a way to improve the efficiency?
12
What do you mean by ‘optimal solution’ ?
Make as few steps as possible?
I would not increase the distance from the start point by 1 every time, because after some time you nearly always visit a position you already visited and the ratio of new visited points converges to 0. I would use a pattern that guarantees that we always visit a fixed ratio of new points.
E.g
r: right step
l: left step
x
r new: 1 old: 0
ll new: 2 old: 1
rrrr new: 4 old: 3
llllllll new: 8 old: 7
rrrrrrrrrrrrrrrr new:16 old:15
This way the ratio of already visited positions to new visited positions id always about 1:1.
1
An exponential growth strategy runs O(n) time, average and worst case. This is optimal if you disregard constant factors. If you want to optimize the constant factor as well, you need to make some assumption about the probability distribution.
For example if you use a doubling strategy, the maximal cost is 7*n
dist = 1
loop
MoveTo(dist)
MoveTo(-dist)
dist = dist * 2
9
Assuming:
- Each step costs time
- There is no predicting where this object is on the infinite “line” of steps
- That you can’t fork or clone your self
- That you only gain more information once you’re on the object (no hints as you go)
Then pick a direction at random and just start walking. No expensive backtracking. Sure it might be one step behind you but that’s just the end of infinity right there.
O(n)
14
On an infinite line you will never find the object. Infinity is a weird thing. i.e. pick a point on a finite line, as the length of the line approaches infinity the probability that the point you picked is the object approaches zero.
Some things that might make this problem meaningful
- The line is finite (some number N)
- The object can only be at discrete points.
I would image that in these cases the optimal (fewest number of steps) solution would be to walk in one direction until you find the object or reach the end. If you reach the end you would turn around.
3