Google NG VO 大概率挂经

求问第三轮和第四轮题目的具体描述，第三轮那个同学描述的有点抽象，楼主可以给个例子吗？
第四轮follow up的例子调三分钟为什么是第一个按钮两次第二个按钮一次呀？第一个和第二个按钮是1分钟和5分钟没错吧,意思是这个follow up是时钟还可以往前调了么？而且说add button的数量不定是指什么意思呢？原始问题求最小操作数add button的数量不相当于也没定吗？感谢！

努力奋斗的小乔 发表于 2022-5-27 14:55
求问第三轮和第四轮题目的具体描述，第三轮那个同学描述的有点抽象，楼主可以给个例子吗？
第四轮follow u ...

第三轮的题目就是相当于给你一个log history， 每一条history 记录 三个东西: LogID, timestamp, Start/End. 记录是按照timestamp排序的。差不多是这个样子:
LogID    timestamp   Start/End1          1                   Start
2           2                 Start
1           3                 End
2           7                 End
3         8                  Start
3         9                 End
这里假如timeout 是 4 的话 log 2就timeout了，返回true。
第四轮 那个follow up 的意思是现在button 数量不固定了，不是像原题那样写死的。他给的例子第一个button 是advance 23小时59分， 第二个button是advance 2分钟，要求往后调3分钟。最优解肯定是往后调两分钟两次之后再往后调23小时59分 一次（等于往前调一分钟）。还有一个例子就是[0, 3] [0, 4] 要往后调6分钟，这个的最优解就是按第一个button两次

匿名者 发表于 2022-5-26 03:38
请问一下第二题有没有例子呀，也想问一下DFS的思路，感谢~

第二题其实我的做法会是把点根据x->y 和 y->x 存hashmap, 然后o(n^2) 两两遍历，两个点如果x不相同并且y也不相同的话(这两个点一定是在对角线上) 就说明可能形成一个正方形 再去hash map里看看其他两个点在不在

www熙 发表于 2022-5-25 18:52
最后一题有点像蠡口Coin Change那道题 用dp做

对 我也想到coin change了 不过有个问题是 coin change amount是固定的 这个玩意你可以不停无限往前转 所以具体不知道该咋搞

最后一题想了一下 可以用BFS 最多只有24*60= 1440的node需要visit
栗子的话23:59 = 1439， 00:02 = 2
从0开始
step = 0: { 0 }
step = 1: { 1439, 2 }
step = 2: { 1438, 1, 4}
step = 3: { 1437, 3, 6}
-------------------------
所以返回3

第四轮这个应该就是背包吧（完全背包），背包size为时间的差

匿名者 发表于 2022-5-27 21:27
对 我也想到coin change了 不过有个问题是 coin change amount是固定的 这个玩意你可以不停无限往前转 所 ...

这个要wrap around，但是increment是已知的有规律的，所以可以穷举出所有可能的步数（比如两个45min相当于-30这样）

求个timeline~