Google OA挂经 SWE new grad early career

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

我基本上两道题也是这么写的，第一题可以不用loop from 2 to i，instead可以用binary search加速。
第二题可以暴力解法因为没有efficiency的要求，加速的话大概可以用hashmap和array two pointer

mron 发表于 2022-4-2 23:01
我朋友就是暴力解写的，已经约好vo了。 我觉得题目上说了focus on correctness instead of performance的 ...

请问暴力解是怎么做的呢

promiscuous6 发表于 2022-04-10 00:46:44
但题目里写的unique element 如果n是26 那这个算法output应该是【2，4，6，8，6】？这样是不是有矛盾啊

应该是2 4 6 14才对

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

题目中要求了都是正数吗？0是偶数吗？或者有负数的话，结果会很大

微信用户_6cfb26e 发表于 2022-3-27 19:05
第二题感觉可以存一个hashmap记录各种出现的最早时间。比如自己有abcd的话你就只记录bcd，出现bcd的时候正 ...

但是这种情况下应该怎么设计 key 呢? 比如我们扫描 abcd 这个 string, 刚扫到 a 的时候 key 应该是 (-1, -1, -1) 吗? 好像没法判断当前的 substring 是 valid 的哇

第一题可以用 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)。      

minghaocui 发表于 2022-4-27 11:00
第一题可以用 greedy,    从最小的even number开始算，2， 4， 6， 8  ....,    也就是找到最小的N，N * (N ...

关于第二题优化，感觉限制unique char也很难deliverO(26N), 比如 aabaac，限制U=2， 这是双指针的rule很难去限定让 i = 1, j = 2; 所以感觉还是brute-force O(26N^2)复杂度；请指教！谢谢
0 1 2 3 4 5
a a b a a c
   i
      j

Hey, can someone post the questions again? I don't have permission to view the questions. Thanks!