未名空间十大: 恭贺新禧发谷家面经

发信人: Mephisto1527 (???), 信区: JobHunting
标题: 恭贺新禧发谷家面经
发信站: BBS 未名空间站 (Mon Feb 23 14:28:40 2015, 美东)

首先感谢推荐以及陪同午饭的大牛哥，以及一直帮忙的美女！
本着同样帮同胞的精神回馈一下版面。

今天接到人力电话，说反馈还不错，但是很遗憾只能明年见了，不知道啥原因。
当时面试感觉挺好的，面之前就知道这个据点不怎么招人，不知道是不是这个原因。
电面两轮。
共五轮，有三轮和面试官谈的双方都很开心，其他的一轮也算中上，有一轮一般，但题
也做出来了。
所有题不是leetcode加面经覆盖过的，就是思路不怎么难的题。
不按照顺序上题

一、一道面经里面提到过讨论过，但是不太一样的。改用中文例子。
就是字符串编码解码。
编码规则是

原字串：
春节快乐喜气羊羊羊年大吉

编码为：
春节快乐喜气3x羊年大吉

两个情况下会有歧义：一个是原字串中的数字加x
之前面经提到的是用两个x转义，但是我遇到的要求是解码程序的逻辑不能改变。

此外还有压缩后前面的数字问题，比如
3羊羊羊开泰
变成33x羊开泰则解码程序会出错。

实际上这两个问题是一个问题，就是编码后源串中代表数字的字符恰好出现在数字加x
前面怎么办。

经过讨论，解决方法是将所有的领头数字编码例如：
3羊羊羊开泰
就编码成
1x33x羊开泰

要求尽量优化，也就是说只有歧义的情况下才将数字编码。
我给出的方法是扫描字符流（这个是限定的输入条件）同时维护一个窗口，然后随时判
断是否可以输出窗口，如果需要则对窗口做转义再输出。

二、每个字串可以编码为头尾字符和中间的字符数
例如
新春快乐万事如意
变成
新6意

实现方法给一个字典，一个字串，返回字串的编码是否在字典里面有冲突。

确认了字串是否一定在字典里；反问你怎么设计；我说如果在的话还是返回是否有冲突
，如果不在的话返回是否和现有的有冲突；认可这个设计。
确认字串长度不足3怎么办；反问你怎么设计；我说不足就是返回原串；认可这个设计。
确认思路是每个字串都可以直接得到编码，之后用这个编码字串判断冲突就可以。
实现很直接；写的时候，提到如果工作中遇到的话，一般要构建这个字典，所以可以保
留一个编码到字串的哈希表，用来直接判断。
对方听了以后让设计这个类的api。

三、
给定字串，输出第一个不重复字符的索引值
例如
0 1 2 3 4
羊年发羊财

输出1，因为羊重复。

其他题都是出过的就不说了。

总结一些要点希望有用。
. 每轮期待做出两题，其中第二题可能是变种，也可能是新题，而第三题一般让说思路
就可以了。我只有其中一面写了三题，大概是因为第二题的变种比较简单。
. 重点还是考代码，和对于算法分析的熟悉，会的思路要能写成简要工作的代码才有用
，如果说了很高深的算法一般也不会让写。
. 重视交流，包括开始有思路的时候要说，就算是有些明显的假定也要说出来，说几个
分支，如果这样如何，如果那样如何，然后讨论；没思路或者有问题的时候要说，确
认哪些是对方的肯定要求，确认问题的存在，提出实例或者解决方法，当场试验也可以
，但是不要冷场；写代码的时候也要说，我这里要干啥，如何如何。要特别注明一点
，对方的反馈即便是反问或反例也有可能是提示讨论或引导，不要反感，而要积极的针
对进行讨论。还有就是面试官不可能准备所有可能的解法，有可能自己的解法不是预
期的，但你确定的话就可以讲解。

最近看大家提到年老色衰的马工准备和刷题的问题，随便说两句希望给大家一些信心：
我是年底时被人力联系，开始没太抱希望，后来过了电面开始准备，刷leetcode，去年
没用的年假都用来干这个了，前后折腾了1个半月，这里感谢一下老婆在这段时间的支
持！
以前也比较怵头刷题，开始刷的时候找简单的开始，刷起来了就有感觉了，第一遍12天
刷完，后来又过了2遍，到现在总来版上看看新题和大家讨论下思路。感觉leetcode上
的题真心不是变态的，刷一下练练编码基本功其实对工作也是有一定帮助的：
一是对于一些简便的方法api，以前不知道用的现在可以顺手使用。
二是一些便捷的实现工具例如链表假头这种简化实现的方法比较熟练了。
三是对一些具体的编码实例系统的掌握了，比如多线程的一些常用模式实现，这个正好
在准备期间用在了修一个公司的问题上。

此外虽然没被问到系统设计，但准备中了解的各方面知识和解决方法感觉挺有用的。

有些朋友可能家里老人小孩工作操劳的没时间没精力，如果不是完全忙到没时间体力，
刷题真心不是特别巨大的工程。
我不是大牛，但咬咬牙也刷过来了，比起一个同事年假在家没事干，某游戏打到50级，
还是有些用的，就算给自己多个选择吧。

有些刷题的个人经验: 实在太怵头的，可以从简单开始，找找感觉。比较有效率的方法
是按专题分类做，比如树，链表，动规等分类。做多了就会总结出常见套路，例如链表
无非是一个假头，一个反转，一个快慢指针几个常规动作，加上一些观察到的技巧。因
为时间原因没时间看G4G，但上面的动规讲的不错，还有计算几何的基本算法也有讲解
，看一下很帮助理解。每题想通搞懂后，留下笔记和注释，包括关于思路的，以及关于
细节的，这样下次再刷就简单了。明显属于思路难的题，稍微想一下想不出来就去搜一
下思路，不然自己想太费时间了。

面经里面的题很多来源不详，很多题都说不清，或者细节缺少太多甚至无法分析，这种
题看看就过了，不过可以把每次类似的放在一起，这样拼凑起来有时候帖子中会提到某
关键点，这样就能知道这道题的关键思路在哪里了。顺便说一句，其实面的时候感觉还
是编码的基本功，面经和刷难题主要的作用是提前分析不熟悉思路，减少临场想的风险
。有近期的高频题最好自己写一下，有的时候版面上说了算法名就过了，可自己写了会
发现在面试中自己写是不可能的，这种情况下最好能多讨论下，或者自己好好研究下。

看版面上有人抱怨中国人刷题搞坏了风气。
这次准备的过程中，我就回想起本人多年前面试时候，那时候还没有这种方便在线刷题
的网站，曾经被三问过的类似leetcode的题。当时还被问到一些概念题，感觉就是他们
在某培训学校学的概念，必须要按照他们设计的答案答才是正解，否则就一脸不屑。最
近朋友也有参加非CS专业考试的时候，看到三们拿着一叠厚厚的面经材料，估计是类似
于新东方爱西西这样的机构搞出来的。所以个人觉得刷题搞面经不一定是我们搞出来的
，始作俑者和现在的踊跃实施者并不一定是我们呢。

当然希望有机会奔向管理的同胞能够更多，不过由于各种原因可能不适合于所有人，所
以根据个人呢机会不同有条件做管理就做管理，有条件发展数量就发展数量，都能帮助
同胞把势做大一些，这样大家都能多一些机会。

祝大家职业发展顺利，合家健康幸福！

--
※ 来源:·WWW 未名空间站网址：mitbbs.com 移动：在应用商店搜索未名空间·[FROM: 199.]