注册一亩三分地论坛，查看更多干货！
您需要 登录 才可以下载或查看附件。没有帐号？注册账号
x
上午第一场，Reverse Polish Notation。大概跟他扯了几句直接上手就写了一个以Operator为base class，然后Add,Subtract, Multiply, Divide四个class继承这个Operator base class的写法，一遍写完调过跑通样例。他就说，你这个实现的是基本的binary operator，如果要支持unary或者是ternary怎么办呢？我就把Operate(intval1, int val2)直接改成了Operate(vector<int>& vals)，一开始想直接定义一个int NumOperands但是不知道为啥C++居然编译挂了，他就说要不咱们改成一个函数getOperands()，这当然没问题了。写过之后又是传统的follow-up question问怎么才能直接给用户binary，让他们可以自由的添加新的operator。我就说好像听说Java可以，C++我说一个简单粗暴的办法是跟用户约定好DLL然后去call这个DLL……他说倒是也行，不过他觉得更好的办法是做XML / JSON的serialization，我表示认同。然后就没有任何悬念的进入了下一题Remove subtree from tree……其实就是类似于DP的思想，加个visited来做memoization，一开始没处理好边界条件小挂了一下改好之后他说你这个code是work的，但是如果第二次运行会有bug……我思考了一下发现我没有更新arrayTree-> size，而且更新了size之后初始化的时候得用capacity。后来他又说这code还会有啥问题么？我就想了两个case，一是index不合法，二是删除一个已经被删除的subtree的时候size会继续往下减，就不对了，所以加了一个特判。这场面试就愉快的结束了，然后我问他这个题目有没有linear time constant space的做法，他说据他所知没有，我的做法应该就是最好的了。 第二是printtimestamps with diff < 1和website太慢应该怎么办……面经上对于这个题目的意思一直都说的很不清楚，正确的说法是他后来想了很久说应该你基本都cover了，我就估计这一轮应该也OK了。 第三轮是wildcardmatching……他给了描述之后我直接给了DP的解法，他一开始还没有理解……自己看那个递归看了很久……看完之后他说你给这个DP的解法太顺利了，咱们就想想linear解法吧……妈的说实话我真的不知道有没有linear解法，LeetCode上那个所谓的linear解法显然是错的，那个是在backtracking……我就尝试问了一些问题比如说你是要worst case linear么还是说只是average case会快不少？我尝试解释了一下two pointer method他马上打断了说你这个本质就是在explore solution space，没有区别……妈的我就觉得这丫在黑我……我就思考来思考去，他就提示我说要用linear的pattern matching algorithm做building block……虽然我不会，但是这个时候还是得展示一下自己懂linear time的pattern matching algorithm……我就赶快说我懂Rabin Karp但是我不知道这个加了*和?怎么做hash。他就说不是这个意思，是要把这个作为building block……我想了很久说可以把通配符拆开，把原pattern string拆成以*和?分开的一些小的pattern string，在原text string上做pattern matching，然后得到一些匹配的index，在这个index上做DP……他说你close了，不过再想想，有更好的办法……我就说也许这个匹配可以greedy……他就问怎么greedy……我说每次取第一个，他就问你能否prove。。。然后后来他说这个greedy好像是错的……anyway，他说我们时间好像不够了，你先写DP吧。我就5分钟写了个DP，他可能觉得太快了……就让我加点testcase，我加完跑完一遍correct，就又开始扯其他的比如说怎么generate large scale的test case云云。后来他解释了一下linear的算法，说是先把不包含通配符的prefix, suffix先match掉，然后整个串就变成了类似于*p1*p2*p3*的样子，然后对于每个p_i可以做取第一个的greedy match……不过我其实并不知道带?的p_i到底应该怎么匹配，当然他这样说了我就点头称是然后说真NB…… 中午去了Aurora，反正不是lunch interview我就不多说了，吃完之后我最关心的就是是不是可以回hotel了……HR过来跟我说你准备一下下午面谁谁谁，呵呵呵我居然也通过早上的面试了 =_= 下午第一轮，anyway完全是culture的question，基本就是介绍了一下我的工作以及whyTwo Sigma? 我就一直围绕着nice geek来谈的似乎他还挺满意…… 下午第二轮，同样是culture question以及介绍自己以前的project，问了一个很弱的battleship怎么实现hit(int r, int c)的函数的问题……反正这个很脑残了我就不说了 下午第三轮，基本上也是culture方面的question，介绍了一下我的工作，然后他问了一个这样的题目：就是一个train在入站台和出站台的时候需要先减速再加速，问你车的哪个部位在整个站台停留的时间最长。我大概思考了一下乱说了一个head……后来work out math的时候我发现head和tail的时间是相同的，我就开始觉得应该是midway停留的时间最长，(这个时候有一个假设是减速和加速的加速度是相同的)。面试官说对，然后就问how much longer? 然后给了一个提示用s = 1/2 * a * t * t这个公式去推，我大概写了几行跟他说大概是(sqrt{2} - 1) longer，他有点惊讶因为他好像觉得我很多步骤跳掉了……anyway他觉得没问题，后来又问如果减速和加速的加速度不同那怎么办，哪个点停留的时间最长？我直接画了两下猜了一个表达式大概就说是要在车的(a2 / (a1 + a2))分界的地方……面试官就问为啥？我尝试work out math了半天未果，反正大概就是1/2 * a1 * t1 * t1 = x, 1/2 * a2 * t2 *t2 = S - x然后去maximize t1 + t2的值，很明显的我的数学水平已然不足以解决这个问题了……不过面试官说我很惊讶你一开始给的答案就是对的，我就说这个intuitively大概就是这样blah blah，然后他说不用推了我们又开心的聊了一些culture问题结束。
| 
狗仔卡
收藏
淘帖
好苗
杂草
提升卡
置顶卡
关贴卡
开贴卡
变色卡
千斤顶
楼主
