Product Management interview question [Technical]: Write an algorithm for a robot that has to get from point A to point B.

picture credit — unsplash

I have a few clarifying questions before I start working on the problem -

1. Can the robot travel diagonally if say point A and B are placed on the diagonal vertex of a rectangle? — No it can’t
2. Is the plane 2D or 3D? — Consider it 2D for simplicity
3. Does the Robot have to use the shortest path between A and B? — No it can travel any path it takes less time to reach the destination
4. Do we take into account curved paths or just straight paths? — Just the straight paths
5. Are there any obstacles in between or a clear path? — Yes, there are obstacles
6. In that case, are the Obstacles in each route known already or will they be known once the Robot reaches those obstacles? — Already known
7. Can I take a constant time required for the robot to overcome an obstacle, say 2 seconds? — Yes, that works
8. Can I assume that the Robots move in values of 1 — for example robot is at coordinate 2 on x-axis, the next time it moves to the right it reaches 3 on x-axis for simplicity? — Yes you can assume that

Thank you! Now I’ll start formulating an algorithm for the robot to reach its destination in the shortest time.

So there are 4 steps that I figured out will be required to move the robot from point A to B. These steps in-turn form the 4 functions that we need to implement in order to form the algorithm. These steps are -

1. Finding the Perpendiculars of point A and Point B which means the coordinates at which a perpendicular from point A and B intersects with coordinates axes.
2. Find all the paths between point A and point B — Finding the coordinates between point A and point B on which the Robot can travel in a straight line. This can be found by the logic that if the x coordinate of Robot is less than the x coordinate of the perpendicular dropping from B then the robot moves in the Right direction. Similarly if the y coordinate of Robot is less than the y coordinate of the perpendicular dropping from B then the robot moves in the Up direction. All these paths can be found by permutations of these conditions.
3. Once all the paths have been found, we’ll know the number of obstacles in each path and this can be calculated by the time taken to overcome each obstacle (in this case we have assumed 2 seconds). This gives the minimum time it takes to travel from point A to point B, and the path taken to take this minimum time.
4. Once we know the path (it looks something like an array of tuples that contain the coordinates that the robot needs to reach after each move to finally reach its Destination i.e. Point B — [(0, 0),(0, 1),(1, 1)… ]) a similar logic as that of point 2 can be used to move the Robot i.e. for each element of Path array if the first element i.e the x coordinate is greater than the x coordinate of robot’s current position then robot’s current position == x coordinate of the array element. Similarly if the y coordinate is greater than the y coordinate of robot’s current position then robot’s current position == y coordinate of the array element.

The pseudo code for the above algorithm will look something like -