Google interview questions #1

找出二叉查找树中出现频率最高的元素。树中结点满足left->val <= root->val <= right->val。如果多个元素出现次数相等，返回最小的元素。 http://blog.csdn.net/luckyxiaoqiang/article/details/8934593

不用额外空间. in-order

struct TreeNode{
   int val;
   TreeNode *left;
   TreeNode *right;
   TreeNode(int val) {
      this->val = val;
   }
};

void countNodesHelper(TreeNode *root, TreeNode *&pre, int &count, int &maxCount) {
 if (root == NULL) return;
 countNodesHelper(root->left,pre,count,maxCount);
 
 if (pre == NULL) {
    pre = root;
    count = 1;
  
 }else {
    if (pre->val == root->val) {
       count++;
       if (maxCount < count) {
          maxCount = count;
       }
    }else {
       count = 1;
    }
 }
   pre = root;
   countNodesHelper(root->right,pre,count,maxCount);
}

int countNodes(TreeNode *root) {
   int maxCount = 0,count = 0;
   TreeNode *pre = NULL;
   foo(root,pre,count,maxCount);
   return maxCount;
}

-----------------------------------------------
有一个函数
long compute(int i) {
return …;
}
返回值有可能出错概率是 p=1/10000。

还有一个函数
long total(int n) {
long s = 0;
for (int i =0; i < n; i++) {
   s += compute(i);
}
return s;
}
这样出错概率就是 np;

问： 如何改第二个函数，让他的出错概率小于p?

http://www.mitbbs.com/article_t/JobHunting/32996657.html
----------------------------------------------------------------------------------------------
REF http://www.mitbbs.com/article_t/JobHunting/32980969.html

1：（1）：写一个bool Palindrome(string s)，就是测s是否是Palindrome。
      （2）：已知bool Palindrome(string s)方程，写一个 int howmanyPalindrome
(string s), 输入s，返回s中包含多少个Palindrome的单词。 例如abbbac返回10，有a
,b,b,b,a,c,bb, bbb, bb, abbba.

int countHelper(string &s, int left, int right) {
   int count = 0;
 
   while (left >= 0 && right < s.length()) {
      if (s[left] == s[right]) {
         count++;
         right++;
         left--;
      }else {
         break;
      }
   }
   
   return count;
}
 
int countPal(string s) {
   int count = 0;
  
   for (int i = 1; i < s.length(); i++) {
      count += countHelper(s,i - 1,i); // even
      count += countHelper(s,i,i); // odd
   }
  
   return count + 1;
}

2: 给一个树root的pointer，树包含多个分支，树结构要自己创造。求一条最长[连续]
路径。
例如（括号对应上面node）  [修改：还有条件是 连续]
   树：                     2
                 |            |            |                |
                5            7          3                 6
         （|       | ）（   | ）   （|）         （|       |）
            6       3         2          4             5       8
                                 |
                                  3

返回3因为 （2-3-4） 这条线。优化要求时间O(n)
DFS，tree寻找路径
increasing order

struct TreeNode {
    int val;
    vector children;
    TreeNode(int val) {
        this->val = val;
    }
};
 
int longestPathHelper(TreeNode *root, int &longest) {
  
    int cur = 1;
    for (int i = 0; i < root->children.size(); i++) {
        TreeNode *child = (root->children)[i];
        if (root->val == child->val - 1) {
            cur = max(cur,longestPathHelper(root->children[i],longest) + 1);
        }else {
            cur = longestPathHelper(child,longest);
        }
   
    }
    longest = max(cur,longest);
    return cur;
}
 
int longestIncreasingPath(TreeNode *root) {
    if (root == NULL) return 0;
    int longest = 0;
    longestPathHelper(root,longest);
    return longest;
}

返回路径

struct TreeNode {
    int val;
    vector<TreeNode *> children;
    TreeNode(int val) {
        this->val = val;
    }
};
 
void longestPathHelper(TreeNode *root,TreeNode *pre, vector<int> path, vector<int> &longestPath) {
    vector<int> curLongest;
    if (pre != NULL && root->val == pre->val + 1) {
        curLongest = path;    
    }
    curLongest.push_back(root->val);

    for (int i = 0; i < root->children.size(); i++) {
        longestPathHelper(root->children[i],root,curLongest,longestPath);
    }
    
    if (longestPath.size() < curLongest.size()) {
        longestPath = curLongest;    
    } 
}
 
void longestIncreasingPath(TreeNode *root) {
    vector<int> longestPath,path;
    if (root == NULL) return;
    
    longestPathHelper(root,NULL,path,longestPath);
    for (int i : longestPath) {
        cout << i << endl;
    }
}

3.时间区间合并问题，leetcode上有相似题，关键词interval

4.(1)一个sorted array，如果其中有一个数重复超过array里面总数的1/4 return 
true。就是说{2，2，3，4} return true
{1，1，2，3，4，5，6，7} return false。
（2）优化第一部分用O（log2(N)) 时间复杂度
如果存在超过 1/4 的数，则次数必定会覆盖length / 4, length / 2, length *（3 / 4）这3点中的至少一点，所以只要对这3点上的数做二分搜索，就能找到其长度，然后与 1 / 4的长度对比。复杂度为 O(lgN)

int findFirst(vector<int> &nums, int elem) {
  int left = 0, right = nums.size() - 1;
  
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == elem) {
      if (mid - 1 >= 0 && nums[mid - 1] != nums[mid]) {
         return mid;
      }
      right = mid - 1;
    }else if (nums[mid] > elem) {
      right = mid - 1;
    }else {
      left = mid + 1;
    }
  }
  
  return 0;
}

int findLast(vector<int> &nums, int elem) {
  int left = 0, right = nums.size() - 1;
  
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == elem) {
      if (mid + 1 < nums.size() && nums[mid + 1] != nums[mid]) {
       return mid;
      }
      left = mid + 1;
    }else if (nums[mid] > elem) {
      right = mid - 1;
    }else {
      left = mid + 1;
    }
  }
  
  return 0;
}

bool helper(vector<int> &nums, int index) {
  int last = findLast(nums,nums[index]);
  int first = findFirst(nums,nums[index]);
  
  if (last - first + 1 > nums.size() / 4) {
    return true;
  }
  
  return false;
}

bool longerThanAQuarter(vector<int> &nums) {
  int length = nums.size();
  return helper(nums,length / 4) || helper(nums,length / 2) || helper(nums,length - 1 -length / 4);
}

(3)完全平方解集，做一个：int minsol（int i）。
比如1=1^2 所以minsol(1)返回1,
2=1^2+1^2 返回2,
4=2^2或者4个1^2,1比4小， 返回1，
12=2^2+2^2+2^2或者3^2+3个1^2返回3.

DP

int shortest(int num) {
    int t = sqrt(num);
    if (t * t == num) return 1;
       
    vector<int> dp(num + 1,INT_MAX);
    dp[1] = 1;
    dp[2] = 2;
    
    for (int i = 3; i <= num; i++) {
    int sq = sqrt(i);
        if (sq * sq == i) {
            dp[i] = 1;
        }else {
            for (int j = 1; j < i / 2 + 1; j++) {
                dp[i] = min(dp[i],dp[j] + dp[i - j]);
            }
        }
    }
    
    return dp.back();
}

5.有一个游戏，他说是fishing game，给一个数组vector<int> Basket, 比如里面元素
是{2，3，5，1，3，4，7}
有A，B 2个player，规定只能从Basket2端选数字，意思就是A开始的话一开始A只能选2
或者7，然后B选，同样只能2端选。所以比如一开始A选了7，B只能从2和4中选。问给定
数组A能取的最大值。B的策略已知，是greedy，就是总会取最大的那个数。
写一个 int maxA（vector<int>& Basket）；
Lintcode, Coins in a Line III http://www.lintcode.com/en/problem/coins-in-a-line-iii/#
DP, Memoization. iteration待写

int helper(vector<int> &nums, int start, int end, vector<vector<int> > &dp) {
    if (start == end) return 0;
    if (start + 1 == end) {
        return min(nums[start],nums[end]);
    }
 
    if (dp[start][end] != 0) return dp[start][end];

    if (nums[start] < nums[end]) {
        end--;
    }else {
        start++;
    }
 
    int play_1 = helper(nums,start + 1,end,dp) + nums[start];
    int play_2 = helper(nums,start,end - 1,dp)  + nums[end];
 
    dp[start][end] = max(play_1,play_2);
    return max(play_1,play_2);
}

int play(vector<int> &nums) {
    vector<vector<int> > dp(nums.size(),vector<int>(nums.size(),0));

    return max(helper(nums,0,nums.size() - 2, dp) + nums[nums.size() - 1],helper(nums,0,nums.size() - 2, dp) + nums[nums.size() - 1]);
}