Google面试经历

其实面完已经有半个多月了，最后挂了在HC轮，感觉挺可惜的，但是能总结的有很多，趁这次把blog迁移到pelican之后赶紧补掉这份面经吧。

背景

本人弱校软工毕业，大学折腾过三年ACM，在队里属于读题型选手，运气好品尝过Regional银的滋味，其他时间基本都在被虐。

对于这次拿到Google面试的机会，还是挺意外的，主要原因还是recruiter主动联系了我，问有没有意向尝试一下，其中还解释了为什么联系你，招聘大致流程，确定电面大致时间等相关问题。Google作为程序员眼中的Dreaming Company，谁会选择放弃这种机会呢？

为了做一些基本知识的复习和回忆，和recruiter约了20多天后电面，不得不赞叹Google的招聘流程，非常人性化，特别为应聘者考虑周到，这个后面再提及。

在这之后，recruiter发了一份相关的面试准备资料，其实里面的内容也不多，主要是面试过程中所需要掌握的一些知识点概述，从算法数据结构到OS编译原理等，覆盖的面还是非常非常广的。

接下去的20多天，针对自己薄弱的部分做了点突击复习和整理，主要还是围绕操作系统和网络等方面。

说来也巧，在接到recruiter的电话之前，刚刚好抽空刷完了LeetCode的题目，而且那段时间国内外Coding比赛也很多：Codejam ...

Nginx限制模块的共享内存

起因

对于Nginx中的limit_conn_zone和limit_req_zone两个模块，搜了一遍，发现网上都是讲这两个模块的意思和基本用法，却好像都没怎么细讲到一个问题：两个模块都配置了一个内存最大值来维护$variable（一般为$binary_remote_addr）所对应的请求数和请求速率，却没细说怎么维护，内存用完了怎么处理等问题。

重提

先再提提这两个模块的用法，换起一点回忆。

首先是limit_conn_zone

http {  
    limit_conn_zone $binary_remote_addr zone=addr:10m;  
    server {  
        location /home/ {  
            limit_conn addr 5;  
        }
    } 
}

在http上下文中配置了最大为10m的内存块，维护请求IP的链接数：最多支持5个来自同一IP的并发连接。

然后是类似的limit_req_zone

http {  
    limit_req_zone $binary_remote_addr zone=one ...

项目感受

忙了一个多月，第一个能说是正式的项目算差不多忙完了（后续优化不算的话），感受颇深，做个小总(tu)结(cao)。

学到的东西

Nginx

之前在学校里的时候，知道并稍微了解过一部分相关的资料，但并没有实际上手搭建或者配置过Nginx。由于不是很熟悉相关配置，需要经常一边查文档、资料，一边修改Nginx的配置，然后再测试。在经历了反反复复的几次“配置测试”后，对基本的location匹配，rewrite等有了进一步的认识，同时也养成了经常查官方文档的好习惯: )。其中，最容易搞错的问题在于location的优先级上，下面是一个比较简单的总结：

~     # 执行一个正则匹配，区分大小写
~*    # 执行一个正则匹配，不区分大小写
^~    # 进行普通字符匹配，如果匹配，之后不匹配别的选项
=     # 进行普通字符精确匹配（优先级最高）
@     # 定义一个命名的location，使用在内部定向时，例如error_page, try_files
1. 如果满足某个字符精确匹配，停止搜索。
2. 对于剩余的匹配字符串，进行最长匹配。如果这个匹配使用^~前缀，停止搜索。
3 ...

空数组

这是在看Redis源码的时候遇到的，由于底层字符串是封装了C风格的字符串，在src/sds.h可以看到这个结构的申明：

typedef char *sds;
struct sdshdr {
    int len;
    int free;
    char buf[];
};

buf为什么定义成空数组？

这个结构体的大小是8，即使你写成char buf[0]，它的大小还是8，但是buf不是0的时候显然sizeof(sdshdr)就变了，此时还要考虑内存对齐的情况。这么定义的好处在于buf这个字符缓冲区不会被定死，可以很好的处理变长的问题。

如果定义成char* buf的话，结构体的大小会变大，而且在构造函数里需要给buf动态的分配空间，这里管理的不好就会有内存泄露的问题。

技巧

buf这个指针的大小本身不算进结构体，它指向的是紧跟在 ...

Online Judge Submitter

做这个的东西就是为了熟练掌握一下Python，书买了很久，看了一大半了，但具体实现的代码很少。给自己订了了目标，主要是为了掌握一些基本点和网络编程的小入门，之前看到过有人做过类似的，所以也尝试的做了一个，虽然不怎么实用。

原理也很简单：

• 给OJ发Post的login请求，在response中获得Cookie
• 带上之前的cookie提交代码，然后根据runId（没的话直接去搜用户提交记录）来获取Judge结果

细节还是很多的：用户名密码，题目编号，文件对应的编译器，网页源代码中正则出有用数据，etc. 这几天加紧补上国内其他主要OJ的相关部分，这里也当做日志记录好了。

项目地址：https://github.com/Altynai/OnlineJudgeSubmitter

【2012.11.08】Add ZOJ (http://acm.zju.edu.cn)

【2012.11.09】Add POJ (http://poj.org), HDU(http ...

对于Cleo@LinkedIn的一些小分析和体会

Cleo是LinkedIn的一个开源项目，主要应用还是Typeahead这块地方。项目的主页链接：http://sna-projects.com/cleo/

大致的介绍以及简单的架构可以在那里看到，这里就不再重复。然后，最下面引用了两篇相关的论文。其中，第一篇是Facebook的Typeahead开发团队成员写的一个关于Typeahead的生命周期的文章，第二篇是几个THU大牛写的相关方案。我对这两篇文章做了简单的翻译，英语水平有限，凑合着看吧，传到百度文库了，地址：第一篇，第二篇。

推荐的做法就是去运行一下它给的Demo，其中有Generic Typeahead和Network Typeahead这两个部分，然后深入的去研究它的实现机理。

好了，下面主要说一下对Generic Typeahead这块的理解（Network Typeahead这部分的道理与其基本一致）。

假设现在有一些公司（Document）的列表，数据库中的每条记录就代表一个公司。每个公司都有自己的属性：编号（DocumentId），名称（Name ...

9月杂记

又到了一年一度的开学季，上周末回校的时候，路上看到依旧还是一些穿着拖鞋、拎着饭菜奔波于寝室和校外的老生。每年的这个时候是最热闹的，卖自行车的、卖电话卡的全部都凑过来了，能赚一笔，而且新生好骗嘛（我至今很后悔3年前来报到时买了一辆车，结果没几个月之后就被顺走了）。这周末回去就能看到遍地的新生了，我其实只想看看他们脸上的那种表情罢了，一定是满怀期待的那种吧，那种表情是最好看的，或许能看到自己3年前的样子。

再过两周实习就满3个月了，每天的早出晚归早已成为了习惯。每天早上醒来的第一反应就是“干！怎么又要起床了！”，后来干脆把闹钟的提醒改成了“起床了啊魂淡！操！努力了啊！”，感觉好一点了。马上就要日短夜长了，冬天一来，早起又是一个大考验。对于这2个半月的感受，其实也没什么，最锻炼的还是心理吧。当你面对一个任务的时候，可能这个任务你很难胜任，一开始你就害怕，害怕做不好，害怕自己能力不足，以至于你埋头苦干的时候，你才突然捂头发现，心理默想：糟糕，我好像陷在其中了。这就是我最近的感受，今晚开会的时候被组老大看出来了。其实这是完全没必要害怕担心的事情，慢慢来，稳稳做好基础，一步一步来就是了，这和打比赛什么的不一样，不是被封锁在几个小时的时空内 ...

Hdu 4391 Paint The Wall 线段树(优化)

【hdu 4391】http://acm.hdu.edu.cn/showproblem.php?pid=4391

【题意】100000个点，100000个操作，操作1把[l,r]的点涂成颜色z，操作2查询[l,r]内颜色为z的点个数，0<=z<=2^31

【思路】2012多校最后一场，当时是我上去敲的，我一开始的思路：线段树记录两个附加域 ncolor表示这段的颜色（-1表示这段为多种颜色）nor表示整段所有颜色的或值。更新就不多说了，push_up和push_down函数不要写错就好。然后查询的时候，假设查询到一个线段，如果这个线段内部包含z这个颜色，那么一定满足nor&z>=z（都看成二进制就好理解了），交了之后T了。。。后来想了一下这个剪枝太他妈的不够了。。因为 ...

Hdu 4389 X mod f(x) 数位DP

【hdu 4389】http://acm.hdu.edu.cn/showproblem.php?pid=4389

【题意】f(x)表示x各位的数字和. 给定1<=L<=R<=10^9, 求[L,R]范围内满足x%f(x)=0的个数.

【想法】由于L,R的范围很大, 所以很能想到答案是funcation(R)-funcation(L-1), 然后就是想办法求funcation. 可以观察到1<=f(x)<=81, 所以一开始想的是枚举每个y=f(x),每次预处理dp ...

实习一周的感受

本来说是7月2号才去上班的，后来觉得在家实在太虚度时光了，所以主动提早到6月25号去了。

有点一不错的是离家不远，下班赶得上公交车的话7点左右就能到家了，也就是这周的晚饭都是7点以后吃的，也就是以后的晚饭。

如果回校的话，估计还得迟半把个小时，想想就觉得胃疼。

我很好奇这群人的早饭都吃了什么，12点的时候竟然木有一个人想去吃饭的。一般过会儿才有人站起来说要不吃饭去吧，才陆陆续续分波出去吃！还有长期叫外卖的！这是死宅的行为啊！中午至少得出去透透气啊！整天在空调房里多不好！吐槽下每天的中饭，贵！第一天去的时候不懂行情，点了1荤2素1汤！擦！20块！太坑了！不过味道还算凑合。之后的几天一直省着点吃，一菜一汤差不多就够了=。= 那些人都2荤2素的吃的！你们到底赚多少一个月啊！2荤2素很贵的好不好！ T T

说说工作吧，这一周其实也就去打了打酱油。那边安排了小欧老师（几天相处下来，感觉小欧老师人很好，跟我一样有点腼腆，哈哈~！）做我的导师，我的工作就是帮他做做收集一些资料的工作，具体一点就是抓网页上的数据。他也没规定怎么做，只要把最后的数据给他看就行了。所以我直接乱搞了，用python抓网页源代码，然后正则匹配出关键字做记录，生成sql语句导到数据库。中间遇到了有些错误的数据 ...