## Highbridge Capital Interview Question for Java Developers

Country: United States
Interview Type: In-Person

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

This problem can be solved by modified inorder traversal.
conventional inorder-
---------------------
visit left child
root
then right child
---------------------
modified inorder-
------------------------
1>first visit right child
2> then root
3>then left child
-------------------------
In b/w them we can keep track of last visited node.(Let prev)
when we shall find the actual node we would have next biggest node(in prev).
O(n)

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

Ur method is partially wrong. If the second largest node is at the left of the biggest node, then it's not the Prev containing the second, but the left.

Comment hidden because of low score. Click to expand.
1
of 3 vote

You can simply find the successor of the given Node.
Takes O(logN) time, if you do inorder traversal it will take O(N) time.

``````if(Node->right!=NULL)
{
Node=Node->right;
while(Node->left!=NULL)
Node=Node->left;
}
else
{
while(Node->parent!=NULL || Node==Node->parent->right)
Node=Node->parent;
}
return Node;``````

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

while(Node->parent!=NULL || Node==Node->parent->right), in this line, if the first condition fails, that means Node->parent=NULL.
So to the next check, (Node == Node->parent->right),will try to dereference Node->parent, which is NULL.

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

// To get maximum value in the tree.
public int getMax(BinarySearchTree rootNode) {
BinarySearchTree rNode = rootNode;
int res = 0;
while (true) {
if (rNode.rightNode != null) {
rNode = rNode.rightNode;
} else {
if (rNode != null) {
res = rNode.value;
}
break;
}
}
return res;
}

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

Just treat the left node of the given node as the root node. This will work fine.

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

Inorder traversal with memory; basically return the node traversed immediately after we find our target. This assumes we have the root to start, which is not mentioned in the problem, but you need it to find a solution.

``````Node* next_biggest(Node* curr, Node* n, bool& return_next) {
if (!curr) return NULL;
// Recursively call left subtree
Node* ret;
if (ret = next_biggest(curr->left, n, return_next)) return ret;
// These two statements will be executed
// on each node in smallest to biggest order
if (return_next) return curr;
if (curr == n) return_next = true;
// Recursively call right subtree
if (ret = next_biggest(curr->right, n, return_next)) return ret;
return NULL;
}``````

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

explanation ?

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

Is the answer only possible to be one of the three nodes: the direct parent, the very right node of its left subtree and the very left node of its right subtree?

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

Need not be any one of those ......
1) if the Node is a right child of the parent , parent will be less than the current Node ...so it can't be a successor

2) In the same way the other two cases can be checked.

``````10
5                     25
21          29
26``````

The successor of 25 is 26 which is none of those three nodes.

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

Yeah, but the parent could be, right? (if the node is its left child)

In your example 26 is the very left node of its right subtree beginning with 29

Actually I'm also wondering if the "next biggest" means a number only bigger than the given number, or that given number is already the biggest and we are looking for the number which is only smaller than it...

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

I was wondering the same thing about to the wording. "next bigger" would mean the node that is just bigger than the current node while "next biggest" would mean the node that is just smaller than the current node.

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

struct node * search(struct node *root, struct node *elem)
{

if(!root || !elem) return;

if(elem->right != NULL) {

elem = elem->right;
while(elem->left) {
elem = elem->left;
}
return elem;
}
struct node *result = NULL;

while(root) {

if(elem->data < root->data) {
result = root;
root = root->left;
}
else if (elem->data > root->data)
root = root->right;
else
break;

}
return result;
}

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

Perhaps I don't understand what "biggest" means but in a BST (Binary Search Tree) nodes with larger values are on the right, and nodes with smaller values are on the left, or else it is not a binary search tree. Sounds like a trick question to me

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

``````// find the next biggest node in BST
Node* FindNextBiggest(Node* r, Node* cur)
{
if(r == null || cur == null)
return null;

// if cur is the root, return the min on the right child.
if (cur->value == r->value)
{
return FindMin(r->right);
}
else if(cur->value < r->value)
{
// if cur is on the left child, try to get the next biggest on the left child.
// if left child does not have the next biggest, return root.
Node *bigger = FindNextBiggest(r->left, cur);
return bigger == null ? r : bigger;
}
else
{
// if cur is on the right child, get the next biggest on the right child.
// return null if cur points to the maximum in the tree.
return FindNextBiggest(r->right, cur));
}
}

Node* FindMin (Node* r)
{
if(r == null)
return null;

Node* p = r;
while(p->left != null)
p = p->left;

return p;
}``````

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

``````class Node {
int value;
Node parent;
Node left;
Node right;
}

Node  findNextSmallest(Node n) {
return Min(findMin(n.right), n.parent.value, findMin(n.parent.right) );
}

findMin(Node n) {
if (n == Null)
return Integer.MAX_INT;
else
return Math.min(n.value, findMin(n.left));
}``````

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.