Knight's Tour on Infinite Chessboard | Dataford Interview Questions

Write a search algorithm to move a chess knight on an infinite chess board.

Asked in the Coding Round stage. Algorithmic coding problem given during a Google technical interview.

Input and Output

Implement knight_shortest_path(start, target), where start and target are two-element integer lists [x, y]. Return a list of board coordinates beginning with start and ending with target, representing a shortest valid knight path. If both positions are equal, return a list containing that position.

Constraints

start and target each contain exactly two integers
Coordinates may be positive, zero, or negative
The board is infinite and has no boundaries
A valid path always exists on an infinite chessboard
Return one shortest path, using the listed move order to make the result deterministic

Function Signature

def knight_shortest_path(start, target):

Your question is Knight's Tour on Infinite Chessboard. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem