snapchat 挂经

昨天刚面的，是第二次电面。过程如下：准点点开视频链接，等了10分钟不见动静，这时收到一个邮件是recruiter说面试官已经等我10分钟了，不见我踪影。。。
看完立刻关闭浏览器重新点击那个视频链接，就连上了，那头的面试官还在面带微笑。。。刚解释了几句，又发现我的麦有问题，对方听不见。。。折腾半天才，重启电脑才解决。
再次连上时，离规定面试起始时间已经过了20分钟了。我那时候的心情就用四个字概括： 心急如焚。

给面试官道歉，解释了几句，然后双方自我介绍，问了下为什么要选择snapchat（感觉snapchat特别喜欢问这个问题，楼主第一轮电面的时候被问到直接说我一点都不了解snapchat。。。），接下来就是coding环节。

题目大意如下：
给定一个全是正整数的array， 和一个targe值。
你可以取任意数目的elements from the array，允许有重复，然后使得这些elem

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

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

主的最后一根稻草，这道题如果经验丰富点其实可以在很短时间内做出来的。另外感觉snapchat很注重attitude，楼主事先对这个公司做的工作少之又少。

没能拿到snapchat的onsite还是很难过，伤心了一天，求安慰！
















补充内容 (2016-3-2 06:56):

好吧，经地里小伙伴们提醒，这题就是个走楼梯的题。大家可以无视我这么多的分析了- -菜是原罪啊

gengenhappy 发表于 2016-2-19 11:51
“你可以取任意数目的elements from the array，允许有重复” 这句话有歧义吧。
(1)是允许每个元素取的 ...

这题意思就和走楼梯一样的。。只是一般走楼梯要么走一步要么走两步。。他这相当于规定你可以走{1,2,3,4}步都可以。。

应该是走楼梯吧：

        int findComb(vector<int>& candidates, int n) {
                std::sort(candidates.begin(), candidates.end());
                vector<int> dp(n + 1, 0);
                dp[0] = 1;
                for (int i = 1; i < n + 1; i++) {
                        for (int j = 0; j < candidates.size(); j++) {
                                if (i <= candidates[j])
                                        dp[i] += dp[i - candidates[j]];
                                else
                                        break;
                        }
                }
                return dp[n];
        }

gengenhappy 发表于 2016-2-19 11:31
不太理解为什么1d array 可以求解。请lz赐教！
能想出来的也就是dfs先求得unique解，再对每个解做permutat ...

你这个属于brute force了。。。
首先，其实用dfs也可以做到直接把所有的解枚举出来的。这个并不难想。
然后，说说用1array的DP解法：
    int state[] = new int[target + 1]; // state[i] 表示 target为i的时候，有多少种解法。
     state[i] = sum (state[i - array[k]])  (for k = 0,1,...n-1， i - array[k] >= 0)


补充内容 (2016-2-19 11:44):
state[i] = sum (state[i - array[k]])  (for k = 0,1,...n-1， i - array[k] >= 0)

补充内容 (2016-2-19 11:45):
斜体字格式有问题。请无视。。
state【i】 = sum (state[i - array[k]])  (for k = 0,1,...n-1， i - array[k] >= 0)

这道题是不是backtracking就好了呢？

没有面挂过的程序员不是好工程师！

haoxuango 发表于 2016-2-19 09:11
这道题是不是backtracking就好了呢？

没有面挂过的程序员不是好工程师！

想了下，确实可以！~哎，自己就想不出来。。。

haoxuango 发表于 2016-2-19 09:11
这道题是不是backtracking就好了呢？

没有面挂过的程序员不是好工程师！

又仔细想了下 backtracking的复杂度是 O(length的target次方)
DP的复杂度是O(length * target)
差的有点多。

不太理解为什么1d array 可以求解。请lz赐教！
能想出来的也就是dfs先求得unique解，再对每个解做permutation。

panlong222 发表于 2016-2-19 11:43
你这个属于brute force了。。。
首先，其实用dfs也可以做到直接把所有的解枚举出来的。这个并不难想。
...

“你可以取任意数目的elements from the array，允许有重复” 这句话有歧义吧。
(1)是允许每个元素取的数目重复
(2)数组中存在重复元素但每个元素只能取一次
如果是第一种情况的话，dp得解。
如果是第二种情况的话，以上dp应该并不能吧
LZ应该说的是第一种吧

gengenhappy 发表于 2016-2-19 11:51
“你可以取任意数目的elements from the array，允许有重复” 这句话有歧义吧。
(1)是允许每个元素取的 ...

嗯 第一种。example里可以看出来的哈。

phantom 发表于 2016-2-19 12:03
这题意思就和走楼梯一样的。。只是一般走楼梯要么走一步要么走两步。。他这相当于规定你可以走{1,2,3,4} ...

正解。