阿里内推2016面试(终 总结).doc

孙彦晨 阿里一面项目，问了一个项目，是学术项目1.多态2.虚指针3.知道STL吗list用过吗 它是怎么实现的list是C+标准模版库(STL,Standard Template Library)中的部分内容。实际上,list容器就是一个双向链表,可以高效地进行插入删除元素。使用list容器之前必须加上头文件：#include;hash_map用过吗 它是怎么实现的容器都有哪些数组与链表的区别？3.知道设计模式吗？用过单例模式吗？ 叙述一下单例模式的过程在单例模式下，用多线程会出现问题吗？4.Java中没有delete，C+中最讨厌delete，怎么解决？引出智能指针 加锁5.数据库 多线程访问数据库 读到脏的数据 怎么办用到乐观锁与悲观锁的知识点悲观锁(Pessimistic Lock), 顾名思义，就是很悲观，每次去拿数据的时候都认为别人会修改，所以每次在拿数据的时候都会上锁，这样别人想拿这个数据就会block直到它拿到锁。传统的关系型数据库里边就用到了很多这种锁机制，比如行锁，表锁等，读锁，写锁等，都是在做操作之前先上锁。乐观锁(Optimistic Lock), 顾名思义，就是很乐观，每次去拿数据的时候都认为别人不会修改，所以不会上锁，但是在更新的时候会判断一下在此期间别人有没有去更新这个数据，可以使用版本号等机制。乐观锁适用于多读的应用类型，这样可以提高吞吐量，像数据库如果提供类似于write_condition机制的其实都是提供的乐观锁。两种锁各有优缺点，不可认为一种好于另一种，像乐观锁适用于写比较少的情况下，即冲突真的很少发生的时候，这样可以省去了锁的开销，加大了系统的整个吞吐量。但如果经常产生冲突，上层应用会不断的进行retry，这样反倒是降低了性能，所以这种情况下用悲观锁就比较合适。6.叙述一下TCP三次握手中客户端与服务器之间状态的变化7.大数据排序 文件中9亿条不重复的9整数 排序问题:假设一个文件中有9亿条不重复的9位整数，现在要求对这个文件进行排序。 一般解题思路: 1、将数据导入到内存中 2、将数据进行排序（比如插入排序、快速排序） 3、将排序好的数据存入文件 难题: 一个整数为4个字节 即使使用数组也需要900,000,000 * 4byte = 3.4G内存 对于32位系统，访问2G以上的内存非常困难，而且一般设备也没有这么多的物理内存 将数据完全导入到内存中的做法不现实 其他解决办法: 1、导入数据库运算 2、分段排序运算 3、使用bit位运算 解决方案一:数据库排序 将文本文件导入到数据库，让数据库进行索引排序操作后提取数据到文件 优点：操作简单 缺点：运算速度慢，而且需要数据库设备。 解决方案二:分段排序 操作方式： 规定一个内存大小，比如200M，200M可以记录(200*1024*1024/4) = 52428800条记录，我们可以每次提取5000万条记录到文件进行排序，要装满9位整数需要20次，所以一共要进行20次排序，需要对文件进行20次读操作 缺点： 编码复杂，速度也慢(至少20次搜索) 关键步骤： 先将整个9位整数进行分段，亿条数据进行分成20段，每段5000万条 在文件中依次搜索05000万，500000011亿 将排序的结果存入文件 解决方案三:bit位操作 思考下面的问题: 一个最大的9位整数为999999999 这9亿条数据是不重复的 可不可以把这些数据组成一个队列或数组，让它有0999999999(10亿个)元素 数组下标表示数值，节点中用0表示这个数没有，1表示有这个数 判断0或1只用一个bit存储就够了 声明一个可以包含9位整数的bit数组(10亿)，一共需要10亿/8=120M内存 把内存中的数据全部初始化为0, 读取文件中的数据，并将数据放入内存。比如读到一个数据为341245909这个数据，那就先在内存中找到341245909这个bit，并将bit值置为1遍历整个bit数组，将bit为1的数组下标存入文件8.你有什么问题问我的吗?内推孙婉君阿里一面1.TCP与UDP区别1.基于连接与无连接；2.对系统资源的要求（TCP较多，UDP少）；3.UDP程序结构较简单；4.流模式与数据报模式 ；5.TCP保证数据正确性，UDP可能丢包，TCP保证数据顺序，UDP不保证。2.冒泡排序、快速排序3.双向链表中插入一个节点4.面向对象编程特点封装 继承 多态5.继承、多态、多继承优缺点多重继承的优点就是一个类可以实现多个接口（对象可以调用多个基类中的接口），缺点是（容易出现二义性）容易造成混淆（例如俩接口提供同一个函数）多态多态：可以理解为事物存在的多种体现形态。比如说人：男人、女人；动物：猫，狗。多态：多种形态。多态的优点 提高了代码的扩展性。多态的缺点 1.耗费内存2.父类调用不了子类特有的成员函数好处：提高了代码的扩展性。弊端：前期建立父类的引用虽然可以接收后期所有该类的子类对象。但是只能使用父类中的功能，不能使用子类中的特有功能，因为前期的程序无法知道后期的子类的特有内容的。但是前期的程序可以使用子类覆盖了父类的方法的内容。封装优点：良好的封装能够减少耦合 类内部的实现可以自由的修改 类具有清晰的对外接口 继承优点：使得所有子类公共的部分都放在了父类，使得代码得到了共享，就避免了重复继承可使得修改或扩展继承而来的实现代码都较为容易。缺点：父类变，子类不得不变，继承会破坏包装，父类实现细节暴露给子类，其实是增大了两个类之间的耦合性。注意：c#中，子类从它的父类中继承的成员有方法，域，属性，事件，索引指示器，但构造方法只能被调用不能继承。可以用base关键字调用父类的成员。当两个类之间具备“is-a”关系时，就可以考虑用继承。多态特点：子类以父类的身份出现子类在工作时以自己的方式来实现子类以父类身份出现时，子类特有的属性和方法不可以使用要实现多态，要将父类声明为虚方法，子类将方法重写：override注意：重载：一般在类内部，在不改变原方法的基础上，增加新功能；两个方法必须要方法名相同，但参数类型或个数必须要有所不同。重写：一般在不同的类中，必须要跟重写的方法返回类型及参数个数及类型都相同，需要加override关键字，被重写的方法要加 virtual关键字。 抽象类和接口的区别：表面上看：1.抽象类可以给出一些成员的实现，而接口不包含任何成员的实现抽象类的抽象成员可被子类部分实现，而接口的成员需要实现类完全实现一个类只能继承一个抽象类，但可实现多个接口深层次： 1 .类是对对象的抽象，抽象类是对类的抽象（类相关性），接口是对行为的抽象（行为相关性）对于行为跨越不同类的对象，可使用接口；对于一些相似的类对象，用继承抽象类从设计角度讲，抽象类是从子类中发现了公共的东西，泛化出父类，然后子类继承父类；而接口是根本不知子类的存在，方法如何实现还不确定，预先定义。抽象类往往是通过 重构 得来的，是自底而上抽象出来的，而接口则是自顶向下设计出来的。6.平时看哪些与软件相关论坛CSDN Github内推董金凤阿里一面1.虚继承解决什么问题？怎么解决的？虚继承，就是在被继承的类前面加上virtual关键字，这时被继承的类称为虚基类。多继承中只有一个虚基类的备份。2.贪吃蛇，飞机大战游戏里用到什么技术？略3.知道什么排序算法，哪些是稳定的冒泡，直接插入，简单选择，希尔，归并，快速，堆希尔、简单选择、堆、快速是不稳定的4.快速排序的时间复杂度，怎么算出来的？Nlog2N最坏情况是(N2)5.虚函数不加关键字会出现什么问题会产生覆盖，前面定义的是什么类型的指针就调用谁的，不会延迟绑定函数6.意向城市是杭州，c/c+是在北京，这个可以吗？内推赵新宇阿里一面1.-STL1)vector和map的区别向量 相当于一个数组在内存中分配一块连续的内存空间进行存储。支持不指定vector大小的存储。STL内部实现时，首先分配一个非常大的内存空间预备进行存储，即capacituy（）函数返回的大小，当超过此分配的空间时再整体重新放分配一块内存存储，这给人以vector可以不指定vector即一个连续内存的大小的感觉。通常此默认的内存分配能完成大部分情况下的存储。优点：(1) 不指定一块内存大小的数组的连续存储，即可以像数组一样操作，但可以对此数组进行动态操作。通常体现在push_back() pop_back()(2) 随机访问方便，即支持 操作符和vector.at()(3) 节省空间。缺点：(1) 在内部进行插入删除操作效率低。(2) 只能在vector的最后进行push和pop，不能在vector的头进行push和pop。(3) 当动态添加的数据超过vector默认分配的大小时要进行整体的重新分配、拷贝与释放双向链表每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小方便的进行添加和删除操作。使用的是非连续的内存空间进行存储。优点：(1) 不使用连续内存完成动态操作。(2) 在内部方便的进行插入和删除操作(3) 可在两端进行push、pop缺点：(1) 不能进行内部的随机访问，即不支持 操作符和vector.at()(2) 相对于verctor占用内存多deque双端队列double-end queuedeque是在功能上合并了vector和list。优点：(1)随机访问方便，即支持 操作符和vector.at()(2)在内部方便的进行插入和删除操作(3)可在两端进行push、pop缺点：(1) 占用内存多Map实现是基于RBTree的2)vector如何删除用erase(it)之后it会指向后一个元素，所以删除的时候要用continue结束此次循环，否则会跳过一个元素3)map查找的时间复杂度红黑树实现的，时间复杂度是log2N4)STL 算法2.C+ 中的autoauto用于修饰一个自动变量，但通常可以省略。一般定义在函数内部的，没有添加任何其他修饰符的变量都是自动变量。如：void f() int i; auto int j; static int k; extern int m;i和j都是自动变量，但k和m不是自动变量。3.多线程4.同步异步的区别线程同步是多个线程同时访问同一资源，等待资源访问结束，浪费时间，效率低 线程异步：访问资源时在空闲等待时同时访问其他资源，实现多线程机制5.对多态的理解多态指同一个实体同时具有多种形式。它是面向对象程序设计（OOP）的一个重要特征。如果一个语言只支持类而不支持多态，只能说明它是基于对象的，而不是面向对象的。C+中的多态性具体体现在运行和编译两个方面。运行时多态是动态多态，其具体引用的对象在运行时才能确定。编译时多态是静态多态，在编译时就可以确定对象使用的形式。6.-完成端口和重叠I/O重叠模型的基本设计原理是让应用程序使用重叠的数据结构，一次投递一个或多个WinsockI/O请求。针对那些提交的请求，在它们完成之后，应用程序可为它们提供服务。模型的总体设计以Windows重叠I/O机制为基础。这个机制可通过ReadFile和WriteFile两个函数，在设备上执行I/O操作。要想在一个套接字上使用重叠I/O模型，首先必须创建一个设置了重叠标志的套接字。主要有两种方法来管理重叠I/O的请求。1.事件对象通知 2.完成实例。7.-设计模式-工厂模式-迭代器模式8.-在数组中删除重复的n个数9.-ios中的RunLoop怎么计算两个文件的重合率布隆过滤器内推黄春娟（测试）1.自我介绍2.你不是学的电子硬件方向的吗？3.那你是自学还是报班学4.那你知道测试是什么吗？5.简单云盘的后台操作与具体传参，怎么实现的。（项目问的很具体）内推韩玉阿里一面1.网络协议2.数据结构算法题 有一群数据显示各地城市名称和温度 你用什么方式快速找出我提出的城市以及温度3.排序4.TCP/IP协议要想理解socket首先得熟悉一下TCP/IP协议族， TCP/IP（Transmission Control Protocol/Internet Protocol）即传输控制协议/网间协议，定义了主机如何连入因特网及数据如何再它们之间传输的标准，从字面意思来看TCP/IP是TCP和IP协议的合称，但实际上TCP/IP协议是指因特网整个TCP/IP协议族。不同于ISO模型的七个分层，TCP/IP协议参考模型把所有的TCP/IP系列协议归类到四个抽象层中应用层：TFTP，HTTP，SNMP，FTP，SMTP，DNS，Telnet 等等传输层：TCP，UDP网络层：IP，ICMP，OSPF，EIGRP，IGMP数据链路层：SLIP，CSLIP，PPP，MTU5.网络知识6.网络编程7.socket套接字编程具体过程以及应用8.为什么用MFC内推陈颖阿里一面1.自己叙述一个项目2.项目中遇到哪些难点，如何解决的？3.你觉得从项目中学到了什么？4.数据传输中有没有出现过数据丢失的情况？怎么解决？5.如何在Linux里查找“张三”？用find name6.数据库中想调用第100和200条之间的数据，用什么语句实现的？1).select top m * into 临时表(或表变量) from tablename order by columnname - 将top m笔插入 set rowcount n select * from 表变量 order by columnname desc 2).select top n * from (select top m * from tablename order by columnname) a order by columnname desc 3).如果tablename里没有其他identity列，那么： select identity(int) id0,* into #temp from tablename 取n到m条的语句为： select * from #temp where id0 =n and id0 = m 如果你在执行select identity(int) id0,* into #temp from tablename这条语句的时候报错,那是因为你的DB中间的select into/bulkcopy属性没有打开要先执行： exec sp_dboption 你的DB名字,select into/bulkcopy,true 4).如果表里有identity属性，那么简单： select * from tablename where identitycol between n and m7.堆栈、数列的概念、区别队列8.用push、pop实现一个内推刘金凤 阿里一面1.extern “C”作用主要作用就是为了能够正确实现C+代码调用其他C语言代码。加上extern C后，会指示编译器这部分代码按C语言的进行编译，而不是C+的。2.重载和重用重载（overload）：对于类的方法（包括从父类中继承的方法），方法名相同，参数列表不同的方法之间就构成了重载关系。覆盖 (override)：也叫重写，就是在当父类中的某些方法不能满足要求时，子类中改写父类的方法。当父类中的方法被覆盖了后，除非用super关键字，否则就无法再调用父类中的方法了。3.虚析构函数的作用基类的指针指向派生类对象，并用基类的指针删除派生类对象。如果某个类不包含虚函数，那一般是表示它将不作为一个基类来使用。当一个类不准备作为基类使用时，使析构函数为虚一般是个坏主意。因为它会为类增加一个虚函数表，使得对象的体积翻倍，还有可能降低其可移植性。4.标准库实现机制 内存管理 vector、map里实现的数据结构5.进程和线程的区别 进程间通信方式6.TCP/IP协议怎么样的一种协议7.TCP阻塞控制8.用没用过非阻塞的函数9.工作地点有要求吗？原博内推 阿里一面项目方面：1.自己做了哪些项目，说出一个最熟悉的2.项目参与有几个人，你做了哪些工作3.项目的大致流程；课题方面：1.课题的方向2.简单介绍内容3.提问了一个问题：在一个网站上，如何验证一个图片是否正确显示其他方面：1.看了哪些有关编程的书籍2.会哪些语言，着重问了是否会JAVA和脚本语言3.介绍一下什么是Socket张雪内推 阿里一面问题：1.自我介绍2.会JAVA吗？3.本计算机专业学过哪些课程4.学过编译原理没有，编译原理的几个过程a) 词法分析b) 语法分析c) 语义分析d) 中间代码生成e) 代码优化f) 代码生成5.常用数据结构有哪些，数组和链表的区别C+语言中可以用数组处理一组数据类型相同的数据，但不允许动态定义数组的大小，即在使用数组之前必须确定数组的大小。而在实际应用中，用户使用数组之前有时无法准确确定数组的大小，只能将数组定义成足够大小，这样数组中有些空间可能不被使用，从而造成内存空间的浪费。链表是一种常见的数据组织形式，它采用动态分配内存的形式实现。需要时可以用new分配内存空间，不需要时用delete将已分配的空间释放，不会造成内存空间的浪费。二者都属于一种数据结构从逻辑结构来看1). 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费；数组可以根据下标直接存取。2). 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项，非常繁琐）链表必须根据next指针找到下一个元素从内存存储来看1). (静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小2). 链表从堆中分配空间, 自由度大但是申请管理比较麻烦 从上面的比较可以看出，如果需要快速访问数据，很少或不插入和删除元素，就应该用数组；相反， 如果需要经常插入和删除元素就需要用链表数据结构了。6.有一个四则运算式子含括号怎么验证式子的合理性 赵家盈内推 阿里一面1.讲一个项目，亮点。自己做了什么，哪做的不错2.vector删除一个结点（erease 会出现什么问题）3.输入一个数组arr，再输入一个数X，怎么在arr中找到2个元素，使它们的和是X，返回元素的下标。4.微博上长URL转为短URL是如何实现的算法原理算法一1)将长网址md5生成32位签名串,分为4段, 每段8个字节;2)对这四段循环处理, 取8个字节, 将他看成16进制串与0x3fffffff(30位1)与操作, 即超过30位的忽略处理;3)这30位分成6段, 每5位的数字作为字母表的索引取得特定字符, 依次进行获得6位字符串;4)总的md5串可以获得4个6位串; 取里面的任意一个就可作为这个长url的短url地址;这种算法,虽然会生成4个,但是仍然存在重复几率,下面的算法一和三,就是这种的实现.算法二a-zA-Z0-9 这64位取6位组合,可产生500多亿个组合数量.把数字和字符组合做一定的映射,就可以产生唯一的字符串,如第62个组合就是aaaaa9,第63个组合就是aaaaba,再利用洗牌算法，把原字符串打乱后保存，那么对应位置的组合字符串就会是无序的组合。把长网址存入数据库,取返回的id,找出对应的字符串,例如返回ID为1，那么对应上面的字符串组合就是bbb,同理 ID为2时，字符串组合为bba,依次类推,直至到达64种组合后才会出现重复的可能，所以如果用上面的62个字符，任意取6个字符组合成字符串的话，你的数据存量达到500多亿后才会出现重复的可能。具体参看这里彻底完善新浪微博接口和超短URL算法，算法四可以算作是此算法的一种实现，此算法一般不会重复，但是如果是统计的话，就有很大问题，特别是对域名相关的统计，就抓瞎了。5.单例模式6.删除链表中倒数第K个元素7.为什么想加入Alibaba，职业规划姜宏山内推 阿里一面1.服务器的构造2.项目中用到的锁，你除了临界区还知道什么锁 3.序列化和反序列化 4.两端收数据不一致，丢包如何处理先存上，再拼上5.存活检测6.多继承和虚继承 7.API HOOK8.项目中hash函数如何应用的9.项目中如何去锁10.如何解决大小端问题11.看过什么开源代码赵欣欣内推 阿里一面1.自我介绍2.说一个项目 项目中遇到的难点，异常3.数组指针与指针数组的区别，并举例4.字符串比较的实现，strcmp5.Linux下的命令有哪些，找出当前文件夹下的含abc的文件 6.用人和电脑为例子，说出操作系统的不同（用操作系统的角度说人与电脑的区别） 梁天哥内推测试1.自我介绍2.自己做了哪些项目，说出一个最熟悉的，遇到的困难。问了好多项目的问题。3.怎么查找一个数组中两个相同的数（数组中判断是否有重复的）数组aN1)使用i,j作为下标一次对比数组中的两个数。2)用最简单的方法找出数组中的最大最小数，时间为O(n)。然后建立一个binary array，用0代表某个数没有在数组a中，1代表在数组a中。这样就可以找到两个相同的数。时间为O(n)3)对数组排序，然后依次查看每个两个相邻的数即可。排序时间复杂度最小为O(nlogn)。总共时间为o(nlogn+n)。4.链表是怎么创建的5.数字转换字符6.说说你对测试的理解。7.你了解Linux下的基本命令cat find谭化友内推 阿里一面1.自我介绍2.项目描述协议的定制 3.快速排序、堆排序、桶排序，说怎么实现，时间空间复杂度，最坏时间复杂度，适用场合，为什么。4.七层模型，每层都有什么重要的协议并列举（1）物理层 物理层所处理的数据单位是比特(bit)，物理层向上为数据链路层提供物理链路，实现透明的比特流(bit stream)传输服务，物理层向下与物理媒体相连，要确定连接物理媒体的网络接口的机械、电气、功能和过程方面的特性。（2）数据链路层 数据链路层负责在单个链路上的结点间传送以帧(frame)为pdu的数据，在不太可靠的物理链路上实现可靠的数据传输。数据链路层的主要功能包括：建立、维持和释放数据链路的连接，链路的访问控制，流量控制和差错控制。（3）网络层 网络层传送的pdu称为分组或包(packet)，在物理网络间传送分组，负责将源端主机的报文通过中间转发结点传送到目的端。网络层是通信子网的最高层，为主机提供虚电路和数据报两种方式的服务。网络层主要负责分组转发和路由选择，根据路由表把分组逐跳地由源站传送到目的站，并能适应网络的负载及拓扑结构的变化，动态地更新路由表。（4）传输层 传输层传输的pdu称为报文(message)，传输层为源结点和目的结点的用户进程之间提供端到端的可靠的传输服务。端到端的传输指的是源结点和目的结点的两个传输层实体之间，不涉及路由器等中间结点。为了保证可靠的传输服务，传输层具备以下一些功能：面向连接、流量控制与拥塞控制、差错控制相网络服务质量的选择等。（5）会话层 会话层在传输层服务的基础上增加控制会话的机制，建立、组织和协调应用进程之间的交互过程。会话层提供的会话服务种类包括双工、半双工和单工方式。会话管理的一种方式是令牌管理，只有令牌持有者才能执行某种操作。会话层提供会话的同步控制，当出现故障时，会话活动在故障点之前的同步点进行重复，而不必从头开始。（6）表示层 表示层定义用户或应用程序之间交换数据的格式，提供数据表示之间的转换服务，保证传输的信息到达目的端后意义不变。（7）应用层 应用层直接面向用户应用，为用户提供对各种网络资源的方便的访问服务。物理设备OSI 七层模型通过七个层次化的结构模型使不同的系统不同的网络之间实现可靠的通讯，因此其最主要的功能就是帮助不同类型的主机实现数据传输 。完成中继功能的节点通常称为中继系统。在OSI七层模型中，处于不同层的中继系统具有不同的名称。 一个设备工作在哪一层，关键看它工作时利用哪一层的数据头部信息。网桥工作时，是以MAC头部来决定转发端口的，因此显然它是数据链路层的设备。具体说:物理层：网卡，网线，集线器，中继器，调制解调器数据链路层：网桥，交换机网络层：路由器网关工作在第四层传输层及其以上集线器是物理层设备,采用广播的形式来传输信息。交换机就是用来进行报文交换的机器。多为链路层设备(二层交换机)，能够进行地址学习，采用存储转发的形式来交换报文.。路由器的一个作用是连通不同的网络，另一个作用是选择信息传送的线路。选择通畅快捷的近路，能大大提高通信速度，减轻网络系统通信负荷，节约网络系统资源，提高网络系统畅通率。5.ping用什么协议（ARP，ICMP），从网址到主机的具体过程且用什么协议，路由器用什么协议等等，这里问得比较细。网址到主机的具体过程且用什么协议 DNS HTTP1).连接 当我们输入这样一个请求时，首先要建立一个socket连接，因为socket是通过ip和端口建立的，所以之前还有一个DNS解析过程，把变成ip，如果url里不包含端口号，则会使用该协议的默认端口号。DNS的过程是这样的：首先我们知道我们本地的机器上在配置网络时都会填写DNS，这样本机就会把这个url发给这个配置的DNS服务器，如果能够找到相应的url则返回其ip，否则该DNS将继续将该解析请求发送给上级DNS，整个DNS可以看做是一个树状结构，该请求将一直发送到根直到得到结果。现在已经拥有了目标ip和端口号，这样我们就可以打开socket连接了。2).请求 连接成功建立后，开始向web服务器发送请求，这个请求一般是GET或POST命令（POST用于FORM参数的传递）。GET命令的格式为：GET 路径/文件名 HTTP/1.0文件名指出所访问的文件，HTTP/1.0指出Web浏览器使用的HTTP版本。现在可以发送GET命令：GET /mydir/index.html HTTP/1.0，3).应答 web服务器收到这个请求，进行处理。从它的文档空间中搜索子目录mydir的文件index.html。如果找到该文件，Web服务器把该文件内容传送给相应的Web浏览器。为了告知浏览器，Web服务器首先传送一些HTTP头信息，然后传送具体内容（即HTTP体信息），HTTP头信息和HTTP体信息之间用一个空行分开。常用的HTTP头信息有： HTTP 1.0 200 OK 这是Web服务器应答的第一行，列出服务器正在运行的HTTP版本号和应答代码。代码200 OK表示请求完成。 MIME_Version:1.0它指示MIME类型的版本。 content_type:类型这个头信息非常重要，它指示HTTP体信息的MIME类型。如：content_type:text/html指示传送的数据是HTML文档。 content_length:长度值它指示HTTP体信息的长度（字节）。4).关闭连接：当应答结束后，Web浏览器与Web服务器必须断开，以保证其它Web浏览器能够与Web服务器建立连接。ARP 地址解析协议（数据链路层） ARP为IP地址到对应的硬件地址之间提供动态映射。报文的意思是：如果你是这个IP地址的拥有者，请回答你的硬件地址。报文是在网上广播的。 ARP高速运行的关键是，每个主机上都有一个ARP高速缓存。这个高速缓存存放了最近Internet地址到硬件地址之间的映射记录。高速缓存中的每一项的生存时间一般为20分钟。 ARP代理：如果ARP请求是从一个网络的主机A发往另一个网络的主机B，那么连接这两个网络的路由器R就可以回答该请求，这个过程称作委托ARP或ARP代理（Proxy ARP）。这样可以欺骗发起请求的发送端，使它误以为路由器就是目的主机，而事实上目的主机是在路由器连接的另一边的网络。路由器的功能相当于目的主机的代理，把分组从源主机转发给目的主机。事实上，主机A的ARP缓存中，路由器R和主机B的IP地址都映射到路由器R的端口硬件地址。RARP 逆地址解析协议（数据链路层） RARP一般用于无盘工作站启动时获得IP地址。具有本地磁盘的系统引导时，一般从本地的配置文件中读取IP地址。但是无盘工作站需要用其他方式获得其IP地址，它首先读取主机的网卡硬件地址，然后发送RARP请求，该请求在网络上广播，该工作站期待某个主机响应该请求，为其指定一个IP地址。 RARP、ARP的请求报文为广播类型，但是，应答报文为单播类型。ICMP Internet控制报文协议（网络层） ICMP在主机和路由器间传递差错报文和控制报文。如目的主机不可达、端口不可达、协议不可达、目的网络不可达等。其报文被放到IP数据包内传输。其校验和字段覆盖整个ICMP报文（IP报文校验和只覆盖IP报文首部）。 ICMP还用于，无盘工作站在引导过程中获取自己的子网掩码。 常用于ICMP时间戳请求和应答。一种常见的ICMP报文是端口不可达。UDP的规则之一是，如果收到一份UDP数据报，而目的端口与某个正在使用的进程不相符，那么UDP返回一个ICMP端口不可达报文。ARP（address resolution protocol）在网络通讯时，源主机的应用程序知道目的主机的IP地址和端口号，却不知道目的主机的硬件地址，而数据包首先是被网卡接收到再去处理上层协议的，如果接收到的数据包的硬件地址与本机不符，则直接丢弃。源主机发出ARP请求，询问“IP地址是的主机的硬件地址是多少”，并将这个请求广播到本地网段（以太网帧首部的硬件地址填FF:FF:FF:FF:FF:FF表示广播），目的主机接收到广播的ARP请求，发现其中的IP地址与本机相符，则发送一个ARP应答数据包给源主机，将自己的硬件地址填写在应答包中。ping（网络层）ping命令是网络层的协议。 使用的是ICMP协议报文。ping命令可以测试某个主机是否可以通达，还能测出该主机的往返时间，即延迟。还允许我们查看分组的丢失率、失序等。ping报文不经过传输层。以太网和IEEE 802.3对数据帧的长度都有限制，其最大值分别是1500和1492字节，将这个限制称作最大传输单元（MTU，Maximum Transmission Unit）。如果IP层有一个数据报要传，而且数据的长度比链路层的MTU还大，那么IP层就要进行分片（Fragmentation），把数据报分成若干片，这样每一片都小于MTU。当网络上的两台主机互相进行通信时，两台主机之间要经过多个网络，每个网络的链路层可能有不同的MTU，其中两台通信主机路径中的最小MTU被称作路径MTU，Internet上标准MTU为576B（TCP）、512B（UDP）。路由协议：Rip、eigrp、ospf都属于内部网关协议（igp）。igp是用来在网络内计算路由的协议。egp外部网关协议，用来在不同自治系统（暂且理解为小的网络吧）之间传路由的，它本身不会计算出路由。一般只在运营商网络或企业网接入运营商网络的边界路由器上使用。rip：是最早出现的开放标准的路由协议，是按跳数一跳一跳的传路由信息的，这种协议有支持网络规模小、技术原理上存在路由环路等缺点。主要在小型网络上用。eigrp: 是思科公司开发的路由协议，技术细节我没有学习过。由于是思科的私有协议，不方便和不支持这种协议的其他厂商设备互通组网，所以这种协议不常用。ospf: 通过在网络中洪泛链路信息（网络拓扑信息），让每个设备都得到区域内所有其他设备的链路信息，然后运行最短路径树算法计算路由的协议。是开放标准的协议。较rip具有能支持大型网络、不存在固有环路等优点，比较常用。6.离散数学中图论，最短路径算法（他问的是dijkstra算法）的实现过程，个人觉得拓扑排序被问的几率较大。7.是两个有关大数据的问题，对10G数排序，数据无规则。对1000个文本文件分类比如有科技类文学类等等，分类依据，文本文件格式大小没规则。当随便又来一个文本文件又怎么归类？8.Select，Poll，epoll模型实现细节原理并区别适用场合，即是他们为什么会有各自的优缺点？Selectselect本质上是通过设置或者检查存放fd标志位的数据结构来进行下一步处理。这样所带来的缺点是：1 单个进程可监视的fd数量被限制2 需要维护一个用来存放大量fd的数据结构，这样会使得用户空间和内核空间在传递该结构时复制开销大3 对socket进行扫描时是线性扫描Pollpoll本质上和select没有区别，它将用户传入的数组拷贝到内核空间，然后查询每个fd对应的设备状态，如果设备就绪则在设备等待队列中加入一项并继续遍历，如果遍历完所有fd后没有发现就绪设备，则挂起当前进程，直到设备就绪或者主动超时，被唤醒后它又要再次遍历fd。这个过程经历了多次无谓的遍历。它没有最大连接数的限制，原因是它是基于链表来存储的，但是同样有一个缺点：大量的fd的数组被整体复制于用户态和内核地址空间之间，而不管这样的复制是不是有意义。poll还有一个特点是“水平触发”，如果报告了fd后，没有被处理，那么下次poll时会再次报告该fd。Epollepoll支持水平触发和边缘触发，最大的特点在于边缘触发，它只告诉进程哪些fd刚刚变为就需态，并且只会通知一次。在前面说到的复制问题上，epoll使用mmap减少复制开销。还有一个特点是，epoll使用“事件”的就绪通知方式，通过epoll_ctl注册fd，一旦该fd就绪，内核就会采用类似callback的回调机制来激活该fd，epoll_wait便可以收到通知注：水平触发（level-triggered）只要满足条件，就触发一个事件(只要有数据没有被获取，内核就不断通知你)；边缘触发（edge-triggered）每当状态变化时，触发一个事件。SelectPollEpoll支持最大连接数1024（x86） or 2048（x64）无上限无上限IO效率每次调用进行线性遍历，时间复杂度为O（N）每次调用进行线性遍历，时间复杂度为O（N）使用“事件”通知方式，每当fd就绪，系统注册的回调函数就会被调用，将就绪fd放到rdllist里面，这样epoll_wait返回的时候我们就拿到了就绪的fd。时间发复杂度O（1）fd拷贝每次select都拷贝每次poll都拷贝调用epoll_ctl时拷贝进内核并由内核保存，之后每次epoll_wait不拷贝9.如果让你去开发IOS你愿意吗？为什么？10.问他一个问题，我问了两孙美婷内推 阿里一面1.你了解hash_map吗？它是怎么实现的？在大数据的情况下，怎么保证用hash_map查找的高效率和准确率。时间复杂度多少？HashMap 与 Hashtable 在开发中是很常用的。他们的优点都是因为有key，所有进行查找是很方便的。对于HashMap 由于其是以牺牲空间来获得时间复杂度为O(1)，所以对于数据量比较小的话，还是建议不要轻易使用他。严格意义上来说，hashmap的时间复杂度并不是O(1)hash_map的查找，内部是通过一个从key到value的运算函数来实现的，这个函数“只接受key作为参数”，也就是说，hash_map的查找 算法与数据量无关，所以认为它是O(1)级的。总体来说，hash_map 查找速度会比map快，而且查找速度基本和数据数据量大小，属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小， hash还有hash函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash_map。但若你对内存使用特别严格，希望程序尽可能少消耗内存，那么一定要小心，hash_map可能会让你陷入尴尬，特别是当你的hash_map对象特别多时，你就更无法控制了，而且 hash_map的构造速度较慢。HashMap的实现是一个标准的hash表+链表结构：1. HashMap中持有一个数组成员变量table2. table的每个元素都是一个链表（用于解决冲突）3. 链表的每个元素Entry都存储着一对key/valuehash_map基于hash table（哈希表）。哈希表最大的优点，就是把数据的存储和查找消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。 其基本原理是：使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标，hash值）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方，称为桶。 但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“冲突”，换句话说，就是把不同的元素分在了相同的“类”之中。 总的来说，“直接定址”与“解决冲突”是哈希表的两大特点。 hash_map，首先分配一大片内存，形成许多桶。是利用hash函数，对key进行映射到不同区域（桶）进行保存。其插入过程是： 1. 得到key 2. 通过hash函数得到hash值 3. 得到桶号(一般都为hash值对桶数求模) 4. 存放key和value在桶内。 其取值过程是: 1. 得到key 2. 通过hash函数得到hash值 3. 得到桶号(一般都为hash值对桶数求模) 4. 比较桶的内部元素是否与key相等，若都不相等，则没有找到。 5. 取出相等的记录的value。 hash_map中直接地址用hash函数生成，解决冲突，用比较函数解决。这里可以看出，如果每个桶内部只有一个元素，那么查找的时候只有一次比较。当许多桶内没有值时，许多查询就会更快了(指查不到的时候)。由此可见，要实现哈希表, 和用户相关的是：hash函数和比较函数。这两个参数刚好是我们在使用hash_map时需要指定的参数。HashMap的数据结构数据结构中有数组和链表来实现对数据的存储，但这两者基本上是两个极端。数组数组存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为O(1)；数组的特点是：寻址容易，插入和删除困难；链表链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O（N）。链表的特点是：寻址困难，插入和删除容易。哈希表那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表。哈希表（(Hash table）既满足了数据的查找方便，同时不占用太多的内容空间，使用也十分方便。哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法 拉链法，我们可以理解为“链表的数组” ，如图：从上图我们可以发现哈希表是由数组+链表组成的，一个长度为16的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解，一个线性的数组怎么实现按键值对来存取数据呢？这里HashMap有做一些处理。首先HashMap里面实现一个静态内部类Entry，其重要的属性有 key , value, next，从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean，我们上面说到HashMap的基础就是一个线性数组，这个数组就是Entry，Map里面的内容都保存在Entry里面。/* * The table, resized as necessary. Length MUST Always be a power of two.*/transient Entry table;HashMap的存取实现既然是线性