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

FB两道Onsite题

🔗
say543 2018-8-3 14:24:44 | 只看该作者
全局:
cexq 发表于 2018-7-29 22:56
第一题:??
vector allocatedMemory;
int nestedlevel;

我有同样的想法 基本上就是stack吧?
回复

使用道具 举报

🔗
cexq 2018-8-4 03:20:34 | 只看该作者
全局:
say543 发表于 2018-8-3 14:24
我有同样的想法 基本上就是stack吧?

class Node
{
  List<char *> memory;
}

stack<Node>


对。就是stack想法
回复

使用道具 举报

全局:
设计直播平台 楼主怎么回答的?
回复

使用道具 举报

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

感谢分享 为啥这个是nlogn?
回复

使用道具 举报

🔗
chenyangtc 2018-8-8 04:40:05 | 只看该作者
全局:
楼主面试的好难。。大神。。
回复

使用道具 举报

🔗
 楼主| 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 给你点个赞!

查看全部评分

回复

使用道具 举报

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

使用道具 举报

🔗
 楼主| magicsets 2018-8-9 14:21:50 | 只看该作者
全局:
liuyuanpotato 发表于 2018-8-8 02:08
设计直播平台 楼主怎么回答的?

其实这个题目很大,我也是随便说到哪里算哪里.. 可以看看知乎这个:https://www.zhihu.com/question/42162310
回复

使用道具 举报

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

本版积分规则

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