I recently had an interview problem where I was asked to find a compact representation of nodes in a tree.
As an example, consider the following tree:
A / | \ B C D / | \ | \ E F G H I /\ J K
The task was, given a list of node values, find a compact list of node values that completely describes the list given. A node value being in the list implictly means that all it's children are in the list as well and viceversa.
As a few examples, for the tree given:
compact([A]) = [A]
compact([B, C, D, J]) = [A]
compact([J, K]) = [E]
compact([J, K, F, G]) = [B]
compact([E, F, G, H]) = [B, H]
compact([H, I, D]) = [D]
This was my recursive attempt in python (from memory so may be some mistakes/syntax errors), which would be called with the root of the tree first. I was told:
- I don't need to check for empty trees
- I can assume that each node has basic tree methods (so can check it's value, if it's a leaf node etc).
- The non-compact list of nodes values is passed in through node_list and I was told that there would be no duplicates in this list and that each value in it would correspond to a node in the tree
def compacted_tree(node, node_list):
compact_list = []
if node.value in node_list:
#if this node is in the list then it is it's own consise representation
return [node.value]
allChildrenInCompactList = True
for child in node.get_children():
compact_list.extend(compacted_tree(child, node_list))
if (allChildrenInCompactList):
#only keep checking this if it's still true
allChildrenInCompactList = child.value in compact_list
if (allChildrenInCompactList and !node.isleaf()):
#all my children are in the list so the compact list should just be me
return [node.value]
return compact_list
I said that this would run with complexity \$O(n^2)\$ (with n=number of nodes in the tree) as in the worst case, every node needs to be visited and, in the worst case, every node needs to check all it's children against the node_list which is an \$O(n)\$ operation too. I said the space complexity should be \$O(n)\$ as in the worst case you may have to add all your nodes to the compact_list
before it can simplify.
It was hard to get a good read of how I went from the interview but I'm yet to get a call back. The interviewer hinted that the task could have been done with better complexity but I fail to see how. He also said that my time complexity should have been not just in terms of the number of nodes in the tree but also the length of the node_list
.
Is anyone able to tell me how I should've approached this problem/analysis better?
[A]
is always an answer. What are expected result for[B, C]
and[E, H]
? \$\endgroup\$ – vnp Aug 29 '14 at 21:52node_list
or all of it's children are in the list. I guess you could say the task was to repeatedly compact the set of nodes using the two above rules until you get the smallest possible set of nodes. Really sorry if this wasn't clear before. \$\endgroup\$ – user246431231232352 Aug 29 '14 at 23:04