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
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)
