【实习记】2014-08-29算法学习Boyer-Moore和最长公共子串（LCS）问题——阿里校招题

2014-08-29T21:23:00+08:00

最长公共子串问题分析¶

其实这是一个序贯决策问题，可以用动态规划来求解。我们采用一个二维矩阵来记录中间的结果。这个二维矩阵怎么构造呢？直接举个例子吧：”bab”和”caba”(当然我们现在一眼就可以看出来最长公共子串是”ba”或”ab”)

b　　a　　b

c　　0　　0　　0

a　　0　　1　　0

b　　1　　0　　1

a　　0　　1　　0

我们看矩阵的斜对角线最长的那个就能找出最长公共子串。

不过在二维矩阵上找最长的由1组成的斜对角线也是件麻烦费时的事，下面改进：当要在矩阵是填1时让它等于其左上角元素加1。

b　　a　　b

c　　0　　0　　0

a　　0　　1　　0

b　　1　　0　　2

a　　0　　2　　0

这样矩阵中的最大元素就是最长公共子串的长度。

在构造这个二维矩阵的过程中由于得出矩阵的某一行后其上一行就没用了，所以实际上在程序中可以用一维数组来代替这个矩阵。

代码实践¶

根据以上算法使用C语言实践了一下。

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int comfix(const char* stra, const char* strb);
int main(void){
    const char
        *stra = "hello world",
        *strb = "malloc";
    printf("%s,%s: %d\n", stra, strb, comfix(stra, strb));
    return 0;
}

int comfix(const char* stra, const char* strb){
    /*
     * 变量第一字符
     * c:char*, l:len
     * 变量第二字符
     * s:small, l:large
     */
    const char
        *cs  = stra,
        *cl  = strb;
    int ret = 0,
        la  = strlen(stra),
        lb  = strlen(strb),
        ls  = la,
        ll  = lb;
    /* 如果不对，就调换呗 */
    if (lb<la)
        cs = strb, ls = lb, cl = stra, ll = la;
    /* 矩阵，只保存矩阵的一行即可动态之 */
    int *pint = (int*)malloc((ls+1)*4);
    memset(pint ,0 , (ls+1)*4);
    int i, j;
    for (i=0; i<ll; i++){
        /* 生成下一行，同时上一行内容被回收 */
       for (j=ls; j>ret; j--)
           if (cl[i]==cs[j])
               pint[j] = pint[j-1]+1;
       /* 如果有更大就更新ret */
       for (j=ls; j>ret; j--)
           if (pint[j]>ret)
               ret = pint[j];
    }
    return ret;
}

这种算法非常巧妙地化繁为简，有时换一个思路，就会扩然开朗！

比较喜欢这种锻炼。

参考¶

研究了求最长公共子串问题，顺便研究了字符串匹配

字符串匹配的Boyer-Moore算法 http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html

字符串匹配的KMP算法 http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

动态规划算法之：最长公共子序列 & 最长公共子串（LCS） http://my.oschina.net/leejun2005/blog/117167

腾讯2014实习面经——记一个非计算机学生的首次面试

2014-04-30T23:58:00+08:00

地点：华南理工大学大学城校区，为广州考点。

流程：网申3.X + 笔试4.12 + 一面4.15 + 二面4.17 + 三面4.19 + 签约4.25

前言¶

腾讯实习招聘笔试到拿到offer（软件工程师-研发反向），历时两星期，只算笔试到终面的话则是一星期，效率比阿里要好。

腾讯是我的处面，一路过来我没有夸张，只是平实的叙述我的故事，认真谨慎的答问。

我容易紧张，但幸好没有太紧张。

2014-3-18 网申（宣讲会在大学城太远了跳过～呵呵）¶

(^0^)

准备：

1、寒假就开始准备，主要是重拾算法，发现没之前开始学编程那么难了。

2、寒假期间pythontip有个挑战python，做72题后排第三名。挑战最长回文，最长上升子串等算法题，综合能力提升。

3、看完《编程珠玑》和《编程之美》。

4、google面经，做往年题练手。

5、Linux下gcc+vim实践7大经典排序算法（这个效用较高）。

6、精心准备的简历，3月8号就做了1.0版，后修改不下10次，要求尽量简洁美观。

2014-4-12 周六 14:30 - 16:00 笔试¶

×—×

心情：

1、收到信息，知道阿里笔试被鄙视了。

2、三个项目在手（都是不感冒的web项目-_-）。

3、报大创，课程作业，等等等等……，一个字，累！

内容：

1、20不定选择（一半把握）填空5题（4题把握）附加2题（会后一题）。

2、C语言C++，操作系统，网络，数据库，经典算法，数学IQ题加起来占80%以上吧。

感受：

做的不上不下，做得快，但修改得多。交卷到了，还把一题对的改错了，囧。

后记：

1、打击过后的我只敢保守地估计，谨慎地乐观，默默地独自回校。

2、心中感觉一些轻松，一些冷漠，像我本是局外人。

2014-4-15 周二 10:00 - 11:00 一面单面¶

T_T

过程：

1、面试官是位大叔，讲话少，自我介绍时“嗯”了很多，有时闭着眼在听。

2、以C语言的宏的作用是什么开头，问了我很多广泛问题。

3、幸好C语言，C++我都记得，答取结构偏移址，宏用途，宏在C与C++之间重要性的区别还答得上。

4、但是问到数据库时瘪了，索引什么的更是一知半解（本来至少应该摆个二分法），大数据找重也不好的。最记得让我描述http协议，我不知从何说起，各点都提一提。

5、我尝试过避开这些，引导到Linux上，无效。越到后面我就越觉得机会小。

6、最后让我一边去写strcpy，我用了assert，并加上测试，还应此知道缺const。

感受：

1、没玩过游戏，但我觉得一个初出茅庐的0级玩家被40级玩家虐的时候也是这样吧。

2、我知道简单问题考细节，幸好这时刻这点我做得不错。

3、从专业名看到话面试官还是以为我技术出身，幸好后来我答题时明确说明了。

4、答题是不坚定，没自信，这是我的弱点。

后记：

1、阿里铩羽而归后的又一次打击，本来觉得我应该无后文，继续华为，小米，百度实习关注填表。

2、我后来惊喜收到二面短信，可能和我很重实践，Linux，github，操作系统代码有关。

3、当时答得不太好的如socket，进程通信，netstat -ptln我都马上复习了，为了别的面试。结果让我在二面表现更好。

2014-4-17 周四 8:30 - 9:00 二面单面¶

^-^

过程：

1、自我介绍8分钟，以Ubuntu14.04正式版发布这开源新闻开始，还是那篇讲学习经历和项目的自我介绍。最浓缩就是：windows->Linux->Python。期间他有打断问我具体细节，我都详细作答了。

2、他问我有没有纸，我说8太早了工作人员让我直接去房间。面试官有些失望的样子，我在暗想，草稿纸算法题目必需的，这是对我故意的眷顾，会不会是上个面试官的特意安排吗？不知道，也许就是偶然的幸运。

3、面试问题问细节比较多，问的深度和一面挺像，所以感觉没什么压力。

4、面试官过程中礼貌而中肯地多次说”OK”，最后说“OK，现在你有几分钟时间问我问题。”。

5、我问了腾讯与开源的一个烟雾弹问题，还问微信未来是否会像易迅一样开微店，——干脆利三个字“有可能”——意料之中，然后我们最后握手告别。

感受：

1、一开始面试官就看出我的紧张，他笑着指出了。还好之后整个过程都比较轻松。

3、能到这里其实我是满足的，不管怎样。

4、我在最后的一瞬间感觉到了一种肯定，那握手和神情。但我依然很保守地乐观。

后记：

1、出来后心情，做番201去星海过程中观赏者大学城。

2、回去过程在回想面试，面试官给我感觉挺好的，他当时穿了米黄色衬衫，中等身高有点胖，印象中头发有点蓬松，和脸相搭。

3、出来后直到回学校，觉得我是幸运的。

2014-04-19 周六 15:22 - 15:37 三面单面¶

(^w^)

感受：

1、微信状态变成HR面是很开心，因为有HR不怎么刷技术岗之说。同时感概些许，也许就在前面了，但我告诫自己绝不能倒在这关。

2、告诉舍友我到HR时，他们都为我高兴了，我们笔试时几乎全宿舍都去了（光说动员，6人中5人去了-_-）。

3、紧张而兴奋，期待而舒畅的等待着。

过程：

1、面试官还是男性，还是那份简历，还是华工大学城中心酒店。

2、15分钟，自我介绍，和HR聊天，我不太健谈，不过还算一个愉快的过程。

3、最后让问问题，查笔试成绩没成，问可能去向问到了。

后记：

2014-04-25，offer终签成，一件好事来了。哈哈。

面试经历总记：¶

我是个粗心人!

1、14号晚收到一面通知在15好，而我以为当天是13号，睡前发现这个“BUG”，起来准备到2点才睡，第二天7点起床。

2、微信查进度jg这两字符总漏了，“修复”后得到第一个回复是处在到HR面中。我的色弱也许占部分原因。

3、我是个不懂得察言观色，后知后觉型小傻呆。所以无法把握自己的面试，最近有看《Lie To Me》，对没能运用这知识有点遗憾。

我是个认真务实好学的人！

1、自学C/C++，java，html/css/js，kenerl，Linux，Shell，Python等等。

2、为应聘做了很多的准备，寒假就开始，有针对性的练习算法，多次锤炼简历，2小时准备的自我介绍586字。

3、不懂时就问，敢问，问得很多，感觉有时被鄙视了（我想懂得范畴以外，我都是白痴）。

4、边学边实践，边看书籍，边写敲键盘。因此记得还算牢固，学习速度还可以。

5、不是到用的时候才有，而是到用的时候来总结。所以不会被问到哑口无言。

经验总结

后来我猜，自学能力，多种语言，C/C++功底，Linux，blog，github，项目，这些是决定我能留下来的组成部分。

其他：¶

我是谁？我是大学开始自学技术的商科学生

1、技术的我：一个Linux与Python爱好者，关注开源和C/C++，使用Vim编辑器，喜欢Shell下工作。（技术宅？不是的，希望像耗子大叔一样。）

2、学生的我：一个商科11届大学生，来自广东文科老二，理科老三的（按高考分数线的话）211暨南大学(JNU)。大学以自学副业为主，暂没获得过奖学金。

3、生活的我：爱好比较广泛（童心OR好奇心……随便吧-_-）；历史(春秋迷)，登山(户外迷)，排球还不错，听电台，LoveQ。听电台的90后不多了，我就是其中之一，嘻！

关于

关于简历。word是彩版，但印的是黑白，怕面试官认为华而不实。（-_-,也许心疼成本才是真，囧）。

关于招聘。搜“算法+数据结构”可能还不如你搜“笔试面经”获得的结果好，强，全。

关于经验。腾讯2013暑期实习生招聘经历分享对我很有帮助，作者是同校同乡的上一届师兄。这后来成为我写本文的原因一部分。

关于暨大。个人认为腾讯与暨大之间存在信息不对称问题，结果导致暨大实习生比例过低。前几年均如此。当然也不排除暨大自身问题啦。

关于腾讯。我明白获得实习offer只是开始，但是腾讯给出的资薪待遇挺不错的，至少对于我，呵呵。

关于自学。图书馆 -> google -> 独立博客 -> rss鲜果 -> 开源。遇见Linux是转哲点。

我用到过的好资源共享：

别的程序员是怎么读你的简历的 http://coolshell.cn/articles/1695.html

找工作笔试面试那些事儿（系列） http://blog.csdn.net/han_xiaoyang/article/category/1664765

白话经典算法 http://blog.csdn.net/morewindows/article/details/17488865

程序员面试、算法研究、编程艺术、红黑树、数据挖掘5大系列集锦 http://blog.csdn.net/v_july_v/article/details/6543438

2014年计算机求职总结–准备篇 http://blog.csdn.net/luckyxiaoqiang/article/details/13000431

《程序员编程艺术 — 面试和算法心得》 https://github.com/julycoding/The-Art-Of-Programming-By-July

《剑指Offer——名企面试官精讲典型编程题》博客 http://zhedahht.blog.163.com/

Linux迷+Python粉 - 校招

【实习记】2014-08-29算法学习Boyer-Moore和最长公共子串（LCS）问题——阿里校招题

最长公共子串问题分析¶

代码实践¶

参考¶

腾讯2014实习面经——记一个非计算机学生的首次面试

前言¶

2014-3-18 网申（宣讲会在大学城太远了跳过～呵呵）¶

2014-4-12 周六 14:30 - 16:00 笔试¶

2014-4-15 周二 10:00 - 11:00 一面 单面¶

2014-4-17 周四 8:30 - 9:00 二面 单面¶

2014-04-19 周六 15:22 - 15:37 三面 单面¶

面试经历总记：¶

其他：¶

2014-4-15 周二 10:00 - 11:00 一面单面¶

2014-4-17 周四 8:30 - 9:00 二面单面¶

2014-04-19 周六 15:22 - 15:37 三面单面¶