FastPrepFind File Paths in a Directory Tree

Find File Paths in a Directory Tree

Uber logoUber● MediumFULLTIMEPHONE SCREEN
Learn

Problem statement

You are given the complete paths of every directory and file in a filesystem. Directory and file names may repeat in different locations, but every complete path is unique.

Build the directory tree and return every complete file path whose final component equals targetName. Traverse the tree with an explicit stack rather than recursion. Return matching paths in lexicographic order.

Function

findFilePaths(directoryPaths: String[], filePaths: String[], targetName: String) → String[]

Examples

Example 1

directoryPaths = ["/home","/home/docs","/tmp"]filePaths = ["/home/docs/report.txt","/tmp/report.txt","/home/photo.jpg"]targetName = "report.txt"return = ["/home/docs/report.txt","/tmp/report.txt"]

The same file name appears under two different full paths.

Example 2

directoryPaths = ["/a","/a/b"]filePaths = ["/a/b/readme.md"]targetName = "missing.md"return = []

No file has the requested final component.

Constraints

  • 1 <= directoryPaths.length + filePaths.length <= 20000
  • Every path is canonical, absolute, nonempty, and unique.
  • Every file's parent directory appears in directoryPaths.
  • Path components contain no slash; targetName is one nonempty component.
  • The total number of characters across all paths is at most 200000.

More Uber problems

See Uber hiring insights
public String[] findFilePaths(String[] directoryPaths, String[] filePaths, String targetName) {
    // Write your code here
}
directoryPaths["/home","/home/docs","/tmp"]
filePaths["/home/docs/report.txt","/tmp/report.txt","/home/photo.jpg"]
targetName"report.txt"
expected["/home/docs/report.txt", "/tmp/report.txt"]
Checking account…