一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1561|回复: 32
收起左侧

Google电面面的什么玩意儿

[复制链接] |试试Instant~ |关注本帖
2326 发表于 2015-9-28 07:26:22 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Failfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
印度小哥。上来聊了20分钟一个os project,25分钟写一道题:implement malloc...
给一个char类型的大数组:char MEM[MAX_SIZE],让implement两个函数:void *malloc(int s), void free(void *p)
我下面把MEM称为内存。其中,malloc接受长度参数s,表示user想要的内存长度,返回指向内存起始位置的指针。free接受指针参数,把这一块内存free掉(随你怎么free)。
要求不能调用系统的malloc(即不能有额外的空间)。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
上上周电面的,前天跪的。这题有人能在25分钟之内写出来?!

本帖被以下淘专辑推荐:

Wizmann 发表于 2015-9-28 11:03:34 | 显示全部楼层
ototsuyume 发表于 2015-9-28 10:23
你写线段树跟treap不用管回收,那是因为os和标准库给你回收了,现在人家的目的就是要让你实现一个memory  ...

所有方法都是有适应性的。没有背景就预设结论,都是耍流氓。

buddy mem allocation刚才我看了下,和线段树的搞法类似。并没有什么优越的地方。

云风自己都说了,他的allocator写了不到一小时。我觉得您一定能在25分钟内写完,登上人生巅峰。.1point3acres缃

恩,就是这样。
回复 支持 1 反对 0

使用道具 举报

readman 发表于 2015-9-28 07:58:37 | 显示全部楼层
默默的点个赞.....
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2015-9-28 08:03:18 | 显示全部楼层
这个真的是算法题吗?。。
回复 支持 反对

使用道具 举报

 楼主| 2326 发表于 2015-9-28 08:04:19 | 显示全部楼层
kelvinzhong 发表于 2015-9-28 08:03
这个真的是算法题吗?。。

. 1point 3acres 璁哄潧我也不知道啊,但我面的职位就是码农...
回复 支持 反对

使用道具 举报

cjlm007 发表于 2015-9-28 08:11:07 | 显示全部楼层
这个就是实现一个simple memory pool(不考虑内存碎片优化)。

malloc(size)大致是记录一个flag。这个flag可以是之前标记成free的区域(大小要>=size),也可以是内存池的最后面。
然后把要返回的内存地址作为key,flag作为value存到一个map里面。然后flag += size即可。(也需要一些其他的小操作)-google 1point3acres

free的话把某个块标记成free即可。.1point3acres缃

这个东西的麻烦的地方是处理碎片。如果他不让你解决内存碎片,应该是不难写的。我觉得面试官应该看到你简历上有os背景吧。
回复 支持 反对

使用道具 举报

 楼主| 2326 发表于 2015-9-28 08:13:02 | 显示全部楼层
cjlm007 发表于 2015-9-28 08:11. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这个就是实现一个simple memory pool(不考虑内存碎片优化)。

malloc(size)大致是记录一个flag。这个fl ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
我跟你的解法类似,但是,你用map吧?map调没调用系统的malloc?面试官就这么问我的
回复 支持 反对

使用道具 举报

cjlm007 发表于 2015-9-28 08:17:35 | 显示全部楼层
2326 发表于 2015-9-28 08:13
我跟你的解法类似,但是,你用map吧?map调没调用系统的malloc?面试官就这么问我的

那就只能用那个大数组的一部分来维护这个map啦,这货不会让你现场写一个map吧??
回复 支持 反对

使用道具 举报

cjlm007 发表于 2015-9-28 08:19:49 | 显示全部楼层
cjlm007 发表于 2015-9-28 08:17
那就只能用那个大数组的一部分来维护这个map啦,这货不会让你现场写一个map吧??

实在不行用一个链表,只是每次都要扫一下

补充内容 (2015-9-28 08:22):
好吧 我忘记了,链表也要开新空间,面试官wins
回复 支持 反对

使用道具 举报

Wizmann 发表于 2015-9-28 09:07:58 | 显示全部楼层
为什么要搞的这么复杂呢?
  1. #include <cstdio>
  2. #include <string>. Waral 鍗氬鏈夋洿澶氭枃绔,
  3. #include <iostream>

  4. using namespace std;

  5. #define print(x) cout << x << endl

  6. const int SIZE = 123456;

  7. char my_buffer[SIZE];
  8. int idx = 0;. From 1point 3acres bbs

  9. char* my_malloc(int s) {
  10.     char* res = my_buffer + idx;
  11.     idx += s;. 1point 3acres 璁哄潧
  12.     return res;. From 1point 3acres bbs
  13. }. visit 1point3acres.com for more.

  14. void free(void* p) {
  15.     // pass
  16. }
  17. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  18. int main() {
  19.     char* s = my_malloc(10); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  20.     snprintf(s, 10, "f*** me");
  21.     print(s);
  22.     free(s);
  23.     return 0;. more info on 1point3acres.com
  24. }
复制代码

补充内容 (2015-9-28 09:10):
如果要支持内存回收,方法有两个。

一是用多级队列,所有的内存块的大小是一定的。malloc的时候直接拿整块内存,肯定有浪费,不过也不用管。
二是搞个线段树,求在数组里最大连续空闲内存,然后直接填充进去。

补充内容 (2015-9-28 09:11):-google 1point3acres
这两种都不是电面能做出来的。我觉得烙印是黑了你一小道,这题比较恶心。也不知道他有没有提示你做法。
回复 支持 反对

使用道具 举报

ototsuyume 发表于 2015-9-28 09:16:44 | 显示全部楼层
光靠刷题不能解决面试,基础的os知识还是要有的吧?mmap是系统调用,malloc是c标准库函数,根本不是一个层次的东西,而实际上malloc的实现就是先通过mmap来分配一大块内存然后实习了一个memory pool,free的时候把要free的那块空间给放回去,一个简单的实现就是buddy memory pool。而楼上那种实现明显是不行的,那不是只管分配不管回收么?哪个系统用你这种实现程序系统程序都跑不了两个就挂了
回复 支持 反对

使用道具 举报

darkwowgamer 发表于 2015-9-28 09:22:32 | 显示全部楼层
patpat, 换我碰上这题也会想撞墙的
回复 支持 反对

使用道具 举报

 楼主| 2326 发表于 2015-9-28 09:24:16 | 显示全部楼层
cjlm007 发表于 2015-9-28 08:17
那就只能用那个大数组的一部分来维护这个map啦,这货不会让你现场写一个map吧??

面试快结束的时候他说别写了,指出了这个问题。用大数组存corner case有多少我都数不过来....
回复 支持 反对

使用道具 举报

romanchelsea 发表于 2015-9-28 09:46:09 | 显示全部楼层
弱弱问一句,跟hr约面试的时候,说自己喜欢的语言是 Java > C++ > C, 被问到lz这样的问题的概率应该很小吧?
回复 支持 反对

使用道具 举报

Wizmann 发表于 2015-9-28 09:47:48 | 显示全部楼层
ototsuyume 发表于 2015-9-28 09:16
光靠刷题不能解决面试,基础的os知识还是要有的吧?mmap是系统调用,malloc是c标准库函数,根本不是一个层 ...

也不知道你的“明显不行”的结论是怎么做出来的。

当年我们写线段树,写Treap这类数据结构时,就是用这种不回收的内存池的。要的就是效率。完事直接清空就好了。

话说,比时间效率,没有比这个更好的方法了吧。

当然,回收list也是一种很好的方法,学习了。谢谢:)
回复 支持 反对

使用道具 举报

ototsuyume 发表于 2015-9-28 10:23:15 | 显示全部楼层
Wizmann 发表于 2015-9-28 09:47
也不知道你的“明显不行”的结论是怎么做出来的。
. From 1point 3acres bbs
当年我们写线段树,写Treap这类数据结构时,就是用 ...

你写线段树跟treap不用管回收,那是因为os和标准库给你回收了,现在人家的目的就是要让你实现一个memory pool,你却只管分配不管回收,然后拿写线段树不用回收来举例子是不是不太合适?

云风以前写过一个buddy memory pool https://github.com/cloudwu/buddy,整个实现也就200行代码,而他这个代码是用在实际生产环境上面的,各种边界情况调试信息都比较完善。只是应对面试的话不用写得那么详细,在面试的45分钟内写出来虽然有点压力但问题应该不大。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

还有面试是考察你的一个思考的过程,不是说你一开始给了一个完美的算法就一定能过,也不是你给不出完美的算法就过不了。对这道题来说,你没听说过buddy memory allocation那没问题,你觉得treap、线段树rbtree效率高那没问题,你先假设有这么个api然后把分配的算法先写出来,然后跟面试官讨论再慢慢优化或者详细实现,面试官说不定觉得你想法新颖而且也可行也把你pass了。假如你是面试官,你给一道题目你肯定有一个判断对错的标准。这道题最简单的标准就是不管效率只要你的算法可行就pass,而你上面写的那个算法,你预分配了100kb的内存,然后我调用了拿了100kb然后free了后面又调用一次要分配100kb,这种情况下明明应该成功但你的算法却报oom了,从根本上就是不可用的,这跟你提出一个哪怕效率非常低但是能work的算法比起来谁给好?
回复 支持 反对

使用道具 举报

 楼主| 2326 发表于 2015-9-28 10:29:24 | 显示全部楼层
Wizmann 发表于 2015-9-28 09:47
也不知道你的“明显不行”的结论是怎么做出来的。

当年我们写线段树,写Treap这类数据结构时,就是用 ...

你好,我拿到这题首先写出来的就是这个版本,显然这是不够的。对于内存回收,多级队列我想到过但是觉得并不能解决问题,线段树显然也要用到extra space,当然也可以考虑用那个数组来存线段树,但corner case少不到哪儿去。
回复 支持 反对

使用道具 举报

 楼主| 2326 发表于 2015-9-28 10:30:23 | 显示全部楼层
romanchelsea 发表于 2015-9-28 09:46
弱弱问一句,跟hr约面试的时候,说自己喜欢的语言是 Java > C++ > C, 被问到lz这样的问题的概率应该很小吧?

凭什么C++,C就要面难题...
回复 支持 反对

使用道具 举报

Wizmann 发表于 2015-9-28 11:04:55 | 显示全部楼层
2326 发表于 2015-9-28 10:29
你好,我拿到这题首先写出来的就是这个版本,显然这是不够的。对于内存回收,多级队列我想到过但是觉得并 ...

可以用一个单链表来存,代码也不难。

但是性能不太好。

你有没有找面试官要hints啊?问他具体想要啥。
回复 支持 反对

使用道具 举报

ototsuyume 发表于 2015-9-28 11:20:22 | 显示全部楼层
Wizmann 发表于 2015-9-28 11:03
所有方法都是有适应性的。没有背景就预设结论,都是耍流氓。

buddy mem allocation刚才我看了下,和线 ...
. 鍥磋鎴戜滑@1point 3 acres
我觉得吧,要是面试官给出这样一道题目,你却预设只用分配不用free,给出的算法连malloc(100kb),free(),malloc(100kb)都过不了的话,那也不用面了

我前面就说过了,云风这个代码用在实际系统上面的,边界条件和性能这些都考虑了,面试的时候自然要投机取巧一下缩短代码。你觉得buddy memory allocation没什么优越的话那你可以把你的线段树搞法弄出来,然后跟linux的buddy算法对比一下,要是性能更高的话可以直接给linux提交patch-google 1point3acres

补充内容 (2015-9-28 11:33):
. Waral 鍗氬鏈夋洿澶氭枃绔,你前面回复里面说的多级队列也是linux中用到的一种算法,虽然有缺点但肯定也是一种可行解,但是这个问题本身就是一个开放问题不存在完美的解法。面试本来就不一定要你给完美解,不然也不会有那么多搞acm的大牛面g...
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 18:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表