Windless
订阅/Feed
稗田千秋(i@wind.moe)

2018 秋季 Python 研发岗面试题目分享

稗田千秋
Sep.23 2018 code

笔者今年刚从软工专业毕业,之前在校期间也有算点实习经验和算法基础,毕业后本着放飞自我的原则,没有去找工作而是去旅游浪了一圈,还全程扎心地看完 ti。最后在家里人的强烈要求下中断考研复习开始自救(X)。九月初开始投简历,投的都是社招一到三年经验的岗位,深圳这边 Python 岗不多,每个岗位投递人数都爆满,开始还是有点慌的。。用了两星期陆续面了一些传统行业、电商、量化交易和AI公司,拿到了[9*13,18*15] 区间中的五六个offer,最后选了一家 AI 创业公司体验一下高大上的算法(才不是因为965,在这里将碰到的部分面试题整理一下供参考。

算法部分

每次面试必写的排序算法,基本都问快排,归并这两种,反正面试问的也不外乎那几种,以不变应万变。题目大多不难,最多也就是LeetCode Medium 难度。

有家量化公司给的印象最深刻,一面直接发了一套纯英文笔试题手写代码,还收了手机,突然有种单刷的快感,给了三个小时的时间,期间贴心地送了午饭,可惜没表。。。有部分题目特别有趣,下面会提到。

其中有一道大数加法的题目考的是协程,当时饿了一早上脑子抽了没反应过来在纸上手写了一出大数加法,交卷的时候面试官愣了一会,最后笔者解释了写完才记得 Python 原生支持大数加法。

快速排序相关

一共是四道连续的题目,先是文字描述了快排的实现,需要画出每一步元素的变化,接下来实现描述的快排算法,然后计算其各种复杂度,最后这题当时没想出来怎么做,操作系统很多具体概念当时都忘了。。大意是使用前面实现的快排算法,运行于一个32位的系统上,同时其限制其栈大小为64kb,请描述什么时候会抛出StackOverFlow异常? 这道题的快排其实只是诱饵,真实目的是让你描述爆栈的过程,大概就是看前面代码的实现是递归的,所以当递归调用次数过多就会爆栈,这时该怎么计算有多少层栈呢,这里考的就是栈是怎么存储的了,易得32位系统的指针大小4字节,每一层等于是存一个指针地址什么的,然后通过换算求出栈深度,接着通过算法的最坏时间复杂度来求解。

求第k大/小的数

最简单的算法就是排序按下标取,好的这样面试官肯定不够满意,后面的实现是维护一个 k 大小的数组,从头遍历这个无序数组,每次扫到一个数就把k长度的数组与这个数合并排序切片,这样实现了一个不是最优解法的同时还能在面试官深入问的时候巧妙优化hhh,即使用最小堆(其实是因为手写实现一个最小堆有点累人),当然后续拓展到 k 不是定值的情况下还能聊很多按下不表。

外部排序

大意是有 100GB 外部文件需要排序,给你 4GB 内存和 1TB 硬盘,进行排序(向面试官确认数据可能有大量重复后排除位图解法) 正常在学归并的时候都会接触到这个问题,本质就是实现多路归并,分成每块都足够装入内存的小块,然后每块先进行排序保证成为有序块,接着维护一些值记录某个文件当前读取的行数,不断比较下去并写入文件。

旋转数组

一个没有重复的有序数组经过旋转得到新数组,恢复原数组。 第一遍使用遍历的方法,当 n < n-1 时即找到断点,进一步追问,使用二分进行优化,通过。

剩下的题具体没什么印象了,但是问过快速幂,斐波那契数列,两个栈实现一个队列,最长回文子串(Manacher 算法)等,这些平时刷题就能做到的就不再多解释了。其实很多时候不要担心题目简单有坑,因为可能真的很简单。。。当然详实的描述也很重要,上面那道外部排序的题我就用外部排序描述了一下,不知道声音太小还是怎么样,面试官没反应,导致当时脑内在疯狂搜索是否有更优解法,场面一度很尴尬。

数据库

数据库方面主要有如下问题:

  1. MySQL中你用过哪些引擎,说说他们的区别?
    当时就简单聊了聊InnoDB,MyISAM这两种,行级锁与事务什么的
  2. 谈谈索引,以及它的优缺点
    从上面的 InnoDB 引擎开始说,然后引向 B+ 树,然后介绍索引其实就是包含表中所有记录的引用指针的结构,可以极大提高查询速度,但是会降低删除更新表的速度等等
  3. 给你表,写查询语句
  4. Redis 有哪些数据结构?
    五种基本的结构String、Set等介绍一下,然后大概说下用法
  5. 用过 MongoDB 吗,介绍一下
  6. 等等
计算机网络
  1. 介绍一下 TCP/IP 协议
  2. 介绍一下 HTTP 协议,说说它的特点,每个特点深入问一下
  3. tcp 流量控制
Python 相关
  1. 实现一个 Singleton 模式,不限用法
  2. 介绍一下 aiohttp / sanic 框架,开发中遇到什么坑了?(因为简历中写了相关技术)
  3. 问了一些语法糖执行的结果,列表推导等
  4. Python 中 dict 的内部实现
  5. 线程安全方面的问题
  6. 装饰器
  7. 协程
  8. unittest 和 Selenium 使用的一些细节
  9. 文件读写和字符串操作,然后引申出 with 细节
其他相关
  1. 介绍一下 cookie 和 session
  2. 介绍一下 Docker,说一下 Dockerfile 和 Docker Compose,再聊聊 swarm 和 stack
  3. 哈希表使用的问题以及冲突解决方案、复杂度
  4. 进制换算(换成二进制中转)以及负某数的二进制在内存中的表示方式(考补码)
  5. 为什么要用消息队列,为什么选择 RabbitMQ / ZeroMQ 不选择其他的
  6. 介绍一下 RESTful API
  7. ELK 相关
你有什么想问的吗
  1. 办公室有猫吸吗?
  2. 办公协作方式/工具?
  3. 每天的工作是怎么确认的?
  4. 如果我入职的话,我会负责哪些相关内容?
  5. 工作时间,地点,是否会外派,薪酬,五险一金等

总结下来发现问的问题各个方面都有,除了特定框架相关的问题,其他基本都是基础题,感觉现在的面试官大都觉得只要其他方面没问题即使第一次用这些框架都能很快上手?

最后还是感谢一下 LeetCode 和 剑指Offer,这两者大致刷完之后面试的算法题基本能够通吃。。。

--END--
文章创建于 2018-09-23 01:05:32,最后更新 2018-09-23 01:05:32
Comment
尝试加载Disqus评论, 失败则会使用基础模式.
    • play_arrow

    About this site

    version:1.02 Alpha
    博客主题: Lime
    联系方式: i@wind.moe
    写作语言: zh_CN & en_US
    博客遵循 CC BY-NC-SA 4.0许可进行创作

    此外,本博客会基于访客的Request Headers记录部分匿名数据用于统计(Logger的源码见Github),包含Referer, User-Agent & IP Address.个人绝不会主动将数据泄露给第三方