【面经+timeline】狗家（东京） new grad

不久之前发过贴但是发错版面了，然后好像没什么人看……现在再来发一遍【。为team match积攒一点人品

3月海投

4月底oa：地里应该有类似的帖子，第一道是处理timestamp，具体忘了，应该是求两个timestamp之间的duration的变体。第二道是给一堆有dependency的task求最短finish time，topological sort可解

5月底店面：一个国人小哥，给一棵tree，兔子只有跳到某一leaf上才会停，问停到每个leaf上的概率。这个leetcode面经讨论版上有原题。
follow up：

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

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

6月底4轮technical。由于在美国所以hr把onsite split成了两天。

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

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

大概过了4天就收到回复schedule behavioral，接着一周就面了bq, BQ是个日本小哥，问的题style和amazon挺相似的，如果要准备照着amazon的bq准备就可以……

当天收到feedback说送hc，一周后说hc approve，进入team match阶段。

以及有没有同样在面东京狗的朋友求交流一下哇。回帖就行了><

以及求大米！！求大米！！！救救孩子

东京社招swe L4卡在了team match，已加面了tse的domain knowledge，准备入职

33847682 发表于 2020-7-16 06:15
请问lz知道东京那边的headcount情况嘛？在招l3嘛？

这个真的不太了解……而且new grad和l3应该有区别吧？

想问下第一轮最后那个follow-up "左上角走到右下角需要改变的高度和的最小值是多少" 这个和第一个follow-Up有什么区别吗？不都是从高度为h1的cell走到h2的cell需要消耗h2 - h1，这个消耗就可以看成需要改变的高度（改成同样高度就可以？），然后找一条路使得这些cost的和最小？

旧未来 发表于 2020-7-15 04:21
想问下第一轮最后那个follow-up "左上角走到右下角需要改变的高度和的最小值是多少" 这个和第一个follow-Up ...

区别是第二个follow up里一条路上每个cell都需要增高……
比如说
1->2->3->4 这条路径（数字代表height)
那么为了从1走到4，我每个cell都要变成4，那么改变的高度和就是 3 + 2 + 1 = 6
而之前只是 1 + 1 + 1 = 3

匿名者 发表于 2020-7-15 04:25
区别是第二个follow up里一条路上每个cell都需要增高……
比如说
1->2->3->4 这条路径（数字代表height ...

嗷嗷我原来的理解是1->2先把1变成2，然后走过去，然后2再变成3,..原来是要一次性都改变好，lz有什么好的方法做吗？binary search? 以及可以高改低，低改高吧? 还有改了高度之后，依然是可以高->低，但是反过来不可以吧？

旧未来 发表于 2020-7-15 04:35
嗷嗷我原来的理解是1->2先把1变成2，然后走过去，然后2再变成3,..原来是要一次性都改变好，lz有什么好的 ...

对，改了高度依然是可以高到低
我当时用dfs……类似于对于每一个cell来说，需要增高到的高度是max(自己的height,接下来cost最小的路上最高的height），然后每次dfs都会返回从该起点出发到终点cost最小的路径上的最大值……
当时时间不多了，小哥说因为不用担心一定要做出来，也没有写码，由于小哥说之前还没有问过别人这个follow up所以他好像也没有想到比较好的方法hhh

匿名者 发表于 2020-7-15 05:15
对，改了高度依然是可以高到低
我当时用dfs……类似于对于每一个cell来说，需要增高到的高度是max(自己 ...

"增高到的高度是max(自己的height,接下来cost最小的路上最高的height）"
一定是这样吗？举个例子
12
34
我看到的最好的修改cost是变成下面这样，cost = 3
32
33
1->3 而不是4， 还是说只能变高，不能变矮（4->3)？

旧未来 发表于 2020-7-15 05:42
"增高到的高度是max(自己的height,接下来cost最小的路上最高的height）"
一定是这样吗？举个例子
12

不能变矮诶，如果你这个例子的话应该是
42
44 cost最少

匿名者 发表于 2020-7-15 07:08
不能变矮诶，如果你这个例子的话应该是
42
44 cost最少

啊那我感觉应该就是用Binary Search + Dijkstra了
我的思路是：
首先最后可行的path上，每个cell所需升高到的height是由path上最大的那个height决定的，然后我们肯定希望这个最大的height越小越好，于是我们可以先找到这个最小的max height (利用Binary search, 在max(start, end) 到 max(grid) 之间搜索，给定一个猜的值，把图中所有大于这个值的cell都设为不可走，然后看看能不能走到右下）。
找到了这个height之后， 再把图上小于这个height的cell的值设置为height - original value （也就是这个cell的cost）,大于这个height的cell都设置为不可走，最后run一个Dijkstra就是最后要的结果了最后的复杂度在O（mnlog(mn) + mn) 应该可以接受

我也申请了同样的职位，五月底开始的VO，现在team match还没有结果。。。

zszszs1234 发表于 2020-7-15 10:35
我也申请了同样的职位，五月底开始的VO，现在team match还没有结果。。。

要不交流一下？