-
为什么Google的工程师也买不起房
发表于 2010年10月20日 2 条评论这个话题的由头来自这里：“Google2011校招笔试题暗示搞软件没前途，囧”，这是在招聘现场的面试题，但从我个人的招聘经验来看，后面几乎肯定是会问及原因以便更深入的考核人才。 这里说说我在仅仅只是看到题目时，大约5分钟内对此问题的相关思考。 这个时间对于面试来说，已经不少了，需要在表达前面的考虑时进一步抓紧思考压缩时间了。
首先考虑回答其作为选择题的答案，我毫不犹豫的选择了“永远买不起房”，原因是早有科学实验表明，正常人最多七天不吃不喝就挂了。当然，我也会选择再花30秒左右的时间做一下简单计算或者是题目基本完成后重新验算。 在这个回答背后还有一个原因是我并不相信Google会要那种只懂得在“真空”、“过程中无能量损耗”的假定下表现良好的做题天才。
后来李开复在新浪微博上对此回复：“不吃不喝早死了”，大概也算是间接的支持了我这个观点。
让我们从快速检查的角度再来考虑，用简略的方式来做一个估算：首先200万的房子需要5年才能买。而10%的增长在5次后心算一下大约是1.6上下一点，但必然大于1.55。因此，5年后房子应该在310万以上，工程师需要3年的时间完成这部分积累。而又由于3年时间房价再增长30%，也就是增值93万以上，因此8年内肯定买不起。最后，第9年是400万以上的基数增长，从此，这房子是真的不用考虑了。
在我向人讲解我的上述思路的时候，想到了另外一个更加快捷计算方法：首先我们假定房价至少翻倍这工程师才有可能买得起房，也就是400万，400万后由于涨幅高于年收入不用考虑了。400万Google工程师需要10年的时间来积累，而无比明显的是，八到九年，10%的增长必然已经导致翻倍。 同时，由于在达到400万前，工程师的存款增长高于房价增长，因此，10年内不存在买得起房的可能。
最后，如果能进入面试流程。还得告诉面试官我的前面两个思路，并且告诉他们为什么我认同“不吃不喝早死了”，依然会做验算：一方面是出于谨慎；另一方面是我很是向往Google的免费三餐（特意找了个链接：http://www.dianping.com/group/fubai/topic/108841/lz）因此我相信那位工程师确实不需要为吃喝付出什么，住宿也可以在公司十年如一日的睡袋解决。其次，如果能开动脑筋帮工程师（也许就是你未来的同事，也许就是将来的你）解决“丈母娘难题”，那就更好了。 比如说先上车后补票，找个年收入在12万上下也许要略高些的美女跟你一起共建和谐社会，SO你可以跟丈母娘保证8年后你们一起拥有爱巢。 这个答案是绕开了“不贷款，不涨工资，没有其他收入，每年不吃不喝不消费”的要求，梗着脖子说美女的收入不是你的收入。 也许这不够优雅也许弄巧成拙，只说前面的考虑更好些。 反正在10分钟内，我没有想到更好的方法了。
最后感叹一句：杯具啊！
相关日志：
-
也说海量数据的快速排序
发表于 2010年07月11日 没有评论
年初的时候就有同事面完以后回来和我聊过，5000万无重复32位无符号整数中取出10000个数字的时间+空间最优排序方法，以及存在重复数字时的最优方法。 今天正好有空，把当时考虑的解决思路写下来：
首先肯定是空间换时间，方法基于位运算创建一个大内存区，单次接受数据，每个数字设置其所属的bit，随后遍历输出。这样子的话所需要的内存空间是32-3=29位，也就是512M。这个算法时间性能是足够保证了，毕竟无迭代，空间通过分块的方式来降低是一个思路，但4亿数据（32位）中有5000万，稀疏的程度远不足够，只能作罢。 这个方案的好处是即使进行全排序，其时间性能和空间性能也不会发生改变。 空间最优则应该是通过维护一个红黑树，先丢10000个数字进去，然后遍历剩下的数，从红黑树中汰选最小值替换之即可，遍历红黑树进行汰选前先比较预存的树中最小数在正常分布下能有效减少性能损失。
重复数字的简单解决方法是增加一次遍历，首次遍历将需要取出的10000个数字汇总后构建哈希表，再次遍历时仅只计算哈希表中元素的出现次数，最后按照10000个数字的次序遍历，并累计哈希表中的计数至10000次即可。 空间最优方案依然还是选择红黑树。
从综合考虑上来说当然是红黑树的实现在时间和空间上都有不俗的表现，但实际应用起来还是位运算靠谱，毕竟再怎么高效查找也好，碰上一个悲观分布（数据本来就是有序的且和要求输出序同向），那就是5000万次树遍历了。而位运算的空间占用是恒定的，时间则和总数据量等比，非常稳定。
当然，如果是有重复，全排序，基本上也只能考虑MapReduce了。
相关日志：
-
如何用两个立方体表示所有日子的组合
发表于 2010年02月4日 4 条评论
今天碰到一个很有趣的问题，如何用两个立体表示所有的日子（不需要年和月）。
一开始就考虑123是可能需要重复出现的，而12种组合里扣除3个以后无法表示10个数字组合，故此路不通。 而且这问题应该没这么简单吧？
花了下空间图，结果发现了一个很取巧的方法，其中一个立方体上写上456789，另外一个则是310221。通过仔细的组合，其实能够让第二个“奇怪”的立方体表示出01、02、03、10、11、12、20、21、22、30、31，其他也就不用多说了。思考的时候也考虑过把数字颠倒或者是用LED字体，通过两个立方体组合显示等，不过都没办法解决。
啊哈，当然没那么简单。不能这么的取巧，不同的数字要分步在两个立方体上。 又再考虑了下，其实3在重复组合中是个特例，仅需要30和31 。 所以，只要让3和0分开，两个立方体上都有1和2，那么就刚好可以匹配所有选择。 不过这个答案还是不对，因为无法表现01-09的所有组合。 0也是个特殊化的数字，没有00，然而需要从1-9并没有办法减少对数字的需求，所以我面对质疑还是肯定的说，如果需要表现01-09，则应该是无解的，因为10个基本数字外仅容许两个冗余，1和2已经把名额用光了。 嗯，当然，如果我们说的立体不是正六面体的话，那自然是很简单的啦，哈。
好吧，我也承认这个只是取巧，不可能采用。 回到电脑前查了一下，发现这个问题其实还是有解的，恰恰是我思考中考虑过的，通过字体来“欺诈”，呵呵，很多字体特别是LED字体中的6和9颠倒过来是一样的，可以省出一个空格，只要这个空格放上0并且和之前那个0不在同一个立方体上就可以做到了。 当然，这就不再是数学的解法了。
有些时候，完成一件事情所需要的条件我们都具备或者是不费力的拥有，却无法得出一个最优的答案。 事实上我考虑这个问题的时候一开始并没有限于数学领域，否则也不会有相邻组合的取巧做法和非正六面体组合的想法，然而得出最接近真相的方法是数学方法，于是在得到需要01-09的时候也自然的用了数学方法准确的证明此题无解。
记录下来，提醒自己不要钻进一个胡同后，蹲在胡同里考虑所有前面巷子转弯的组合就断言罗马不可达，不要忘了递归算法能解决问题最重要的办法就是算不出来就回溯，换个方法再算！
相关日志：
最近评论