## Two Sigma Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
0
of 0 vote

How about just traversing the tree based on the given index and setting isValid flag to false. That should be O(n).

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)
}
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();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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) {
index = n.parent;
n = a[n.parent];
}

for (int i = 0; i < a.length; i++) {
if (!hs.contains(i))
a[i].isValid = false;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

the stupidity of ppl is amazing

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.