[Behind CS] CS平台设计随笔 – 综述

转眼再过一个月就要离开西邮。2014年5月到2015年5月,一年时间,受阳哥所托,花了很多精力在一个小具规模的项目上——西邮Linux兴趣小组内部协作交流平台(Xiyou Linux Group Collaboration System),简称CS。因为是第一次从头构思设计实现一个平台级项目,也是第一次带领十数人的团队,受制自己水平有限,走了很多弯路,但也终于有了一点成果,积累了很多经验与感悟。一方面希望能够把它们总结下来自我回顾,另一方面也希望能给后来人留下一些资料,所以在这里开一个系列文章[Behind CS]。

为什么要做CS

小组自2006年成立以来,至今已走过8年,走出了一批批活跃在各地各方向上的优秀的学长学姐们。然而,随着时间推移,小组也暴露出了一些问题,比较明显的就是传承与沟通上的缺失——一方面,往届学长学姐们曾经开发的优秀项目鲜有后人维护,毕业后心系小组却缺少了解小组近况的途径,在校学习期间精心收集整理积累下的学习资源材料也难以向下沉淀;另一方面,在校的小组成员想要参与原有项目,却因文档缺失难以入手,想要联系往届同学咨询,却缺乏有效联系方式而求助无门……

同时,作为一个技术型团体,小组内部的信息化程度却并不高;小组官网也多年无人维护;而随着邮件列表的日益冷清,急需一个能够替代邮件列表进行问题讨论与结论沉淀的平台;刚诞生的小组基金,也急需摆脱人工记账的原始方式,而有一个便捷稳定,方便公示与查询的载体……

为了解决这些问题,一年前,王亚刚老师与10级的刘丹阳学长,启动了这个项目。我们组建了一支前后共12人的开发团队。经过一年的不断摸索尝试,无数次讨论、争执、重构,终于有了现在呈现的这个雏形。

CS的业务结构是什么样的

设计之初,我们就清楚的认识到,目前我们考虑到的需求——基金管理、讲座、项目、活动、……绝不会,无法,也不应该限制系统未来的职能与边界;既然如此,平台就应该具备极灵活的架构与极大的可扩展性。

业务角度,作为项目PM,我给这个平台的定位,是使其逐渐发展为小组日常运营的服务型中心。如下图所示:

CS业务架构

我们把整个系统分为两大部分:底层应用服务框架,和上层应用。为了真正让这个系统成为小组内部联结的纽带,适应未来可能出现的新需求,也让每个人都有可能参与平台的开发,我们将项目、问答、招聘、基金、活动等具体业务需求定义为上层应用(App),以类似WordPress插件的形式与应用服务框架结合;应用服务框架为应用提供了封装好的各类API,以及全站搜索、站内信、用户管理、应用管理等各类基础服务。具体架构将在下一节中详述。

从图中可以看出,整个小组的信息化建设分为对内对外两部分;对外主要包含官方网站与微信平台等公开渠道;对内则是完整的CS生态圈;CS平台为其上的应用提供丰富的接口与基础服务支持,而各个应用则成为了官方网站与微信平台等对外渠道的数据与服务源,提供类似“近期讲座”、“纳新报名”等信息与功能的后台支撑。

简单来说,理想情况下,这个平台将成为小组生活、学习、活动与对外交流的中心,成为小组“Free Open Share”精神的体现,以丰富可用的功能与大量宝贵的优质内容吸引大家常常使用。“每天来到小组第一件事,就是打开CS”。(野心不可谓不大……)

CS的技术架构是什么样的

如前所述,CS将平台服务多层封装,平台与应用之间高度解耦来实现高度可扩展性。技术架构如下图所示:

CS技术架构

如图所示,平台技术架构分为四层。

最底层(Server层)基于经典的LNMP(Linux+Nginx+MySQL+PHP)架构。

平台的下层(Model层),首先将基本数据库操作封装为CSDB类,提供数据库服务(DB Service);在DB层之上,平台实现并封装了四大类服务与接口——账户服务(Account Service),提供用户账户控制(增删改查)、用户信息获取(基本资料,在线状态)、用户权限分级管理(管理员权限移交)等服务;消息服务(Message Service),提供站内信一对一、一对多收发,管理,以及已读状态等服务;动态服务(Activity Service),提供用户自发布状态,以及应用产生富文本动态服务;搜索服务(Search Service),提供基于动态的跨应用全站搜索服务。

平台的中层(Control层),利用下层提供的丰富的服务接口,开发了平台基础模块的后台(登陆、找回密码、首页、个人资料页、站内信模块、搜索模块、用户管理模块与应用管理模块等)。同时对接应用的后台。各应用后台通过本层实现业务逻辑并对前端模板进行渲染,同时封装对外提供接口。

平台的上层(View层),基于前端渲染框架Smarty,平台约束了两类基本模板——Frame.tpl与Base.tpl。平台页面与应用页面,利用这两类基本模版,开发并渲染前端展示页面。同时,平台页面通过约定规范,向应用请求并展示各类整合信息,例如首页侧边插件,导航栏应用动态数字等。

小结

在本文中,我们对CS项目的目的与意义,CS的业务结构,以及CS的技术架构有了初步的认识。后面的文章将会关注各个技术细节的实现与心得。

CS平台分为线上正式版与开发版。线上正式版地址:cs.xiyoulinux.org   开发版地址:dev.xiyoulinux.org

CS平台的全部代码,开源于Github。仓库地址:https://github.com/Jensyn/cs-xiyoulinux/   应用开发文档地址:https://github.com/Jensyn/cs-xiyoulinux/wiki

托福心得

这篇是写给福州新东方骗点高分奖金的……不过也算记录了一下自己的托福之旅吧。贴在这留个纪念,也为后人留点不敢说经验,权当教训吧。

我在2014年寒假,趁着春节放假回家的时间,报名了福州新东方的托福强化。之所以当时直接报的强化段,主要是因为自己的时间安排太紧,假期也比较短没有充足的时间上全程;此外针对自己的情况,认为自己亟需加强的是针对托福的解题思路与技巧,于是在做了一套测试题后就直接报了强化。事实证明新东方不愧是外语教学领域的领军者,即便只参加了强化段,仍然让我感觉收获颇丰。下面说说我一战托福的经验。

先介绍一下我的情况。我是2月8日开班后真正开始托福准备,此前只草草看过题型介绍,单词都没开始背(只有六级水平)。2月16结课后报了5月11的场;结果4月份因为一些个人原因将考试延期到6月28日。前前后后隔了4个多月。这里告诫大家如果可以,还是在上完班后尽早报考,效果会比较好。我属于反例,拖到临考前其实很多老师告诫的要点已经有些记不清了。

成绩方面,我的总分是104,听力和写作分别拿了28和27,阅读稍差一些26,口语比较拖后腿只有23,算是一个遗憾吧。先说说听力,我觉得新东方有一个观点特别对,就是唯听写是提升听力的唯一途径。我之前练听力的方式比较低效,就是在闲暇的时候反复听相同的材料,比如一些经典的外语演讲。刚开始可能能听懂50%~60%,但到后期就能感觉大部分都能听懂甚至能复述。个人认为这种方法对于长期培养语感可能有帮助,但对于中短期提升听力水平进展太慢。而换用老师提倡的直接听写TPO的conversation和lecture,而后和原文进行比对找出自己错误的点,分析为什么听不出来,是连读的问题,还是其他原因;然后针对性的加强,能够在短期内起到不错的效果。此外,好的笔记习惯也对考场上作答有很大帮助。平时就要针对性的训练自己快速而有条理的整理lecture笔记,并根据笔记尽可能复述原文。这样考场上不会慌乱,也能迅速定位题目对应的笔记位置并回想起细节。

写作的话,个人认为不要片面追求过于华丽的词汇和太复杂的句式。重要的是清晰明确且有理有据地表明自己的观点。但平时也不要只看题想观点而不练手。若很少练习,容易在考场上因为慌乱而脑子短路想不出句式回忆不起单词,最后只能拼凑简单句草草了事。独立写作不妨在开始动手前,花5分钟左右梳理出文章的脉络和论据,想想自己文章的亮点。从而使写作过程一气呵成。

阅读只能算不功不过。只能建议大家平时多做练习加快阅读速度,考场上只会比平时慢而不会快,即便快准确率也会没有保障。阅读的提升,技巧只能是锦上添花而不能雪中送炭。纯靠技巧,风险太高。

口语是短板,也是比较遗憾的点。只能说,口语套路相对固定,平时不能只在脑子里想或者在纸上写,一定要多张口说,这样考场上才不会磕磕绊绊,影响发挥也浪费答题时间。我就吃亏在平时张口练习太少,考场被周围的人影响而回答的并不流利。

最后想跟大家说的是,不要过度依赖机经。我在考前和同学交流得知5月份机经命中率极高,以为6月也能重现全中奇迹;没想到最后口语机经一道没中差点慌神。因此告诫大家,靠实力才是王道,机经不妨当做高保真模拟题。切勿依赖机经。

这就是我的托福一战经验。希望对大家有所帮助。

[7.22实习笔记] 校招实习生百阿百技培训笔记

前几天报名了今天的校招实习生百阿百技培训。今早9点半在1号楼的白马山庄准时开始。主持人先闲扯了下,介绍一天的计划,上午是华黎带来的关于阿里技术发展历程以及个人经验的分享,下午还有两场讲座但与技术关联不大。由于师兄还给我布置了任务,我就参与了上午的讲座就回来了。在这里整理一下上午听到的笔记,可能比较零散,凑合着看。

从集中式应用到分布式应用

淘宝07年的负载是每天100万笔订单,当时采用的还是集中式的系统。集中式系统并不落后,不要陷入唯分布式至上的误区。

08年时,淘宝的数据库力量非常强悍,Oracle认证有60%在淘宝。当时的策略是,性能瓶颈了都从数据库角度入手,优化SQL、建索引等……虽然数据库技术力量非常强,撑起了淘宝的高访问量,但这种做法始终是有瓶颈的,一旦负载超过了天花板,会没有补救的办法(没法加机器水平扩展)。当年JD的618大促挂了,刘强东说要加三倍的机器,但这不能解决问题。集中式应用不可扩展,所以淘宝决定升级架构。

但需要明确,集中式应用的开发和维护代价都比较小。

分布式应用需要解决的核心问题:如何利用多个节点解决计算和存储;应用解耦和异步化;

传统关系型数据库的集群方案不靠谱。淘宝面对非常多类型的存储。

淘宝2.0~3.0的转变。HSF,Notify和数据访问层 三个中间件让集中式走向分布式应用。

※做好接口!你的产品可以有问题,但你应该是第一个发现的,不能让别人跑来告诉你你的产品有问题。(程序员的尊严)

分布式调试非常困难(解耦后找不到消息去向)

如何做线上容量规划和评估(线上真实引流压测)

水平扩展和垂直扩展:工程师不要因为分布式能够水平扩展而过度依赖水平扩展;目前过度依赖加机器,而没有充分发挥单机性能。

同城多机房;异地多机房。

趋势

算法的价值:先发优势

云计算时代:开发让应用做到可伸缩

无线(天猫的无线优先)

DT:数据≠算法。能不能让存数据的成本低,能不能让数据计算快。业务工程师应该有数据的sense:业务如何为公司产生数据;如何在业务中利用数据;如何利用数据产生价值。

建议

站在风口。

选择对职业发展有帮助的公司和职位。机会和空间很重要。看书和学知识只是基础,实战很重要。

找个感兴趣的方向,很辛苦但不会很痛苦。

目标:定短期目标。随着年龄的增大时间会越来越碎,如果愿意在事业上有发展,刚毕业对自己狠一点。

危机感。推荐书籍《浪潮之巅》。

实习应聘记(二)——阿里,总结

上一篇博文写了简历撰写,去哪儿笔试和360电面。这篇主要写写阿里的三轮电面(主要是技术面,HR面是第四轮还没接到…),以及自己这段时间的一些总结吧。

阿里一面

一个学姐给的内推机会,我选的岗位是研发工程师。被分到的部门是天猫事业部。

3月6日在线投递简历,没想到3月7日周五下午就接到了一面电话。当时是下午2点多,我正迷迷糊糊准备上床小睡一会儿,突然来了个0571的固话号码,我也没多想就接了起来。对方说是天猫的,看到了我的简历,打电话来“简单聊一聊”。我突然意识到,我去,电话面试。

面试官可能为了打开话题,先问我最近在忙啥。我脑子正糊,说最近在忙着投简历呢,不是各大公司都开始校招了嘛……面试官笑了下,呵呵。突然脑子清醒过来,靠对方想问的应该是学术上在干啥好继续深入问技术问题吧。赶忙说除此之外也在做一个什么什么项目,跟着老师研究什么什么课题云云。我说到了我的可视化项目,对方表现出了一些兴趣,我赶忙趁热打铁说这个项目有在线演示的地址,您是否有兴趣看看?面试官说好,我就把URL报给了他。开始边介绍操作边解释项目(可见,有可能的话,最好能在面试前把能够展示的项目都搭到网上,特别是这种电话面试,隔空交流本就不如当面顺畅,如果能让对方直观的看到项目效果,沟通效果会好很多)。 

面试官问,这个项目遇到了什么难点?我说,是数据库的瓶颈。我们使用的是MySQL,目前三四百个点的规模查询效率还好,但上千个点的情况,查询时间可能达到十几秒。面试官问什么样的查询,我描述了下先是根据输入的关键字找到ID,再根据ID找出直接相关的ID,这样构成一个ID集合,最后查找集合内两两ID是否存在连接,过程类似点→树→图,每个请求要经过这三步查询。  

于是面试官问数据库查询做了哪些优化。我就说了下我是怎么设计的数据库,分了几个表,用类似邻接表的结构来存整个复杂网络,如何建的索引,然后提到了,有一个字段是一个枚举量,只有{“PersonProfile”,”OrgProfile”,”LocationProfile”}三种取值,因此我把类似这种的量直接数值化存储然后建索引,提高了查询效率。

面试官抓住这个,问我为什么字符串数值化后能够提高查询效率?从数据库存储引擎的角度解释……我就懵了,因为我对数据库内部存储的原理并不了解,只停留在使用的层面上。只能猜测:数值和字符串相比,比较与排序的时间都短得多?

显然这不是面试官想要的答案,他提示我,数据库存储引擎用B树或B+数作为存储结构。又是一箭穿膝盖……我对B树和B+树也不了解啊!只好老实说并不是非常清楚B树和B+树……

面试官还不放弃!(或许这就是阿里的面试风格吧… )他继续提示我,就简单把B树或B+数想象成一颗自平衡二叉排序树,结点存索引,叶子要么指向磁盘中存数据的地址,要么直接指向一块存数据的空间(当然这并不是B树或B+树的正确定义,面试官只是想短时间引导我继续思考,大家有兴趣可以去网上查阅B树,B+树,B*树等相关知识的文章 )。我只好猜,数值化后数据小,可以存在直接指向的空间,而不需要频繁磁盘IO?

最后面试官告诉我,和磁盘每次取一个512K的block有关。数据小,一次能拿出的数据就多。字符串有可能一个block只存的下一两个。

而后就是一些常规问题,何时毕业,何时实习,有什么问题想要问他。我问了他天猫对于海量真实用户数据做了哪些挖掘?他大概给我讲了下天猫的挖掘过程:先将用户分类,而后分析同类用户购买商品,而后把这些商品反过来推荐给该用户,这样一个推荐过程。然后就告诉我如果有消息他的同事会和我进一步联系。结束了面试。整个过程大约二十分钟。   

阿里二面

一面结束后,不久就有消息说通过后一周之内会接到二面,而且二面传闻还是视频面试……于是3月10日到16日一整周时间我都过得提心吊胆……真是“又期待又怕受伤害”……可是这周过得风平浪静波澜不惊。就在我都不知道还会不会有二面的时候,3月17日周一上午计算机硬件实验上机,突然来了个0571…于是…二面来了。

本以为电话是约视频面试的时间,没想到又是直接说“聊聊”,看来又是一轮电话面试。跟面试官说给2分钟换一个安静的地方,然后就跑回教室拿上简历又跑到空无一人的楼梯间(电面高发期随身携带简历还是很必要的)。两分钟后面试官的电话就又来了。

这一轮的面试,纯技术问题并不多。面试官上来第一个问题,居然是“说说在大学阶段做过的印象最深的事”。当时又傻了一下(我发现我在电面过程中老是会被面试官问傻…唉…),之前都在准备技术问题,从来没想过会来这一出…我就问是技术相关还是非技术相关的?对方说都行。我想了想就说是校学生会的经历吧,我相信,重要的并不是你加入了哪些牛逼的组织,而是你的加入对它产生了什么改变。在我加入科技部之前,科技部在学生会的地位并不高,属于实打实的辅助型部门。任部长期间我和另外两位部长努力将它由幕后转向台前,在校会历史上第一次成功联合各大院级学生会合办了视频大赛。面试官问,在这个过程中遇到了什么难点,如何解决。我说难点主要在于和院会沟通吧。因为并不是所有院会都乐于与校会合作。解决方法就是清楚的分析利弊,说明他们有我们所没有的资源——能够拉外联,能更好的煽动本院学生参与;而我们有更成熟完善的活动举办经验,更高的活动规格(校级)。合作是一种双赢。解释清楚后大部分学院还是愿意合作的。

又聊到“目前受到的比较大的挫折”,我犹豫了下,回答可能高考算一个吧。当时因为一些个人失误发挥的并不好,对我和我家人都是比较大的打击。面试官问如何恢复。我说当时最紧要要面临的抉择就是是否复读。我父亲是极力反对我复读的。因为他也是一名高中教师,他说复读能够有大幅提分的情况非常少。最后我没有复读,来了西邮。当然我现在回头来看,我不后悔当时的选择。因为首先我读的是我喜欢的计算机专业,其次我有幸进入了西邮Linux兴趣小组,结识了一帮志同道合的朋友,在这个积极上进的圈子里共同努力共同奋斗。现在想来,大学的好坏,甚至师资的好坏,都不是决定性的因素。真正重要的是个人的努力。面试官评价说在我的年龄能有这个想法的不多(心里窃喜一下,觉得应该问题不大了~)。

后来说到项目,面试官问我用C++做了什么项目,我说完全用C++实现的就是简历上第三个项目,用的C++ MFC。面试官问是团队项目还是个人项目?我说是4人团队,我是负责人。于是面试官问我如何分工。我就大概阐述了下因为开发周期只有20天比较紧,所以没有同时分工开发客户端和服务端,而是先集中力量一起攻破客户端,再一起攻破服务端。每个阶段再根据客户端和服务端的模块划分任务。这样遇到技术问题也好沟通。 

后面面试官又问了个很“奇怪”的问题:有没用自己的技术赚过外快。我说因为我对计算机各个方面都挺感兴趣,所以也会一些网页前后端,视频音频处理之类的。之前在导师介绍下帮陕西省互联网大会制作了开场视频;也曾经帮一家物流公司制作了网站前端。当时对方要求网站符合RWD(响应式网页设计)而我不会,所以我咨询了一些学长,选用了bootstrap框架完成,这个框架原生支持RWD。(我说这段其实是想有意展现快速学习能力,不知道面试官有没理解…)面试官问,那些核心技能呢?C++,C之类的。我说没有用它们赚过外快,基本都是用它们在校内做一些项目,并没有用来盈利……

再后来面试官问我,看我的简历应该很有可能是能拿到保研的(简历写得有点…美化自己…大家懂…),对未来是什么规划。我说因为本校并不是很好的学校,保研也只能保本校而我不大愿意在本校读研。如果能有幸拿到贵公司的实习机会并参与工作,可能会选择就业;如果没能够进入贵公司,我最近也在准备托福,可能会选择出去读研,香港等地…… 

而后问我实习希望做哪方面工作。我回答我对数据挖掘挺有兴趣,虽然了解不多。而我知道天猫掌握着海量的用户真实数据,恰好我一面也有向面试官询问天猫的数据挖掘,其实我还挺希望能够在实习阶段接触到相关的业务,不知道有没有机会。面试官说他不能确定但会帮我在评价中注明。紧接着面试官就反问我,如果由我来做天猫推荐算法,我会如何给用户进行分类。这个问题恰好我以前有想过,但并没有验证过正确性,于是我就阐述了下我的思路:首先作为一个电商网站,用户间最大的差异应该在于消费能力。因此先根据消费能力(近期月均消费额等数据)进行分类。然后是性别,再然后是年龄,最后是地域。因为众所周知的“南北差异”等原因我认为地域也会对消费习惯造成影响。这就是我对于分类方法和优先级的想法。

面试过程就差不多结束了,随后就是例行的“何时来实习”,“有什么问题想问我”。这次我问了阿里系各个垂直产品是独立进行开发,还是共用同一个底层架构在上层拉分支?面试官回答是后者。支付宝、天猫、淘宝、阿里巴巴等,底层其实是使用同一套技术。然后就告诉我有进一步消息会有人和我联系。结束了二面。全过程约半小时。

总体感觉,二面并不是技术型面试,更多的是对综合能力和思维模式的考察。尽量在每一个问题上展现自己的闪光点和独特之处就好。

阿里三面

二面结束后,下午我随手打开阿里校招网站,看到我的状态已经从“应聘中”变成了“应聘成功”,顿时非常兴奋!但又不敢确定,难道两轮面试就有结果了?后来内推的学姐在Q上恭喜我终面通过,我一下放松下来,觉得世界都是美好的~

可是……事实证明,我还是Too young too simple。兴奋期还没过,周二晚上在实验室和同学写一个项目的需求分析,突然来了一个010的电话。我想,是不是去哪儿的笔试结果出来了呢?出门接电话,是一个自称北京阿里的工程师打来的。和我预约面试时间。当时我就懵了(对,又一次),因为之前都是杭州的号码(天猫在杭州),于是我问,我已经参加过阿里的面试,请问您是哪个部门?对方反问我参加的是哪个部门的面试,我说是天猫,对方说他也是。他不知道具体流程,HR安排的。我只好和他商量了下,约在3月20日周四晚8点,进行第三轮面试。

因为他自称是工程师,所以我明白,这次一定是一场实打实的技术面没跑了。本来彻底放松的神经又开始紧张,甚至更甚于前,紧张到全身发抖。为何后台显示通过却又加面一轮?是和往年一样借此刷人?还是其他原因?会问什么技术问题? ……这些都没有答案,我能做的也就只有尽力准备了。

周三满课。周四直到晚7点前,我把我的简历过了一遍又一遍,想象他会在哪几个点下挖;准备了自我介绍的稿子;把树和图的常用算法以及时空复杂度快速过了一遍;看了小组群共享里张瑞上传的《十道海量数据处理面试题与十个方法大总结》。这里向大家强烈推荐这篇文章!不长的篇幅能让大家快速掌握海量数据处理面试题的大概套路和可选路线。(膜拜JULY大神!)而事实证明,我在三面中碰到两道里面的类似题目!实战亲身验证效果!

晚上8点15,电话来了……这次的面试官比较常规。首先让我做自我介绍。我大概说了一下事先准备的稿子。因为在自我介绍中提到项目里使用了很多开源软件,因而对开源精神有一种推崇和向往。他就问我,具体用过哪些开源的东西。我说,底层来说,Linux,Apache,MySQL之类的一套;上层的话,做可视化用到了D3.js这个开源库,前端用Bootstrap开源框架,还有一些XML,JSON协议解析也用到了开源的库。他就问,在配置过程中有遇到什么问题吗?我说基本遇到的问题也都通过官方文档或论坛社区解决了,没有遇到什么特别难的问题。

然后他说,看我的简历,技能主要的点在于1、CC++JAVA 2、数据结构和算法 3、数据库 是吗?我说我对JAVA不能算熟练,只是项目有用到,知道语法而已。更多的是用C和C++。于是他问我,C++的STL有用过吗。我非常惭愧的说只用过map之类简单的…他继续问,知不知道智能指针。我就不出所料的被问倒了。只好说不是很了解。面试官就知趣的往下问了。

然后是数据结构与算法4连杀!

第一个问题:给千万级规模整数数组做去重。我一听问题就乐了,和360那个问题简直如出一辙嘛~bitmap搞定。

第二个问题:如何从M个数中找出前N大的数。这个问题在我上面说的那篇十道海量数据处理面试题的博文里有详细解答。主要就是构建一个N个结点的小顶堆,而后将后面的每一个数和堆顶比较,比堆顶大则替换,然后维护堆。这样遍历一次以后就得到了前N大的数。时间复杂度O(M log N)。

第三个问题:给定一个整数数组,找出一段连续区间使得区间内元素和最大。这道题把我卡住了,虽然记得明明是见过的一道水题但就是想不起来方程。我只好先说,最朴素的做法是枚举区间起始点和终点,复杂度O(N^2)。优化方法是动态规划,不好意思有点紧张,让我想一下方程……过了一会儿实在紧张的没思路,只好问能否给些提示。于是面试官说,每个区间都有终点,我反应过来,状态是用区间尾表示。最终在面试官提示下写出了动归方程f(n)=max{f(n-1)+a(n), a(n)}。其中f(n)表示以n位置为区间尾的区间最大和。它有两种情况,要么是f(n-1)连上当前元素,要么是从当前元素重新开始。面试官问时间复杂度和空间复杂度。我说都是O(n)。

第四个问题:第三个问题的加强版。如果第三题是循环数组,怎么处理。这个问题比较简单,我说直接把原数组复制一份接在原数组后面,再用相同的方法做就可以了。时空复杂度不变。

到这里技术面试的部分就差不多了。又问了我是否有参加过ACM竞赛,我说我们学校没有组织组队和集训,所以我只能和同学组队报名参加一些邀请赛。

后面就进入闲聊模式。面试官和我聊学校,聊未来打算,聊出国就业,劝我不要去香港读研要去就去美国云云…总之聊得挺投机。最后例行公事“有没什么要问我的问题”,我之前准备的问题都是关于天猫的,无奈面试官表示他是支付宝的,也在阿里云呆了几年。对天猫并不了解。 面试也就差不多结束了。技术部分大约15~20分钟,非技术闲聊了十来分钟。全程大约半小时出头。

面试结束后感觉不错。第二天也果然接到了经理的电话,告知我3面技术面试都通过了。还有一轮HR不过以他对我的认识他认为问题不大(我才知道好像二面那轮就是这位经理面的),如果也通过就是去杭州天猫他的部门。后面的校园宣讲就不用参加了。听到这里我才终于如释重负……这段经历也算接近尾声。

总结

这段经历让我非常充分的感觉到,平日的积累真的很重要。人品也真的很重要(问到的问题差不多刚好在我的能力范围内,不大擅长的LINUX底层都没问)。如果正面临面试,已经没有过多时间做深入积累或者积攒人品,那就做好能做的所有准备:自我介绍,简历所有可能被问的技能和技术点,数据结构和算法(树非常爱考!然后就是动归!),以及海量数据处理题。 除此之外,在每个面试过程中,尽量在回答每一个问题时能扯到展现出自己的某一个闪光点,并且联系实际例子来证明。 最后,千万千万放平心态,不要紧张。有时候,打败自己的不是难题,而是失常发挥。另外,千万不要轻易放弃任何一个问题而直接说不知道,可以问面试官“能否给一些提示?”只要在他的引导下大概能回答个六七成,留下的印象也会大大改观。而且保不准对方一提示就想出来了呢~

最后,相信大家都会找到理想的实习,所以我也就祝大家早点达成这个成就啦~加油!  

实习应聘记(一)——简历撰写,去哪儿,360

从开始准备简历撰写,到现在基本确定实习岗位,晃晃忽忽过了大半个月。半个月说长不长,说短不短,但绝对是我这20年来最难忘的历程之一。其中经历的心态上的大起大落,只有当自己真的置身其中,才能有所体会。写下这篇博客,一来记录自己第一次应聘岗位的心路历程,二来也是想记录下几轮笔试面试的题目,希望能对各位小伙伴们准备后续面试有所帮助。

简历

我大约从3月1日开始准备简历,当时李力通知3月7号交第一稿,给实验室的学长学姐们修改。开始的几天,完全没有头绪,不知道该从哪里开始下笔。最后胡乱挑了WORD上的一个看着还顺眼的联机模板拿来改。 于是有了现在看来不堪入目的第一稿……(每稿简历的修改我都保留了备份,现在回头看来也算感慨颇多)

简历第一稿

这稿简历当时自认为还算简洁,但却被学长学姐挑出了一堆毛病,才知道原来自己有那么多细节没有注意:

  1. 留白过多,字体太小,颜色难看,不满两页。(简历要么一页写完,要么撑满两页,忌一页半。)
  2. 名字下方的信息,内容不显眼,排版不清晰。HR看到一份简历时,希望能够快速定位到手机和邮箱两个联系方式,应当前置。尤其是手机,应当用连字符分隔(形如:130-1234-5678),避免HR拨错号码,与职位失之交臂。
  3. “目标”改为“求职意向”更妥。
  4. 教育经历前置,将奖学金与专业排名等信息调整到“个人荣誉”中,HR关心的信息是何时毕业。这才是重点。
  5. “技能”中,程度副词由高到低依次是精通,熟练,熟悉,了解。因此简历中尽量使用熟练”和“熟悉”不要使用“了解”。同时,技能应当根据所应聘职位的要求,内容和顺序做针对性调整。忌同一份简历海投所有公司。当然,上面说的“求职意向”也是同理。
  6. “项目”中,把每个项目使用到的技术点前置,单独列出,有助于面试官快速了解项目。 
  7. “个人荣誉”部分,分为竞赛、奖学金、德育三块,把时间、项目、奖项分三列对齐列出,并按时间倒序排列。

大体要点就是这些,都是些容易忽略的细节。在学长学姐帮助下修改了若干稿后,得到了我在后续投递中使用的终稿:

简历2

简历是职位的敲门砖,还是需要花时间反复修改推敲的。我相信这份反复修改的简历在我的整个应聘过程中,起到了很大的作用。

去哪儿

其实严格按时间顺序,我是先接到了阿里的电话一面,然后才参加的去哪儿网笔试。但为了逻辑清晰,还是把去哪儿的笔试提到前面来写吧。

去哪儿网的简历网投其实开始的挺早,但需要在中华英才网上填一个巨繁琐的表格……我当时其实算是相当早开始填写的,但特别逗比的拖到了截止当天下午6点才提交(该死的拖延症),而后来发现去哪儿下午6点20就在官微上发布了“笔试邀请函发放完毕”的微博。于是我妥妥的没有收到邀请……

怎么办?果断霸笔呗!

去哪儿要求携带学生证和笔试邀请邮件打印稿前往西安交大笔试。因为我的确有提交简历,所以也有了一个“简历编号”。于是果断把小伙伴们的笔试邀请邮件拿来,“稍作修改”,自己给自己发的邀请函就火热出炉啦。早上10点,实验室小伙伴们结伴向交大进发。

印象非常深刻当天是3月8日妇女节。恰逢周末,路上堵得不行(中国人总是有把任何节日过成情人节的能力)。 经过一小时的士上的颠簸,即将晕车吐出来的时候,我们终于到了……找到笔试教室,发现门口一堆霸笔的人被拦下HR不让入场。但HR只会对照打印的邀请函,根本没有签到表或联网查询编号来验真伪,于是成功凭借伪造的邀请函混了进去!

当天笔试是开发与测试同一份卷子,开发做1,2,5三题,测试做3,4,5三题。题目并不能算难。

1、要求实现一个函数,对于给定有序整型数组以及一个给定整数,若整数存在于数组中,输出其位置;否则输出其应被插入的位置。例:

[1,2,3,4,5] 4 –> 3

[1,2,3,4,5] 6 –> 5

[1,2,4,5] 2 –> 1

[1,2,4,5] 3 –> 2

这道题就是一个简单的二分查找,时间复杂度O(log N)。当然一般的顺序查找也可以但O(N)解法对于这道题目来说有点太水了。我当时懒得写循环,直接4行递归写完了查找函数,然后再用要求实现的函数调用自己写的查找函数。唯一一点棘手的,是题目给的函数声明并不包含数组长度。如果是java,可以很方便的用.length()方法获取数组长度,但C就无能为力。其实去哪儿内部大量采用JAVA,因此笔试暗示用JAVA解题也不无道理。但因为自己对JAVA并不熟练所以整套卷子仍然用C答。这里我只好随意声明了个长度变量,随意用sizeof赋了个值(当然肯定是没用的)。当时只希望改卷的人不要纠结这种细节。

2、给定两个文件,格式如下:

1.txt

学号  科目  成绩

1001  数据结构  79

1002  编译原理  85

……

2.txt

学号  学院  专业  姓名

1001  计算机学院  软件工程  张三

……

要求输出每个专业总分排名第一的人的姓名,有挂科的不算。

这道题目是三道题目中最为麻烦的一道。我当时的想法是这样的,两个文件以学号为单位交叉比对每一个人并求出总分,需要M*N^2(假定N人M科),显然过于麻烦。因此首先按行读入第一个文件,将学号进行哈希(当时时间紧张直接注释这一思路并直接用f(x)=x作为哈希函数)把成绩加到哈希后总分数组相应元素中。至于挂科,我的处理是碰到<60的单科分数直接把总分减去INT_MAX来将其排出。

而后读入第二个文件,因为输出的是专业排名第一,所以学院信息直接忽略。同样哈希学号来得到每个学号对应的姓名和专业名。而后根据专业(第一关键字)和总分(第二关键字)进行双关键字的快排(只需重写compare函数就可以了,优先比较专业,相同专业比较总分)。这样得到按专业排序,同专业分数递减的结果。输出只需遍历一遍,专业名和前一个人不同的输出姓名,否则continue。求总分O(N*M),映射姓名和专业O(N),排序O(N log N)。因此总时间复杂度为O(N*M)和O(N log N)中的最大值,小于朴素的O(N*M^2)。

C语言实现的代码,整整写了正反两面A4纸……最后时间紧张还把快排失误写错了一点。 

3、给第一题写测试用例。

因为没有专门研究过测试方法,我就按我的思路分了几类:

  • 数组元素数量为奇数
  •     查找数存在
  •         查找数在开头
  •         查找数在中间
  •         查找数在结尾
  •     查找数不存在
  •         查找数在开头
  •         查找数在中间
  •         查找数在结尾
  • 数组元素数量为偶数
  •     查找数存在
  •         查找数在开头
  •         查找数在中间
  •         查找数在结尾
  •     查找数不存在
  •         查找数在开头
  •         查找数在中间
  •         查找数在结尾

共3级12类测试用例。

90分钟,我掐着点做完交卷。 当时感觉还行,至少把能展现的能力都尽量展现了。而后来也成功接到了笔试通过,等待电话通知面试安排的短信,说明结果也是不错的。这场笔试为我树立了比较大的自信。 也让我对霸笔霸面不再有那么强的紧张感。

360

360的职位是实验室学姐帮助内推的,系统部,负责360的底层技术和大数据平台。 当时是在一堂“跨文化交流”课上,突然来了一个010开头的电话,一看来显猜测是360的电面就赶忙出来接了。

这是我整个应聘过程中感觉发挥的最差的一场,以至于面完后我一度认为自己没有通过的希望。

面试官是典型的按简历一条一条向下过的面试思路。他注意到我的获奖经历中有提到ACM-ICPC(虽然只是一个水水的Honorable Mention,可见企业对于ACM竞赛经历是多少看重 ),技能中又提到了算法与数据结构,因此直接从数据结构开始问。

第一个问题,描述一下如何建立一棵二叉树

这个问题我就有点蒙,建立一棵树,这怎么说啊?我回答这要看具体的问题需求还有输入数据的格式,可以按照线性存,用2n和2n+1存左右孩子;也可以按链式存,节点以指针相连建树。

第二个问题,非递归遍历二叉树

脑子里直接蹦出栈了,但是因为电面太突然,脑子一下有点白,愣是没描述清楚具体过程,吭吭哧哧卡了一会儿,才说出先 压树根,而后每出栈一次,将非空的左右孩子入栈。直到栈空,遍历完毕。 

第三个问题,给出不重复但不保证全部出现的1~10亿间的自然数,进行排序。

面试前没有准备大数据类型题目,其实这是一道很经典的题。我当时只能回答,可以用桶排的思想,先将数按高位分为若干个文件,再依次细分文件,外部排序。或者使用外排归并。面试官直接说,直接读内存放不下,外排磁盘IO过高。我想了一下没想出其他方案,最后面试官告诉我用bitmap……这个问题回答的不好让我一下对这场面试更加没信心了。 

后面就是快速过了一下我简历上的每一个项目。当时因为先接到阿里的一面电面,面试官会抓着项目某个技术点深挖,因此当360面试官问我某个项目时,我只是很笼统的概述了一下,等待他问具体技术细节。没想到他竟然就这样很快的过掉了简历上的三个项目,没一个问到技术细节。又问了“何时能入职”等常规问题,而后直接跟我说等待通知,结束了面试。也没问我是否有问题要问他。整场面试只持续了13分钟,出奇的短。这也直接让我对这场面试的结果失去了信心。心情瞬间跌到谷底。 这些题目根本不算难,甚至可以说相当基础,但我却答得不好……

没想到次日内推的学姐就告诉我面试结果不错,通过了,并且没有后续的技术电面,只要等HR和我联系就行了。

这个结果大大出乎我的意料,但也是我通过的第一个职位,给了我很大的鼓励。

下面就是阿里的三轮技术面试了,因为过程较长内容较多,同时也是这段时间的主要内容,后面单开一篇博文写。有兴趣的读者可以继续阅读下一篇博文《实习应聘记(二)——阿里,总结》 

最小编辑距离 算法原理

问题

最小编辑距离 Minimum Edit Distance
关于两个字符串s1,s2的差别,可以通过计算他们的最小编辑距离来决定。
设A、B为两个字符串,狭义的编辑距离定义为把A转换成B需要的最少删除(删除A中一个字符)、插入(在A中插入一个字符)和替换(把A中的某个字符替换成另一个字符)的次数,用ED(A,B)来表示。直观来说,两个串互相转换需要经过的步骤越多,差异越大。
例如 s1 = “12433” 和 s2 = “1233”;
则可以通过在s2中间插入4得到12433与s1一致。
即 d(s1,s2) = 1 (进行了一次插入操作)

性质

计算两个字符串s1+c1, s2+c2的编辑距离有这样的性质:

1.   d(s1,"") = d("",s1) = |s1|
     d("c1","c2") = c1 == c2 ? 0 : 1;
2.   d(s1+c1,s2+c2) = min(  d(s1,s2)+ c1==c2 ? 0 : 1 ,
                            1 + d(s1+c1,s2),
                            1 + d(s1,s2+c2)  );

第一个性质是显然的。
第二个性质: 由于我们定义的三个操作来作为编辑距离的一种衡量方法,于是对c1,c2可能的操作只有:

1.  把c1变成c2
2.  s1+c1后删除c1              d = (1 + d(s1, s2 + c2))
3.  s1+c1后插入c2              d = (1 + d(s1 + c1, s2))

对于2和3的操作可以等价于:
_2.   s2+c2后添加c1        d = (1 + d(s1, s2 + c2))
_3.   s2+c2后删除c2        d = (1 + d(s1 + c1, s2))

因此可以得到计算编辑距离的性质2。

复杂度分析

从上面性质2可以看出计算过程呈现这样的一种结构(假设各个层用当前计算的串长度标记,并假设两个串长度都为 n )
可以看到,该问题的复杂度为指数级别 3 的 n 次方,对于较长的串,时间上是无法让人忍受的。
分析: 在上面的结构中,我们发现多次出现了 (n-1,n-1), (n-1,n-2)……。换句话说该结构具有重叠子问题。再加上前面性质2所具有的最优子结构。符合动态规划算法基本要素。因此可以使用动态规划算法把复杂度降低到多项式级别。

动态规划求解

首先为了避免重复计算子问题,添加两个辅助数组。
一. 保存子问题结果。
M[ |s1| ,|s2| ] , 其中M[ i , j ] 表示子串 s1(0->i) 与 s2(0->j) 的编辑距离
二. 保存字符之间的编辑距离.
E[ |s1|, |s2| ] , 其中 E[ i, j ] = s1[i] = s2[j] ? 0 : 1
三. 新的计算表达式
根据性质1得到

M[ 0,0] = 0;
M[ s1i, 0 ] = |s1i|;
M[ 0, s2j ] = |s2j|;

根据性质2得到

M[ i, j ]   = min(  m[i-1,j-1] + E[ i, j ] ,
                    1 + m[i, j-1] ,
                    1 + m[i-1, j]  );

复杂度
从新的计算式看出,计算过程为

      i=1 -> |s1|
             j=1 -> |s2|
                    M[i][j] = ……

因此复杂度为 O( |s1| * |s2| ) ,如果假设他们的长度都为n,则复杂度为 O(n^2)

改进

当s[i]和s[j]相等时,代价为0,必然为最小值,所以首先判断两字符是否相等,若相等则直接判定M[i][j]=M[i-1][j-1],判断下个。这样可以省很多计算。

工具宏:直接用一个宏来完成“求取三者最小值”的功能。不同于递归,宏定义消耗很小,完全可以放心使用。

#ifndef _MIN(xyz)
#define _MIN(xyz) ((x<y)?((x<z)?x:z):((y<z)?y:z))
#endif // _MIN(xyz)

再议LCS(最长公共子序列)

上次在实验室作《从分治到动归 – 最优问题解法》的讲座的时候,举了LCS(最长公共子序列)作为例子。当时讲的是传统的动态规划解法。下面先提一下这个解法作为铺垫。

LCS问题

LCS是Longest Common Subsequence的缩写,即最长公共子序列。一个序列,如果是两个或多个已知序列的子序列,且是所有子序列中最长的,则为最长公共子序列。

例如:

X={A,B,C,B,D,A,B}

Y={B,D,C,A,B,A}

则X和Y的最长公共子序列(之一)是{B,C,B,A}

传统动归解LCS

设有二维数组f[i,j] 表示 X 的 i 位和 Y 的 j 位之前的最长公共子序列的长度,则有:

f[i,j] = max{f[i-1][j -1] + same(i,j),f[i-1,j],f[i,j-1]}

其中,same(a,b)当 X 的第 a 位与 Y 的第 b 位相同时为“1”,否则为“0”。

初值:f[i][0]=0 f[0][i]=0 f[1][1] = same(1,1)

这个动归方程乍看可能不好理解。它的思想是这样的。

对于已知f[i][j]的值,要往后拓展,有这两种情况:其末位i和j相同,或不相同。

考虑相同情况。因为i和j相同,它们必然已被记入最长公共子序列的部分。此时要想延长这个公共子序列,只得令i和j都向后移,看看它们后一位是否也相同。这就是f[i][j]+same(i+1,j+1)。

而对于不同情况,有这几种可能: 虽然第i和j位不相同,但i和j+1是相同的。此时要想延长,便是f[i][j+1]的情况。当然也可能i+1和j相同,便是f[i+1][j]的情况。

综上,写成递归式,因为不知道前一个状态的情况,所以便在这三种可能中取最大值。此时f[i][j]变为f[i-1][j-1],f[i][j+1]变为f[i-1][j],f[i+1][j]变为f[i][j-1]。便得到了上面的递归式。而初值很好理解,这里就不赘述了。

不难算出,这个算法的时间复杂度是O(n^2),空间复杂度也是O(n^2),但因为状态只与上一行有关,所以可以将空间复杂度优化至O(n)。

另一种解法?(以下内容有误,13/10/25勘误)

网络上还能找到另一种解决这个问题的方法:

(1)将两个字符串分别以行和列组成矩阵。

(2)计算每个节点行列字符是否相同,如相同则为1。

(3)通过找出值为1的最长对角线即可得到最长公共子串本方法只能得到最长连续公共子串,下列讨论关于最长公共子串全部应替换为最长连续公共子串。

为进一步提升该算法,我们可以将字符相同节点的值加上左上角(d[i-1,j-1])的值,这样即可获得最大公共子串的长度。如此一来只需以行号和最大值为条件即可截取最大子串。

这个方法非常好理解,直观易懂。而不难发现它的时间复杂度,竟然也是O(n^2),空间复杂度也可以由O(n^2)优化到O(n)!

这是巧合吗?

我们来分析一下这个做法。首先我们能总结出这个方法的递推式:d[i][j]=d[i-1][j-1]+same(i,j)。是不是很眼熟?但和上面的还不大一样啊?缺了两种情况呢。

别急,这个方法还需要在全矩阵中找出最大的值。而上面的动归方程,分散在各个状态求max的过程,合并起来,不就是求全矩阵的最大值吗?这段也有错误。详见下方勘误。

殊途同归!

动归解法通过记录各个不同截取位置的方法,避免朴素解法中的重复比较,从而提升了效率。而这个方法中的矩阵,其作用不难发现,也是一种记录的行为。

思想只存于我们的脑子中,我们的思维使算法发生了变化。但其结果,却殊途同归。

算法,是一种哲学。

2013年10月25日勘误

打造群博2:借助WP-o-Matic实现RSS自动抓取

上一篇我们讲到了关于改造模板使得文章只显示摘要以方便阅读,这一篇我们来讨论下如何基于WordPress来实现自动根据RSS抓取文章的群博功能。

介绍一下这个强大的插件:WP-o-Matic。这是我试了N个不同插件之后唯一能用而且效果还行而且支持中文的RSS抓取插件……它也是一个开源项目,目前的最新版本是2.3.9。
Continue reading “打造群博2:借助WP-o-Matic实现RSS自动抓取”

打造群博1:将WP模板首页显示全文改为显示摘要

这两天在帮小组搭建群博,在此记录一下整个过程中学到的一些关于WordPress的技巧。

不得不说WordPress真的是一个非常强大而灵活的建站工具。丰富的插件和主题都给了它非常自由的发展空间。

话不多说,先来看看遇到的第一个问题:挑了一个看起来不错的模板,无奈其目录页(首页,分类等)都是全文显示博文,使得查看很不方便,页面加载也慢。后台并没有提供修改显示全文还是显示摘要的功能,怎么办呢?
Continue reading “打造群博1:将WP模板首页显示全文改为显示摘要”