Software Engineer · Onsite · Coding

Uber — Software Engineer

Level: Unknown Level

Round: Onsite · Type: Coding · Difficulty: 5/10 · Duration: 60 min · Interviewer: Unfriendly

Topics: Union Find, Tree Traversal

Location: San Francisco, CA

Interview date: 2025-12-28

Summary

The question asks me to construct the full path from a top-level folder down to a specified target folder, given a folder system represented by three arrays: idList, children, and nameList. I need to return the path as a single string, with folder names ordered from root to target and separated by commas. If the target folder doesn't exist, I should return an empty string.

Details

The coding question I got was:

You are given a representation of a folder system using three parallel arrays, along with a specific folder ID. The folders together form a **forest** (i.e., multiple independent trees).

The inputs are defined as follows:

* **`idList`**
  A list of unique integers, where each integer represents a folder ID.

* **`children`**
  A list of lists, where `children[i]` contains the IDs of all direct subfolders of the folder whose ID is `idList[i]`.

* **`nameList`**
  A list of strings, where `nameList[i]` is the name associated with folder `idList[i]`.

* **`targetId`**
  The ID of the folder whose absolute path needs to be determined.

Folders that do **not** appear in any `children[i]` list are considered **top-level folders** (roots).

Return the full path from a top-level folder down to the folder identified by targetId.

• The path should be returned as a single string
• Folder names must appear from root to target
• Names should be separated by commas (, )

If the target folder does not exist in the hierarchy, return an empty string ("").

My approach:

1. I first created a mapping from folder ID to its name.
2. Then, I identified the root nodes by checking which IDs do not appear in the children list.
3. After identifying the root nodes, I performed a depth-first search (DFS) starting from each root to find the target ID.
4. During the DFS, I maintained the current path and updated it as I traversed the tree.
5. If the target ID was found, I constructed the path string by joining the folder names with commas.
6. If the target ID was not found after traversing all trees, I returned an empty string.

Key insights:

• Efficiently mapping IDs to nodes is crucial for quick lookups.
• Identifying root nodes correctly is essential for initiating the search.
• DFS is a suitable algorithm for traversing the folder hierarchy and finding the target.

Proposed solution:

`python from typing import List, Optional from collections import deque

class Solution: def findFolderPath(self, idList: List[int], children: List[List[int]], nameList: List[str], targetId: int) -> str: n = len(idList) idToName = {} parentMap = {}

    for i in range(n):
        nodeId = idList[i]
        idToName[nodeId] = nameList[i]
    
    # Build parent map
    for i in range(n):
        nodeId = idList[i]
        for childId in children[i]:
            parentMap[childId] = nodeId
    
    # Check if targetId exists
    if targetId not in idToName:
        return ""
    
    # Find path from targetId to root by backtracking
    path = []
    currentId = targetId
    
    while currentId in idToName:
        path.append(idToName[currentId])
        if currentId not in parentMap:
            # Reached a root node
            break
        currentId = parentMap[currentId]
    
    # Reverse to get root-to-target path
    path.reverse()
    
    return ",".join(path)

`