OpenAI如何evaluate面试过程？

匿名用户 发表于 2026-03-11 22:31:04
是malloc，为什么malloc是万恶的？

只是我自己个人不理解这道题的考点😐，要求O(logN)的时间复杂度，同时要求从最低位开始优先分配，并且没有padding的处理，与实际OS做内存管理的思维差异挺大。

匿名用户 发表于 2026-03-11 22:58:03
只是我自己个人不理解这道题的考点，要求O(logN)的时间复杂度，同时要求从最低位开始优先分配，并且没有padding的处理，与实际OS做内存管理的思维差异挺大

我们想法太一致了，不能有padding的问题是size map 会很大，这个log N也不见得有多快。

匿名用户 发表于 2026-03-11 22:58:03
只是我自己个人不理解这道题的考点，要求O(logN)的时间复杂度，同时要求从最低位开始优先分配，并且没有padding的处理，与实际OS做内存管理的思维差异挺大

我最后选择用最大堆来存freelist，原来想的是因为这样malloc可以O（1）直接找最大的freesize。但是写到最后发现标准库的heap不支持erase和重组堆

话说这道题正确的logN思路是什么啊？

log n要用set或者平衡树

log m就行，总操作次数，可以做到跟size N无关

匿名用户 发表于 2026-03-11 23:13:02
我最后选择用最大堆来存freelist，原来想的是因为这样malloc可以O（1）直接找最大的freesize。但是写到最后发现标准库的heap不支持erase

Pat pat，这道题不用非标准库自带的树状索引的话，确实挺难同时满足这几个需求的。我自己看到的大部分面经都选择线段树，但问题是metadata占据的空间比数据空间本身还多，同时在没padding的时候fragmentation 就很严重了，所以也是个非常反直觉的解法，作为candidate很难纯用逻辑思维把线段树给提出来，刷题感太重了😞
请问现场面试官有强调必须logN的时间复杂度么？还是也可以O(N)？

patpat, 感觉也不一定，这个有点看面试官

我第一次面 OAI 的时候写 resume iterator 做了一个优化之后一个 bug 到最后也没有 debug 出来，但是最后还是给了 strong 的 rating (虽然后来挂在 SD 上面了）

匿名用户 发表于 2026-03-12 08:26:41
Pat pat，这道题不用非标准库自带的树状索引的话，确实挺难同时满足这几个需求的。我自己看到的大部分面经都选择线段树，但问题是metadata占据的空间比数据

我怎么记得这道题没有最低位这个要求

coding现在考难的也没啥用了吧，都是ai编程了呀