面试经验分享之数据结构、算法题
来自：Blog of 太极儒
作者 Frank Song，微博@太极儒
Github - frank19900731
链接：http://frank19900731.github.io/blog/2014/11/18/mian-shi-jing-yan-fen-xiang-zhi-shu-ju-jie-gou-suan-fa-fen-xiang/
前言
面试 IT 企业的研发岗位，数据结构和算法显然是必考的项目。俺只学过普通的数据结构课程，没读过 STL，也没有过 ACM 的训练和比赛经历，在一开始面对这样类型题目的时候，心里还是十分忐忑的。大大小小几十场面试下来，自己在这方面总算有了一定的心得积累，在此抛砖引玉，以飨读者。
在正式介绍题目和准备方法之前，有两点需要说明，
- Google 和 Facebook 这类对算法有很高要求的公司的在线测试我没有参加过（不过在牛人内推帮助下有过面试体验……），这超出了我目前的编码能力范围，网上有不少拿到 Google、Facebook offer 的经验总结文章，可以移步观赏；
- 前段时间在微博上又看到有人说自己把 leetcode 刷了好几遍，不过一些转发评论者觉得， IT 公司面试中的算法考察没有价值，一来工作里用不太上，二来把程序员素质考察搞成了应试教育，他们认为更重要的是应聘者的工程能力。遇到这样的讨论，我一般喜欢和一把稀泥。若干年前， Google、微软的面试题让大家眼前一亮，觉得能选拔出个性十足的聪明人来，不过随着大家对这类题目的适应，可能选拔出来的人也在趋同，至少很多人都会在面试前用心准备，据报道 Google 最近也是放弃了这类面试题目。没有什么一劳永逸、一成不变的考查方式，毕竟面试是人和人之间的动态“较量”。不要贪恋算法的奇技淫巧，也不要因为题目筛选力度的衰减而否定考察初衷。面试不仅是考验求职者，也同样在考验面试官，如果问的都是老题儿，那本山大叔肯定都会抢答了。
言归正传，以下分数据结构题目、算法题目、开放题目三部分来介绍我在面试中碰到的问题。
数据结构题目
概述
虽然课本由简到繁、由难到易地介绍了诸多数据结构，我在面试中被问到的却还都是基本类型，比如堆栈、队列、链表、二叉树。题目主要有两类，数据结构实现和具体情境下数据结构的应用。
分类讨论
类型一：数据结构实现
1、实现 java.util.List 中的基础功能；
2、实现栈，使得 添加、删除、max 操作的复杂度为 O(1)（我脚着好像是不可实现的，想到最好的是添加、删除 O(log)， max 是 O(1)），实现见 正在努力减肥的胖子 同学给出的评论，参考 leetcode 中的这道题目，惭愧；
3、选取任意数据结构实现添加、删除、随机返回三个功能，分析复杂度；
4、用数组实现队列，各操作的复杂度分析。
类型二：数据结构应用
1、两棵树相加——对应位置两棵树都有值则相加，对应位置只有一棵树有值则取该值；
2、用速度不同的指针可以判断链表中是否有环，问两速度满足怎样的关系可以保证发现环；
3、如何在语料中寻找频繁出现的字串，分析复杂度（tire树）；