google onsite

MTV 四轮上周面的
1. leetcode 425 word square     当时理解错题目了。。。

2. find num of ways from one point to another point （n * n square）
    Ex     1 2 3 4
            5  6 7 8
            9 10 11 12

永远从

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

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

ome，chrome就到当前的app，其他的app 在background 进程， 同时后端有个监控器，会有一些log记录app的相关信息（比如启动app，app crash了）   理解下app最最基本的生命周期比较好

achilleszou 发表于 2016-11-4 12:35
我的思路差不多。

因为每次选出的pair 是相邻的。那么假设选出的pair 是 那么dp 转移方程为

我觉得是这样。

dp[m][i] = min( dp[m][i + 1],                                      ----> 不选 pair(i, i+1)
                         max(dp[m - 1][i + 2], diff(i, i+1))        ----> 选 pair(i, i+1)


补充内容 (2016-11-4 12:46):
打错，等式左边应该是 dp[m][i];

补充内容 (2016-11-4 12:47):
dp[m][  i  ]

blood8088 发表于 2016-11-4 12:45
我觉得是这样。

dp[m] = min( dp[m],                                      ----> 不选 pair(i, i+1) ...

你的dp 解法中 dp[m][i] 代表从 [i, ... n] 中 选m双筷子?

我的解法中 dp[m][i] 代表从[0, ... i] 中 选m双筷子。

如果我的理解没错的话，应该两个都行

blood8088 发表于 2016-11-4 11:32
说说自己第三题的思路：

先排序，然后用DP，DP里面有个贪心的地方，就是最后选出来的m个pair，每个pair ...

我的思路差不多。

因为每次选出的pair 是相邻的。那么假设选出的pair 是[i, i+1] 那么dp 转移方程为
dp[m][j][l] = min{max{dp[m1][j][i-1]}, dp[m2][i+1][l], diff(i, i+1)} (m1 + m2 = m-1)....
不过感觉复杂度不止o(mn)...
似乎可以继续优化。。。

求问第三题贪心的思路，多谢

为啥你有design ？ new grad 不是不考design 吗

第三题需要一个简单得dp，或者二分答案贪心吧

我也觉得第三题是DP
SORT之后类似house robber吧！

suiyuan2009 发表于 2016-11-2 02:26
第三题需要一个简单得dp，或者二分答案贪心吧

求思路

同问为啥楼主有 system design？

楼主也是上周五面的吗？

第三题 sort 一下， 建个m ＊ n的数组，然后每次看选不选这支筷子，选的话update下max，不选继续recursion
我试着把代码写一下，

吐槽下他们拿的我去年初的简历，那时才大二。。。

design有的，但是不难，当时最后一轮了，讨论了很多，写了大概的框架和里面几个function把其他的讲了讲就没时间了

意思是现在new grad也考system desgin了。。

Hgcas 发表于 2016-11-2 10:33
第三题 sort 一下， 建个m ＊ n的数组，然后每次看选不选这支筷子，选的话update下max，不选继续recursion
...

第三题 感觉应该可以优化。。