Google Interview Question
Software Engineer / DevelopersCountry: United States
FindNextNodeInOrder(Node root, Node node){
// search the first in-order node in the right tree
// because in in-order traverse, the left tree must
// have been traversed before we reach the current node
if(cur.right != null){
Node cur = node.right;
while(cur!= null){
cur = cur.left;
}
return cur;
}else{
// if there is no right tree, we search for the first ancestor
// who is a left child, this ancestor's parent will be the next
// node we are looking for. Be careful since we may reach the root
// without seeing any ancestor as a left child, in which case cur
// will end up being null.
cur = cur.parent;
while(cur!= null && cur != cur.parent.left){
cur = cur.parent;
}
if(cur!= null)
return cur.parent;
else
// no ancestor is a left child
// it means the node in question itself is the last node
// in the in-order traverse, there is no next node.
return null;
}
}
FindNextNodePreOrder(Node root, Node node){
if(cur.left != null){
return cur.left;
}else if(cur.right != null){
return cur.right
}else{
cur = cur.parent;
// complex logic, the false conditions are either cur is null
// or cur is left tree and it's right sibling is not null
// the while loops says keeping searching if we haven't found
// an ancestor who is a left child, or we found one but it's
// right sibling is null
while(cur!= null
&& ((cur != cur.parent.left)
||(cur == cur.parent.left && cur.parent.right == null))){
cur = cur.parent;
}
if(cur == null){
return null;
}else{
return cur.right;
}
}
}
FindNextNodePostOrder(Node root, Node node){
Node cur = node;
if(cur.parent == null){
return null;
}
if(cur = cur.parent.left){
if(cur.parent.right != null){
// search the left most node in the right sibling
cur = cur.parent.right;
while(cur.left != null){
cur = cur.left;
}
return cur;
}else{
return cur.parent;
}
}else{
return cur.parent;
}
}
These methods need parent link. If parent link don't exist, we can traverse the tree first and keep a parent array, and use the same methods. Or we can use recursive traverse, but pass two boolean values (one for target node, one for next node) and the target node along the way, whenever we see the boolean is true, it means we just found the target node, so the current recursion call, which should be visiting the next node, should set the next node boolean to true, and all other calls should bail out when they see the next node boolean is set to true.
import java.util.*;
class logEntries{
int startTime;
int endTime;
int RAMUsage;
int id;
logEntries(int startTime,int endTime, int RAMUsage,int id)
{
this.startTime=startTime;this.endTime=endTime;
this.RAMUsage=RAMUsage;this.id=id;
}
}
class entryNode
{
int id;
int time;
int RAMUsage;
entryNode(int id, int time, int RAMUsage)
{
this.id=id;
this.time=time;
this.RAMUsage=RAMUsage;
}
}
public class peakRAM {
public static Comparator<entryNode> entryComparator=new Comparator<entryNode>(){
public int compare(entryNode n1, entryNode n2)
{
return (int)(Math.abs(n1.time)-Math.abs(n2.time));
}
};
static int findPeakRam(ArrayList<logEntries> entries)
{
Queue<entryNode> entryPriorityQueue=new PriorityQueue<entryNode>(1,entryComparator);
//Dividing the entries t
for(logEntries en : entries)
{
entryPriorityQueue.add(new entryNode(en.id,en.startTime,en.RAMUsage));
entryPriorityQueue.add(new entryNode(en.id,-en.endTime,en.RAMUsage));
}
//Polling the entries
int Max=0,curr=0;
while(true)
{
entryNode en=entryPriorityQueue.poll();
if(en==null)
break;
//System.out.println("ID: "+en.id + " time : "+en.time + " RAMUsage : "+en.RAMUsage);
if(en.time < 0)//
curr-=en.RAMUsage;
else
{
curr+=en.RAMUsage;
Max=Math.max(curr, Max);
}
}
return Max;
}
public static void main(String[] args) {
ArrayList<logEntries> entries=new ArrayList<logEntries>();
entries.add(new logEntries(0, 100, 500, 1));
entries.add(new logEntries(10, 70, 300, 2));
entries.add(new logEntries(50, 200, 1000, 3));
entries.add(new logEntries(110, 220, 400, 4));
entries.add(new logEntries(175, 280, 750, 5));
System.out.println(findPeakRam(entries));
}
}
1) parent pointer is given.
- go to the parent of the current node.
- if current node is the right child of its parent => print parent.
- else return leftmost node of the right sub-tree of parent.
2) parent pointer is not given.
- traverse the tree and find the parent of the current node
- do the same as method (1).
Note that of current pointer is root than post-order successor if NULL (no post-order successor).
/* post order successor in binary tree
*/
#include<iostream>
using namespace std;
struct Node{
int data;
Node *left;
Node *right;
Node(int x): data(x), left(NULL), right(NULL) {}
};
Node *leftMostLeaf(Node *root){
while(root->left || root->right){
if(root->left) root = root->left;
else
root = root->right;
}
return root;
}
Node *postorderSuccessorRec(Node *root, int key, Node *parent, Node *treeroot){
//case 1: If current root is NULL, then succ is NULL
if(root == NULL)
return NULL;
//case 2: If current root is target node for which we are looking for successor
if(root->data == key){
//case 2.1: If current root is the root of the tree, succ is underfined.
if(root == treeroot)
return NULL;
//case 2.2: Otherwise, if current root is a right child, succ is parent.
else if(parent != NULL && parent->right == root)
return parent;
//case 2.3: otherwise current root is a left child and the following applies
//case 2.3.1: If the node has a right sibling, r, succ is the leftmost leaf in r's sub-tree
else if(parent != NULL && parent->left == root && parent->right != NULL)
return leftMostLeaf(parent->right);
//case 2.3.2: Otherwise succ is parent
else if(parent != NULL && parent->left == root && parent->right == NULL)
return parent;
//case 2.3.3: If none of above applies, then succ does not exist
else
return NULL;
}
//case 3: current root is not the target node for which we are looking successor
else{
//case 3.1: Search target node and its successor in left side of tree recursively, return if found
Node *left = postorderSuccessorRec(root->left, key, root, treeroot);
if(left)
return left;
//case 3.2: Search target node and its successor in right side of tree recursively, and return.
return postorderSuccessorRec(root->right, key, root, treeroot);
}
}
int main(){
Node *root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
root->right->left = new Node(6);
Node *succ;
succ = postorderSuccessorRec(root, 3, NULL, root);
cout<<succ->data<<endl;
}
// link-to-parent version
Node findNextNode(node n) {
if (n == null)
return null;
// is there a right child?
if (n.right != null) {
n = n.right;
// find the left-most node of the right branch
while (n.left != null)
n = n.left;
return n;
}
// no right node
// find the first parent of a left node
while (n.parent != null) {
if (n == n.parent.left)
return n.parent;
n = n.parent;
}
return null;
}
// in-order traverse version - no link to parent
Node findNextNode(Node n, Node givenNode, BoolWrap nextIsIt) {
if (n == null)
return null;
if (n.left != null)
findNextNode(n.left, givenNode, nextIsIt);
if (nextIsIt.val)
return n;
if (n == givenNode)
nextIsIt.val = true;
if (n.right != null)
findNextNode(n.left, givenNode, nextIsIt);
}
class BoolWrap {
boolean val;
}
With parent is trivial. Without parent the idea is also simple - traverse the tree looking for the value and storing the smallest value which is greater than required.
void next(node* root, int & x)
{
if (root->value > x)
x = min(x, root->value);
if (root->value > x)
find(root->left);
else
find(root->right);
}
I might have been too tired when wrote that code down. Corrected version is below.
int next(node* root, int x)
{
int result = INT_MAX;
if (root->value > x)
result = root->value;
if (root->value > x)
result = min(result, find(root->left));
else
result = min(result, find(root->right));
return result;
}
- msmajeed9 May 27, 2014