Shell Path Autocomplete
Figma● MediumFULLTIMEPHONE SCREENONSITE INTERVIEWProblem statement
Implement path completion similar to pressing Tab in a shell.
You are given absolute file paths, an absolute current directory, and the text already typed by the user. If the typed text is relative, resolve it beneath the current directory. If it begins with /, use it as an absolute prefix.
Find every file path that starts with the resolved prefix. If at least one path matches, return the longest common prefix of all matching absolute paths. Completion may advance through one or more directory components when every match shares them. If no file matches, return the resolved prefix unchanged.
Function
autocompletePath(paths: String[], currentDirectory: String, input: String) → StringExamples
Example 1
paths = ["/home/foo/f1.txt","/home/foo/f1_2.txt","/home/foo/README","/home/foo/bar/f1.txt","/home/foo/bar/README"]currentDirectory = "/home/foo"input = "f"return = "/home/foo/f1"The two matching files agree through f1, then diverge at . and _.
Example 2
paths = ["/work/folder/file1","/work/folder/file2","/work/folder/file/new","/work/other.txt"]currentDirectory = "/work"input = "f"return = "/work/folder/file"Every match is inside folder, so completion enters that directory and continues through the shared file prefix.
Example 3
paths = ["/work/folder/file1","/work/folder/file2","/work/folder/image.png"]currentDirectory = "/tmp"input = "/work/folder/fi"return = "/work/folder/file"An absolute input is completed without using the current directory.
Constraints
1 <= paths.length <= 200000.- The total length of all paths is at most
10^6. - Every path and
currentDirectoryis absolute and normalized: it contains no repeated slash,., or..component. currentDirectoryhas no trailing slash unless it is/.inputcontains no.or..path component.