趋势科技面试过程回顾
参加的武大宣讲会，然后现场做题。宣讲会给我的感觉是一家十分有活力，有极客精神的一家公司。主要是宣讲的小哥演讲能力真的很棒，人也十分幽默，就像认识很久的学长一样娓娓道来~ 后来的我面试官也是他，整个过程比较轻松，没有那么大的压迫感。我感觉很幸运。
因为是一家做安全相关的科技公司，所以考察的内容相对比较底层，笔试中涉及了较多的操作系统、计算机网络、数据结构相关的内容。面试的过程也是基于操作系统、计算机网络、数据结构以及编程语言来考察。接下来主要记录面试的过程和被问到的问题:
昨天睡得比较晚，甚至晚上做梦是在参加面试，在思考题目…然后早上比较早就醒了..大概六点钟…的样子。然后一直睡不着，八点的时候起床，出门吃早饭，发现在下雨，而且简历没有打印。又跑回住的地方拿伞，打印店关门了，好在还有原来打印的旧简历，就直接出发了。到了酒店发现原来腾讯也是在那家酒店面试，有很多人，我看还早就在大厅坐了会，看了看https相关的内容。时间快到了就上去了，先在hr房间签到，然后等通知上26楼面试官房间。面试官是宣讲的时候的小哥，对他印象很好，所以也不是很紧张。
1.首先自我介绍，我着重讲了项目的内容，看得出来由于我做的是JavaWeb方面的项目，所以他不是很关心，也没有过多针对项目提问。在最后我主要讲了我平时解决问题的一些方式和经常使用的技术类网站。
2.我是计算机专业毕业，所以就开始问操作系统相关的问题：
a.什么是线程、什么是进程？
关于进程和线程的解释参考阮一峰的网络日志
Java中的线程和进程参考IBM developerWorks Java 中的进程与线程
线程有两种调度模型：
分时调度模型 所有线程轮流使用 CPU 的使用权，平均分配每个线程占用 CPU 的时间片
抢占式调度模型 优先让优先级高的线程使用 CPU，如果线程的优先级相同，那么会随机选择一个，优先级高的线程获取的 CPU 时间片相对多一些。
Java使用的是抢占式调度模型。b.线程间如何通信？进程间如何通信？
c.线程的调度方式有哪些？时间片轮转、优先就绪队列，中间问了时间片轮转是怎么轮转，每个线程有不同的时间片还是每个线程时间片相同，我回答时间片相同。关于线程调度的方式
d.我提到了优先就绪队列，他就问了我线程的优先级是如何确定的？我回答线程分为用户线程和守护线程，根据此来确定优先级，他又问我用户线程和守护线程的优先级谁高？我不确定，先说了用户线程，又说守护线程…其实应该是用户线程。再者本题面试官应该想问的是线程的有限级设置吧…在java里面通过public final int getPriority() 和public final void setPriority(int newPriority)来分别获取和设置线程的优先级。
f.操作系统的虚拟存储是如何实现的？答，通过分段和分页。那么逻辑地址和物理地址是如何映射的？
leves1989的博客3.关于计算机网络，回答Java中Socket编程使用到的方法的名称.当时我就愣了，时间比较久，久根据印象回答了服务端和客户端的方法。但是客户端基本答错了。
主要流程是服务端创建ServerSocket对象，构造方法的参数是端口号。然后ss对象调用accept()方法对该端口进行监听并返回一个Socket对象，然后使用该对象可以获得IO流进行数据的传输。
客户端则是通过创建Socket对象，对要连接的主机的地址和端口号的设置可以通过Socket的构造方法直接设置，也可以缺省构造方法参数，使用socket.connect(SocketAddress)的方式，SocketAddress是一个抽象类，空实现，InetSocketAddress继承了SocketAddress类，可以构造一个有ip地址和端口号的对象。Socket对象还有一些其他的方法，例如bind(SocketAddress),是将本地的的IP地址和端口号绑定到Socket对象，注意此处的IP地址只能是主机的IP。
4.如果使用TCP连接，传输一个很大的数据，那么tcp是如何传输的？答曰TCP面向流，会分块。那么是通过什么来实现分块？我回答是根据TCP消息头的校验区域所能校验的最大数据量来划分的。后来在最后的问题中他解答了，其实是希望我从TCP下的网络层的IP协议来分析。也就是说TCP是通过Ip协议来传输的，由Ip协议来划分数据块
*IP 网际协议IP是TCP/IP的心脏，也是网络层中最重要的协议。
IP层接收由更低层（网络接口层例如以太网设备驱动程序）发来的数据包，并把该数据包发送到更高层—TCP或UDP层；相反，IP层也把从TCP或UDP层接收来的数据包传送到更低层。IP数据包是不可靠的，因为IP并没有做任何事情来确认数据包是按顺序发送的或者没有被破坏。IP数据包中含有发送它的主机的地址（源地址）和接收它的主机的地址（目的地址）。
IP协议提供了数据块（数据报）在源和目的地之间的透明传输机制；源和目的地是固定长度的地址确定的主机；
IP协议提供了对长的数据报的分段和重组机制（长数据报需要在”小分组”网络传输）
IP协议定义了在互联网络的主机间传输比特包（数据报）的机制，没有提供端到端的数据可靠性、流量控制、有序传输等机制。*5.如何确定两个局域网内的主机之间可以实现数据互通？答使用ping。那么ping是怎么实现的？答，ping是通过ICMP协议来实现的，然后后面的回答就错了，什么广播啦，丢弃之类的，然后就问我那么有没有可能伪造应答？我答可能，继续问我怎么识别伪造是否伪造的…懵逼了。
Ping工作过程：
*假定主机A的IP地址是192.168.1.1，主机B的IP地址是192.168.1.2，都在同一子网内，则当你在主机A上运行“Ping 192.168.1.2”后，都发生了些什么呢?
首先，Ping命令会构建一个固定格式的ICMP请求数据包，然后由ICMP协议将这个数据包连同地址“192.168.1.2”一起交给IP层协议（和ICMP一样，实际上是一组后台运行的进程），IP层协议将以地址“192.168.1.2”作为目的地址，本机IP地址作为源地址，加上一些其他的控制信息，构建一个IP数据包，并在一个映射表中查找出IP地址192.168.1.2所对应的物理地址（也叫MAC地址，熟悉网卡配置的朋友不会陌生，这是数据链路层协议构建数据链路层的传输单元——帧所必需的），一并交给数据链路层。后者构建一个数据帧，目的地址是IP层传过来的物理地址，源地址则是本机的物理地址，还要附加上一些控制信息，依据以太网的介质访问规则，将它们传送出去。
其中映射表由ARP实现。ARP(Address Resolution Protocol)是地址解析协议,是一种将IP地址转化成物理地址的协议。ARP具体说来就是将网络层（IP层，也就是相当于OSI的第三层）地址解析为数据连接层（MAC层，也就是相当于OSI的第二层）的MAC地址。
主机B收到这个数据帧后，先检查它的目的地址，并和本机的物理地址对比，如符合，则接收；否则丢弃。接收后检查该数据帧，将IP数据包从帧中提取出来，交给本机的IP层协议。同样，IP层检查后，将有用的信息提取后交给ICMP协议，后者处理后，马上构建一个ICMP应答包，发送给主机A，其过程和主机A发送ICMP请求包到主机B一模一样。*IMCP协议介绍
*1. 前面讲到了，IP协议并不是一个可靠的协议，它不保证数据被送达，那么，自然的，保证数据送达的工作应该由其他的模块来完成。其中一个重要的模块就是ICMP(网络控制报文)协议。
2.当传送IP数据包发生错误－－比如主机不可达，路由不可达等等，ICMP协议将会把错误信息封包，然后传送回给主机。给主机一个处理错误的机会，这也就是建立在IP层以上的协议是可能做到安全的原因。ICMP数据包由8bit的错误类型和8bit的代码和16bit的校验和组成。而前 16bit就组成了ICMP所要传递的信息。
3.尽管在大多数情况下，错误的包传送应该给出ICMP报文，但是在特殊情况下，是不产生ICMP错误报文的。如下:a.ICMP差错报文不会产生ICMP差错报文（除了IMCP查询报文，防止IMCP的无限产生和传送）
目的地址是广播地址或多播地址的IP数据报。
b.作为链路层广播的数据报。
c.不是IP分片的第一片。
d.源地址不是单个主机的数据报。这就是说，源地址不能为零地址、环回地址、广播地 址或多播地址。*ICMP的应用
*除了ping以外，ICMP还可以应用于Traceroute，Traceroute是用来侦测主机到目的主机之间所经路由情况的重要工具，也是最便利的工具。前面说到，尽管ping工具也可以进行侦测，但是，因为ip头的限制，ping不能完全的记录下所经过的路由器。所以Traceroute正好就填补了这个缺憾。
Traceroute的原理是非常非常的有意思，它受到目的主机的IP后，首先给目的主机发送一个TTL=1（还记得TTL是什么吗？）的UDP数据包，而经过的第一个路由器收到这个数据包以后，就自动把TTL减1，而TTL变为0以后，路由器就把这个包给抛弃了，并同时产生一个主机不可达的ICMP数据报给主机。主机收到这个数据报以后再发一个TTL=2的UDP数据报给目的主机，然后刺激第二个路由器给主机发ICMP数据报。如此往复直到到达目的主机。这样，traceroute就拿到了所有的路由器ip。从而避开了ip头只能记录有限路由IP的问题。
有人要问，我怎么知道UDP到没到达目的主机呢？这就涉及一个技巧的问题，TCP和UDP协议有一个端口号定义，而普通的网络程序只监控少数的几个号码较 小的端口，比如说80,比如说23,等等。而traceroute发送的是端口号>30000(真变态)的UDP报，所以到达目的主机的时候，目的 主机只能发送一个端口不可达的ICMP数据报给主机。主机接到这个报告以后就知道，主机到了。*
参考：inject2006的博客6.接下来是数据结构相关内容的考察，问了如何实现一个式子的求和操作？我回答了逆波兰式，使用栈的数据结构来实现，但是当时已经忘了具体如何实现了，所以卡了很久，最后也没有说出个所以然来。
中缀表达式转换为逆波兰式实现思路：
（1）建立两个栈，一个S1用来存放操作符+ - / ( )，另一个S2用来存放生成的逆波兰表达式，操作符栈遵循越往栈顶操作符优先级越高的原则。
（2）从中缀表达式的最左端开始逐个读取字符X，按一下规则对X进行处理：
a：如果X为数字，则直接放入S2
b：如果X为操作符，按以下情况处理：b1. 如果X为’(‘，则直接压入S1
b2. 如果X为’)‘，则将S1中距离栈顶最近的’(‘之间的元素依次弹出放入S2，’(‘直接抛弃
b3.如果X为’+ - * /‘，若当前S1为空，则直接将X压入S1，否则将X与S1当前栈顶元素比较，若X的优先级大于S1当前栈顶元素优先级，则将X直接压入S1，否则将S1的栈顶元素弹出，放入S2，直到S1栈顶运算符优先级低于（不包括等于）X的优先级，此时再则将X压入S1（3）步骤（2）结束之后，将栈S1中剩余的元素依次弹出，放入S2。*
逆波兰表达式运算思路：
*1.如果是数字则入栈
2.如果是运算符则弹栈两次，将数字用该运算符运算的结果再次压栈，直到结束
7.然后是一个树的深度优先搜索问题，如何实现树的深度优先搜索。我的回答是使用遍历，他接着问有没有其他办法，不通过遍历？我就硬着头皮说每次判断节点是否有子节点，如果有就进入，没有就会回溯。然后他就问我回溯的话怎么回溯，因为树的结构是从父指向子的，所以要记录父节点，我就回答用哟个变量记录，继续问我对这个变量的描述？我回答是一个有两个节点的数据结构。在最后的交流中他说，其实是希望我从栈的角度去考虑，栈的实现可以记录父节点，发生回溯的时候只需要弹栈即可。其实数据结构书上的走迷宫问题的解决方案也是利用栈的特点进行深度优先搜索。而对应的广度优先就是使用队列的数据结构。
具体可以看这个博客：gujinjin2008写的比较详细也有代码实现
今天进行了一场面试，由于昨晚没有睡好，中午的时候一觉睡到了下午接近五点。起床以后就在整理面试相关的问题和复习知识点，然后晚上七点做了携程的在线笔试，感觉还不错。笔试结束以后收到了之前顺丰的面试通知，其实完全没想到，因为笔试的编程题只AC了一题，另一题由于有一个方法没有完成所以只有10%的通过率。整理到现在比较晚了，今天就先休息啦，明天再整理携程的笔试题。洗澡睡觉了~~
把每一场面试当做一次提升的机会~加油！！！