回复: 24
跳转到指定楼层
上一主题 下一主题
收起左侧

空气床电面

全局:

2017(10-12月) 码农类General 博士 全职@airbnb - 网上海投 - 技术电面  | | Fail | 在职跳槽

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

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

x
网上自己投的简历,大约2周后recruiter联系,简单电话聊了一下安排技术电面

空气床的电面是不聊天直接开始做题的,题目跟这个帖子里第一个是一样的



给一个N,求出 1 <= n <= N 所有变换步数的最大值。用的是 recursion + memorization 的办法,我是C++选手,用一个hash表来记录中间结果 unordered_map<
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
strong>补充内容 (2017-12-12 11:20):
整个过程互动性较差,面试官好像不太熟悉c++,基本上就是能过test case才行,否则都没戏,说实话这样的方式还不如直接做个oa更好。

上一篇:BB 面经 OCI
下一篇:简街OA
推荐
 楼主| kqxqx 2017-12-21 23:54:21 | 只看该作者
全局:
magicsets 发表于 2017-12-21 14:33
为了加速memoization表的存取可以用一个vector作为primary memo,一个unordered_map作为secondary memo

...

太感谢了!看来这个题目的坑主要就是N=1,000,000的时候中间需要计算的n会超过32位int的表示范围,我回去改了一下我的code,把int换成long型,其余的不变,recursion + memorization就能跑出正确的结果了。哎,怎么当时就没有想到是这个问题呢 anyway,当时的code确实没有跑出正确结果,只好move on了

补充内容 (2017-12-22 00:50):
N=100,000,则中间需要计算的最大n=1570824736,没超出int范围;
N=1,000,000,则最大n=56991483520,远超int范围。看来这个1,000,000的测试数据是精心挑选的,就是个坑。
回复

使用道具 举报

推荐
magicsets 2017-12-21 14:33:22 | 只看该作者
全局:
为了加速memoization表的存取可以用一个vector作为primary memo,一个unordered_map作为secondary memo

此外这题目有个坑就是对于N = 1000000,中间结果是会超过int表示范围的,比如n = 704511时,中间结果会到达 56991483520

写了一份参考代码,带优化编译的话大概100~200毫秒可以跑完:

  1. #include <algorithm>
  2. #include <cstdint>
  3. #include <iostream>
  4. #include <stack>
  5. #include <unordered_map>
  6. #include <vector>

  7. class Solution {
  8. public:
  9.   std::int64_t exec(const std::int64_t N) {
  10.     // 调整这个系数会影响性能
  11.     // 系数越大,耗费空间越多,但速度也越快
  12.     // 8应该是一个比较好的选择...
  13.     constexpr std::int64_t kFactor = 8;

  14.     bound_ = N * kFactor;
  15.     primary_memo_ = std::vector<std::int64_t>(bound_, -1);
  16.     secondary_memo_ = std::unordered_map<std::int64_t, std::int64_t>();

  17.     std::vector<std::int64_t> stk;
  18.     stk.reserve(N);

  19.     setMemo(1, 0);
  20.     for (std::int64_t i = 2; i < N; ++i) {
  21.       // pre-check以加速运算
  22.       if (getMemo(i) >= 0) {
  23.         continue;
  24.       }

  25.       std::int64_t curr = i;
  26.       std::int64_t ret = -1;
  27.       stk.push_back(curr);

  28.       // 模拟的递归调用
  29.       while (ret < 0) {
  30.         const std::int64_t next = (curr & 0x1) ? (curr * 3 + 1) : (curr >> 1);
  31.         if ((ret = getMemo(next)) < 0) {
  32.           stk.push_back(next);
  33.           curr = next;
  34.         }
  35.       }

  36.       // 模拟的递归返回
  37.       while (!stk.empty()) {
  38.         setMemo(stk.back(), ++ret);
  39.         stk.pop_back();
  40.       }
  41.     }

  42.     return *std::max_element(primary_memo_.begin() + 1,
  43.                              primary_memo_.begin() + N);
  44.   }

  45. private:
  46.   inline std::int64_t getMemo(const std::int64_t key) const {
  47.     if (key < bound_) {
  48.       return primary_memo_[key];
  49.     } else {
  50.       auto it = secondary_memo_.find(key);
  51.       return it == secondary_memo_.end() ? -1 : it->second;
  52.     }
  53.   }

  54.   inline void setMemo(const std::int64_t key, const std::int64_t value) {
  55.     if (key < bound_) {
  56.       primary_memo_[key] = value;
  57.     } else {
  58.       secondary_memo_.emplace(key, value);
  59.     }
  60.   }

  61.   std::int64_t bound_;
  62.   std::vector<std::int64_t> primary_memo_;
  63.   std::unordered_map<std::int64_t, std::int64_t> secondary_memo_;
  64. };

  65. int main(int argc, char *argv[]) {
  66.   Solution s;
  67.   std::cout << s.exec(1000000) << "\n";

  68.   return 0;
  69. }
复制代码

评分

参与人数 1大米 +3 收起 理由
kqxqx + 3 多谢解惑!

查看全部评分

回复

使用道具 举报

推荐
liuyuzhou111 2017-12-12 11:54:04 | 只看该作者
全局:
从1 开始倒推,
                                         21, 。。。
1,2,4,8,16,32, 64,128,  。。。
                           5,  10, 20 。。。
                                          3 。。。
DFS 所有可能情况,直到当前数字超出给定范围结束。用一个global variabe 记录 最大变换步数和相应的最大数。

应该不会爆栈吧
回复

使用道具 举报

🔗
hychin 2017-12-12 11:27:38 | 只看该作者
全局:
大神专攻U和A,佩服。。现在bar好高啊,另外你为啥用那么大的N做test case??
回复

使用道具 举报

🔗
 楼主| kqxqx 2017-12-12 11:38:56 | 只看该作者
全局:
hychin 发表于 2017-12-12 11:27
大神专攻U和A,佩服。。现在bar好高啊,另外你为啥用那么大的N做test case??

面试官要求的,他说我手头没有其他N的结果,只有这个1,000,000,所以我只看这个结果。。。

回复

使用道具 举报

🔗
 楼主| kqxqx 2017-12-12 12:09:01 | 只看该作者
全局:
liuyuzhou111 发表于 2017-12-12 11:54
从1 开始倒推,
                                         21, 。。。
1,2,4,8,16,32, 64,128 ...

你这个是用一个min heap每次pop出最小值,直到heap顶的元素>=N,复杂度是O(Nlog(N))?这样确实不需要递归了,估计不会爆栈
回复

使用道具 举报

🔗
yikehongxin 2017-12-12 13:32:51 | 只看该作者
全局:
liuyuzhou111 发表于 2017-12-12 11:54
从1 开始倒推,
                                         21, 。。。
1,2,4,8,16,32, 64,128 ...

is it possible that some cases are not visited? eg. 7
shurufa huaile. zaixia bushi laoyin
回复

使用道具 举报

🔗
liuyuzhou111 2017-12-12 13:59:47 | 只看该作者
全局:
daguanyuan 发表于 2017-12-12 13:32
is it possible that some cases are not visited? eg. 7
shurufa huaile. zaixia bushi laoyin

不会啊,只要没有超出范围都能到。我的想法是用DFS recursion. 从1开始逐渐分出很多分支,直到超出范围结束。
回复

使用道具 举报

🔗
 楼主| kqxqx 2017-12-12 22:42:52 | 只看该作者
全局:
liuyuzhou111 发表于 2017-12-12 13:59
不会啊,只要没有超出范围都能到。我的想法是用DFS recursion. 从1开始逐渐分出很多分支,直到超出范围结 ...

你如果用recursion的话,我觉得爆栈的可能性很大,算法上是work的
回复

使用道具 举报

🔗
yikehongxin 2017-12-12 23:31:13 | 只看该作者
全局:
kqxqx 发表于 2017-12-12 12:09
你这个是用一个min heap每次pop出最小值,直到heap顶的元素>=N,复杂度是O(Nlog(N))?这样确实不需要递归 ...

自己实现了下,结果不太对,然后发现,有一个bug需要修订:直到heap顶元素>=N,这个逻辑有问题。假如N给定是100吧,99的时候是不是会 99 * 3 +1了呢。此时就超过100了。

补充内容 (2017-12-12 23:32):
但是这个也得算吧
回复

使用道具 举报

🔗
 楼主| kqxqx 2017-12-12 23:47:38 | 只看该作者
全局:
daguanyuan 发表于 2017-12-12 23:31
自己实现了下,结果不太对,然后发现,有一个bug需要修订:直到heap顶元素>=N,这个逻辑有问题。假如N给 ...

是的,不用recursion的话得注意逻辑,保证所有中间结果都能cover掉

我最后几分钟写的iteration的版本也有类似的问题,就是中间一些计算的结果并没有存到cache里面,所以时间复杂度上是有问题的(慢),但至少不会爆栈。。。这也是我一开始用recursion的原因

说个插曲:到大概30多分钟的时候,面试官说我可以多给你几分钟,你如果能快速用其他的语言重写一遍,把N=1,000,000这个case跑出来就行,可惜我只会c++ 所以我猜,这个面试官心里的答案,算法应该是和我一样的,但没准用java/python什么的写出来就能跑过了

补充内容 (2017-12-12 23:49):
当然,也有可能有其他更好的算法。。。anyway,我只能愿赌服输了
回复

使用道具 举报

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

本版积分规则

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