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);

}

word break -- Leetcode

Question:

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Answer:

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
      vector<bool> flag(s.length() + 1);
      flag[0] = true;
     
      for (int i = 0; i < s.length(); i++) {                         //s[0]-s[n-1]
         for (int j =i; j >=0; j--) {
            if (flag[j] && dict.find(s.substr(j, i-j+1)) != dict.end()) {                              //flag[j]->s[j-1]
                flag[i+1] = true;
                break;
            }
         }
      }
      return flag[s.length()];
   }
};

Reverse Integer -- Leetcode

Question:

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

click to show spoilers.

Have you thought about this?

Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!

If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?

For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Update (2014-11-10):
Test cases had been added to test the overflow behavior.

Answer:

class Solution {
public:
    int reverse(int x) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int a,b;
        int sum=0;
        if(x<0){
            a=abs(x);
        }
        else{
            a=x;
        }
       
        while(a>0){
            b=a%10;
            a=a/10;
            sum=sum*10+b;
        }
        if(x<0)sum=-sum;
       
        return sum;
    }
};

palindrome partition II -- leetcoce

Question:

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Answer:

class Solution{
public:  
int minCut(string s) {
   
      int leng = s.size();
   
      int dp[leng+1];
      bool palin[leng][leng];

      for(int i = 0; i <= leng; i++)
        dp[i] = leng-i;
        for(int i = 0; i < leng; i++)
            for(int j = 0; j < leng; j++)
                palin[i][j] = false;

      for(int i = leng-1; i >= 0; i--){
        for(int j = i; j < leng; j++){
          if(s[i] == s[j] && (j-i<2 || palin[i+1][j-1])){
            palin[i][j] = true;
            dp[i] = min(dp[i],dp[j+1]+1);
          }
        }
      }
      return dp[0]-1;
    }
};

K most frequent numbers in an array -- PG first round phone

Question:

list of n integers:
1, 2, 3, 3, 3, 2, 4, 5, 5, 1

find k most frequent numbers:
k = 1:    3
k = 2:    3, 5 or 3, 2 or 3, 1
k = 3:    3, 5, 2 or 3, 5, 1 or 3, 2, 1

Answer:

time complexity = O(n * log(n))

class wrapper{
  int number;
  int freq;

public:
  wrapper(int i, int j){
    number = i;
    freq = j;
}

struct cmp{
  bool operator(wrapper lhs, wrapper rhs){
     if(lhs.freq < rhs.freq) return true;
  }
}

vector<int> mostFrequent(vector<int> arr, int k){
    int len = arr. length();
 
    unordered_map<int, int> mmap;
    for(int i=0;i<len;++i){
       if(mmap.find(arr[i]) == mmap.end()){
          mmap[arr[i]] = 0;
       }
       mmap[arr[i]] ++;
    }
 
    vector<wrapper> warr;
    vector<int> res;
    priority_queue<wrapper, vector<wrapper>, cmp> pq;
 
    for(int i=0;i<len;i++){
       if(mmap.find(arr[i])!= mmap.end()){
          wrapper wa = new wrapper(arr[i], mmap[arr[i]]);
          pq.push(wa);                                  //log n
          mmap.delete(arr[i]);
        }
    }
 
    for(int j=0;j<k;++j){
       wrapper tmp = pq.top();                   //log n
       pq.pop();
       res.push_back(tmp.number);
    }
    return res;
}

One Edit Distance -- Leetcode

Question:

Given two strings S and T, determine if they are both one edit distance apart.

Answer:

public class Solution {
    public boolean isOneEditDistance(String s, String t) {
       
        //consider all cases : 1.adj acj 2.acd abcd 3.abc abcd
       
        if(s.length() > t.length()){
            String tmp = t;
            t = s;
            s = tmp;
        }
        if(t.length() - s.length() >1)return false;   //to ensure t.length-s.length<=1
       
        boolean diffOne = false;
       
        for(int i=0,j=0; i< s.length(); ++i,++j){
            if(s.charAt(i) != t.charAt(j)){
               
                if(diffOne){
                    return false;
                }
               
                diffOne = true;
                if(t.length() > s.length()){
                    --i;
                }
            }
        }
       
        return diffOne || (t.length() > s.length());  
    }
}