google onsite 面经

catyoyo 发表于 2019-9-15 00:31
感谢楼主分享。

想问几个问题（顺便帮看看自己的想法对不对）。

1. 不行 不能建list 必须在原来string上操作
2. 我也是dfs 但这样复杂度会是N^ 4，我问面试官，她建议build一个tree 把数字放在一个root 然后连着它的就是node，最后就是算这颗树里所有path的最大和；我记得leetcode里有道类似的 不过不记得是第几题了
5. 我讲的我phd帮朋友们debug经验……然后那个猪队友问题……我就说先把自己事情干好 然后去帮他 要是一直这样 和manager旁敲侧击……
onsite需要导师推荐信

hanscat2018 发表于 2019-9-15 13:24
求问一下第四题的解法， 没什么好思路。

面试官一上来就把问题给我拆解了：
1. given x and one row， how many ways to form the brick? (f(x) = f(x-2)+ f(x-3))
2. given x and one row， list out all the possible ways to form the brick
3. given two ways to form the row, check whether there is a breach
4. Brute force compare any two rows in the list.
他很nice 就让我一步步实现，但最后一步时间不够了，我就写了3个函数，然后最后一步和他说 就一个个比较 他也认可了

caoduo12 发表于 2019-9-16 11:28
面试官一上来就把问题给我拆解了：
1. given x and one row， how many ways to form the brick? (f(x)  ...

cool 字数字数字数

caoduo12 发表于 2019-9-16 11:26
1. 不行 不能建list 必须在原来string上操作
2. 我也是dfs 但这样复杂度会是N^ 4，我问面试官，她 ...

感谢楼主分享！

1. 那应该假设这个string是mutable，也就是List of chars。解法是先算出单词之间有几个空格，然后从左向右扫描，如果第i处空格不够就从右边找到空格（其位置记为j），填在第i处，并把原来[i:j]的字符串右移。复杂度N平方。不知道有没有优化方法。

2. 我不太理解图怎么变换成tree。如果原来的地图里有很多环怎么办？一个极端的例子是一个2x2的地图里全都是gold，[[3, 4], [5, 6]]。这种情况下，如果以3作为root，那么tree应该是什么样子的呢？

4. 感谢楼主的分析。感觉面试官很“帮忙”，一般面试官是不会给提示的，楼主有主动找hint吗还是面试官主动帮你分析了？

catyoyo 发表于 2019-9-16 12:16
感谢楼主分享！

1. 那应该假设这个string是mutable，也就是List of chars。解法是先算出单词之间有几 ...

1.对！我就是这么做的
2.对！我忘了说 面试官特意说 假设图里没有环；因为我一上来就想dfs 于是就没明白为啥要这个假设
4. 没有……他出完题，我问了问他什么 weak 啊 breach的定义，然后站在那里愣了几秒钟 他立刻就说 我们把这题拆开做，你先。。。确实很nice，这是他自己编的题，估计也是怕自己题出得太难？

caoduo12 发表于 2019-9-16 12:34
1.对！我就是这么做的
2.对！我忘了说 面试官特意说 假设图里没有环；因为我一上来就想dfs 于是就没明白 ...

2. 这么说就通了，看来此题就是换了马甲的刷题网的衣而斯。

楼主能详细讲一下第一题吗，我没有太看懂那个做法？谢谢！

Qingyang 发表于 2019-9-16 15:24
楼主能详细讲一下第一题吗，我没有太看懂那个做法？谢谢！

第一题我的思路是先把所有的单词都往左放，每个单词之间空一格，同时count单词个数和空格个数。接着可以计算出每个单词之间空几格以及最后会有多少多余的空格。然后从右往左用two pointer填单词。
（in place的算法应该也是允许使用constant space的吧）

多谢面经, 感觉除了第三题, 其它题目都好难, 代码不好写.

楼主我也是数学phd，刚刚面完电面还没回音，你面得好快啊。
能请问一下导师推荐信是什么时候要的吗？我完全没听hr说。