狗狗昂赛特+timeline

贡献一波昂赛特。
1. 一个integer array, 然后两个players,每次只能拿最左或最右的数字，问你如果先拿的话最多能拿到的数字和，假设对手绝对聪明。还有一道很简单的matrix的题目，实在记不起来了。
2. input是一个string，和integer k。 问你这个string包不包含所有长度为k的1，0组合起

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

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

第二天就拿到onsite了。
11/13 onsite
11/15 过hc
11/22 offer通知(中间应该完成了PA match和svp review)

祝大家offer多多！

hychin 发表于 2017-11-23 10:19
这题感觉可以维护一个大小为K的滑动窗口在S里面滑动，然后更新一个set，最后check那个set size是不是2^k? ...

恩恩，我最开始的那个是这样做的。其实就是你表达清楚逻辑就好了，因为如果k一直很小，input一直很长的话这样就不好。input一直很短，k一直很大的话这样就比较好。我感觉是这样，反正就是把自己想到的都说出来就好了。

victorlbb 发表于 2017-11-23 14:23
有点记不起来了。。。感觉好像是一道很经典的题目，你不如google一下。。。不好意思。

嗯，搜了下好像是这样？

f(start, end) = Math.max(nums[start] + Math.min(f(start + 2, end), f(start + 1, end - 1)),
                                    nums[end] + Math.min(f(start + 1, end - 1), f(start, end - 2)))

fledgling 发表于 2017-11-23 09:24
请问楼主第2轮除了2^k brute force还有什么其它办法。。。多谢。

补充内容 (2017-11-23 09:42):

我也是用的brute force。他也没叫我优化。followup好像没有标准答案，我那时候也是想到啥说啥。我就是从全部都是0的那个combination开始然后加前缀或者后缀。而且我assume了最短的长度就是2^k+k-1。面试官貌似默认了是对的，他说证明很复杂，所以也没叫我证明。

请问楼主第2轮除了2^k brute force还有什么其它办法。。。多谢。

补充内容 (2017-11-23 09:42):
follow up 可以用 greedy approximation 么。。。恭喜楼主大神拿到google offer~~

恭喜，求问第一题咋弄啊

penggeqiang 发表于 2017-11-23 09:44
恭喜，求问第一题咋弄啊

第一题就是用recursion,有点min/max tree的意思。

第三题怎么做的呢，感觉union find没法做，因为不支持删除，难道只能每次进来就做DFS？

hychin 发表于 2017-11-23 10:09
第三题怎么做的呢，感觉union find没法做，因为不支持删除，难道只能每次进来就做DFS？

对的，感觉应该是dfs+memorization.不能union find.

victorlbb 发表于 2017-11-23 10:07
我也是用的brute force。他也没叫我优化。followup好像没有标准答案，我那时候也是想到啥说啥。我就是从 ...

第二轮其实和以前谷歌一道经典的密码锁题一样的，用欧拉回路最短可以很短很短，因为可以重复使用比如k=4, 11001 既包含1101 也包含1001
http://www.1point3acres.com/bbs/thread-166111-1-1.html
http://xwk.iteye.com/blog/2129621

hychin 发表于 2017-11-23 10:14
第二轮其实和以前谷歌一道经典的密码锁题一样的，用欧拉回路最短可以很短很短，因为可以重复使用比如k=4, ...

要substring，为什么11001包含了1101啊？

victorlbb 发表于 2017-11-23 10:07
我也是用的brute force。他也没叫我优化。followup好像没有标准答案，我那时候也是想到啥说啥。我就是从 ...

这题感觉可以维护一个大小为K的滑动窗口在S里面滑动，然后更新一个set，最后check那个set size是不是2^k?