📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 17
跳转到指定楼层
上一主题 下一主题
收起左侧

FB两道Onsite题

全局:

2018(4-6月) 码农类General 博士 全职@meta - 猎头 - Onsite  | | Pass | 应届毕业生

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
1. 给定内存分配释放的两个接口:

char* alloc();  // 分配4096 bytes内存
void free(char*);  // 释放给定内存

要求使用上面两个接口实现下面这个半自动GC类:
class MemoryManager {
public:
  // 初始化一个新的frame
  void begin();

  // 结束当前frame
  void end();

  // 分配所要求长度的内存,长度不会超过4096
  char* alloc(size_t len);
};

要求这个memory manager可以支持嵌套的begin()/end()调用,然后end()的时候释放所有当前frame内所分配的内存,不需要优化内存碎片。

比如说考虑下面一段代码:
MemoryManager mm;

void g() {
  mm.begin();
  char *A = mm.alloc(1000);
  mm.end();
}

void f() {
  mm.begin();
  char *B = mm.alloc(3000);
  g();
  char *C = mm.alloc(2000);
  mm.end();
}

f();

那么应当满足下面的执行语义:
(1) 进入f(),开始第一层frame,分配3000 bytes给B
(2) 调用g(),开始第二层frame,分配1000 bytes给A
(3) 结束第二层frame,回收A所使用的内存,退出g()返回f()
(4) 分配2000 bytes给C
(5) 结束第一层frame,回收B和C所使用的内存,退出f()

2. LC 319,原题是每隔1,2,3,..个开关,变体是每隔1,3,5...个开关


Onsite的其它题目很常见,这里也贴一下..
您好!
本帖隐藏的内容需要积分高于 101 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 101 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies



评分

参与人数 5大米 +17 收起 理由
idatascience + 3 给你点个赞!
moritor123 + 3 给你点个赞!
xiemenger + 4 给你点个赞!
Big_Biang + 5 很有用的信息!
helloworld00 + 2 很有用的信息!

查看全部评分


上一篇:回报地里, 一发脸书pass经和timeline
下一篇:新鲜出炉亚麻家的面经

本帖被以下淘专辑推荐:

推荐
 楼主| magicsets 2018-7-29 13:55:36 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

推荐
 楼主| magicsets 2018-8-9 14:09:37 | 只看该作者
全局:
Big_Biang 发表于 2018-7-29 16:04
感谢分享~楼主可不可以简单说一说第一题的思路啊,看着有点晕。。

第一题总体思路是用一个stack,不过要使用给定的内存分配/释放接口,也就是要管理内存碎片(但是不用优化),我写了一份参考代码:

  1. #include <cstddef>
  2. #include <cstdlib>
  3. #include <iostream>
  4. #include <stack>
  5. #include <vector>

  6. // 给定的内存分配/释放接口,里面用std::malloc/std::free简单实现了一下用来运行测试
  7. namespace api {

  8. char* alloc() {
  9.   return static_cast<char*>(std::malloc(4096));
  10. }

  11. void free(char *data) {
  12.   std::free(data);
  13. }

  14. }  // namespace api

  15. class MemoryManager {
  16. public:
  17.   void begin() {
  18.     if (frames_.empty()) {
  19.       const Cursor begin{0, 0};
  20.       frames_.emplace(Frame{begin, begin});
  21.       blocks_.emplace_back(api::alloc());
  22.     } else {
  23.       const Cursor &begin = frames_.top().current;
  24.       frames_.emplace(Frame{begin, begin});
  25.     }
  26.   }

  27.   void end() {
  28.     const Frame &frame = frames_.top();
  29.     for (std::size_t block_id = frame.current.block_id;
  30.          block_id > frame.begin.block_id ; --block_id) {
  31.       api::free(blocks_[block_id]);
  32.       blocks_.pop_back();
  33.     }
  34.     frames_.pop();
  35.     if (frames_.empty() && !blocks_.empty()) {
  36.       api::free(blocks_.front());
  37.       blocks_.pop_back();
  38.     }
  39.   }

  40.   char* alloc(const std::size_t len) {
  41.     Cursor cursor = frames_.top().current;
  42.     if (cursor.byte_offset + len > 4096) {
  43.       cursor = {blocks_.size(), 0};
  44.       blocks_.emplace_back(api::alloc());
  45.     }
  46.     char *data = blocks_.back() + cursor.byte_offset;
  47.     cursor.byte_offset += len;
  48.     frames_.top().current = cursor;
  49.     return data;
  50.   }

  51. private:
  52.   struct Cursor {
  53.     std::size_t block_id;
  54.     std::size_t byte_offset;
  55.   };

  56.   struct Frame {
  57.     Cursor begin;
  58.     Cursor current;
  59.   };

  60.   // 保证正确性的invariant:
  61.   //   (frames_.empty() && blocks_.empty()) ||
  62.   //   (frames_.top().current.block_id + 1 == blocks_.size())
  63.   std::stack<Frame> frames_;
  64.   std::vector<char*> blocks_;
  65. };
复制代码

评分

参与人数 1大米 +5 收起 理由
Big_Biang + 5 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
helloworld00 2018-7-28 06:14:41 | 只看该作者
全局:
lz 面都的很难啊。。。
回复

使用道具 举报

🔗
houqingniao 2018-7-29 04:30:49 | 只看该作者
全局:
请问319 变化一下,还有trick吗?还是就模拟过程?
回复

使用道具 举报

🔗
lattelatte 2018-7-29 05:46:35 | 只看该作者
全局:
都好难啊。请问楼主背景?
回复

使用道具 举报

🔗
 楼主| magicsets 2018-7-29 13:59:06 | 只看该作者
全局:
lattelatte 发表于 2018-7-29 05:46
都好难啊。请问楼主背景?

主要是DB背景,面我的好像都是data infra的人
回复

使用道具 举报

🔗
Big_Biang 2018-7-29 16:04:12 | 只看该作者
全局:
感谢分享~楼主可不可以简单说一说第一题的思路啊,看着有点晕。。
回复

使用道具 举报

🔗
cexq 2018-7-29 22:56:25 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
cexq 2018-7-29 23:55:39 | 只看该作者
全局:
设计直播平台

能不能说详细点?类似于instigram?
回复

使用道具 举报

🔗
say543 2018-8-2 14:53:40 | 只看该作者
全局:
magicsets 发表于 2018-7-29 13:55
我当时剩的时间不多了,分析了两分钟面试官直接让写一个最简单解法.. 所以面试的时候使用的是模拟过程方 ...

多谢分享 这个2^y 是怎么想到的 能多说点吗?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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