廉价电面

下午刚电面完，感觉没戏啊。东南亚小哥，上来自我介绍了。我还没有自我介绍就开始做题了。

1. 伞撕气，这题很久之前耍过，上来说了思路，开始写，然后优化用k size priority queue，然后问用什么heap，优化写到一半说不用写了，做下一题
2. 柳阿姨，变形！应该挂在这一轮了，task schedule如

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

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

是原题，其实不是。卧槽啊，good suggestion。那么多题根本耍不完，五年工作经验如弃草芥。

实在心累。耍那么多题，好徒劳啊。平时工作还挺忙，简直跳槽无望啊~

crazybadboy 发表于 2021-2-21 11:21
对我觉得应该就是这个逻辑，维持一个unordered_set，遇到相同的就加相应的cool down重新再来，
当时我感 ...

那这题实在是坑太大了，理解对了题意后就是如下简单解法了：

1. /*
   
2. AABBCC, cooldown=3
   
3. A***AB***BC***C
   
4. */
   
5. int schedule(string &tasks, int cooldown) {
   
6.     int time = 0;
   
7.     int n = tasks.size();
   
8. 
   
9.     for (int i = 0; i < n; i++) {
   
10.         if (i && tasks[i] == tasks[i-1])
    
11.             time += cooldown;
    
12.         time++;
    
13.     }   
    
14. 
    
15.     return time;
    
16. }
    

复制代码

hh6028206 发表于 2021-2-20 13:55
你应该是挂在第一题了， 用heap就挂了， Facebook明确说要quick select 的， 你heap不是最优解，所有面试官 ...

btw 这题 bucket select最优解，写起来几行搞定

1. class Solution:
   
2.     def topKFrequent(self, nums, k):
   
3.         bucket = [[] for _ in range(len(nums) + 1)]
   
4.         for num, freq in Counter(nums).items(): bucket[freq].append(num)
   
5.         return list(itertools.chain(*bucket))[-k:]

复制代码

Jennifer1986 发表于 2021-2-20 14:17
啊，fb有这个规定啊

纯扯淡。。。

我觉得如果上来直接问怎么写quick select，能过5%就不错了。。。

从我面试的经验来看，能知道用heap做topK的也就最多20%。我有个面试题最优解是heap的，但是如果别人能用binary search写出一个该题简化版的解法都会过（原版那个题的binary也能解 但是目前没有人能写出来）

想问下楼主，order mater还是没理解，原题也是cooldown之后才执行相同的

你应该是挂在第一题了， 用heap就挂了， Facebook明确说要quick select 的， 你heap不是最优解，所有面试官不用你写了，heap 谁都会！

hh6028206 发表于 2021-02-19 21:55:34
你应该是挂在第一题了， 用heap就挂了， Facebook明确说要quick select 的， 你heap不是最优解，所有面试官不用你写了，heap 谁都会！

你要说先统计frequency再quick_select那也没啥问题.我当时没提quick select。我本着先写一个solution出来，然后再优化的原则，时间不是很够啊

Jennifer1986 发表于 2021-02-19 21:10:35
想问下楼主，order mater还是没理解，原题也是cooldown之后才执行相同的

如果是A A B B C C的话，cool down是3
那就是A_ _ _ A_ _ _ B...以此类推

hh6028206 发表于 2021-2-20 13:55
你应该是挂在第一题了， 用heap就挂了， Facebook明确说要quick select 的， 你heap不是最优解，所有面试官 ...

啊，fb有这个规定啊

Jennifer1986 发表于 2021-02-19 22:17:37
啊，fb有这个规定啊

我记得输出也是根据frequency排好序的，用了quick sort最后还得再排一下序。我觉得quick select也是可以写的，quick select怕是没有时间写完

crazybadboy 发表于 2021-2-20 14:07
你要说先统计frequency再quick_select那也没啥问题.我当时没提quick select。我本着先写一个solution出来 ...

现在时间很紧，估计没时间装了，我也是在面FB，感觉FB的一个考点就是heap和quick select如何选，我面就是直接上quick select

Jennifer1986 发表于 2021-2-20 14:17
啊，fb有这个规定啊

挺朋友说的，也不一定，参数太小了，可能也有heap okay的

crazybadboy 发表于 2021-2-20 14:09
如果是A A B B C C的话，cool down是3
那就是A_ _ _ A_ _ _ B...以此类推

给楼主加米。 不要气馁！面试运气成分很大。我也有相同疑问，
如果是AABBCC, 间隔是3 原题顺序应该是 ABC_ABC_ABC
按楼主讲的 A_ _ _ A _ _ _ B _ _ _ B _ _ _ C_ _ _ C
没有任何技术含量啊，一路排下去就行了？