FastPrep
Problem · Tree

Find File Paths in a Directory Tree

Learn this problem
● MediumUber logoUberFULLTIMEPHONE SCREEN
See Uber hiring insights

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

drafts saved locally
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