搜索

面试经验分享之数据结构、算法题

gecimao 发表于 2019-04-13 15:36 | 查看: | 回复:

  面试 IT 企业的研发岗位,数据结构和算法显然是必考的项目。俺只学过普通的数据结构课程,没读过 STL,也没有过 ACM 的训练和比赛经历,在一开始面对这样类型题目的时候,心里还是十分忐忑的。大大小小几十场面试下来,自己在这方面总算有了一定的心得积累,在此抛砖引玉,以飨读者。

  ●Google 和 Facebook 这类对算法有很高要求的公司的在线测试我没有参加过(不过在牛人内推帮助下有过面试体验……),这超出了我目前的编码能力范围,网上有不少拿到 Google、Facebook offer 的经验总结文章,可以移步观赏;

  ●前段时间在微博上又看到有人说自己把 leetcode 刷了好几遍,不过一些转发评论者觉得, IT 公司面试中的算法考察没有价值,一来工作里用不太上,二来把程序员素质考察搞成了应试教育,他们认为更重要的是应聘者的工程能力。遇到这样的讨论,我一般喜欢和一把稀泥。若干年前, Google、微软的面试题让大家眼前一亮,觉得能选拔出个性十足的聪明人来,不过随着大家对这类题目的适应,可能选拔出来的人也在趋同,至少很多人都会在面试前用心准备,据报道 Google 最近也是放弃了这类面试题目。没有什么一劳永逸、一成不变的考查方式,毕竟面试是人和人之间的动态“较量”。不要贪恋算法的奇技淫巧,也不要因为题目筛选力度的衰减而否定考察初衷。面试不仅是考验求职者,也同样在考验面试官,如果问的都是老题儿,那本山大叔肯定都会抢答了。

  言归正传,以下分数据结构题目、算法题目、开放题目三部分来介绍我在面试中碰到的问题。

  虽然课本由简到繁、由难到易地介绍了诸多数据结构,我在面试中被问到的却还都是基本类型,比如堆栈、队列、链表、二叉树。题目主要有两类,数据结构实现和具体情境下数据结构的应用。

  2、实现栈,使得 添加、删除、max 操作的复杂度为 O(1)(我脚着好像是不可实现的,想到最好的是添加、删除 O(log), max 是 O(1)),实现见 正在努力减肥的胖子 同学给出的评论,参考 leetcode 中的这道题目,惭愧;

  1、两棵树相加——对应位置两棵树都有值则相加,对应位置只有一棵树有值则取该值;

  2、用速度不同的指针可以判断链表中是否有环,问两速度满足怎样的关系可以保证发现环;

  上上之选当然是看《算法导论》,书 和 公开课 都算。时间精力不足又想临时抱佛脚,清华大学计算机系邓俊辉老师的 教材 是好选择,也可以看 公开课。注意熟记不同数据结构的不同操作的不同实现方式(比如 哈希表的插入删除查找)的复杂度分析,不管面试官给你出的题目是难是易,妥妥儿的会问复杂度。

  有过面试经历的企业(BAT、小米、宜信、猿题库、FreeWheel等)当中,还没有谁问过我需要复杂算法(比方说 此链接 中的很多知识点)才能解决的问题。我遇到的算法题目大致可以分为两类:

  ●经典算法实现题 快速排序、归并排序、堆排序、KMP算法等都是重点,重要的是代码的正确性,其次是复杂度分析,当然,人家也不都是直接问你怎么实现这个具体算法,而是包装到情境里;

  ●思维益智题 考察你分析问题的能力,大部分可以归结到二分、动态规划、递归上,重要的是思路,其次是尽量低的复杂度,再次是代码的正确性。

  2、两个有序数组,寻找归并排序后数组的中位数/第 k 大数字(与二分有关);

  3、一维数组,swap 其中的几对数字(每个数字只属于一次 swap 操作),实现查找(与二分有关);

  4、一个有序数组,其中一个数字发生变异,但不知道变异后会不会影响整体序,如何实现查找;

  12、数组可能是递增、递减、递减后递增、递增后递减四种情况,递增递减都是非严格的,如果有转折点,返回转折点的值,否则返回-1;

  13、单向网络,起点和终点唯一且连通,寻找那些一旦被删除将导致起点终点无法连通的点;

  ●不要纠结于是否是最佳思路,要保证能在 10-15 分钟内给出一个解决方案,并分析复杂度;

  ●基础的可以读读 @研究者July 的这本 电子书,更深入的可以阅读 CSDN 等博客中大牛们写的 ACM 解题报告;

  这类开放题目让你自主选择数据结构,主要是考察求职者对于数据结构的特性与使用场景的综合理解,在面对具体应用场景时能否运用已有的数据结构和算法知识提出合理的解决方案。一般来说在这类问题里哈希表的出场率会比较高……例题如下

  1、大数据量的 url log,怎么去重且统计每个 url 的出现次数,复杂度分析;

  4、流媒体播放客户端从多个完全相同的发送方接收视频包,同一发送方的包会按序到达,不同发送方的包则不一定,有可能会丢包,但还是要保证播放流畅度,设计播放客户端的算法。

  ●训练自己算法复杂度的分析能力,有的时候对复杂度的分析会反过来会帮助你找到更好的算法;

  ●一定量的题目积累很重要,就好像准备高考数学压轴题一样,见识的越多,思路来得越快,当然,前提是你能够不断总结反思。

本文链接:http://baumseelen.com/duipaixu/64.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部