从“成都-go-戒炸鸡”的面试题开始说起

今天晚上“高性能服务器开发”QQ群(群号:49114021,有兴趣的读者可以加一下)里面一名叫“成都-go-戒炸鸡”的群友提出了他最近面试的一些面试题,面试题内容个人觉得非常典型、也非常有代表性和针对性,故拿出来与大家分享一下,也感谢他的分享。成都-go-戒炸鸡说:

“今天面试,我没答出来的有redis持久化机制,redis销毁方式机制,mq实现原理,c++虚函数,hash冲突的解决,memcached一致性哈希,socket函数select的缺陷,epoll模型,同步互斥,异步非阻塞,回调的概念,innodb索引原理,单向图最短路径,动态规划算法。”

为了避免问题有歧义,面试题略有修改。

思路分析

从面试题的内容可以看出,这是一个后台开发的职位。

除了关于 c++ 虚函数这个问题以外,其他的大多数问题都与哪种编程语言关系不大,大多数是原理性和基础性的问题,少数是工作经验问题,笔者试着给大家分析。

语言基础

C++ 虚函数这是面试初、中级 C ++ 职位一个概率95%以上的面试题。一般有以下几种问法:

  1. 在有继承关系的父子类中,构建和析构一个子类对象时,父子构造函数和析构函数的执行顺序分别是怎样的?
  2. 在有继承关系的类体系中,父类的构造函数和析构函数一定要申明为 virtual 吗?如果不申明为 virtual 会怎样?
  3. 什么是 C++ 多态?C++ 多态的实现原理是什么?
  4. 什么是虚函数?虚函数的实现原理是什么?
  5. 什么是虚表?虚表的内存结构布局如何?虚表的第一项(或第二项)是什么?
  6. 菱形继承(类D同时继承B和C,B和C又继承自A)体系下,虚表在各个类中的布局如何?如果类B和类C同时有一个成员变了m,m如何在D对象的内存地址上分布的?是否会相互覆盖?
算法与数据结构基础

说到算法和数据结构,对于社招人士和对于应届生一般是不一样的,对于大的互联网公司和一般的小的企业也是不一样的。下面根据我当面试官面试别人和找工作被别人面试经验来谈一谈。

先说考察的内容,除了一些特殊的岗位,常见的算法和数据结构面试问题有如下:

  1. 排序(常考的排序按频率考排序为:快速排序 > 冒泡排序 > 归并排序 > 桶排序)

一般对于对算法基础有要求的公司,如果你是应届生或者工作经验在一至三年内,以上算法如果写不出来,给面试官的影响会非常不好,甚至直接被 pass 掉。对于工作三年以上的社会人士,如果写不出来,但是能分析出其算法复杂度、最好和最坏的情况下的复杂度,说出算法大致原理,在多数面试官面前也可以过的。注意,如果你是学生,写不出来或者写的不对,基本上面试过不了。

  1. 二分查找 二分查找的算法尽量要求写出来。当然,大多数面试官并不会直接问你二分查找,而是结合具体的场景,例如如何求一个数的平方根,这个时候你要能想到是二分查找。我在2017年年底,面试agora时,面试官问了一个问题:如何从所有很多的ip地址中快速找个某个ip地址。
  2. 链表 无论是应届生还是工作年限不长的社会人士,琏表常见的操作一定要熟练写出来,如链表的查找、定位、反转、连接等等。还有一些经典的问题也经常被问到,如两个链表如何判断有环(我在2017年面试饿了么二面、上海黄金交易所一面被问过)。链表的问题一般不难,但是链表的问题存在非常多的“”,如很多人不注意边界检查、空链表、返回一个链表的函数应该返回链表的头指针等等。
  3. 队列与栈 对于应届生来说一般这一类问的比较少,但是对于社会人士尤其是中高级岗位开发,会结合相关的问题问的比较多,例如让面试者利用队列写一个多线程下的生产者和消费者程序,全面考察的多线程的资源同步与竞态问题(下文介绍多线程面试题时详细地介绍)。 栈一般对于基础要求高的面试,会结合函数调用实现来问。即函数如何实现的,包括函数的调用的几种常见调用方式、参数的入栈顺序、内存栈在地址从高向低扩展、栈帧指针和栈顶指针的位置、函数内局部变量在栈中的内存分布、函数调用结束后,调用者和被调用者谁和如何清理栈等等。某年面试京东一基础部门,面试官让写从0加到100这样一个求和算法,然后写其汇编代码。
  4. 哈希表 哈希表是考察最多的数据结构之一。常见的问题有哈希冲突的检测、让面试者写一个哈希插入函数等等。基本上一场面试下来不考察红黑树基本上就会问哈希表,而且问题可浅可深。我印象比较深刻的是,当年面试百度广告推荐部门时,二面问的一些关于哈希表的问题。当时面试官时先问的链表,接着问的哈希冲突的解决方案,后来让写一个哈希插入算法,这里需要注意的是,你的算法中插入的元素一定要是通用元素,所以对于 C++ 或者 Java 语言,一定要使用模板这一类参数作为哈希插入算法的对象。然后,就是哈希表中多个元素冲突时,某个位置的元素使用链表往后穿成一串的方案。最终考察 linux 下 malloc(下面的ptmalloc) 函数在频繁调用造成的内存碎片问题,以及开源方案解决方案 tcmalloc 和 jemalloc。总体下来,面试官是一步步引导你深入。(有兴趣的读者可以自行搜索,网上有很多相关资料)
  5. 树 面试高频的树是红黑树,也有一部分是B树(B+树)。 红黑树一般的问的深浅不一,大多数面试官只要能说出红黑树的概念、左旋右旋的方式、分析出查找和插入的平均算法复杂度和最好最坏时的算法复杂度,并不要写面试者写出具体代码实现。一般 C++ 面试问 stl 的map,java 面试问 TreeMap 基本上就等于开始问你红黑树了,要有心里准备。笔者曾经面试爱奇艺被问过红黑树。 B树一般不会直接问,问的最多的形式是通过问 MySQL 索引实现原理(数据库知识点将在下文中讨论)。笔者面试腾讯看点部门二面被问到过。
  6. 图 图的问题就我个人面试从来没遇到过,不过据我某位哥哥所说,他在进三星电子之前有一道面试题就是深度优先广度优先问题。
  7. 其他的一些算法 如A*寻路、霍夫曼编码也偶尔会在某一个领域的公司的面试中被问到,如宝开(《植物大战僵尸》的母公司, 在上海人民广场附近有分公司)。
编码基本功

还有一类面试题不好分类,笔者姑且将其当作是考察编码基本功,这类问题既可以考察算法也可以考察你写代码基本素养,这些素养不仅包括编码风格、计算机英语水平、调试能力等,还包括你对细节的掌握和易错点理解,如有意识地对边界条件的检查和非法值的过滤。请读者看以下的代码执行结果是什么?(笔者2011年去北京中关村的鼎普面试的问题)

for(char i = 0; i < 256; ++i) 
{
   printf("%d\n", i);
}

下面再列举几个常见的编码题:

  1. 实现一个 memmov 函数 这个题目考查点在于 memmov 函数与 memcpy 函数的区别,这两者对于源地址与目标地址内存有重叠的这一情况的处理方式是不一样的。
  2. 实现strcpy或strcpy函数 这个函数写出来没啥难度,但是除了边界条件需要检查以外,还有一个容易被忽视的地方即其返回值一定要是目标内存地址,以支持所谓的链式拷贝。即: strcpy(dest3, strcpy(dest2, strcpy(dest1, src1)));
  3. 实现atoi函数 这个函数的签名如下: int atoi(const char* p); 容易疏忽的地方有如下几点:
  • 小数点问题,如数字0.123和.123都是合法的;
  • 正负号问题,如+123和-123;
  • 考虑如何识别第一个非法字符问题,如123Z89,则应转换成应该123。 我在面试掌门科技(无线万能钥匙那一家)就遇到过这样的问题。
多线程开发基础

现如今的多核CPU早已经是司空见惯,而多线程编程早已经是“飞入寻常百姓家”。对于大多数桌面应用(与 Web 开发相对),尤其是像后台开发这样的岗位,且面试者是社会人员(有一定的工作经验),如果面试者不熟悉多线程编程,那么一般会被直接 pass 掉。

这里说的“熟悉多线程编程”到底熟悉到什么程度呢?一般包括:知道何种场合下需要新建新的线程、线程如何创建和等待、线程与进程的关系、线程局部存储(TLS 或者叫 thread local)、多线程访问资源产生竞态的原因和解决方案等等、熟练使用所在操作系统平台提供的线程同步的各种原语。

对于 C++ 开发者,你需要:

  • 对于 Windows 开发者,你需要熟练使用 Interlock系列函数、CriticalSection、Event、Mutex、Semphore等API 函数和两个重要的函数 WaitForSingleObject、WaitForMultipleObjects。
  • 对于linux 开发者,你需要熟练使用 mutex、semphore、condition_variable、read-write-lock 等操作系统API。

对于 Java,你需要熟悉使用 synchronized关键字、CountDownLatch、CyclicBarrier、Semaphore以及java.util.concurrent 等包中的大多数线程同步对象。

数据库

数据库知识一般在大的互联网企业对应届生不做硬性要求,对于小的互联网企业或社会人士一般有一定的要求。其要求一般包括:

  1. 熟悉基本 SQL 操作 包括增删改查(insert、delete、update、select语句),排序 order,条件查询(where 子语句),限制查询结果数量(LIMIT语句)等
  2. 稍微高级一点的 SQL 操作(如Group by,in,join,left join,多表联合查询,别名的使用,select 子语句等)
  3. 索引的概念、索引的原理、索引的创建技巧
  4. 数据库本身的操作,建库建表,数据的导入导出
  5. 数据库用户权限控制(权限机制)
  6. MySQL的两种数据库引擎的区别
  7. SQL 优化技巧
网络编程

网络编程这一块,对于应届生或者初级岗位一般只会问一些基础网络通信原理(如三次握手和四次挥手)的socket 基础 API 的使用,客户端与服务器端网络通信的流程(回答 【客户端创建socket -> 连接server ->收发数据;服务器端创建socket -> 绑定ip和端口号 -> 启动侦听 ->接受客户端连接 ->与客户端通信收发数据】即可)、TCP 与 UDP的区别等等。

对于工作经验三年以内的社会人士或者一些中级面试者一般会问一些稍微重难点问题,如 select 函数的用法,非阻塞 connect 函数的写法,epoll 的水平和边缘模式、阻塞socket与非阻塞socket的区别、send/recv函数的返回值情形、reuse_addr选项等等。Windows 平台可能还会问 WSAEventSelect 和 WSAAsyncSelect 函数的用法、完成端口(IOCP模型)。

对于三年以上尤其是“号称”自己设计过服务器、看过开源网络通信库代码的面试者,面试官一般会深入问一些问题,这类问题要么是实际项目中常见的难题或者网络通信细节,根据我的经验,一般有这样一些问题:

  1. nagle算法;
  2. keepalive选项;
  3. Linger选项;
  4. 对于某一端出现大量CLOSE_WAIT 或者 TIME_WAIT如何解决;
  5. 通讯协议如何设计或如何解决数据包的粘包与分片问题;
  6. 心跳机制如何设计;(可能不会直接问问题本身,如问如何检查死链)
  7. 断线重连机制如何设计;
  8. 对 IO Multiplexing 技术的理解;
  9. 收发数据包正确的方式,收发缓冲区如何设计;
  10. 优雅关闭;
  11. 定时器如何设计;
  12. epoll 的实现原理。

举个例子,让读者感受一下,笔者曾去BiliBili被问过这样一个问题:如果A机器与B机器网络 connect 成功后从未互发过数据,此时其中一机器突然断电,则另外一台机器与断电的机器之间的网络连接处于哪种状态?

内存数据库技术

时下以NoSql key-value为思想的内存数据库大行其道,广泛地用于各种后台项目开发。所以熟悉一种或几种内存数据库程序已经是面试后台开发的基本要求,而这当中以 redis 和 memcached 为最典型代表,这里以 redis 为例。

  • 第一层面一般是对 redis 的基础用法的考察 如考察 redis 支持的基础数据类型、redis的数据持久化、事务等。
  • 第二层面不仅考察 redis 的基础用法,还会深入到 redis 源码层面上,如 redis 的网络通信模型、redis 各种数据结构的实现等等。

笔者以为,无论是从找工作应付面试还是从提高技术的角度,redis 是一个非常值得学习的开源软件,希望广大读者有意识地去了解、学习它。

项目经验

除了社会招聘和一些小型的企业,一般的大型互联网公司对应届生不会做过多的项目经验要求,而是希望他们算法与数据结构等基础扎实、动手实践能力强即可。对于一般的小公司,对于应届生会要求其至少熟练使用一门编程语言以及相应的开发工具,号称熟悉linux C++ 开发的面试者,不熟悉 GDB 调试基本上不是真正的熟悉 linux C++ 开发;号称熟悉汇编或者反汇编,不熟悉 IDA 或者 OllyDbg,基本上也是名不符实的;号称熟悉 VC++ 开发,连F8、F9、F10、F11、F12等快捷键不熟悉也是难以经得住面试官的提问的;号称熟悉 Java 开发的却对 IDEA 或 eclipse 陌生,这也是说不过去的。

这里给一些学历不算好,学校不是非常有名,尤其是二本以下的广大想进入 IT 行业的同学一个建议,在大学期间除了要学好计算机专业基础知识以外,一定要熟练使用一门编程语言以及相应的开发工具。

关于项目经验,许多面试者认为一定要是自己参与的项目,其实也可以来源于你学习和阅读他人源码或开源软件的源码,如果你能理解并掌握这些开源软件中的思想和技术,在面试的时候能够与面试官侃侃而谈,面试官也会非常满意的。笔者的一个学弟前段时间告诉我,他看懂了我公众号【easyserverdev】中《服务器开发基础系列和进阶》的文章后,成功拿到了网易的offer

,有兴趣的读者可以好好看一下。

很多同学可能纠结大学或者研究生期间要不要跟着导师做一些项目。当然,如果这些项目是课程要求,那么你必须得参加;如果这些项目是可以选择性的,尤其是一些仅仅拿着第三方的库进行所谓的包装和加工,那么建议可以少参加一些。

思路总结

不知道通过我上面的技术分析,聪明的读者是否已经明确本文开头“成都-go-戒炸鸡”同学提出的面试题中,哪些是技术面试重难点,哪些又是技术开发的重难点呢?

技术比重与薪资

这里根据我自己招人的经验来谈一谈技术水平与薪资,就上面的面试题来看:

  • 第一层次:如果面试者能答出上面面试题中的C++基础问题和算法与数据结构题目(如 C++ 函数与hash冲突的解决、innodb索引原理,单向图最短路径,动态规划算法等),可以认为面试者是一个合格的初、中级开发者,薪资范围一般在6 ~ 12k(注意:这里以我所在的上海为参考标准)。
  • 第二层次:在第一层次基础之上,如果面试者还能答出上述面试题中网络编程相关的或者多线程相关的问题(如socket函数select的缺陷,epoll模型,同步互斥,异步非阻塞,回调的概念等),可以认为面试者是个基础不错的中级开发者,薪资范围一般在14~22k之间。
  • 第三层次:在前两个层次之间,如果面试者还能回答出上述问题中关于redis、memcached和mq实现原理,说明面试者是一个有着不错项目经验并且对一些常用开源项目也有一定的理解,薪资可以给到22k +。

总结

工资收入是每个人的秘密,一般不轻易对外人道也。这里笔者冒天下之大不韪,只想说明一点——对于普通开发人员,提高薪资最好的捷径就是提高自己的技术,无论是“面向搜索引擎编程”还是“面向工资编程”终将得不偿失,聪明的你一定会深谋远虑的。

原文发布于微信公众号 - 高性能服务器开发(easyserverdev)

原文发表时间:2018-11-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一个会写诗的程序员的博客

计算机语言是怎样设计出来的

所谓计算机语言只是一个抽象的规范,而编译器是这个规范的实现,它是在这个规范的严格定义下被实现的.

961
来自专栏java架构师

设计模式学习笔记之桥接模式

这个模式在看书时,一直没想到更好的应用场景,由此感慨一下《设计模式之禅》这本书, 通过这本书,的确对各种模式有了个比较清晰的理解,甚至对模式的结构也能很明确。也...

3597
来自专栏程序员的诗和远方

20180722_ARTS_week04

这题寻找两个已经排好序的数组的中值,一开始思路比较简单,两个数组合一起,然后排个序就很容易找到中值了。

1061
来自专栏数据小魔方

关于数据地图的几个遗留问题解决方案

今天跟大家分享三个数据地图的遗留问题,包括以前因为技术手段限制无法解决的问题,以及读者吐槽最多的问题。 如何在一个版面上呈现不同行政级别的地理信息; 如何给版面...

3237
来自专栏养码场

限时领取| 6GJavaScript高级视频,高级前端工程师必备武器!

之前场主分享了13G的JavaScript基础视频,共140集实战教学。没想到领取人数竟超过了5000+,着实让场主感受到了JavaScript教程的需求,及还...

762
来自专栏企鹅号快讯

C语言的前世今生,及其特点、利弊和入门须知三把斧

C语言的开展前史: ? 20世纪70年代初,贝尔实验室的Dennis Richie 等人在B语言基础上开发C语言,最初是作为UNIX的开发语言; 20世纪70年...

2116
来自专栏一个会写诗的程序员的博客

附录B 编程的本质附录B 编程的本质编程的本质N小结编程简史名词纪要参考资料

尼古拉斯·沃斯(Niklaus Wirth,1934年2月15日—),生於于瑞士温特图尔,是瑞士计算机科学家。Pascal语言之父。

923
来自专栏高性能服务器开发

去BAT,你应该要看一看的面试经验总结

说下我的面试经验吧,都是亲身经历,不喜勿喷: 我去年12月份从上一家公司离职,一直到今年3月份,基本上都在面试中度过来的。 先交代下背景:坐标上海,做技术开发,...

3984
来自专栏技术博客

设计模式原则(单一、开放封闭、里氏代换、依赖倒转、迪米特法则五大原则)

        如果一个类承担的职责过多,就等于把这些职责耦合在一起,一个职责的变化可能会削弱或者抑制这个类完成其他职责的能力,当变化发生时,设计会遭受到意想不...

1052
来自专栏韩伟的专栏

面向对象的代码风格(下)

面向对象代码的结构 在结构化编程中,代码的结构以分解流程,实现处理方案为核心,代码的分解原色是以实现步骤为主。理解这种结构的代码,我们需要先理解问题的解决方案,...

3504

扫码关注云+社区