2/3 second round phone -- PG

Problem Statement:

“In the object-oriented language of your choice, write a function that takes as input an array (or equivalent data structure) of objects. These objects are black boxes; you don’t know anything about them, except that they have a color property. The color property can take one of three values: red, green, or blue. Your function must sort the array in place by color using the ordering relationship that red is less than green and green is less than blue. The function must run in O(N) time and O(1) extra space.”

r < g < b
0   1   2  

void sortRGB(Object[] a){
    int len =  a.length();
 
    int redIndex = 0;
    int blueIndex = len-1;
    int index = 0;
 
    while(index<=blueIndex){
       if(a[index].color == 'red'){
           swap(a[index],a[redIndex]);
           redIndex++;
           index++;
        }
        else if(a[index].color == 'blue'){
            swap(a[index], a[blueIndex]);
            blueIndex -- ;
        }
        else{
            index++;
        }
    }
}
     

=======================================================================

BST (Binary Search Tree) Review:
A Binary Search Tree is a binary tree (2 children: ‘left’ and ‘right’) where every node in
the tree follows this rule: Given a node, every node in its left subtree must have value
smaller than itself and every node in its right subtree must have value larger than itself.

You have a BST where each node has pointers to its two children AND to its parent.
Given a node in the BST, find the next largest node in the BST, e.g. if all the nodes
were sorted by value in ascending order, it would be the next on the sorted list.
Assume that all node values in the tree are unique--no repeats.
Assume that the node given is guaranteed to be somewhere in the BST.

struct Node {
    Node *left;
    Node *right;
    Node *parent;
}

           
1 3 4 5 6 8 9
      5
  3       8 <- n
1   4   6   9 <- result



Node* minV(Node *root){
   Node* cur = root;
   while(cur->left){
      cur= cur->left;
   }
   return cur;
}


Node *nextLargestNode(Node *n) {
    if(n && n->right){
       reuturn minV(n->right);
    }
 
    Node *p=n->parent;
    while(p && n == p->right){
       n=p;
       p=p->parent;
    }
    return p;
 
 
 
}

====

Problem: Now assume that nodes do not have a pointer to their parents.
Write a function that takes in a node AND the root node and returns the
next largest node in the BST.

1 3 4 5 6 8 9
      5
  3       8 <- n
1   4   6   9 <- result

method 1: Time : O(n) 

Node *nextLargestNode(Node *n, Node *root) {
   return nextLNHelp(n, root, false);
}

Node *nextLNHelp(Node *n, Node *cur, bool& find){

   Node* left = nextLNHelp(n, cur->left, flag);
   if(left!=NULL) return left;

   if(cur == NULL) return NULL;
   if(find == true) return cur;
   if(cur == n){
              // Is there any danger of missing the NLN if its a child of n?
      flag = true;
    }
 
    Node* right = nextLNHelp(n, cur->right, flag);
    if(right!=NULL) reutrn right;

    return NULL;
}

method 2: Time : O(log n)

int findNLR(TreeNode * root, int target, int min, int max) {

    if(root->val <= target) {

        if(root->right != nullptr) {

            return findNLR(root->right, target, root->val, max);

        }

        else {

            return max;   //!important

        }

    }

    else {            //root->val > target

        

        if(root->left != nullptr) {

            return findNLR(root->left, target, min, root->val);

        }

        else {

            return root->val;

        }

    }

}

int findNL(TreeNode *root , int target){

    return findNLR(root, target, INT_MIN, INT_MAX);

}