10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 437|回复: 8
收起左侧

跪求狗家2017年度面经集锦

[复制链接] |试试Instant~ |关注本帖
newJames 发表于 4 天前 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Other在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
最近要面Google了,是西雅图的职位,跪求今年狗家面经总结。BTW,我近期也会贴出我的其他公司面经回馈地里。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
haifengc 发表于 昨天 00:43 | 显示全部楼层
* points insider a triangle
    * http://www.geeksforgeeks.org/check-whether-a-given-point-lies-inside-a-triangle-or-not/
* 第一轮
    * leetcode 163 missing range
    * leetcode 269 Alien Dictionary
* 第二轮
    * java gc
    * 抽象类和接口的区别,很多细节
    * unit test时好时坏怎么办,看随机数,Date, 多线程
    * ✓ leetcode 238 Product of Array Except Self
* 第三轮. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    * 烙印让设计一个订票系统,各种表,不过感觉烙印有点弱,也不太懂,开始说不管性能,最后剩5分钟开始问性能,几乎要重新设计,轻度被黑. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
* 第四轮
    * 跑得快,手上一堆整数,能不能全部分成顺子,顺子是3个以上连续数. from: 1point3acres.com/bbs
* 第五轮.鏈枃鍘熷垱鑷1point3acres璁哄潧
    * 200k个字符串,找到最小的会文字串,还要同时包含所有的字母(字母集合可能不止512). Waral 鍗氬鏈夋洿澶氭枃绔,
. visit 1point3acres.com for more.
* 第一轮
    * 两个string,char一对一match。比如(“banana”和“cololo”),follow up:如果有一个String[]对一个String,同样的match判断,要求输出所有match的string
* 第二轮
    * 1、有一个无限长的double linked list,和一个pointer array,每个pointer指向list中的一个node,求有多少个不相连的node group。
    * 2、二维平面上给一个矩形(和坐标轴平行),在矩形中给一个unified random的点。.鐣欏璁哄潧-涓浜-涓夊垎鍦
    * 3、有一个touch screen的键盘layout,给一个test用的string array,要求return一个map,每一个test string对应一个result string。result string是手指在layout上按顺序划过的characters。
    * 4、给一个string pair list,两个query string,根据string pair list判断两个query string是否match。
    * 5、给一个二维grid,从(0,0)到(n,0),只允许右,右上,右下,有几种走法。

* 第一轮
    * ✓1.1 问一个数组里面最长的连续的递增数列的长度
    * 1.2 如果是一个tree,不一定是binary tree,的最长的连续递增的序列的长度, 这一问我是用recursive dfs做的,然后被要求用iterative 做一下。
* 第二轮
    * ✓求两个整数的二进制有多少个不同的位数
* 第三轮
    * ✓问一个数组能否只改变一个数字,从而让他变成单调增的数组。, 比如[3,3,2,2] 不可以,[1,2,5,3,3] 可以把5变成2或者3,可以。
* 第四轮. From 1point 3acres bbs
    * guess number,好像是以前的题?我没做过,还好跟leetcode上那个predict winner(或之类名字)的题很相似。
    * 给定一个范围,我要猜一个这个范围内的数字,每猜一个数,我要支付这个数字相同的钱,每次我猜之后,他的回答是大了,或者小了。问最后我最少付多少钱可以一定猜到这个数
    * 我设了一个dp 2D array,然后跟leetcode 做法predict winner相似。总而言之是我和他都要取对自己最有利的下一步。
* 第五轮
    * ✓给定一个函数f(x),由一段单调增一段单调减构成,比如抛物线。给定单调增的x的数组输入,要求输出单调增的y。
        * 大概做法是从两端开始考虑,结果数组里填f(x),要注意区分抛物线(比如)开口向上向下的情况。期间还指导了我如何写出漂亮的程序结构,比如loop里少用些if条件。

* 第一轮 电面
    * ✓要求实现一个计时的 map 和其两个功能,set和get:
        * set(key, val, time)插入val和time for key
        * get(key,time) return val if not found return None
        * 每个key可以有好几个val和time。我选了dict来实现。因为我用的python,用了defaultdict(list),面试官一开始没反应过来tricky部分是,set调用多次,不一定time递增调用,然后get,如果time=1,3,4 for key1, get(key1, 2), 要求返回time=1的val。我一开始忽略了,结果直接返回none,因为2不在1,3,4里面。。。面试官(安慰我?)说好多人也犯过这个错误。连连道歉然后猛改。。。越改越紧张,磕磕绊绊。问get的复杂度,O(N)。面试官全程很nice很照顾,就是自己太紧张了!!!
        * follow up如何优化get,我说keep a sorted list based on time,这样get是logN,不过set也是logN了。. 1point 3acres 璁哄潧

* 第一轮 电面
    * 第一个是一个美国大叔,做infrastructure的,聊了一会儿我的背景和做过的项目。warm up 问了一些算法的时间复杂度,
    * 技术题问了 wildcard matching... follow up 让给手动过了几个例子。然后完了还有十几分钟,又聊了一会儿google cloud。
* 第二轮电面
    * 第二个是一个国人或者(ABC)小哥,一开始聊背景,做的research,然后问了 full binary tree (每个node 要么有两个child要么没有)的问题,求给定leaf node数量,生成所有可能的树的结构。做完还有点时间,他介绍了一下他intern 和 fulltime的经历,他对google 的看法.1point3acres缃
. visit 1point3acres.com for more.


* 第一轮
    * system design,设计一个ticket system,其实就是一堆client都request一个number,traffic巨大,要求所有client request的ticket要基本sequential
* 第二轮
    * coding,给一个function D(), 假设这个function运行时间不一定,有时候很长,有时候很短,写一个wrapper function,里面是不停的call这个D(),要保证这个wrapper function运行时间是一定的, 第二题不记得了
* 第三轮
    * 聊很多很多的网络知识,聊项目
* 第四轮
    * leetcode 394 Decode String. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
* 第五轮
    * leetcode 301 Remove Invalid Parentheses


* 第一轮. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    * 分享一个Google onsite趣味题,面的其它题目比较常规,就不赘述了。趣味题如下:有一道密码门,设有二进制密码,事先不知道密码,也不知道密码有多少位。密码输入只有0和1两个按钮。系统内部设有一个buffer会存储输入,当输入达到和密码相同的位数时,系统会比较输入和密码是否匹配,如果匹配,则门开;否则没有任何反应,并清空buffer。问如何试出密码?
. 1point3acres.com/bbs
* 第一轮.鏈枃鍘熷垱鑷1point3acres璁哄潧
    * 给了一个迷宫,类似于一个二维矩阵,让用一个data structure表示这个迷宫,我用了一个vector<vector<set<char> > >, 其中set<char>里存四个方向,比如(0, 0)点右边是一堵墙,那么(0, 0)里面只需要存 'D',因为只有向下的方向可以走,版上的大牛也许会有更好的方法,然后给定一个start point和end point,找出从start point到end point的一条路径。
* 第二轮
    * 出的题是link list的变种,skip list,反正我是没听过,让我写这个skip list的struct结构,然后给定一个target value,让在skip list里找这个target value,要用到skip list的一些特性,类似于二分查找
* 第三轮
    * 给一个多叉树,让遍历这个树,然后的follow up是假设这个多叉树被corrupt了,给出一个set存了树里所有节点,让找出根节点。
* 第四轮
    * 给一个数组,每个element可以最多backward移动k个位置,但forward可以移动任意个位置,让尽可能的将这个数组排序,在时间复杂度上讨论了很久,从最初的n^2算法,到k*n算法,最后改进到logk*n算法
* 第五轮
    * 问了挺多security相关的问题,因为和我的背景match,他本身也是security组的,最后让实现一个调用hash function的函数。. more info on 1point3acres.com

* 第一轮 电面
    * leetcode 297. Serialize and Deserialize Binary Tree 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

.鏈枃鍘熷垱鑷1point3acres璁哄潧
* 第一轮
    * nextpermutation 这么简单的题楼主也吭哧半天,水平太差了。最后还剩十几分钟面试官MM居然说因为本人答得快,开始聊项目。多谢高抬贵手
* 第二轮. 1point3acres.com/bbs
    * find k-th largest element from a max-heap   
    * leetcode 128. Longest Consecutive Sequence
* 第三轮
    * sqrt(n) , 然后引申出去考基础知识,hashmap 如何以最优空间存这个结果, search tree怎么存最优空间, 从f(n)反向求n需要什么条件,等等. more info on 1point3acres.com
* 第四轮
    * 设计一个订票中分配座位系统,方方面面讨论的比较多
* 第五轮
    * 专业知识比较水,面试官完全不是我这个方向的,以我讲为主


* 第一轮
    * leetcode 66 Plus One. From 1point 3acres bbs
    * union find

* 第一轮
    * 如果給定一串小寫的英文字串,那麼按照字典順序,最小的下一個字串是什麼呢
        * 只要把給定的字串尾巴補個 char  'a' 就好。

* 第一轮 2轮coding 3轮general SE
    * finding longes prefix
    * giving a set of points, find all rectangles. 看到这题有点闷,一直在纠结最优解,觉得用对角线中点外加斜边长度外加x或y应该可行,但是脑子僵了卡了半天。面试官很nice,说要不用暴力解吧,我想了下说,暴力解要O(N^4),而且觉得代码量也蛮长,就不大想写。最后纠结半天,说了暴力解的思路。在最后几分钟,感觉对角线解也想出来了,跟面试过说了下,他说that might work,就走了。
    *  friends of friends 外加一些计算机基础知识
    * Use one-dimension bitarray to mimic a two-dimension bit matrix,支持set, get某一个点设成0或1. follow-up是在这个matrix上画横线,竖线。 再follow up是画斜线。。当场我就投降了说,不是graphics major。不会。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    * minimum substring that contains the given characters ,秒了,刚想写代码。大哥说,你做过吗?我说没啊。他说,我觉得你idea对的,咱换个题。。我。。后来换成不给string, 给一个string iterator,用HasNext和next接口. more info on 1point3acres.com
. from: 1point3acres.com/bbs
* 第一轮 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    * leetcode 151 Reverse Words in a String
    * 类似decode ways的题目。不过题目背景是摩斯编码,要求输出所有可能的解码方式,而不单单是数目。用了类似decode ways的DP解法,只不过数组里存的是a list of decode strings
*  第二轮
    * leetcode 288 Unique Word Abbreviation的题。Follow up是如果要提供一个web service, 给一个很大的dictionary,用户提交Unique Word Abbreviation的查询请求,返回Word Abbreviation是否在字典里出现过,问怎么设计。楼主一开始给了个很naive的解法,就是单纯地把字典分成几份,分给几台机器,每次请求都问每台机器,然后merge results。面试官表示不满意,问我有没有可能每次请求只要访问一台机器。我想了想,提出先sort字典,然后记住每台机器的range,每次来请求先看这个word在哪个range范围,就问哪台机器。面试官还是不满意,说sort太费劲,提示我用hashing。然后我就给出了把Abbreviation encode成数字,在模n的结果来选择机器。面试官说这个解法可以,就开始聊天了。
.1point3acres缃
* 第一轮. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    * 输入一个二维的char[][] board, 里面的元素只能是black,white和empty,
    * 输出个是boolean, 问是否有黑棋被白棋围死(只要有一个就行), 棋盘的四周默认是white.

* 第一轮
    * 国人小哥,第一题166. Fraction to Recurring Decimal,问了为什么一定会循环,要求证明,然后说复杂度。第二题给一个网格每个点一个数,求从左上到右下最大乘机,每次只能向右或者向下。这题跟加法唯一区别是要记录最小的负数是多少。然后问了一堆multithread的问题。. 鍥磋鎴戜滑@1point 3 acres
* 第二轮
    * merge interval
    * best time stock1
    * 第三题dp,化简完了是斐波那契额数列,然后码完followup问能更快么,我就给了她一个logn的
.鐣欏璁哄潧-涓浜-涓夊垎鍦
* 第一轮
    * longest Palindrome Substring.1point3acres缃
    *  直方图最大长方形
    * 分析correctness 和 时间空间复杂度。

* 第一轮.鐣欏璁哄潧-涓浜-涓夊垎鍦
    * 给定数组A,求数组B,满足b = A所有元素相乘除了a,不让使用乘法,问怎么办
* 第二轮. from: 1point3acres.com/bbs
    * 给定数组A,和k,求数组B,满足b=a*a[i+1]*...*a[i+k-1],同样不让使用除法。
    * 不知道这个是原题不,反正我也没见过。。。按部就班想,开始暴力算法,O(n*k),他问能不能优化,卡了,想了一阵,好像O(nlogk)?他也啥话没说,然后我慢慢,卡卡的写完了代码,后面还发现了bug,写的不很顺。
    * 具体想法就是,按照二进制进行优化,如果K=3=0b(11),那么创造两个数组A1=[A,B,C,D,E,F,G], A2 = [AB, BC, CD, DE, EF, FG],组合产生[A*BC, B*CD, C*DE, E*FG]

* 第一轮
    * (问答题)一个有1000个word的list,sorted好了, 现在给你一个word,查找出来这个word是否在这个list里面,问这是什么算法,要找到需要找多少次,如果是100000个的话需要找多少次
    * (问答题)heap和stack memory的区别
    * (问答题)如果有个file很大,内存装不满,需要remove文件里面的duplicates并且sort,问怎么做
    * (问答题)python里面try catch 怎么样才能够执行本来会被skip的execution
    * (代码题)leetcode 110, balanced binary tree.1point3acres缃
    * (代码题)leetcode 20 valid parentness 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. From 1point 3acres bbs
* 第一轮. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    * 题目是实现Tab功能,用户输入一个命令的前面部分,按下tab之后,提示用户所有可能的match。直接用trie实现,唯一难点是trie的遍历,要找出所有可能的match 鏉ユ簮涓浜.涓夊垎鍦拌鍧.


* 第一轮
    * 309 digits,相当于 2^1024.1point3acres缃
    * The fuel control mechanisms have three operations:. 鍥磋鎴戜滑@1point 3 acres
        * 1) Add one fuel pellet
        * 2) Remove one fuel pellet. more info on 1point3acres.com
        * 3) Divide the entire group of fuel pellets by 2 (due to the destructive energy released when a quantum antimatter pellet is cut in half, the safety controls will only allow this to happen if there is an even number of pellets)
    * Write a function called answer(n) which takes a positive integer as a string and returns the minimum number of operations needed to transform the number of pellets to 1. The fuel intake control panel can only display a number up to 309 digits long, so there won't ever be more pellets than you can express in that many digits
    * answer(4) returns 2: 4 -> 2 -> 1.鐣欏璁哄潧-涓浜-涓夊垎鍦
    * answer(15) returns 5: 15 -> 16 -> 8 -> 4 -> 2 -> 1

* 第一轮
    * 给一个fair coin,对任意正整数n,如何模拟出1/n的概率。follow up:简要证明,然后写这个程序。
. from: 1point3acres.com/bbs
* 第一轮
    * 给一个2D的grid, grid上面每一个element是一个character. 然后给一个input的单词,找出在这个2维grid里面所有可能match这个单词的path的集合
    * input: 2D grid, string word
    * output: 所有单词的path的集合
    * 问复杂度,我一开始有点蒙,跟他说我想一下,他说好的你慢慢想,也没有一直问我跟我说话. 假设二维数组一共有A个element,单词长度是B, 我一开始觉得是O(A^B), 后来又好好想了想,写出来应该是 O(4*3^(B-1)*A),他很惊讶,说我说的是对的,他要是自己想的话,会直接说O(4^B*A), 然后我笑了笑说仔细想想是有个小trick在里面的,不过我们讨论的很开心. Waral 鍗氬鏈夋洿澶氭枃绔,


* 第一轮
    * Presentation of my phd research
    * Basic probability, basic algorithm.鏈枃鍘熷垱鑷1point3acres璁哄潧
    * flip a string.. 实现很简单,然后讨论了好一会哪个方案好; 还考了一些C++基础. from: 1point3acres.com/bbs
* 第二轮
    * 比如问stack,queue的内部实现有什么区别,tuple和list有啥区别. From 1point 3acres bbs
    * 问的全是ML问题,linear regression,unsupervised learning什么的
    * 考的是flip a number, e.g. 2345 -> 5432。有一些edge case要考虑。我先在白板上给她比划分析,她说她要我写code,好像怕我用比划比划混过关一样。2分钟内写完code基本满意。她问我time complexity, 我说O(logn), 她仔细确认了我的答案,我说O(logn). 她说是O(k), k 是digit数字。我说没错,两个答案都对嘛。她说怎么可能是O(logn), 1, 34, 9345, 这难道都是logn?心中万千马飞过,再多解释了几句,最后居然没有达成共识。

* 第一轮
    * DP, 第一题类似paint fence,第二题是一个小升级
* 第二轮
    * 第一题简单binary search, 第二题简单DFS
* 第三轮
    * 实现多项式乘法,自定义data class
    * 主要用dictionary.
* 第四轮
    * BFS,leetcode上最新的几题之一。第一次碰到原题感觉像作弊,虽然第一次见该题的时候也很快想到做法,但是做过了还是可以更好的和reviewer讨论,而且白板上的code简直像抄的,基本没涂改. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    * 面之前和reviewer 去cafe 吃了点东西聊聊天,聊到我想做ML相关的。回来面了个open question, anomaly detection,讨论了可行方法,最后写了pseudo code.1point3acres缃
. From 1point 3acres bbs

* 第一轮
    *  merge 2 strings, make result smalest
* 第二轮
    * multi-threading to calculate Pi
* 第三轮 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    * 聊了一下research,因为背景和reviewer有一点类似。问题是8-queen verifier.-google 1point3acres
* 第四轮
    * 小manager:计算飞机上能看到最远的地方有多远; shuffle words in a string.
* 第五轮
    * 大manager:中国人,中英穿插着闲聊. 1point 3acres 璁哄潧

* 第一轮
    * warm up.非常简单,找出unsorted数组中的第一个duplicate number. HashSet 或Map 的解法就行。
* 第二轮
    * Validate 一个二维整数矩阵n * n 从top left to bottom right, 是否斜着的每一条line上数字都相等。比如下面的矩阵,就是一个valid矩阵. from: 1point3acres.com/bbs
1 2 3 4.鐣欏璁哄潧-涓浜-涓夊垎鍦
5 1 2 3
. from: 1point3acres.com/bbs 6 5 1 2
7 6 5 1
    * Follow up 1, 如果矩阵很大不能完整读到memory中,但是可以读至少一行怎么办?. 1point3acres.com/bbs
    * Follow up 2, 如果连一整行都读不到memory中怎么办,只能partially的读入一行的一部分怎么办?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
* 第三轮
    * 给一个blacklist 含有一些整数[0, N) 中,写一个function 返回 [0, N)的随机数,但是不要返回任何包含在blacklist的数,要求uniform distribution, 且尽可能减少call 系统Math.random() 的次数。


* 第一轮
    * 记电话号码
You are given a String numbercontaining the digits of a phone number (the number of digits, n, can be anypositive integer) . To help you memorize the number, you want to divide it intogroups of contiguous digits. Each group must contain exactly 2 or 3 digits.There are three kinds of groups:
• Excellent: A group that containsonly the same digits. For example, 000 or 77.
• Good: A group of 3 digits, 2 ofwhich are the same. For example, 030, 229 or 166.. 1point3acres.com/bbs
• Usual: A group in which all thedigits are distinct. For example, 123 or 90.
The quality of a group assignment isdefined as
2 × (number of excellent groups) +(number of good groups)
Divide the number into groups suchthat the quality is maximized. Design an
efficient algorithm to return thesolution that maximizes the quality
感觉上是用  DP,  但是想不出关系式。 从  j-1 到 j  要看前面好几个数字的关系

* 第一轮
    * 写2D点的k-means clustering。这个比较小众,大概是他们组工作有用也跟我research相关
* 第二轮
    * LeetCode number of islands II. Follow up: operation 是把1变成0,count the number of islands. 还是用union-find,找相邻1的root..鏈枃鍘熷垱鑷1point3acres璁哄潧
* 第三轮
    * 一些stream和排列组合的题
* 第四轮.鐣欏璁哄潧-涓浜-涓夊垎鍦
    * 版上经典的flower题,借用个链接吧http://www.1point3acres.com/bbs/thread-159651-1-1.html. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    * 这个答得非常不好,基本只写了brute force加一点优化。当时没怎么看面经,没想到其实也是DP,只是要update之前的cell.鐣欏璁哄潧-涓浜-涓夊垎鍦
* 第五轮. Waral 鍗氬鏈夋洿澶氭枃绔,
    * 国人mm,判断4个点能否组成正方形。. 1point 3acres 璁哄潧
总结:面完之后觉得下午面得很不好,很幸运还是拿到了offer。感觉不单是要把题做出来,做题时的交流也很影响interview的打分。一定要把自己的思路说出来,哪怕是在尝试阶段的思路,也可以展示思考的过程。如果实在来不及了,也要把brute force的code写出来,再优化,code都是要拍照的。
. 1point3acres.com/bbs

* 第一轮. Waral 鍗氬鏈夋洿澶氭枃绔,
* moving window average for double value。楼主用了类似LRU的double linkedlist 和 sum 解的, 但是感觉这个应该不是最好的办法。
    * follow up 1) 如果input data stream非常大的话会不会有error
    * linkedlist会有会有经常delete/create node,有没有什么改进。

* 第一轮
    * 实现java的garbage collector
    * 你需要不断的跟面试官交流以缩小问题范围。最后实质上是实现一个双链表结构,当你删除链表上一个node的时候,这个node要保存到另外一个deleted链表里面。如果你访问的node在deleted链表里面,你要把它捞回原来的链表。另外,面试官全程低气压,面试的时候让我感觉很不爽。但事后想想可能低气压也不是坏事,至少比笑面虎强。关键是不要让面试官的behavior影响到自己的发挥,保持冷静。

* 第一轮
    * Fill  screen with a string, 能fill多少次.1point3acres缃
    * 一个原题是在vertical和horizontal分别有序的matrix里找一个数,最优O(n)..鐣欏璁哄潧-涓浜-涓夊垎鍦
    * find first duplicate of an array
    * Find minimum number of edits to make a string palindrome (应该已经出现过很多次了吧)
    * when the passroad is totally wet with rain drops.


其实算法题就只是三种:数学归纳法,tree, graph。他就是出Word Ladder II的那个人啦。要是谁有兴趣,请回复


* 第一轮
    * 电话面试,问的是简单的图算法。感觉自己stuck了就问点tip,不慌就能写出来了。. 1point3acres.com/bbs
    * 另外一点体会是用google docs最好提前自己进去设置舒服的字体,页面orientation设置为横向。arial 或times new roman字体写代码丑爆了,换个喜欢的字体吧. more info on 1point3acres.com
    * 问: 给个directory,找出其下面所有的java文件。写代码
    * recursive function,很简单
    * 问: 如果肉眼看java代码,class之间的引用关系怎么找?
    * 看reference的type;new operator之后跟来的class name。 或者分析用reflection写的object construction代码。
    * 问:假设已经有了getClassDependency(A) api,作用是返回A class所依赖的其他类。现在有一个硕大的代码库,其中有些java class早已没人用。怎么找出所有此类class?
    * 图算法。把代码库看成图,每个class是节点,依赖关系是边。从有用的class开始遍历图,并标记已访问的节点。最终没有被标记的节点是不可达的,即为没用的class。类似JVM的垃圾回收。. visit 1point3acres.com for more.
    * 问:你说的算法是不是还有missing part?
    * 缺了找有用的class的api. 1point 3acres 璁哄潧
    * 问:那什么样的class是有用的? give some example?
    * 包含main method的,或者框架类的subclass,例如jsp的servlet。. visit 1point3acres.com for more.
    * 问:假设已经有了api获取这些有用的class,实现上述的算法。. Waral 鍗氬鏈夋洿澶氭枃绔,
    * 图遍历。只要注意标记过的节点不重复访问就好(可能有环)。其他没啥难点。. from: 1point3acres.com/bbs

. Waral 鍗氬鏈夋洿澶氭枃绔,
* 第一轮 电面
    * 首先给一个字典,比如:{apple, people,...}
    * 再给一个misspelling word,比如:adple,返回它的正确拼写,即 apple
    * 还知道一个限制条件,misspelling word只跟原单词有一个字母的区别。如果输入是addle,返回null。如果字数不同,也返回null
    * 还是比较简单的一个题,一开始以为是warm up。结果发现这种简单题也是能扯出很多东西的,主要在问题的理解和交流上。比如:是不是需要返回所有的correction,如何降低一些时间复杂度。写完代码,又问了下我怎么测试。一共用了30分钟在这道题上。剩下的15分钟就是聊我过去的项目和她现在的team。45分钟准时挂电话。


* 第一轮
. from: 1point3acres.com/bbs     * Leetcode的Buy Stock的1和2


* 第一轮
    * 第一题是random generator的题,比如给100*100的matrix,初始为全零,让随机把其中p(比如百分之六十)的值设为1
    * 第二题是tree level order traversal,按层输出,只用打印出来就可以了

* 第一轮. more info on 1point3acres.com
    * 第一个问题OOD看代码给输出,代码贴在DOC上了,楼主从来没复习过OOD,直接说不会,她说OK, let‘s move on
    * 第二题,一个数组长度为n+1: 1 2 3 4 .... m, m, m+1, m+2, ......n注意每个数都在[1 - n], 已排序,求出现了两次的那个数,也就是m。直接二分,非常水。。。
    * 第三题,输出锯齿状数组,比如输入为1,2,3,4,5, 输出1,3,2,5,4。也就是下标奇数的大于它的前一个和后一个元素。楼主直接先排序再输出,复杂度lgn。面试官说能不能更优
    * 我说那直接扫一遍,遇到不满足条件的两两交换,就是线性复杂度。然后问了我为什么这么做是对的。然后时间到了,问了两个问题结束。
* 第二轮:
鏉ユ簮涓浜.涓夊垎鍦拌鍧.     * 全程就一道题。missing range。[0-99] 也就是(3,5,99)输出字符串“0-2,4,6-98”。又非常的水,写完了问复杂度,然后找corner case跑。然后可能他发现我定义了全局变量,就问我这个函数调用两次是不是输出都一样。我立马反应过来,我说不一样,然后改成局部变量就一样了。然后他问题能不能优化成亚线性时间。卧槽这怎么优化,我想了半天我说sorry我想不出来。他说那你是不是觉得这个问题不能优化。我说对我觉得线性时间已经是最优了,最后问我如何在多核上实现并行,这还不简单,直接把输入拆分了并行做然后合并边界。然后时间到了,问问题,结束。

* 第一轮. 1point 3acres 璁哄潧
    * 两个数组A,B,找在B里不在A里的。第二题记不得了,汗
* 第二轮 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    * 第一题无限长输入,统计win内的平均值,并问时间长了double精度drift怎么办(重新算); 第二题LRU设计和psuedocode。
* 第三轮.鏈枃鍘熷垱鑷1point3acres璁哄潧
    * design, 本来要问LRU,发现问过了,就改问类似youtube的系统如何设计cache
* 第四轮
    * 第一题算x^y,第二题serialize/deserialize string
* 第五轮
    * 第一题若干人赛跑,已知是一个pair list, 譬如(1,4)表示1在4之前到达,求最后的排名,和scheduling一个意思吧;第二题是shuffle数组,问了些概率

. Waral 鍗氬鏈夋洿澶氭枃绔,

* 第一轮.鏈枃鍘熷垱鑷1point3acres璁哄潧
    * Longest Consecutive Sequence.. more info on 1point3acres.com
    * Binary Tree Longest Consecutive Sequence 的变种,Tree Longest Consecutive Sequence,可以允许多孩子节点。. from: 1point3acres.com/bbs

* 第一轮. more info on 1point3acres.com
    * 第一面: 给了一堆老鼠, 然后判断两只老鼠是不是有血缘的关系。类似Lowest Common Ancestor of a Binary Tree。但是有两个Parent。. more info on 1point3acres.com
    * 第二面:Game of Life, 问了些如何并行加速运算
    * 加面:
        * (1) Given two strings, check whether they are same ignoring the space
        * (2) Give N points (x, y), find the shortest loop: 用了最简单的生成所有排列,然后找出所有距离最小的。
        * (3) Give N sorted arrays, find the intersection of all arrays:每次取所有头部的最大值,然后检查是否在所有arrays中出现,如果是,就加到并集里。


* 第一轮
    * H-Index.鐣欏璁哄潧-涓浜-涓夊垎鍦
        * given an array, output a maximum k such that there are k elements larger than the value k
        * 面的时候,面试官和我说先来个简单的,结果就是这个题,我理解这个题就用了好一会儿,心想这怎么简单了。O(nlogn)的解法其实挺直接的,但是我觉得这个太简单了,G不可能,所有挣扎着想出了个O(n)的解法,就是用bucket sort的思路。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

* 第一轮
    * 给定一个产生[0,1]直接随机数的函数,以及一个三角形。要求调用这个函数随机产生一个在三角形内的点
    * 给一个string,比如aababbc,然后对字母重新排序,使得相邻的字母都不相同,比如abcabab。
* 第二轮
    * 给出一些string,每一个都是一个不包含"/"的路径,比如“usrbinpython”,“usrbinperl”,“usrbinjava”,然后要求输出最有可能的路径,比如这个例子就应该输出"usrbin/java", "usrbin/p/ython", "usrbin/p/erl". 还有一些follow-up,比如怎样避免这个p被劈开,当输入数据很大的时候,怎样选最有可能的路径之类的。.1point3acres缃
    * 这题应该是用trie吧?我反正也是挣扎了很久,写了满满一大黑板,有时候改了后面还要改前面,然后面试官就一直跟着我拍照。
* 第三轮 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    * 给一个linkedlist,然后给了一些node。要求输出有几个group,group的定义是连在一起的node就算一个group。比如linkedlist是这样的1->2->3->4->5->6->7->8->9, 然后给的弄得是[3,4,7,2,5], 那就输出2. 这题也是有很多优化和边角讨论. Waral 鍗氬鏈夋洿澶氭枃绔,

* 2D Segment Tree
    * 一个binary image的编码,问怎么样编码最好。答案是4-tree,就是每次把图片分成4块,如果每一块只有一种颜色,就用一个leaf表示,否则就继续四分下去
    * 题目就是,怎样把两棵这样的4-trees合并起来
    * 不相同为black
. 1point 3acres 璁哄潧
*
* tree level order traversal
    * Time O(n), space O(n)
    * Time O(nlogn), space O(logn)
    * 正常方法用queue写完后,要求用更少的space。我当时提出了用populating next right pointer的写法来写,这样时间是O(n), 空间是O(1).但是可能因为是电话,我解释的不好,面试官好像没听懂,他没接受这个解法。后来经过他的提示,要求我写的是时间O(nlogn),空间O(logn)的,就是给把tree多扫描几次,每次遇到需要打印的level就打印,不需要的就不打印。
. more info on 1point3acres.com
. 1point3acres.com/bbs
* range search
    * binary search leftmost, right most
    * leetcode range search

* 可能最小的排序,每个数最多移动k步
    * 给一个string="bcdaea",和一个int k=2,输出最小的排列,每个字母只能换到距离k以内的地方
    * Given an array of n elements, where each element is at most k away from its target position, devise an algorithm that sorts in O(n log k) time.
. From 1point 3acres bbs

回复 支持 3 反对 0

使用道具 举报

cnxdj20XY 发表于 4 天前 | 显示全部楼层
楼主同求Google面经。。。
回复 支持 反对

使用道具 举报

cser017 发表于 前天 02:23 | 显示全部楼层
后天就要面了,同求
回复 支持 反对

使用道具 举报

anchyhy 发表于 昨天 00:35 | 显示全部楼层
同求同求,最近在面
回复 支持 反对

使用道具 举报

siren01 发表于 昨天 00:38 | 显示全部楼层
同求,话说这样管用么?
回复 支持 反对

使用道具 举报

edyyy 发表于 昨天 00:50 | 显示全部楼层
楼主好运,我也铜球
回复 支持 反对

使用道具 举报

乌云典当记 发表于 昨天 00:53 | 显示全部楼层
和楼主跪成一排求……
回复 支持 反对

使用道具 举报

immutable 发表于 昨天 04:57 | 显示全部楼层
也和楼主跪成一排求……
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-9-20 03:10

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表