Hierarchical Document Search
Amazon● MediumFULLTIMEONSITE INTERVIEWProblem statement
Implement document search over a hierarchy of folders. Each folder contains documents or subfolders.
For this exercise, assume nodes have zero-based IDs and the aligned arrays describe one valid rooted tree. parents[i] is the parent of node i; exactly one parent is -1. A documentFlags[i] value of 0 denotes a folder and 1 denotes a document. Document size and type are in sizes and documentTypes; folder values are ignored.
Search the subtree rooted at folder root. Return document IDs whose size is strictly greater than minSize and whose type equals wantedType. An empty wantedType disables the type condition. Type comparison is case-sensitive. Combine enabled conditions using AND and return matching IDs in increasing order.
Keep traversal separate from predicates so another document condition can be added without rewriting traversal. Explain how you would test nested folders, combined filters, and size boundaries.
Function
searchDocuments(parents: int[], documentFlags: int[], sizes: int[], documentTypes: String[], root: int, minSize: int, wantedType: String) → int[]Examples
Example 1
parents = [-1,0,0,1,1,2]documentFlags = [0,0,0,1,1,1]sizes = [0,0,0,10,30,40]documentTypes = ["","","","pdf","txt","pdf"]root = 0minSize = 20wantedType = "pdf"return = [5]Only document 5 is both larger than 20 bytes and of type pdf.
Example 2
parents = [-1,0,0,1,1,2]documentFlags = [0,0,0,1,1,1]sizes = [0,0,0,10,30,40]documentTypes = ["","","","pdf","txt","pdf"]root = 1minSize = 10wantedType = ""return = [4]Search only folder 1. Document 3 equals the threshold, so only document 4 matches.
Constraints
- For this exercise, assume
1 <= parents.length <= 100000, with all node arrays of equal length. - Parent IDs describe a valid tree; documents have no children, and each folder has either only document children or only folder children.
rootis a valid folder ID.- Document sizes and
minSizeare between0and10^9. - Document types and
wantedTypehave at most 30 ASCII letters; document types are nonempty.