Search a Folder Hierarchy with Extensible Document Filters
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement an extensible search over a hierarchy of folders and documents. Initially find documents above a size threshold; then add document-type filtering and combine size AND type conditions.
Implement `search_documents(nodes: string[][], root: string, minimumSize: int, allowedTypes: string[]) -> string[]`.
### Constraints & Assumptions
This table representation and output order are explicit practice choices for the reported in-memory hierarchy.
- Each node is `[id,parentId,kind,size,type]`, with unique nonempty ASCII IDs. Kind is `FOLDER` or `DOCUMENT`.
- The supplied nodes form one finite rooted tree with root's parentId empty. Every other parent exists and is a folder. Documents have no children. A folder's children are either all folders or all documents, matching the reported hierarchy; empty folders are valid.
- Folder size and type fields are empty. Document size is a decimal integer from 0 through 1000000000 and type is a nonempty case-sensitive string.
- At most 100000 nodes. Root is the tree's folder root. `0 <= minimumSize <= 1000000000`.
- Match a document only when its size is **strictly greater** than minimumSize and, if allowedTypes is nonempty, its type belongs to that list. An empty allowedTypes list disables the type filter. Duplicate allowed types have no effect.
- Traverse children in their order of appearance in nodes and return matched document IDs in depth-first traversal order. Do not rely on the input rows already being in traversal order.
### Example
```text
nodes = [["root","","FOLDER","",""],["f","root","FOLDER","",""],
["a","f","DOCUMENT","100","pdf"],["b","f","DOCUMENT","200","txt"],
["c","f","DOCUMENT","300","pdf"]]
root = "root", minimumSize = 100, allowedTypes = ["pdf"]
result = ["c"]
```
Discuss how the traversal can depend on a document-predicate interface so adding a filter does not rewrite the walk. Explain an AND-combinator for predicates and test the threshold boundary, empty folders, deep trees, absent types, and combinations. The console function implements the two specified filters; a generalized public predicate API is a design extension.
```hint Separate walking from deciding
The tree walk determines which documents are visited. A predicate determines which visited documents are returned.
```
Overview: Search a folder hierarchy with strict size and optional type filters, deterministic traversal, extensible predicate composition, and meaningful boundary tests.
Read the full Amazon Software Engineer interview experience this question came from
Implement an extensible search over a hierarchy of folders and documents. Initially find documents above a size threshold; then add document-type filtering and combine size AND type conditions.
Implement `search_documents(nodes: string[][], root: string, minimumSize: int, allowedTypes: string[]) -> string[]`.
### Constraints & Assumptions
This table representation and output order are explicit practice choices for the reported in-memory hierarchy.
- Each node is `[id,parentId,kind,size,type]`, with unique nonempty ASCII IDs. Kind is `FOLDER` or `DOCUMENT`.
- The supplied nodes form one finite rooted tree with root's parentId empty. Every other parent exists and is a folder. Documents have no children. A folder's children are either all folders or all documents, matching the reported hierarchy; empty folders are valid.
- Folder size and type fields are empty. Document size is a decimal integer from 0 through 1000000000 and type is a nonempty case-sensitive string.
- At most 100000 nodes. Root is the tree's folder root. `0 <= minimumSize <= 1000000000`.
- Match a document only when its size is **strictly greater** than minimumSize and, if allowedTypes is nonempty, its type belongs to that list. An empty allowedTypes list disables the type filter. Duplicate allowed types have no effect.
- Traverse children in their order of appearance in nodes and return matched document IDs in depth-first traversal order. Do not rely on the input rows already being in traversal order.
### Example
```text
nodes = [["root","","FOLDER","",""],["f","root","FOLDER","",""],
["a","f","DOCUMENT","100","pdf"],["b","f","DOCUMENT","200","txt"],
["c","f","DOCUMENT","300","pdf"]]
root = "root", minimumSize = 100, allowedTypes = ["pdf"]
result = ["c"]
```
Discuss how the traversal can depend on a document-predicate interface so adding a filter does not rewrite the walk. Explain an AND-combinator for predicates and test the threshold boundary, empty folders, deep trees, absent types, and combinations. The console function implements the two specified filters; a generalized public predicate API is a design extension.
```hint Separate walking from deciding
The tree walk determines which documents are visited. A predicate determines which visited documents are returned.
```
Constraints
- At most 100000 node rows form one finite rooted tree with the supplied folder root and unique nonempty ASCII IDs.
- Each nonroot parent exists and is a folder; documents have no children and each folder has only folder children or only document children.
- Folder size and type are empty. Document size is between 0 and 1000000000 and type is a nonempty case-sensitive string.
- MinimumSize is between 0 and 1000000000; match size strictly greater and optional allowed-type membership with AND.
- Empty allowedTypes disables the type filter and duplicates have no effect; its length has no separate stated bound.
- Return document IDs in DFS order with siblings ordered by input row appearance, not global row order.
Examples
Input: ([['root', '', 'FOLDER', '', ''], ['f', 'root', 'FOLDER', '', ''], ['a', 'f', 'DOCUMENT', '100', 'pdf'], ['b', 'f', 'DOCUMENT', '200', 'txt'], ['c', 'f', 'DOCUMENT', '300', 'pdf']], 'root', 100, ['pdf'])
Expected Output: ['c']
Explanation: Both strict size and type predicates must match.
Input: ([['a', 'f1', 'DOCUMENT', '20', 'txt'], ['f2', 'r', 'FOLDER', '', ''], ['b', 'f2', 'DOCUMENT', '30', 'pdf'], ['f1', 'r', 'FOLDER', '', ''], ['r', '', 'FOLDER', '', ''], ['c', 'f1', 'DOCUMENT', '40', 'pdf']], 'r', 0, [])
Expected Output: ['b', 'a', 'c']
Explanation: Sibling row appearance determines DFS even when children precede parents.
Community answers
Answer by janaki9sravya
def search_documents(nodes, root, minimumSize, allowedTypes):
result = []
adjList = {}
info ={}
aTypes = set(allowedTypes)
for node in nodes:
name, parent, d_type, size, f_type = node[0], node[1], node[2], node[3], node[4]
if d_type == "FOLDER":
adjList.setdefault(name, []) # <-- ensures every folder has a key, even with no children yet
if parent != "":
adjList.setdefault(parent, []).append(name)
else:
adjList.setdefault(parent, []).append(name)
info[name] = (d_type, size, f_type)
def minSize(node_id):
if int(info[node_id][1])>minimumSize:
return True
return False
def isAllowedType(node_id):
if (info[node_id][2] in aTypes) or( len(aTypes)==0):
return True
return False
def and_combine(*preds):
return lambda node_id: all(pred(node_id) for pred in preds)
check = and_combine(minSize,isAllowedType)
#iterative dfs
stack = [root]
while(stack):
node = stack.pop()
d_type,, = info[node]
if d_type=="DOCUMENT":
if check(node):
result.append(node)
else:
for n in reversed(adjList[node]):
stack.append(n)
return result
nodes = [["root","","FOLDER","",""],["f","root","FOLDER","",""],
["a","f","DOCUMENT","100","pdf"],["b","f","DOCUMENT","200","txt"],
["c","f","DOCUMENT","300","pdf"]]
root="root"
minimumSize=100
allowedTypes=["pdf"]
result = search_documents(nodes,root,minimumSize,allowedTypes)
print(result)