空气床电面

网上自己投的简历，大约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更好。

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的测试数据是精心挑选的，就是个坑。

为了加速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. 
   
8. class Solution {
   
9. public:
   
10.   std::int64_t exec(const std::int64_t N) {
    
11.     // 调整这个系数会影响性能
    
12.     // 系数越大，耗费空间越多，但速度也越快
    
13.     // 8应该是一个比较好的选择...
    
14.     constexpr std::int64_t kFactor = 8;
    
15. 
    
16.     bound_ = N * kFactor;
    
17.     primary_memo_ = std::vector<std::int64_t>(bound_, -1);
    
18.     secondary_memo_ = std::unordered_map<std::int64_t, std::int64_t>();
    
19. 
    
20.     std::vector<std::int64_t> stk;
    
21.     stk.reserve(N);
    
22. 
    
23.     setMemo(1, 0);
    
24.     for (std::int64_t i = 2; i < N; ++i) {
    
25.       // pre-check以加速运算
    
26.       if (getMemo(i) >= 0) {
    
27.         continue;
    
28.       }
    
29. 
    
30.       std::int64_t curr = i;
    
31.       std::int64_t ret = -1;
    
32.       stk.push_back(curr);
    
33. 
    
34.       // 模拟的递归调用
    
35.       while (ret < 0) {
    
36.         const std::int64_t next = (curr & 0x1) ? (curr * 3 + 1) : (curr >> 1);
    
37.         if ((ret = getMemo(next)) < 0) {
    
38.           stk.push_back(next);
    
39.           curr = next;
    
40.         }
    
41.       }
    
42. 
    
43.       // 模拟的递归返回
    
44.       while (!stk.empty()) {
    
45.         setMemo(stk.back(), ++ret);
    
46.         stk.pop_back();
    
47.       }
    
48.     }
    
49. 
    
50.     return *std::max_element(primary_memo_.begin() + 1,
    
51.                              primary_memo_.begin() + N);
    
52.   }
    
53. 
    
54. private:
    
55.   inline std::int64_t getMemo(const std::int64_t key) const {
    
56.     if (key < bound_) {
    
57.       return primary_memo_[key];
    
58.     } else {
    
59.       auto it = secondary_memo_.find(key);
    
60.       return it == secondary_memo_.end() ? -1 : it->second;
    
61.     }
    
62.   }
    
63. 
    
64.   inline void setMemo(const std::int64_t key, const std::int64_t value) {
    
65.     if (key < bound_) {
    
66.       primary_memo_[key] = value;
    
67.     } else {
    
68.       secondary_memo_.emplace(key, value);
    
69.     }
    
70.   }
    
71. 
    
72.   std::int64_t bound_;
    
73.   std::vector<std::int64_t> primary_memo_;
    
74.   std::unordered_map<std::int64_t, std::int64_t> secondary_memo_;
    
75. };
    
76. 
    
77. int main(int argc, char *argv[]) {
    
78.   Solution s;
    
79.   std::cout << s.exec(1000000) << "\n";
    
80. 
    
81.   return 0;
    
82. }

复制代码

从1 开始倒推，
                                         21， 。。。
1，2，4，8，16，32， 64，128，  。。。
                           5，  10， 20 。。。
                                          3 。。。
DFS 所有可能情况，直到当前数字超出给定范围结束。用一个global variabe 记录 最大变换步数和相应的最大数。

应该不会爆栈吧

大神专攻U和A，佩服。。现在bar好高啊，另外你为啥用那么大的N做test case??

hychin 发表于 2017-12-12 11:27
大神专攻U和A，佩服。。现在bar好高啊，另外你为啥用那么大的N做test case??

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

liuyuzhou111 发表于 2017-12-12 11:54
从1 开始倒推，
                                         21， 。。。
1，2，4，8，16，32， 64，128 ...

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

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

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开始逐渐分出很多分支，直到超出范围结束。

liuyuzhou111 发表于 2017-12-12 13:59
不会啊，只要没有超出范围都能到。我的想法是用DFS recursion. 从1开始逐渐分出很多分支，直到超出范围结 ...

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

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):
但是这个也得算吧

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，我只能愿赌服输了