Google OA挂经 SWE new grad early career

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

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

第一题可以用 greedy,    从最小的even number开始算，2， 4， 6， 8  ....,    也就是找到最小的N，N * (N + 1 ) < input_number,    可以线性查找N（slow) 或者binary search，input 如果数字很大， binary search 会很快。  答案是 N + 1.
第二题，暴力解是列举所有的substring, 记录所有字母的出现frequency,  (26)N^2,  一个优化是可以限制出现相同次数的unique character number (U),   for 1 <= U <= 26,  可以用经典的双指针sliding window O(N) 求解，迭代26次取最大值就是答案，N 很大时会有速度优势， O(26N)。      

小亩_5d1794a 发表于 2022-4-3 15:42
谢谢您共享信息！我看了frequency tuple的讨论，但是还没明白具体算法。请问您有兴趣再讲一下吗？非常感 ...

这里我们需要用一个长度为25 的array 来记录相对frequency， 假设我们拿3个字母举例，那么我们需要的array 就只有2个长度

比如在某个index i 这个array是[2 2] 说明 到i 这里为止， b 比a 多2个，c 比a 多两个，（比如 abbcc）我们记录一下这个tuple 已经对应的 index  i  ，存到map 里

下次到index j 的时候如果 出现的tuple 是[2 2] (比如abbccabc)， 这时候只需要查一下就能知道这个tuple 在index 为i的时候出现了， 所以 j - i 就是满足 出现频率一致的 substring
(因为 0到i 和0到j 的字母相对差一样，所以相互减掉这样所有字母和 第一个字母的差都变成0 了就满足我们的条件)

不知道有没有讲清楚;-;

匿名用户 发表于 2022-03-27 18:38:26
请问第一题的解法要怎么确认数组最后一个数字加上N - currentSum是一个even number呢？

因为所有element都是even的所以n是odd的话不存在结果可以直接return

最近google oa好像都是这两题，刚好朋友最近也碰到这俩
第一题 直接i 从2 开始loop 每个even number 加到cursum 上
直到cursum + i 大于 N 的时候 把 N - curSum 加到result list里最后一个数字上就可以，感觉是贪心算法？

第二题 暴力解能过，因为input string最长也就80

mron 发表于 2022-3-27 18:22
最近google oa好像都是这两题，刚好朋友最近也碰到这俩
第一题 直接i 从2 开始loop 每个even number 加到cu ...

请问第一题的解法要怎么确认数组最后一个数字加上N - currentSum是一个even number呢？

LZ是什么时候投的简历呢？

第二题感觉可以存一个hashmap记录各种出现的最早时间。比如自己有abcd的话你就只记录bcd，出现bcd的时候正常increment，出现a的时候就所有值-1。这样只要出现重复的key就代表中间substring里所有char出现次数一样多

这些题还在用,看这网站的还有三哥,不要给自己争光了

微信用户_6cfb26e 发表于 2022-03-27 18:59:38
因为所有element都是even的所以n是odd的话不存在结果可以直接return

对的，第一个corner case就先check N是不是 even，如果不是的话直接return 了

mron 发表于 2022-3-27 18:22
最近google oa好像都是这两题，刚好朋友最近也碰到这俩
第一题 直接i 从2 开始loop 每个even number 加到cu ...

不大对吧，如果N=8， 结果应该是 [2,6]？

patrickwhj 发表于 2022-4-1 11:31
不大对吧，如果N=8， 结果应该是 [2,6]？

2 + 4 cursum 是6， 再加6 大于8 所以吧 8 -（2 + 4） 加到最后一个数也就是4 上面， 得到 2,6
已经交过而且过了当时所有的test case的，应该是没问题