houzz店面跪经

一面，简直惨不忍睹。。。
一开始讲实习的项目，然后为什么选择houzz，然后2道题
第一题经典题，一堆不同面值的硬币，一个target，找到最少硬币数，求和等于target。（用dp做，2个for loop就行了）

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

lz为啥要记录path啊 只需要记录路径的长度就好了啊 这样写 肯定会爆栈啊

int helper(unordered_map<int, int>& map, int target){
        int count = 0;
        while(target != 1){
                if(map.find(target) != map.end())
                        return count + map[target];
                if(target % 2)
                        target = 3 * target + 1;
                else{
                        target /= 2;
                }
                count++;
        }
        return count;
}
int main(){
        int Max = 0;
        unordered_map<int, int> map;
        for(int i = 1; i <= 1000; i++){
                Max = max(Max, helper(map, i));
        }
        cout << Max << endl;
}

贴个代码吧

var helper = function(n) {
    var count = 0;
    while (n != 1) {

      if ((n & 1) == 1) {

        n = n * 3 + 1;

      } else {

        n /= 2;

      }

      count++;

    }
    return count;
}

这个memoization应该只需要纪录: 当前的值=key, 需要的步数=value, 这样只需要到series走到的upper limit就可以了(1000以内最长是871的length = 178 steps; 对871来说,最大值是190996). 试了一下coderpad应该可以run出来.
楼主可能是因为用path当key才爆栈的.

另外,对每个1~1000每个数间要清map, 由10开始到5, 和由5直接开始到5的step,当然是不一样的.

第二题，其实是个数学题，我感觉

补充内容 (2016-11-3 07:52):
好吧，楼主你应该没有做memorization?写了一下感觉跑的很快

huai10 发表于 2016-11-3 07:19
第二题，其实是个数学题，我感觉

补充内容 (2016-11-3 07:52):

用map存不就是memorization吗？我能跑出来，只是面试的时候不知道为什么出不来

lz 序列那题有啥优化吗？ 1-1000 算长度有啥技巧吗？谢谢~

白丁117 发表于 2017-1-11 23:51
lz 序列那题有啥优化吗？ 1-1000 算长度有啥技巧吗？谢谢~

不是说了吗，在for loop里面用stack把这条路径上的数都记录下来，当某一个数可以从map中得到长度后，再一个个从stack中取数，记录这些数都长度

第二题是DP吧

补充内容 (2017-4-9 17:26):
打错了BFS

第二题最近很流行啊。气床也电面我这个了。这个题在线调试通过时可能会引起心理问题，特别是范围很大的时候，因为map会超过VM的size。

shiloh00 发表于 2017-4-3 03:52
lz为啥要记录path啊 只需要记录路径的长度就好了啊 这样写 肯定会爆栈啊

int helper(unordered_map& map ...

这个代码不对吧？。。 因为map貌似没有被更新。？求指导

如果用本楼的代码，然后在main里面记下每一个i对应的max, 序列最长是178吗？