0%

链表的结构比较简单,基本特性以及相关操作这里就不作介绍。如果有同学不自信的话,这有个pdf文档可以参考复习下。http://cslibrary.stanford.edu/103/如果有同学网络问题不给力的话,可以给我发邮件。下面来看几道常见的面试题。

1.链表倒置(两种方法)

这个应该也算比较简单的,直接上代码了。(两种:迭代、递归)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void reverse_iterate(struct node** head)
{
  struct node* result = NULL;
  struct node* current = *head;
  struct node* next;

  while(current != NULL)
  {
  next = current->next;

  current->next = result;
  result = current;
  current = next;
  }
  *head = result;
}

void reverse_recursive(struct node** head)
{
  struct node* first;
  struct node* rest;

  if(*head == NULL)
  return;

  first = head;
  rest = first->next;

  if(rest == NULL)
  return;

  reverse_recursive(& rest);

  first->next->next = first;
  first->next = NULL;

  *head = rest;
}
Read more »

3sum问题就是3数求和问题,可以简单描述如下:给定数据集S找出数据集中的三个元素a,b,c,满足a+b+c=k。直接可能没什么思路,其实3数求和问题可以看成是下面这个问题的扩展:给定数据集S,找出所有数据对a,b,满足a+b=k。

其实对于原始问题的求解时间复杂度可以达到O(n),如果数据集是已排好序的。分别在头部和尾部设置两个指针,求其和,如果大于K,则尾部的指针向头部移动,否则头部的指针向后移动。用C语言简单实现如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void find2sum(int dataSet[], int itemNum, int key)
{
int left=0;
int right = itemNum-1;

while(left<right){
if(dataSet[left]+dataSet[right] == key)
printf("The pair (%d %d) bingo!", left, right);
else if(dataSet[left]+dataSet[right] < key)
left ++;
else
right --;
}
}

对上面的方法进行扩展就可以得到3数求和问题的解答了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void find3sum(int dataSet[], int itemNum, int key)
{
int i, left, right;
sort(dataSet);
for(i=0; i<itemNum-2; i++){
left = i+1;
right = itemNum-1;
while(left<right){
if(sum(i, left, right) == key)
printf("triplet %d %d %d bingo!\n", i, left, right);
else if(sum(i, left, right) < key)
left ++;
else
right ++;
}
}
}

如果文章从这儿就结束了,那也没有写的必要了。

前面求解两数求和问题的时候提到了数组是排好序的,利用这一特性我们可是可以大做文章了。例如:如何求解两个已排序数组的公共子序列?

首先说明下,公共子序列和公共子串是不同的。公共子串是连续的,而公共子序列则没有这一限制。比如{1,2,3,4,5,6}的子序列可以是{1,3,6}。

我们不妨设置两个数组分别为AB,长度分别为mn。结合上文,很容易可以得到时间复杂度为O(m+n)的解法。分别设置两个指针指向两个数组,然后比较,将较小的指针往前移动即可。

另外说到排序好的数组,一个自然反应应该就是二分查找了。对于数组A中的每个元素,对数组B进行二分查找,时间复杂度为O(mlgn)。其实这个讨论是有必要的,当m<<n时,这种方法明显优于上面的。

其实个人觉得效率还可以更高,只要将上面两种方法结合起来,定性描述如下。第一种方法的思想,当找到A[i]=B[j]的时候,下一次对B进行二分查找的时候,只需要查找B[j+1, n-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void commonSeq(int A[], int B[], int m, int n)
{
int index_A, index_B, result;

index_A = index_B = 0;
while(index_A<m && index_B<n){
result = bisearch(B, index_B, n, A[index_A]);
if(-1 == result) /*使没查找到时返回-1*/
index_A ++;
else{
printf("%d\t", A[index_A]);
index_A ++;
index_B = result+1;
}
}
printf("\n");
}

还有一些,以后再说吧!
see you!

开篇点下题,题目出自韩寒的《我所理解的生活》。

再开始本文之前,先感谢下当当的网络书香节。知识无价,但是知识的载体是有定价的。我等区区一介书生,实在是囊中羞涩。在网络书香节期间,当当的书特价,可能有些书是压在库底的,但是只要你分享了,我们都感激你。

好了,对于韩寒,脑海中只有作家的印象。我一直觉得标签是一些人的主观想法,所以在我认识之前,我不打算用别人的标签,所以这里就不过多评论韩寒,只讨论书。说到书,我也只是在大三的暑假读了韩寒的《1988,我想和这个世界谈谈》。当时感觉文风枯燥,可能是一种韩式风格,只不过我不太喜欢。相比之下,还是韩寒的杂文来的痛快。

回到题目上来,可能有人要问这句话是个什么意思。我并不打算来个语文老师式的剖析。一来是因为自己的语文是硬伤,二来是因为我觉得那些剖析也不过是标准答案的口语版本罢了。所以还是先看下原文吧。

“我逐渐觉得,一个好的写作者在杀戮权贵的时候,也应该杀戮群众。2011年间早些的一些文章,从写钱云会村长的《需要真相还是需要符合需要的真相》,我就开始有所变化。当然,在批评中,如果两者并列,则应先批权贵,因为很简单,权贵捞着利益了,苦全是平民受的。但这不代表一个好的作家应该无穷尽无底线的讨好民众。你说民众多么好多么对多么善良多么高素养,民众应该得到什么什么,民众应该享受什么什么,天赋民众各种权,民众的眼睛不光是雪亮的,而且都是双眼皮……”

自古以来,侠客式的“劫富济贫”都备受青睐。这里先不论“不义之财”的问题。但是你们有没有考虑过富人的感受?如果你感受不了,那么当你的东西被别人抢去的时候是什么心理。

权贵毕竟是少数,我们大部分人一直都在扮演着群众的角色。我想再杀戮权贵之前,可不可以先自我反思一下。还有对于杀戮权贵的快感究竟从何而来?

现在网络开放了,大家可以在网上可以完全不负责任的意淫以彰显自己的不同。有些人发着看似高端的,实际上自己都不曾了解的东西。乔布斯死去的当天,校内网的果粉整页整页地在刷屏,后面还有一排小字“来自nokia XXX”。还有的人,为了自己页面的访问面,转载着类似“我爸是李刚,我跑不了的”的言论,更可笑的是下面的评论。李刚的儿子可不需要你的博爱,需要的人在大西北。还有一些伪爱国青年,整天在网上吵吵“我们爱国”,“世界黑暗”,“政府腐败”,然后“该去打dota了”。真正的爱国学生运动发生在80年代,但那也只是热情。我们需要更多的思考,关于如何去使我们的祖国更好的思考,而不是逃避。

下面再引用韩寒的一段话送给各位同学。

“到了2010年,我做的很多批评几乎都是有罪推论和变种八股——制度不好,政府腐败,悲剧发生,人民可怜。我想在任何社会里,这样的批评都会受到民众的欢迎。因为执政者的腐败和贪婪,这个社会官民对立严重。是啊,你在任何地方,对任何人说,咱们真是可怜,你的上司是个屁,他弄砸了这么多事情,还开好车养小蜜。以你的能力,远不应该只获得现在这些,而且凭什么让那个傻逼当你上司,人人都有当上司和换上司的权利,他的那些东西,都应该是你的。这话除了那个上司不爱听,谁都觉得说到他自己心坎里去了。我这么写文章,再加几句俏皮话,大家肯定都觉得我说的特别好,而且凡是不赞同者,皆会被民众说成五毛,是权贵之走狗,民主之敌人。就算想批评我两句,也得先夸一千字,才能委婉提上一两句,否则很容易引起不满被戴上各种帽子,就像我批评的那些人给其他反对者扣帽子一样,所谓左右之间互相从来都没有协商和妥协。当我发现批评我的人越来越少或者越来越小心翼翼的时候,我自然高兴了一阵子,但后来我总觉得不对劲,我知道无论我说的多么对,我必然有地方错了。

这个时代可能有错,但是我们难道就没有错吗?我们要有一种精神,这个民族才能有未来。这种精神就叫作:思想!

对于这句话大家应该都不会陌生,这句话让史蒂夫·乔布斯创造了一流的公司,而乔布斯也让这句话为众人所知。我就当回标题党,以这句话来作为读完乔布斯传记后的感想的文章标题了。分享一下。

一、优秀的艺术家抄袭,伟大的艺术家剽窃

—Jobs: Ultimately it comes down to taste. It’s a matter of trying to expose yourself to the best things that humans have done. And then try to bring those things into what you are doing. Picasso had a saying: “Good artists copy. Great artists steal.” We have always been shameless about stealing great ideas.
—乔布斯:其实归根到底是品位的问题。你要尽量让自己接触到这个世界上最优秀的产品,并把它运用到自己的工作中去。毕加索说过:“优良的艺术家抄袭, 伟大的艺术家偷窃。”当我们剽窃别人的卓越的创意的时候,从不觉得羞愧。“优良的艺术家抄袭, 伟大的艺术家偷窃。”
这句话原话是毕加索说的,至于毕加索当时说这句话是什么想法,各位学术帝也大可不必深究。真正的大师是要靠他的读者的,“导演们在电影上映后都要去豆瓣社区看下电影影评,才领略到自己电影的内涵”。
简述一下事件:施乐PARC,也就是施乐公司的帕洛奥图研究中心(Palo Alto Research Center),最先提出的图形用户界面,乔布斯在参观后凭借其敏锐的洞察力成功将其收入旗下,并且做出了更好的图形用户界面。对了,还有鼠标。乔布斯引用毕加索这句话,就是在告诉世人,普通的艺术家善于模仿,但其作品只能达到形似,却缺乏灵魂;伟大的艺术家不耻于“剽窃”,他们从不盲目地拾人牙慧,而是青出于蓝胜于蓝,最后自成体系,成为领域的领军人物。
无独有偶,看过电影《社交网络》(忽略此处的书名号吧!)的人对于facebook的创始人也有同样的情节。MicroSoft同样。不管是抄袭还是剽窃,都需要我们站在别人的角度下来重新审视一件事,而思考的深度会有那么一点点的影响,而真正起作用的往往就是这么一点点。从某个角度来看,这也是推动人类文明进步了。所以下次当我们嘲笑别人的时候,还请先想一想自己是不是有那个能力,抄袭也好,剽窃也罢!

二、专注成就卓越

乔布斯对用户体验的执著值得我们所有人学习:专注。
乔布斯的极致还表现在他的专注力上。他会设定优先级,把他激光般的注意力对准目标,把分散精力的事情都过滤掉。如果他开始做某件事——麦金塔早期的用户界面,ipod和iphone的设计,把单薄公司引进iTunes商店——他就会非常专注。但是如果他不想处理某件事——法律纠纷,业务事项,他的癌症诊断,某件家事——则会坚决的忽视它。那种专注使他能够说不。他只保留几个核心产品,砍掉一切其他业务,让苹果回到正轨。他剔除按键让电子设备简单化,剔除功能让软件简单化,剔除选项让界面简单化。
我想,他的专注,他的至繁归于至简的理念值得我们所有人学习,毕竟“吾辈也有涯”。

该休息了。最后以乔布斯在中央公园对斯卡利说的一句话,“你是想卖一辈子糖水呢,还是想抓住机会来改变世界”,来结束吧。你我共勉!!!

CSAPP是以前在IBMTC大家对Computer Systems: A Programmer’s Perspective的简称,中文名字是《深入理解计算机系统》。这本书我就不介绍了。最近拿出来温习一下,顺便把这本书上的实验再做一下。

实验主要有:数据实验,二进制炸弹实验,缓冲区溢出实验,体系结构实验,性能实验,shell实验,malloc实验,代理实验。争取都做了吧!

数据实验具体如下:函数srl使用算术(由值xsta给出)来执行逻辑右移,紧跟着的是其他不包括右移或者除尘的运算。函数sta使用逻辑(值由xstrl给出)来执行算术右移,紧跟着的是其他不包括右移或者除法的运算。可以假设int是32位长的,移位量k的取值范围是0~31.

一般而言,机器支持两种形式的右移:逻辑右移和算法右移。逻辑右移在左端补k个0,算术右移是在左端补k个最高有效位的拷贝。所以我们只要设计一个掩码就好,还是比较简单的。

1
2
3
4
5
6
7
8
9
unsigned srl(unsigned x, int k)
{
/*Perform shift arithmetically */
unsigned xsra = (int) x >> k;
/* Make mask of low order 32-k bits*/
unsigned mask = k ? ((1<<(32-k))-1) : ~0;

return xsra && mask;
}
1
2
3
4
5
6
7
8
9
int sra(int x, int k)
{
/*Perform shift logically*/
int xsrl = (unsigned) x >> k;
/*Make mask of high order k bits*/
unsigned mask = k ? ~((1<<(32-k))-1) : 0;

return (x<0) ? mask | xsrl : xsrl;
}

关于移位运算还有一点要注意是优先级问题:1<<5-1等价于1<<(5-1)而不是(1<<5)-1.

上一篇面经写完之后就去赶火车了,昨天到达帝都,空气还不错

之前说到要将linux命令统一来作个总结,今天刚意识到这句话说的真是不严谨啊!linux下面命令实在是太多了,下面对我在面经中接触的命令以及后来实习工作中接触的常用命令作一个总结,至于其它的,我尽量补上吧!

下面要介绍的主要是文本处理方面的命令

Read more »

马上实习离职,写下实习的面经给要实习的同学作个参考。有点久了,尽可能的还原吧。

刚提交简历不久,就有个MM(应该是HR)给回复了,直接打电话来约面试时间,时间定下来之后,邮件里又确认了下等等。不得不说,百度的HR还是很不错的

先说下我面试的职位是云计算开发测试工程师实习生,百度的云计算部门在鹏寰大厦,这名字有点难写,不知道有没有写错。

一面的面试官是个GG,人很nice,后来实习中经常遇到。抱着个笔记本就下来了,没有穿脱鞋,头发也不乱,看来QA应该不是很辛苦。上来第一句,“哈工大的啊?”,我一听,难不成遇到师兄了。一面总的来说,面试的都是些基本的问题。首先问了程序的在内存中存储的问题,分几个段,这个也只有些印象了。然后又问malloc实现以及和C++中new的区别。这个以前在HIT的IBMTC学得《深入理解计算机系统》讨论班,几个实验中有一个就是malloc实现。至于和new的区别,不得不说的一点是new申请内存的时候把类型也给“申请”了。所以在C++中初始化对象的时候如果用malloc可能会出现问题。然后问了些linux上的基础知识,之后我会再详细说下linux下一些比较有用的命令。

如果说百度面试的一个重要的环节肯定就是考查算法了。先让我动手写了一个quicksort程序,这个不难。像QuickSort,BiSearch这些考查基本功的算法,大家都应该很快的可以写出的。然后又问两道算法题目。题目我不太记得了,真的抱歉。

最后就简历上的东西问了问,这里有两点有必要分享一下。一是简历的制作一定要实事求是,什么意思大家都知道,就不说了;二是,当被问到自己熟悉而面试官不熟悉的东西,比如自己做的项目什么,表述一定要表述清楚,比如项目的背景技术这些东西就很容易被忽略。还有对测试的看法以及测试case的设计。

一面持续了一个小时,可以说是很基础的技术面了。最后出于公司礼貌,面试官会让你问他一些问题,当然面试结果肯定是不会和你说的了。如果大家被面的不太爽的话,机会来了一定把握住了喽。

一面是上午11点面试的,12点结束。晚上的时候二面的面试官给我打电话,告诉我通过了一面并约二面的时候。如果面试没有通过的时候,大家也会收到HR的通知的。

二面由于时间的问题,面试官临时调整了下,是个很nice的MM :)。后来知道是比一面的面试官级别高一些。当时面试的人比较多,我们就到了五楼的休息间。面试官MM也是抱着一个笔记本,上面是我的简历。先简要的问了下我的情况,然后就让我写strcmp函数实现。大家可能都感觉好简单啊!其实不然,大家可以搜索下像strcpy,strcmp之类字符串函数在面试中的注意点。边界的检查尤为重要。然后就这个程序进行测试,其实也就是设计测试用例,这个就看考虑问题是否全面了。然后也考查了一些linux下的命令使用,这个之后再统一写吧,比较多。然后考查算法,有266个整数,大小区间在0到255,其中有且只有两个数是相同的,要求找出这个重复的整数。我想了想,给出了个数学的解法:0到255的总和减去题目中266个数字的和得到一个方程组;0到255的平方减去题目中266个数平方得到又一个方程组,其实就是不变量的思想。面试官愣了一下,好吧,懂了。然后用了bit-map计数实现,很简单。

关于位的有趣的问题比较多,这里分享几个。上面说的面试题中是找出重复的数。把题目变一个:有N个整数,其中只有一个数出现一次,其他数都出现了两次,要求找出这个数。联系到位操作很容易想到怎么做。对于没有想到的同学,建议马上去google一下位运算中的异或操作。关于异或操作还有一个有趣的面试题:有一个桶,里面有白球、黑球各100个,人们必须按照以下的规则把球取出来:1、每次从桶里面拿出来两个球;2、如果是两个同色的球,就再放入一个黑球;3、如果是两个异色的球,就再放入一个白球;问:最后桶里面只剩下一个黑球的概率是多少?以后整理下吧!

最后也是问了些项目经历什么的,还有针对职位的面试:如何测试一台自动售货机?

二面持续一个多小时,结束的时候我问面试官MM,你评价我吧?哈哈。

二面完没多久,HR就打电话来了解了一些情况,并协商了入职时间。

由于时间比较久了,面经的质量有点低,有什么问题,大家可以随时联系我哈!