狗家onsite挂经

楼主女生，感恩节周周二onsite MTV。发挥的不太好。准备了很久的面试还是挂了，很伤心。记录一下题目供大家参考。

第一轮：白人。一个数组长度为n 元素值在0～n-1之间。给定起始位置idx和步数k，下一步的位置是当前位置对应的值。求k步后最后位置的idx。很直接的解法，优化循环情况。
第二题 给定一个sorted array 找出出现次数超过总数四分之一元素。如果是小数，取整。比如长度为五，那么超过一次就可以。讲了思路 类似于二分搜索，分成四份比较分界点左右元素。主要是讨论 没写出来代码，小哥也说这道题实现起来比较繁琐。
第二轮 印度人。类似于lc最大化假期的变种但描述不太一样，输入输出很繁琐，要一一沟通确定。顺利dp写出以后，问如果不是一周飞一次 而是一个月任选一周飞 如何最大化。保留原有逻辑，依然要记录每个周两两城市旅行的局部最优值，再进行一次按月份的dp。主要讨论没写代码。小哥也没有标准答案 临时想的。就是沟通聊思路

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

利用该函数生成a到b之间随机数字。有点蒙，经提示做出来，改了容易溢出的bug。当时真的筋疲力尽，而且对方很冷漠。拍完照之后，他想问如果概率不是百分之五十是一个一般的p，怎么解。没来得及做他就说时间到了。

走出大楼，我坐在campus路边的角落，对自己的表现很失望。脱了高跟鞋，把脸埋在膝盖里哭了一会儿。也就move on 吧。水平不够就是不够。只是浪费了这么好的机会，非常遗憾。

希望面经对大家有帮助。希望大家都能有好的发挥。加油！

dongsancu 发表于 2017-12-10 09:59
先BFS一遍找到没有父结点的结点。既然没有指向父结点的指针，不管用什么方法应该都需要先预处理一下的

这题题目感觉还是不清楚，是不是可以允许重新给所有点赋值，还是说必须尽量保留原来的节点的值只要满足大于父节点的条件即可

如果允许重新给所有点赋值的话，其实BFS扫一遍就行了，有没有多个父节点其实关系不大，可以看下面的例子
1.先找出所有入度为0的节点，把这些点的val都设成0，放进q
2.开始遍历q，把每个出队的子节点都重新赋值为cur val + 1 然后重新放进q
依次直至q为空

为什么多个父节点没关系呢，因为该节点会先被它高层次的父节点先更新成一个较小的值，但是随后会被它低层次的另外一个父节点重新覆盖成新的更大的值，也就是说一个点可能进出q多次

以上逻辑经过测试，不过还是得看是不是可以给所有节点重新赋值而定

hychin 发表于 2017-12-10 11:39
这题题目感觉还是不清楚，是不是可以允许重新给所有点赋值，还是说必须尽量保留原来的节点的值只要满足大 ...

这个应该没关系的，即使不能重新赋值也可以这样做，只要每次从队列中取结点时都比较该结点的值和它子结点的当前值就好，如果需要对子结点重新赋值（子结点当前值小于等于该结点值）就设为该结点值+1即可，最后结果就是没有入度的结点值不变，其余结点在最大无入度父结点值的基础上按层级逐级+1

dongsancu 发表于 2017-12-9 03:42
父子结点赋值的follow up可以用topological sort，没有父结点的值不变，加到队列，把队列中结点的子结点的 ...

我觉得拓扑排序可以！不过可能是我理解的不太对，能请问一下这个和层级遍历记录父节点的优势吗？层级遍历也是要查每一个父链接的edge，这个也是要查每一个edge，如果一个图每个节点都有巨多父节点，好像还是时间复杂度很大？

你怎么知道挂了啊。。

hychin 发表于 2017-12-2 08:53
你怎么知道挂了啊。。

因为感觉发挥的不好。看地里发挥好的同学最后都能挂，我这有两轮的followup都没回答好，肯定是必挂无疑TT

1/4那个题往中间平均切三个点，然后用二分法分别check这三个点的左右边界

概率那个题，求a 到 b就是求  0 到 a-b的随机数，你用那个0/1 生成二进制的数，这个数的长度能cover住a-b即可，然后落在a-b之外重新generate一只到能落进a-b的范围即可，你是这么做的吗

抱抱楼主
题目很难啊，几乎没有一个是原题。今年是因为Google Fiber组被裁了所以内部消耗大吧，题目都特别难而且坑也很少。。

cammilajiang 发表于 2017-12-2 08:58
因为感觉发挥的不好。看地里发挥好的同学最后都能挂，我这有两轮的followup都没回答好，肯定是必挂无疑TT

你的题的难度稍微高于平均水平的，所以不一定的，google主要还是看你思维快不快，聪不聪明，至于有没有coding出来其实不是很重要

hychin 发表于 2017-12-2 09:07
1/4那个题往中间平均切三个点，然后用二分法分别check这三个点的左右边界

概率那个题，求a 到 b就是求   ...

是的。第二题他提示了一次。所以我觉得会减分的。你好厉害呀，一眼就道出本质！

liutr90 发表于 2017-12-2 09:07
抱抱楼主
题目很难啊，几乎没有一个是原题。今年是因为Google Fiber组被裁了所以内部消耗大吧，题目都特别 ...

谢谢，感动～回抱一个！

读完全文没找到挂点的就我一个吗？

fentoyal 发表于 2017-12-2 09:17
读完全文没找到挂点的就我一个吗？

我也没找到挂点，楼主其实发挥的挺好的，而且还是个女生，bar自动降低一档，如果是美女，bar自动降低三档。

楼上的大神你都进狗家了怎么还在逛地里看面经？