Google Interview Question


Country: United States
Interview Type: Phone Interview




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

pls explain me the question i couldn't get it....

- ram rs March 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
6
of 6 vote

1) Blacklist root
2) Traverse all leftmost nodes and blacklist them - O(Log N)
3) Traverse all rightmost nodes and blacklist them - O(Log N)
4) Traverse the tree(any BFS or DFS) and blacklist all leaves - O(N)

Time Complexity - O(N)

- tarun16 March 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Awesome! Black powa!

- Eminem. March 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 4 votes

A B-Tree is not a binary tree, its a Bayer's Tree.

- teli.vaibhav March 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes B-Tree is Bayer's Tree. The solution is for B-Tree.

- tarun16 March 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Traversing all leftmost nodes and black listing them could fail in the following scenario

1
2 3
4 5 6 7
8 9 10 11 12 13
14 15

Here nodes to be blacklisted : 1 2 4 8 14 15 9 10 11 12 13 7 3

In this case when looked from left, node 8 will be visible from the left side. But traversing node = node.left will not reach 8 as node 4 will not have any left child.

So what we can do is, do a BFS traversal, put a Empty node in the queue at the end of each level, and for each level black list the first node, node without left and right child, and last node in that level.


eg) Queue contents :

<e> empty node

1 <e> 2 3 <e> 4 5 6 7 <e> 8 9 10 11 12 13 <e> 14 15

So if we do dequeue operation on this queue, the conditions to be checked are,

1. if the previous node is <e> blacklist current node
2. If the next node is <e> blacklist current node
3. If both the children are null for the current node, blacklist current node.

- sriram March 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry the tree which I put with indentation in the last time got messed up.

The structure is 2,3 children of 1
4,5 -> 3
8,9 -> 5
10,11 -> 6
12,13 -> 7
14,15 -> 9

- sriram March 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

14,15 children of 8

- sriram March 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

4,5 children of 2
6,7 children of 3

Sorry for messing it

- sriram March 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

rudolph bayer invented B-Tree - hence also known as bayer tree sometimes leading to some confusion perhaps.

- whitenoise April 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

can u explain the question in detail.

- muralibilla March 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A B-Tree is not a binary tree, its a Bayer's Tree.

- Anonymous March 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

How does that change the solution given by tarun16 ? I think it will still be applicable.

- saki March 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Though the question talks about B tree, basic idea should remain the same.
Consider this tree:

For the below case, when viewed from the left side, the nodes are = 2, 3, 7 & 9
      2
    -    -
 3         5
         -
      7
   -     -
 9        10

Idea is that at every level the left most node is visible. Logic to find out the node visible at every left from left most side:
=> Do a inorder traversal of the tree so that left node comes before right node
=> At every level, if there is no node already seen, this node becomes the visible node

Given below is the simple method to find the left most nodes visible at every level

Map<Integer, String> levelMap = new HashMap<Integer,String>();

void saveLeftPath(TreeNode x, int level) {
   if (x != null) {
       if( ! levelMap.containsKey(l) ) {
           levelMap.put(l, x);
       }
   } else return;

   saveLeftPath(x.l, l+1);
   saveLeftPath(x.r, l+1);
}

- prashant2361 April 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

To view the nodes from the right side, above procedure can be used but the traversal of nodes will be reversed:

//right first
saveLeftPath(x.r, l+1);
saveLeftPath(x.l, l+1);

- prashant2361 April 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Blacklist the question

- Murali Mohan May 29, 2013 | 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