## Google Interview Question for Java Developers

Country: United States

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

Can you give an example? What do you mean by connected here? Are we talking about direct or transitive connectivity? If it's direct, a node i a binary tree is connected to just two child nodes (at most). But if we are talking about transitive connectivity, a node is connected to all the nodes in its left and right subtrees.

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

I assume connected is adjacent and the Node has no parent pointer.

``````Node* find_local_min(Node *root)
{
stack<pair<Node*, Node*>> s;
s.push({ root, root });
while (!s.empty()) {
Node* p = s.top().first; // parent of current, none = root if p = n
Node* c = s.top().second; // current
int cv = c->value_;	// current value
s.pop();
if (c->left_ != nullptr && c->right_ != nullptr
&& cv < p->value_ && cv < c->left_->value_ && cv < c->right_->value_) {
return c;
}
if (c->left_ != nullptr) s.push({ false, c->left_ });
if (c->right_ != nullptr) s.push({ false, c->right_ });
}
return nullptr;
}``````

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

I assume the node is a local minimum node, if the node's value is less than the node's parent's value, and less than the node's children's values.

``````void LocalMinNodes(Node *n, vector<Node *> &out, Node *parent = NULL)
{
if (n) {
if ((!parent || n->val_ < parent->val_) &&
(!n->left_ || n->val_ < n->left_->val_) &&
(!n->right_ || n->val_ < n->right_->val_))
{
out.push_back(n);
}
LocalMinNodes(n->left_, out, n);
LocalMinNodes(n->right_, out, n);
}
}``````

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.