发一个yelp的skype电面面经，已跪

首先要吐槽一下yelp的HR和面试官，真的是我找工作这么久以来遇到的最差的！首先HR screen的时候，就是按着它准备好的题目问你，完全不care你说什么，全程没有互动交流。然后告诉你接下来有哪些流程，安排面试的时候速度极慢，一般是隔个两天给你回复约的时间，好不容易约好面试，再来说说面试官。面我的是一个意大利白人小哥，那口音

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

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

我感觉这题有点像leetcode combination sum那题，但是那题是用回溯求出所有可能解，这题是判断是否可以，想写个recursion的方法，试了几次还是弄不好，求各位大神帮忙。

1. public static boolean isValid(int[] scores, int candidate) {
   
2.         if (candidate < 0) {
   
3.             return false;
   
4.         }
   
5. 
   
6.         boolean[] dp = new boolean[candidate + 1];
   
7.         dp[0] = true;
   
8. 
   
9.         for (int score : scores) {
   
10.             for (int k = score; k <= candidate; k++) {
    
11.                 dp[k] |= dp[k - score];
    
12.             }
    
13.         }
    
14. 
    
15.         return dp[candidate];
    
16.     }

复制代码

dp可以解决吧。。不排序的话就是没法去重了。

这应该是subset sum 问题吧
1. brute force的话 2^n
挨个选，选和不选 是两个选择对于每个数字来说，所以是2^n，iterative 位操作的话可以搞定，递归可以搞定。
2. dp 可以搞定 也就是背包问题 O(nC) n是需要的数字个数，也就是需要几个数字可以到达sum，C就是sum 这是个伪多项式解法，实质还是exponential的。
所以写哪个都可以。

dp方程： dp(i,j) 选i个数字，剩下j 的情况下是否是true
转移方程 dp(i,j) = dp(i+1,j-nums[i])|| dp(i+1,j)
意思就是选择当前数字和不选择当前数字的 or 操作
选择当然数字的话，数字index plus，sum减少，也就是j-nums[i]
不选当然数字的话，sum不减少，数字依旧plus
result就在dp(i,candidate)， i 属于[0, num.length)
只要那一列存在了true，就是true
也就是说 那一列只要有数字可以凑成candidate就返回。

        public boolean isPossible(int[] nums, int target) {
                if (nums == null || nums.length == 0) {
                        return false;
                }
                Arrays.sort(nums);
                return helper(nums, target, 0);
        }
       
        private boolean helper(int[] nums, int target, int pos) {
                if (target <= 0) {
                        return target == 0;
                }
               
                for (int i = pos; i < nums.length; i++) {
                        if (i != pos && nums[i] == nums[i - 1]) {
                                continue;
                        }
                        if (helper(nums, target - nums[i], i + 1)) {
                                return true;
                        }
                }
                return false;
        }

暂时写出来了一个recursion的方法，仅供大家参考。ps递归参数里面选择boolean[]而不是boolean的原因是单个布尔值不好传回来，所以用布尔数组代替。

       public static boolean Solution(int[] scores, int candidate){
                if(candidate<0)
                        return false;
                boolean[] flag = new boolean[1];
                return helper(scores, candidate, 0, flag);
        }
        public static boolean helper(int[] scores, int candidate, int pos, boolean[] flag){
                if(candidate == 0)
                        flag[0] = true;
                for(int i=pos; i<scores.length; i++){                       
                        if(candidate < 0)
                                return false;
                        if(flag[0]) break;
                        candidate -= scores[i];
                        helper(scores, candidate, i, flag);                       
                        candidate += scores[i];
                }
                return flag[0];
        }

應該還是要把possible scores sort過，這樣在helper的for loop裡面可以跳過已經用過的值

while(i < scores.length - 1 && scores[i] == scores[i+1]) ++i;

yao, 你申的是new grad职位吗？是网申还是内推的啊？

请问candidate score是可以在possible scores中任意挑选数字组成，还是说必须选择相邻的一些数字？

stellari 发表于 2015-7-20 12:11
请问candidate score是可以在possible scores中任意挑选数字组成，还是说必须选择相邻的一些数字？

任意挑选数字

brian1118 发表于 2015-7-20 08:15
應該還是要把possible scores sort過，這樣在helper的for loop裡面可以跳過已經用過的值

while(i < scor ...

恩，忘了说我这里偷懒了，假设的input scores是sorted && no duplicates，然后for loop那里注意我是从pos开始的，而每次递归调用helper时传入的参数是新的i

zws0818 发表于 2015-7-20 10:15
yao, 你申的是new grad职位吗？是网申还是内推的啊？

new grad，自己勾搭的HR，没有内推