创新工场面试经历

先赞一下工场的效率，投了2天就来电话了。

一面问了两道关于链表的题，第一道题是，单链表怎么判断有没有环，我说设置一个标志位，他好像是说HASH的方法。

第二道题是：一个双向链表，节点的指针1指向下一节点，节点的指针2指向任意节点。问如何复制这个链表。

第二题没有什么好想法，效率都是很低的，他的意思大概是，可以做到O(n)的不管从时间还是空间上。

又问了我是否了解对于大规模在线的服务器通信的模型，我说我只是知道一点儿，还问linux下查看进程内存的命令是什么，我只记得有个查看进程的倒是，是p开头的，但是包不包含内存就不知道了，所以……只能回答不知道了。

二面的题要难不少，而其全是关于ACM的，“你不是获奖多么，你不是牛么，那我看看你又多牛”，啊……下次不写奖了，可是不写简历都通过不了……

先问我印象最深的一道题目是什么，我就说了一道，他说好像是某某比赛的题……哦NO，估计对面做过相当多的题。

第一题在二维平面上，一个robot移动，给定某移动序列，问经过无数周期后，是否离原地越来越远。想了一下4个周期内一定可以判断出来是否越来越远，后来问我有没有更高效的办法。我一直感觉最终状态在偏离90°后可以回来，可是又不能确定，现在细想一下，只要最终的方向不同貌似都可以回来！无非就是90°转4下和180°转2下。

第二题是一种字符串'0'-'9'组成，n长度，要求这种串的任意一个字串的积不能相当举个例子：

12345

子串 1 3 5 的积 1*3*5 = 15

子串 3 5 的积 3*5 = 15

所以这个串不满足要求

现在问，给定一个n 要求第k大的满足这种条件的串 是什么，

这道题我做的相当悲剧，没有找到这道题的规律，0,1是肯定不可以出现的，然后每个数字只能出现一次，他的积得定义就导致了 是否满足条件和数字的顺序无关。而我却去想积相等一定是质因数分解后相等0-9只有2,3,5,7，然后想不下去了，后来他把规律告诉我，我立即想到搜索，他说，那快把程序写一下吧，我说等会儿，怎么判断这个串是否满足条件还没有想好，子串那么多，不可能枚举吧（后来算了一下最差方法 (2^8)^2*2^8 = 2^24 大约16*10^6还算可以），最终还是没有想出来，他的意思好像是动态规划，他的后来他说，时间也差不了，就结束了。其实现在也没想出来，可是有想法，2,3,4,5,6,7,8,9这几个数，只能出现一次，可以发现，7不和任何数冲突，5也是，但是如果有6的话，那么2、3不能同时出现，比如263这个串，字串2 3 和 6 不行。还有 2 4 和 8不能同时出现，是不是只有这两种情况呢？那么就简单多了……

过了2天，就收到了被拒的消息，我回了一下想知道我的评价，然后工场的确回复我了，思维不够敏捷。工场的确不错，不像大企业，拒人从来不告诉。“蓝领”当不成了，呵呵。的确很向往，据说牛人很多。

你是应届的么？