关门了跌就跌的干脆一点。# Stock
i*e
1 楼
去年的onsite,挂在这题上了。其实不难,之前也有人发过,但好像没详细讨论过。
一组字符串,求所有彼此之间无公共字符的两两组合中,两字符串长度乘积的最大值。
上来就是暴力解O(n^2).问有没有更快的。我问:better than O(n^2)? 对方没正面回答
。结果我以为他是默认了。于是挖空心思的找O(nlogn)的解法,建字符索引,后缀树都
想过。最后没办法,问他有没有hint。结果他提了剪枝。当时我就崩溃了,剪枝早想到
了,但剪枝的话worst case还是O(n^2)啊!我立刻说了按长度排序再剪枝的方法。但是
时间已经不够写代码了。
想问问这题究竟有没有优于O(n^2)的解法。当然,假定比较两字符串的时间设为常数。
我的感觉是没有的。当然,我可能是错的。
教训就是面试是交流的过程,想到什么improvement就说出来讨论讨论,就算他不认可
,至少也知道你想到了一个方法。最忌讳闷头苦想,而面试官根本不知道你在想啥。
==========
去年还面了FB的onsite,挂在把二叉树转为双向链表上,吐血。当时昏了头拼了命要写
个functional style的,结果把自己绕进去了。其实搞个全局变量记录上次访问的节点
的话很简单。
今年想再试试linkedin和twitter两家。因为G和F的recruiter之前联系过了,就不找人
内推了。求帮忙!如果之前有人发过提供内推的贴,给个链接也好。
一组字符串,求所有彼此之间无公共字符的两两组合中,两字符串长度乘积的最大值。
上来就是暴力解O(n^2).问有没有更快的。我问:better than O(n^2)? 对方没正面回答
。结果我以为他是默认了。于是挖空心思的找O(nlogn)的解法,建字符索引,后缀树都
想过。最后没办法,问他有没有hint。结果他提了剪枝。当时我就崩溃了,剪枝早想到
了,但剪枝的话worst case还是O(n^2)啊!我立刻说了按长度排序再剪枝的方法。但是
时间已经不够写代码了。
想问问这题究竟有没有优于O(n^2)的解法。当然,假定比较两字符串的时间设为常数。
我的感觉是没有的。当然,我可能是错的。
教训就是面试是交流的过程,想到什么improvement就说出来讨论讨论,就算他不认可
,至少也知道你想到了一个方法。最忌讳闷头苦想,而面试官根本不知道你在想啥。
==========
去年还面了FB的onsite,挂在把二叉树转为双向链表上,吐血。当时昏了头拼了命要写
个functional style的,结果把自己绕进去了。其实搞个全局变量记录上次访问的节点
的话很简单。
今年想再试试linkedin和twitter两家。因为G和F的recruiter之前联系过了,就不找人
内推了。求帮忙!如果之前有人发过提供内推的贴,给个链接也好。