总的来说还是不错的。以下说说面试的内容（容我吐槽面试官的电话信号太烂了，听不清楚，还有不挂代理的gmail进去太慢了）
1、首先问了我项目上的有些事情，很快就过去了
2、然后问了我一个HTTP中 GET 和 POST的区别
3、然后问了一个大数据问题，这个问题可以简化如下，给了一个内存无法一次载入的大文件，里面包含有很多条string，统计前100个出现次数最多的。这个太easy了，首先取模运算得到小文件，然后对小文件里面的string做hash-map，然后排序，对排序好的小文件使用一个最小堆维护100个元素的集合，这个代价为log(100)复杂度，扫描各个排序后的文件，如果比堆顶大则替换，然后调整堆，否则continue
4、然后就是让我设计一个LRU，这个还用说嘛，上一篇GIST刚提到的，所以我很快的就设计出来并得到了肯定
最后一个在线代码是LCA问题，题目不多述，代码如下：
/*
本题采用两种实现手段，遍历树
1、保存叶节点（也可以是非叶节点）到ROOT的路径，然后计算路径差值，再同步往ROOT节点走直到遇见第一个相等的节点
2、保存ROOT至叶节点（也可以是非叶节点），然后从ROOT开始，直到遇见第一个不相等的节点，那么最后一个相等的节点就是LCA
*/
#include <iostream>
#include <vector>
using namespace std;
/*
find nearest common parent
*/
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode():val(0),left(nullptr),right(nullptr){};
};
bool findleafToRootPath(TreeNode* root,TreeNode* leaf,vector<TreeNode*>& path){
if(!root){
return false;
}
//is leaf
if(leaf == root){
path.push_back(root);
return true;
}else if(findleafToRootPath(root->left,leaf,path)){
//left tree
path.push_back(root);
return true;
}else if(findleafToRootPath(root->right,leaf,path)){
//right tree
path.push_back(root);
return true;
}
return false;
}
bool findRootToLeafPath(TreeNode* root,TreeNode* leaf,vector<TreeNode*>& path){
if(!root){
return false;
}
if(root == leaf){
path.push_back(root);
return true;
}
//try push
path.push_back(root);
bool found = false;
if(!found){
found = findRootToLeafPath(root->left,leaf,path);
}
if(!found){
found = findRootToLeafPath(root->right,leaf,path);
}
//resume
if(!found){
path.pop_back();
}
return found;
}
TreeNode* findNearestCommonParent(TreeNode* root,TreeNode* leftLeaf,TreeNode* rightLeaf){
vector<TreeNode*> leftLeafPath;
vector<TreeNode*> rightLeafPath;
vector<TreeNode*> path;
if(findRootToLeafPath(root,leftLeaf,leftLeafPath) && findRootToLeafPath(root,rightLeaf,rightLeafPath)){
TreeNode* nearestComParent = nullptr;
auto l = 0;
auto r = 0;
for(;l < leftLeafPath.size() && r < rightLeafPath.size();l++,r++){
if(leftLeafPath[l] == rightLeafPath[r]){
nearestComParent = leftLeafPath[l];
}
}
return nearestComParent;
}else{
return nullptr;
}
}
TreeNode* findNearestCommonParent2(TreeNode* root,TreeNode* leftLeaf,TreeNode* rightLeaf){
vector<TreeNode*> leftLeafPath;
vector<TreeNode*> rightLeafPath;
if(findleafToRootPath(root,leftLeaf,leftLeafPath) && findleafToRootPath(root,rightLeaf,rightLeafPath)){
TreeNode* nearestComParent = nullptr;
//size diff between two leaves
auto minSize= leftLeafPath.size() > rightLeafPath.size() ? rightLeafPath.size() : leftLeafPath.size();
auto l = leftLeafPath.size()-minSize;
auto r = rightLeafPath.size()-minSize;
for(;l < leftLeafPath.size() && r < rightLeafPath.size();l++,r++){
if(leftLeafPath[l] == rightLeafPath[r]){
nearestComParent = leftLeafPath[l];
return nearestComParent;
}
}
return nearestComParent;
}else{
return nullptr;
}
}
int main()
{
TreeNode* A = new TreeNode();
TreeNode* B = new TreeNode();
TreeNode* C = new TreeNode();
TreeNode* D = new TreeNode();
TreeNode* E = new TreeNode();
TreeNode* F = new TreeNode();
TreeNode* G = new TreeNode();
TreeNode* H = new TreeNode();
A->val = 1;
B->val = 2;
C->val = 3;
D->val = 4;
E->val = 5;
F->val = 6;
G->val = 7;
H->val = 8;
A->left = B;
A->right = C;
B->left = D;
B->right = E;
D->left = F;
D->right = G;
E->left = H;
TreeNode* result = findNearestCommonParent(A,G,E);
TreeNode* result2 = findNearestCommonParent2(A,F,E);
cout<<result->val<<endl;
cout<<result2->val<<endl;
system("pause");
return 0;
}