Pocket Gem 8.19

原帖地址:一亩三分地

楼主Onsite被拒了。这是楼主找工作第一个onsite,经验准备都还是不足,通过这个onsite也学到了不少经验,通过面试来提高还是很有必要的。以下是面经,基本上和地里的面经一样,面经真是好东西,大家面试之前多看看。
电面一面:ternary expression to binary tree二面:1.sort colors, 2. next largest node in the binary search tree with parent pointer, 3. if a point is in a triangleOnsite: onsite这几题其实面经里都出现过,但是楼主可能有点紧张,写了都有点bug。。大家平时也要注意一些写代码的细节。1. 1.1 Max product, 这题虽然很简单,但是写的时候没有注意出了一个Bug,印度小哥问我有什么问题看了半天没想出来,最后还是他告诉我的。。。1.2 given an array of numbers a, find two numbers at index i and j, such that, j – i <= k1, |a – a[j]| <= k2O(nlgk1) solution if we sort first k1 element and form a tree structure and remove and insert numbers one by one 这题也是leetcode的原题,我用了hashmap,把数字hash到他们所在的范围里(0-k2, k2-2*k2, …),然后找,这个方法是O(n*k1),当然我写的时候又出了一点bug。。。后来印度小哥问能不能更好,没想出来,他告诉我一种O(n*lgk1)的方法,我记得geeksforgeeks上也有的,大致意思是先把前k1个数sort一下,组成一个树的结构,之后每一步就是remove一个数,加入一个新的数,看看和新的数最接近的两个数是不是差小于k2,这样每一步就是lgk1的。2.2.1 Word break, return the maximum split 只需要return 最多能把原string分成几个dictionary里的词,所以应该用dp是比较好的方法,当时楼主没想清楚直接用了DFS。。小哥问了DFS的时间复杂度然后被问住了。。最后实现出来DFS用了剪枝,但还是有一个bug。。。2.2 find the first missing number in 0 to n, (special case, if n is missing) 0 – n continuous numbers (like 0, 1, 3, 2, 0, 2, 数字是连续的, 0 到 3 的每个数字都有), appear once or twice, how to find the number appear once, how to find the number appear twice with constant extra space and linear time. 前一题耗了比较多的时间,这两题就口头答了一下, 第二题楼主给的方法和第一题是一样的,都是把数字swap回和它一样的index (把 0 放在 index 0的位置,以此类推)3. OO Design: Achievement System和地里面经一样,非常感谢地里面经,design的东西要不是看过前辈的回答真是不懂,结果自我感觉这轮答得反而最好。我感觉比较主要的就是设计好requirement 和 reward 两个接口,然后对应player的每个属性,比如金币、动物,各设计一个具体的requirement 和 reward class, 这个在地里的一篇面经上有前辈讲解过了,大家可以去搜一个面经合集里面有,achievement class 的 instance variable 就是一列 requirement 和 一列 reward, 其实的确一组requirement和一组reward就定义了一个achievement.要和面试官多多交流。这轮因为不是做题,所以基本上都一直在和面试官交流。面试官也非常积极得讲他的想法。 然后大概我前两面面的不太好,时间也4点多了,他们也快下班了,就没让我面第四面。面完想了一下其实题目面经里也都有,就是平时写代码的时候不够注意一些细节,有些习惯不好,面试的时候还是会体现出来的。然后算法和数据结构的基础知识还是要学的扎实一些,这样就不会在被问时间复杂度这些问题的时候懵了。在面试的过程中也学到了很多东西,所以通过面试提高也是很好的。