Google Interview Question
Web:
www.google.com
|
HQ:
Mountain View, CA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
1,223 Interview Reviews |
Back to all Google Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Senior Software Engineer at Google:
Oct 13, 2010
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (5)
1 of 2 people found this helpful
Nov 8, 2010
Node *Tree::LeastCommonRoot(x, y)
{
Node *runner = this->root;
while (runner)
if (x < runner->value && y < runner->value)
runner = runner->left;
else if (x > runner->value && y > runner->value)
runner = runner->right;
return runner;
}
{
Node *runner = this->root;
while (runner)
if (x < runner->value && y < runner->value)
runner = runner->left;
else if (x > runner->value && y > runner->value)
runner = runner->right;
return runner;
}
Helpful Answer?
Yes |
No
Inappropriate?
2 of 2 people found this helpful
Dec 7, 2010
Dear Lamont,
You need another "else" statement which should return runner. Otherwise there will be an infinite loop in some cases (when one of x or y is equal to the current root).
You need another "else" statement which should return runner. Otherwise there will be an infinite loop in some cases (when one of x or y is equal to the current root).
Helpful Answer?
Yes |
No
Inappropriate?
1 of 1 people found this helpful
Dec 11, 2010
Here's a Java version:
// This method is in BSTNode class
BSTNode findLowestCommonAnsector(int va1, int val2) {
BSTNode root = this;
while(root != null) {
int val =root.value;
if(val > val1 && val > val2)
root = root.left;
else if(val < val1 && val < val2)
root = root.right;
else
return root;
}
return null;
}
// This method is in BSTNode class
BSTNode findLowestCommonAnsector(int va1, int val2) {
BSTNode root = this;
while(root != null) {
int val =root.value;
if(val > val1 && val > val2)
root = root.left;
else if(val < val1 && val < val2)
root = root.right;
else
return root;
}
return null;
}
Helpful Answer?
Yes |
No
Inappropriate?
Dec 14, 2010
@Aytekin - D'oh! This code originally had an "else break" but I failed to type it in here. It's not like this is a special case. This is what happens when we find the common root and want to return it.
The top solution (Tal) has a similar problem. If x or y equals the current value, the function falls off the end without returning anything. I was trying to improve upon it and ended up making a bigger mistake. Sorry, folks.
The top solution (Tal) has a similar problem. If x or y equals the current value, the function falls off the end without returning anything. I was trying to improve upon it and ended up making a bigger mistake. Sorry, folks.
Helpful Answer?
Yes |
No
Inappropriate?
To comment on this
question,
Sign In with Facebook or
Sign Up
You might also be interested in: Interview Questions, Senior Software Engineer Interview Questions, Google Interview
1 of 1 people found this helpful
by Tal:
{
if(!root)
return NULL
if((root->value < x) &&
(root->value < y))
return FindCommonRoot(root->right,x,y)
else if((root->value > x) &&
(root->value > y))
return FindCommonRoot(root->left,x,y)
else if(((root->value > x) && (root->value < y)) ||
((root->value < x) && (root->value > y)))
return root
}