狗家新鲜五轮昂塞

出卖队友求大米~~ 队友脸家三年经验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)

复制代码

fernando 发表于 2020-11-20 01:07
第二题感觉就是 sliding window？ 找一个最大的全0的subarray 来 flip。
第一题 没太懂，能再说说么？

第二题我没看到是要找subarray，我还以为是找index，我之前的解法那就不对了

找一个最大的全0的subarray 来 flip

这个会错过最优解吧，比如a=1001000，最优应该是flip a[1:]而不是a[4:]
感觉可以这样解：
1. 左右指针初始在第一个0
2. 右指针向前滑动，记录当前窗口内0和1的个数，如果0的个数大于1的个数，继续滑动右指针，如果相等，重置左右指针到下一个0. 滑动右指针的同时要update目前为止最大的flip收益
3. 遍历完以后最大flip收益的指针位置即所要找的subarray

第一题按照lz的例子 [1, ‘abc’], [2, ‘54321’],[1, ‘abcdef’], [1, ‘re’],，先按size sort
a= [1, ‘re’], [1, ‘abc’], [2, ‘54321’],[1, ‘abcdef’]

然后计算size的prefix sum：
s=[2, 5, 10,16]

遍历以上list，发现在s[2]==max_size_over_all, 所以max_size_per_source可能是len(a[2])，如果下一个message的size大于a[2]的size，那max_size_per_source就是a[2]的size，如果相等，那目标是a[2]size的前一个size；
如果遍历时s_i没有恰好等于max_size_over_all而是大于，那目标就是a_i size的前一个size

第一题不用二分吧？在算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交流方面还可以的话那我个人觉得稳了

ispadea 发表于 2020-11-19 16:06
第一题不用二分吧？在算prefix sum的时候就可以判断当前size是不是会超过total size

第二题感觉不需要pref ...

第二题感觉就是 sliding window？ 找一个最大的全0的subarray 来 flip。
第一题 没太懂，能再说说么？

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

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

第一题lz水平有限，还是理解不到位，举的例子有错，重新写一下。
[1, ‘abc’], [2, ‘54321’],[1, ‘abcdef’], [1, ‘re’],...

max_size_over_all = 10

max_size_per_source = 8 (是source的总长度，不是单个message的长度，不能包括[1, ‘abcdef’] ，所以是8)

===以下lz的理解===

首先对每个source prefix sum。

然后二分查找，下界1，上界min(max_size_over_all, max(每个source的prefix sum))，根据判断条件调整上下界直到找到满足条件的largest max_size_per_source

判断条件是在prefix sum array对每个source找到小于max_size_per_source的长度，求和，与max_size_over_all做比较。（这里又是一个二分查找）

时间复杂度不知道对不对。二分查找是logM x klogN，M是搜查空间，k个source，每个source个数N。构建prefix sum要kN。取较大值。

ispadea 发表于 2020-11-20 02:15
第二题我没看到是要找subarray，我还以为是找index，我之前的解法那就不对了

这个会错过最优解吧，比 ...

你好，我对第一题的理解Messages will be stored in chronical order不能sort的。我自己也理解错了，可能造成误解了抱歉抱歉！！具体更新在回复里了。