Bloomberg LP Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Q2.
Node getCommonAncestor(Node root, Node n1, Node n2) {
if (root == null) {
return null;
}
int largerValue = n1.value > n2.value ? n1.value : n2.value;
int smallerValue = n1.value > n2.value ? n1.value : n2.value;
if (root.value >= smallerValue && root.value <= largerValue) {
if (root.left.value == root.value) {
return getCommonAncestor(root.left, n1, n2);
} else {
return root;
}
}
if (root.value > largerValue) {
return getCommonAncestor(root.left, n1, n2);
}
if (root.value < smallerValue) {
return getCommonAncestor(root.right, n1, n2);
}
}
Q1.
Node getCommonAncestor(Node root, Node n1, Node n2) {
if (root == null) {
return null;
}
int largerValue = n1.value > n2.value ? n1.value : n2.value;
int smallerValue = n1.value > n2.value ? n1.value : n2.value;
if (root.value >= smallerValue && root.value <= largerValue) {
return root;
}
if (root.value > largerValue) {
return getCommonAncestor(root.left, n1, n2);
}
if (root.value < smallerValue) {
return getCommonAncestor(root.right, n1, n2);
}
}
Q3.
Node getCommonAncestor(Node root, Node n1, Node n2) {
bool fakeBool = false;
return getCommonAncestor(root, n1, n2, &fakebool, &fakebool);
}
Node getCommonAncestor(Node root, Node n1, Node n2, bool& isN1Found, bool& isN2Found) {
if (root == null) {
return null;
}
bool _isN1Found = false;
bool _isN2Found = false;
if (root == n1) {
_isN1Found = true;
isN1Found = true;
}
if (root == n2) {
_isN1Found = true;
isN2Found = true;
}
Node possibleResult = getCommonAncestor(root.left, n1, _isN1Found, _isN2Found);
if (possibleResult != null) {
return possibleResult;
}
if (_isN1Found) {
isN1Found = true;
}
if (_isN2Found) {
_isN2Found = true;
}
if (_isN1Found && _isN2Found) {
return root;
}
Node possibleResult = getCommonAncestor(root.right, n1, _isN1Found, _isN2Found);
if (possibleResult != null) {
return possibleResult;
}
if (_isN1Found) {
isN1Found = true;
}
if (_isN2Found) {
_isN2Found = true;
}
if (_isN1Found && _isN2Found) {
return root;
}
return null;
}
Node const *LowestAncestorQ1(Node const *n, int val1, int val2)
{
while (n) {
if (val1 > n->val_ &&
val2 > n->val_)
{
n = n->right_;
} else if (
val1 < n->val_ &&
val2 < n->val_)
{
n = n->left_;
} else {
break;
}
}
return n;
}
Node const *LowestAncestorQ2(Node const *n, int val1, int val2)
{
while (n) {
if (val1 > n->val_ &&
val2 > n->val_)
{
n = n->right_;
} else if (
val1 < n->val_ &&
val2 < n->val_)
{
n = n->left_;
} else {
if (n->left_ &&
n->left_->val_ == n->val_)
{
n = n->left_;
} else {
break;
}
}
}
return n;
}
int LowestAncestorQ3(Node const *n, int val1, int val2, Node const **ancestor)
{
int count = 0;
if (!*ancestor &&
n)
{
if (n->val_ == val1 ||
n->val_ == val2)
{
++count;
}
count += LowestAncestorQ3(n->left_, val1, val2, ancestor);
count += LowestAncestorQ3(n->right_, val1, val2, ancestor);
if (count >= 2 &&
!*ancestor)
{
*ancestor = n;
}
}
return count;
}
Q1.
- ajawaid191 April 13, 2017