Two Sigma Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
My O(N) solution. But I am using extra O(N) space too.
class Tree{
List<Integer> children;
Tree(){
children = new ArrayList<Integer>();
}
}
public void cutSubTree(Node [] node , int ind){
int n = node.length;
Tree tree[] = new Tree[n];
for (int i=0; i<n; i++){
tree[i] = new Tree();
}
for (int i =0; i<n; i++){
if (node[i].pI != -1)
tree[node[i].pI].children.add(i);
}
printValids(node);
makeInvalid(tree, node, ind);
printValids(node);
}
public void makeInvalid(Tree[] tree, Node[] node, int ind){
node[ind].isValid = false;
for (int i: tree[ind].children)
makeInvalid(tree, node, i);
}
public void printValids(Node[] node){
for (int i =0; i<node.length; i++){
if (node[i].isValid){
System.out.print(node[i].node + " ");
}
}
System.out.println();
}
Traverse the tree using the Node.parent index adding the parents to a set.
Then, traverse the entire array marking Node.isValid to false to any index that is
not in the set (the ones in the set are the super-tree)
Time O(n), Space O(n);
static void cutST(Node[] a, int index) {
if (a == null || index >= a.length)
return;
else {
HashSet<Integer> hs = new HashSet<>();
Node n = a[index];
while(n.parent != -1) {
hs.add(index);
index = n.parent;
n = a[n.parent];
}
for (int i = 0; i < a.length; i++) {
if (!hs.contains(i))
a[i].isValid = false;
}
}
}
Create an auxiliary boolean array/hashset to keep track of the "invalid" nodes. Then, loop through the array and check if the current node's parent is invalid; if it is, that node is also invalid. I think you only need to loop through the array a limited number of times (twice? probably a little more) max which technically reduces to O(n). If the array is in-order, then you only need one pass. The worst case is if every parent comes after all of its children.
How about just traversing the tree based on the given index and setting isValid flag to false. That should be O(n).
- Abcd May 09, 2017