一不小心面试了百度的两个部门，而且还是同时在面试，有点累。。。
首先是基础架构部的，这个部门太有效率的，早上一面的，然后面完马上就约二面。。不过感觉百度面试官真的很不错。。（想去现场面试，但是百度一直没有机会现场面试，全是电话面试搞定）
一面的时候，很多问题都不是太记得了，不过主要还是围绕着项目在谈，可能是在实验室一直都是做的内核相关的，所以这方面比较好问，问了很多关于这方面的问题，不过问的比较多的都是关于一个write系统调用的整个流程，这个需要从direct_io和page cache IO还分别讨论。
direct_io这个倒是没有什么，但是page cache IO的过程还是很多的，从整个系统调用的写过程开始，到请求下发到磁盘的过程也很繁琐。首先，只是将用户态的写缓冲区中的内容复制到page cache中，然后在一定条件下唤醒pdflush 内核线程将脏page刷到磁盘上（这个过程在后面专门总结一下）。
然后就问了很多基础知识，这方面我觉得我一般都答的还行，所以一般也就没有总结了，再就是写了3个程序：
关于C++中资源泄漏，使用对象来进行管理的：
static const int32_t MAX_ONLINE_NUM = 1000; class Mutex { public: Mutex(); virtual ~Mutex(); // void acquire(); void release(); private: Mutex(const Mutex& other); Mutex& operator=(const Mutex& other); }; class ScopedLock { public: ScopedLock(Mutex& mutex) } class LoginManager { public: // will be called in multi threads void login(const std::string& user) { ScopedLock wrapper(_mutex); _mutex.acquire(); // // do actual work // _mutex.release(); } static LoginManager& get_instance() { static LoginManager manager; return manager; } int32_t get_online_num() const { return _online_num; } private: LoginManager() : _online_num(0) { } Mutex _mutex; int32_t _online_num; };
2 在二叉排序树中查找第k小的结点，最简单的办法可能就是讲二叉树进行中序遍历，然后返回第K小的结点。
方法2：一边遍历，一边计数，到达K的时候返回结点值。
int inorder(TreeNode* root,int k) { if(root==NULL||k<=0) return -1; int count=0; stack<TreeNode*> st; while(root!=NULL||!st.empty()) { while(root) { st.push(root); root=root->left; } if(!st.empty()) { root=st.top(); count++; st.pop(); if(count==k); return root->val; root=root->right; } } return -1; }
3 求二叉排序树中两个节点的最低的公共结点，只要从root结点开始判断，它的值与所给结点值的大小关系，如果大于两个值，说明两个节点在父节点的左边，root=root->left,否则，如果root的小于两个节点，则两个节点在符结点的右边，root=root->right，否则，root就是两个节点的最低的公共祖先
拓展，如果不是二叉排序树呢？
通过遍历整个结点来判断：
bool isParent(TreeNode *parent,TreeNode* child) { if(parent==NULL) return false; if(parent==child) return true; return isParent(parent->left,child)||isparent(parent->right,child); } void findCommon(TreeNode *root,TreeNode *n1,TreeNode *n2,TreeNode* &ret) { if(isParent(root,n1）&&isParent(root,n2)) { ret=root; findCommon(root->left,n1,n2,ret); findCommon(root->right,n1,n2,ret); } } TreeNode* findParent(TreeNode* root,TreeNode *n1,TreeNode *n2) { if(root==NULL) return NULL; TreeNode* ret=NULL; findCommon(root,n1,n2,ret); return ret; }
下午 5：00二面
首先也是介绍项目，介绍项目中也是问一个write过程整个是怎么操作的，然后中间穿插一些小问题，自己尽量去回答，但是也不知道答的好不好。最后也说到了pdflush的刷磁盘问题，什么情况下会去将page cache中脏页写到磁盘上，如果在pdflush中刷脏页的过程中，又有很多的write请求来了，那此时的请求是直接写到磁盘上，还是继续写的page cache中？（答：写的page cache中）但是这样不就存在一个问题，如果写请求太多的情况下会不会导致内存om呢，内核会发生这种情况吗？（答：不会，但是不知道内核是怎么实现一种机制来保证内存不会om的）然后继续问，如果让你来设计，你觉得应该怎样去保证在这个过程中内存不会om呢？（答：是不是可以用一种同步机制，例如，当内存容量太小的时候，此时写请求就阻塞着，不能继续往page cache写数据，知道page cache容量下降到一个值之后，唤醒写请求，继续写到page cache中），然后面试官就说内核差不多是这样实现的。（有惊无险的过了）
然后还问了一下进程和线程的创建过程，以及对应的系统调用，各自的区别，各种引发出的问题，还有就是进程之间的通信机制（管道、套接字、消息队列、共享内存、信号、信号量），Unix 套接字包含哪些？（我好像只知道socket套接字，其他的不太知道）还有一些不记得了，最近百度的面试太多，一天三面百度，想死。。。。
还有就是一个编程题了：
int f() return: 0： 概率p 1： 概率1-p 0<p<1 要求： 构造新的 int fn() return: 0： 概率50% 1： 概率50% int fn() { int num1=f(); int num2=f(); while(num1==0&&num2==0||num1==1&&num2==1) { num1=f(); num2=f(); } if(num1==0&&num2==1) return 0; if(num1==1&&num2==0) return 1; } int fn() { int num1=f(); int num2=f(); if(num1==0&&num2==1) return 0; else if(num1==1&&num2==0) return 1; else return fn(); }
其实思想就是要等概率返回0和1。。。以前只知道思路，今天要写代码，首先对于0和0,1和1的情况，面试官一定需要我考虑，而且一定要我用递归，用循环也不行，但是脑袋都蒙了，只知道递归调用不是要参数的吗。然后面试官就让我说，你给我说说递归的定义，(⊙﹏⊙)b，想多了。。
希望明天还能继续写三面。。。。。。。。。。。。。。。。。
同时这段时间还在面试百度的另一个部门,，目前还只有一面，但是只是一种在讨论linux内核，东西太多太杂了，不知道怎么写，然后直接把自己带到坑里了。。。
貌似记得说过一个C++中抽象类，什么是抽象类以及它的作用（当时死活想不起来抽象类中就是定义了一个纯虚函数的类（纯虚函数，一直不记得这个名称，只能跟面试官描述这个函数的定义了））作用，觉得应该就是做接口一样的，不能定义抽象类的实例，就是为了被其子类继承的。
还有一个就是网络编程中同步IO和异步IO的区别？
二面，才知道这个部门是系统部，好像整个的架构是这样的，首先是应用层，然后是基础架构层，最下面就是系统层，也就是不同的部门在做的。
二面讨论了好多系统的设计，尤其是linux内核的各种机制，实现，以及我的项目和在腾讯的实习经历项目。。。各种挖，不过面试官说我怎么报了软件开发呢，明明就是对系统这么熟悉的人（汗），我找了半天没看到我能报的职位，就随便报了一个啊。。。
不过这个部门好快，白天面完，就约了明天晚上三面，另一个部门呢，三面在哪里？？？？
9.22百度的三面终于面完了，系统部，问了愿意工作的城市，说了深圳，但是不得已还是可能去北京的。。
9.23 百度给发offer了，工作地点给换成了深圳～～
