Two Sigma Interview Question for Software Engineer / Developers


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

- Abcd May 09, 2017 | Flag Reply
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)
				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();
	}

- Vidhya May 15, 2017 | Flag Reply
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) {
				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;
			}
		}
	}

- nelsonwcf May 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the stupidity of ppl is amazing

- xx June 22, 2017 | Flag Reply
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.

- oiii September 11, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More