1、TCP/IP的三次握手与四次挥手(为什么是三次握手,却是四次挥手?此处为重点考点)
关于位码:http://blog.chinaunix.net/uid-22312037-id-3575121.html
关于状态:http://justim.blog.51cto.com/740099/237548
2、HTTP详解: http://www.cnblogs.com/li0803/archive/2008/11/03/1324746.html
没来的及细看的一条,考互联网公司的时候需要注意。
3、 冯诺依曼模型:这个没来得及看,需要补充
4、作业、进程调度算法:
一些基础:
周转时间:从到达到算完。
带权周转时间:周转时间/运行时间
作业调度和低级调度算法:
FCFS:先到先服务算法。
SJF:最短作业优先算法。
SRTF:最短剩余时间,是抢占式的。
HRRF:响应比最高者优先算法(响应比=1+已等待时间/估计运行时间)。
优先级调度算法。
时间片轮转调度算法。
多级反馈队列调度。
彩票调度算法。
多处理器调度算法:
负载共享调度算法、群调度算法、处理器专派调度算法、动态调度算法
5、数据库相关:大题选做题涉及到的,有关Oracle和服务器连接的问题,负载等相关计算,还没看,要看一看。
还有一些语句要非常熟悉,比如说Having等计算的语句。
6、图的相关算法:Prim最小生成树算法、Dijkstra算法(有向图中单个源点到其他顶点的最短路径问题)、Floyd-Warshall算法(解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权的最短路径问题)
这三个算法是怎么操作的,用于做什么,这两个是主要考点,尤其是第二个出在选择题中。
7、操作系统(死锁、银行家、pv操作等)
PV操作没来得及看,有空要补充
银行家:http://baike.baidu.com/link?url=b_yjoCY38kmwd0N9rE14fU07vt6PM0HuvKR92CnVoQFFq6hzbGdZ7JH10k3oqlSK
死锁:
死锁的原因:进程推进顺序不当、PV操作使用不当、资源分配不当、临时性资源使用不加限制。
死锁的四个必要条件:
互斥条件:一个资源每次只能被一个进程使用。
请求与保持条件:一个进程因请求资源而阻塞时,对已获得的资源保持不放。
不剥夺条件:进程已获得的资源,在未使用完之前,不能强行剥夺。
循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。
死锁的破坏:
破坏第一个条件:使资源可同时访问而不是互斥使用。
破坏第二个条件:静态分配。
破坏第三个条件:剥夺式调度算法。当进程在申请资源未获准许的情况下,如主动释放资源(一种剥夺式),然后去等待。
破坏第四个条件:上述死锁防止办法造成资源利用率和吞吐率低。介绍两种比较实用的
死锁防止办法:采用层次分配策略(破坏条件2和条件4)(按序分配策略)
8、32位操作系统 位数 int -32?
9、static 成员变量 被初始化的时间,在第一次该类被用?第一次该类产生实例之时?(尚需查明)
10、Linux进程通信:管道、消息队列、共享内存、套接字Socket
11、 排序算法的时间空间复杂度、及相关问题(这个参考之前的日志,没什么说的,要理解,要记住)
12、算子网数量、子网内计算机的数量(这个也没看呢,果断必须要会算,还有子网掩码等知识)
写给我那已经夭折的面试:
本来还是准备了一些东西,目前看来用不上了,列出来记得下次要看:
1、算法题(丑数那道题、还有三个数组那道题,不解释啊)各种时间空间复杂度要会算
2、项目 Programs(Python项目、PhoneGap/HTML优势)
3、数据库:乐观锁、悲观锁。
4、设计模式 http://www.csdn.net/article/2012-06-04/2806324-software-design-interview-questions
http://wenku.baidu.com/view/524b1b1bfad6195f312ba6c0.html
5、ArrayList VS LinkList(JAVA经典面试题,见之前日志)
6、实际问题:客户反映网页打开过慢,怎么办啊;根据去年的客户消费数据,今年如何做一个推销计划等等。(图片存储)
这些都是网络公司爱问的,从网上搜的,包括大规模数据存储(图片等),需要在面试前作准备。
7、c相关:基本库函数,如atoi、快速排序等的实现(网上搜到的问题)
8、GC 机制:不得不说一直以为GC很简单,现在才发现这个问题非常复杂,一定要看懂,给面试加分:
http://sunzhyng.iteye.com/blog/480148
9、常上的网站:javaeye、csdn(当年进Adobe就被问了2次。。印象深刻)
10、多线程同步/异步问题(这个曾经在电话面试中,被阿里问到过,貌似还有I/O)
-------------------------------------------------
1、宿舍内5个同学一起玩对战游戏。每场比赛有一些人作为红方,另一些人作为蓝方。请问至少需要多少场比赛,才能使任意两个人之间有一场红方对蓝方和蓝方对红方的比赛?答案为4场
2、一个有10亿条记录的文本文件,已按照关键字排好序存储。请设计算法,可以快速的从文件中查找指字关键字的记录。
3. 请描述一下TCP建立连接的三次握手过程
4. 在互联网时代,系统稳定性、可用性要求越来越高,请列举至少4中技术解决硬件、系统、网络等层面的单点问题。
5. 请设计出一个搜索引擎爬虫的架构图,并说明你设计的爬虫需要如何优化来提升性能。
-------------------------------------------------------------
战报交流:战场上不同的位置有N个战士(n>4),每个战士知道当前的一些战况,现在需要这n个战士通过通 话交流,互相传达自己知道的战况信息,每次通话,可以让通话的双方知道对方的所有情报,设计算法,使用最少的通话次数,使得战场上的n个士兵知道所有的战 况信息,不需要写程序代码,得出最少的通话次数。
我能想到的最少通话次数等于2n-4,不知正解为多少
算法该如何设计
a,b,c,d,e.通话
a–b,b–c;d–e;b–d;c–e;a–(b or c or d or e)。 6次通信
通过分组(a,b,c;d,e),每组进行通信,每组中有两人掌握了组内所有信息,两组中两人分别交换信息,可以比2n-3少一次。
所以可以通过分组,减少通信次数。
我觉得即便求出最少值,算法也未必好实施。 容易实现的算法就是一个中心节点,2n-3次通信。
参考答案:
这道题以前做过,正解应当是 2n – 3 。可以很容易证明增加一个人最多需要2次沟通(详见下面的方案)。问题在于怎么证明增加一个人最少需要2次沟通。后者能证明的话,通过归纳法就可以很容易地得出这个结论。下面给出一个可能不够严谨的证明吧。
记最少的沟通次数 y 为人数 x 的函数, y = f(x)。
由于每次沟通只能在两个人之间,在n个人里面收集所有信息,至少需要 n – 1 次沟通;某个人将自己的信息告诉所有其他人也至少需要 n – 1 次沟通。由于“同步信息”所需的次数显然不可能少于收集信息,所以有 f(x) >= x – 1 。
将所有人分成 p 堆(1 <= p < n),第i堆有 a[i] 个人。于是问题可以拆成3个步骤:
总共需要 g(n, p) = 2(n – p) + f(p) 次沟通,所以 y = f(x) = max(g(n, p)) ,O(n^2)的算法,对于不大的n可以很容易地求出来这个最小值;当然这不是我们的目标。下面是重点,描述可能很奇葩,我尽量。。。
这时候如果新增一个人:如果把他放在任意一堆里面,那么至多且至少需要增加2次沟通(在1、3步里面各一次);如果把他另起一堆,于是问题变成递归地求解 f(p+1) 比 f(p) 至少要增加几次。
按照上面的逻辑,把这p+1个人分成q组(1 <= q < p),新增的那个人所在的组 要么多于1个人(于是至少也要增加2次沟通),要么只有一个人(相当于增加一个组),于是又变成递归地求解f(q) 比 f(q-1) 至少要增加几次…… 不断递归,最后组的数量会得到一个比较小的值,比如3,这时候就很容易证明,新增的这个人至少需要增加2次沟通才能够同步信息。
证毕。
至于设计算法,那就太简单了:从a开始依次传递到z,然后在从y依次传递回a,这就是 2n – 3 次。如下所示:
a = b = c = …… = y – z
-------------------------------------------------------------
公共题部分:有一道二叉树的题,大慨述10个有2个度的节点,问这颗树有好多个叶子节点。
还有一道是二叉搜索树,给定一个序列,按照顺序输入,构建一颗二叉搜索树,不考虑平衡性,问这颗二叉搜索树的度。
还有一道题:两个人为一组,现在要求先组合两个人的体重是102斤的,问最高效的算法的时间复杂度。
有两道大题:归并排序,还有个是在一个序列里面找组合的和等于给定的数字,输出所有组合,写一种高效的算法。
专业部分JAVA:有一道大题:第一个小问,写一个缓存的简单实现,要求当缓存一定大小,当大于预先设定的大小时,可以删除最近最久没使用的缓存数据。
第二个小问,是一个关于session的问题,具体的记不清楚了。
以上是我存在脑袋里面的部分题目,描述是根据记忆用自己的话描述的,仅供参考。
----------------------------------------------------------
云计算研究院:
1.三道智力题以及逻辑题,比如。一块钱的问题到底到哪去了。这个是我们平时都在做的题目,我就不展开了。另外,是逻辑题,很简单,就是推理东西最后到哪去了,相信大家都会做,最后两道是,记得是一个国王跟一个预言家,最后预言家说的一句话,让他自己不会死。这个可以到网上去搜搜。
2.第二部分,是简答题,是关于这几个方面的,一个是网络IP地址的划分,另外一道说是暴风影音的风暴问题,导致了整个网络瘫痪。是什么事件?raid的原理?还有几道很难。最后三道编程题。一道是二分查找的程序填空,一道是f(3)=1+2+3,f(n)=n,统计出所有n的值,并算出10000一下这个数的最大值,最后一道有意思,是关于马赛跑的编程题,可以用冒泡程序,结果最后我挂就挂在这道题了。
联系客服