狗家新鲜五轮昂塞

出卖队友求大米~~ 队友脸家三年经验E5，recruiter年中reach out，拖延了好几次最终决定面了算了，于是今日裸考，假都没请面完接着开会= =。据称面的很一般，也不知道面的几，发出来求大米~~
以下由队友复盘。

第一轮：

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

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

第二轮：

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

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

第三轮：

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

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

第四轮 system design：

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

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

第五轮 bq 附赠一道system design （面试官搞错了。。。）：

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

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

求大米~~~


补充内容 (2020-11-20 02:03):
求大米求大米！！想要188大米看面经😭😭😭

补充内容 (2020-11-20 03:17):
第一题有误解，更新在回复，有错误麻烦指出来，谢谢！！

补充内容 (2020-11-27 03:26):
hr给了4的offer，可能因为确实面的一般+只有三年经验。家属直接据了冷冻期一年。

我觉得第二题可以当成 刷题网的雾散来做
遍历数组， 遇见0， sum就+1， 遇见1 sum就减1， 有个数max时刻track sum的最大值。 如果sum<0, then set sum = 0.

做了下第二题，欢迎指正。求米

1. # coding: utf-8
   
2. 
   
3. """
   
4. Given an array containing only 0 and 1s, find the best subarray to perform a single flip operation.
   
5. The goal is that: after the flip, number of 1s should&nbsp;&nbsp;be the maximum.
   
6. Flip operation means that you will convert all 0 to 1, and all 1 to 0 in that array.
   
7. You can skip flipping if you think it is not worth doing the flip.
   
8. Return the maximum number of 1s after you do the flip.
   
9. 
   
10. 队友还是用的prefix sum再找区间最大的差值，面试官说可以O(1)空间，作为homework。
    
11. 
    
12. Follow-up: what if it is a 2D array?</div>
    
13. """
    
14. 
    
15. 
    
16. class Solution:
    
17.     def max_flip(self, bits):
    
18.         dp = [0] * len(bits)
    
19.         for i, b in enumerate(bits):
    
20.             val = 1 if b == '1' else -1
    
21.             prev = dp[i - 1] if i > 0 else 0
    
22.             dp[i] = min(prev + val, val)
    
23.         orig_one_count = sum(1 for b in bits if b == '1')
    
24.         res = orig_one_count + max(-min(dp), 0)
    
25.         return res
    
26. 
    
27.     def max_flip_follow_up(self, bits):
    
28.         # O(1) space. rolling array. dp[i] only relies on the prev one.
    
29.         dp = [0] * 2
    
30.         min_dp = 0
    
31.         for i, b in enumerate(bits):
    
32.             val = 1 if b == '1' else -1
    
33.             prev = dp[(i - 1) % 2] if i > 0 else 0
    
34.             dp[i % 2] = min(prev + val, val)
    
35.             min_dp = min(min_dp, dp[i % 2])
    
36.         orig_one_count = sum(1 for b in bits if b == '1')
    
37.         res = orig_one_count + max(-min_dp, 0)
    
38.         return res
    
39.    
    
40. 
    
41. import unittest
    
42. class Tests(unittest.TestCase):
    
43.     def test1(self):
    
44.         bits = '0001000'
    
45.         sol = Solution()
    
46.         actual = sol.max_flip(bits)
    
47.         self.assertEqual(actual, 6)
    
48.         actual2 = sol.max_flip_follow_up(bits)
    
49.         self.assertEqual(actual2, 6)
    
50. 
    
51.     def test2(self):
    
52.         bits = '1001001'
    
53.         sol = Solution()
    
54.         actual = sol.max_flip(bits)
    
55.         self.assertEqual(actual, 6)
    
56.         actual2 = sol.max_flip_follow_up(bits)
    
57.         self.assertEqual(actual2, 6)
    
58. 
    
59.     def test3(self):
    
60.         bits = '1111111'
    
61.         sol = Solution()
    
62.         actual = sol.max_flip(bits)
    
63.         self.assertEqual(actual, 7)
    
64.         actual2 = sol.max_flip_follow_up(bits)
    
65.         self.assertEqual(actual2, 7)
    
66. 
    
67.     def test4(self):
    
68.         bits = '1010101'
    
69.         sol = Solution()
    
70.         actual = sol.max_flip(bits)
    
71.         self.assertEqual(actual, 5)
    
72.         actual2 = sol.max_flip_follow_up(bits)
    
73.         self.assertEqual(actual2, 5)
    
74. 
    
75. unittest.main(verbosity=2)

复制代码

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

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

第一题不用二分吧？在算prefix sum的时候就可以判断当前size是不是会超过total size

第二题感觉不需要prefix sum，计算0的总数，遍历list，记录当前遇到的0和1的数目，然后计算此时flip的总和，和目前的最大值作比较

第三题同求最优解，naive的遍历所有可能的pair要 n^2，再加上字符串比对，整体要kn^2

第三题应该是LC 318。。。确实必须要有O(n^2)，唯一的优化可能就是用bit mask来辅助

AlbertZhong 发表于 2020-11-19 01:06:33
第三题应该是LC 318。。。确实必须要有O(n^2)，唯一的优化可能就是用bit mask来辅助

跑去看了 是的🥺😂谢谢 我可以睡个好觉了

不知道lz交流的时候怎么样？我个人的经历是面试的时候给出了一个暴力解但是也给过了，我觉得是交流方面比较好所以给过了，如果lz交流方面还可以的话那我个人觉得稳了

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

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

KisekiABC 发表于 2020-11-19 17:27
不知道lz交流的时候怎么样？我个人的经历是面试的时候给出了一个暴力解但是也给过了，我觉得是交流方面比较 ...

谢谢 队友交流还可以 但毕竟是裸考不敢报什么希望😂 昨天我们讨论觉得只要反馈结果不是冷冻期的极大值就阔以了

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

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

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

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