一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3574|回复: 38
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
melody_qyao 发表于 2015-7-20 03:44:21 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Yelp - 网上海投 - 技术电面 |Failfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
首先要吐槽一下yelp的HR和面试官,真的是我找工作这么久以来遇到的最差的!首先HR screen的时候,就是按着它准备好的题目问你,完全不care你说什么,全程没有互动交流。然后告诉你接下来有哪些流程,安排面试的时候速度极慢,一般是隔个两天给你回复约的时间,好不容易约好面试,再来说说面试官。面我的是一个意大利白人小哥,那口音真是醉了,全程面试不带笑,好像刚刚被老板骂过来面试一样。你回答什么,他也不互动,问一个garbage collection,非要问道最后你答不出来为止,还把你往错误的方向上引导。最后来说coding题吧,就是一个dart game,然后有一群possible scores,然后给你一个candidate score,问这个candidate score是不是可能的得分。For example:possible scores: [3,5,3,3,5] (有duplicates,unsorted,可能有很多很多possible score,不一定只有3和5)
candidate score: 6, yes
candidate score: 11, yes
candidate score: 7, no. 1point 3acres 璁哄潧
candidate score: 0, yes
我感觉这题有点像leetcode combination sum那题,但是那题是用回溯求出所有可能解,这题是判断是否可以,想写个recursion的方法,试了几次还是弄不好,求各位大神帮忙。

评分

4

查看全部评分

AndyLiu0429 发表于 2015-7-20 17:18:26 | 显示全部楼层
  1. public static boolean isValid(int[] scores, int candidate) {
  2.         if (candidate < 0) {
  3.             return false;
  4.         }

  5.         boolean[] dp = new boolean[candidate + 1];
  6.         dp[0] = true;
  7. . From 1point 3acres bbs
  8.         for (int score : scores) {
  9.             for (int k = score; k <= candidate; k++) {
  10.                 dp[k] |= dp[k - score];. more info on 1point3acres.com
  11.             }. 1point 3acres 璁哄潧
  12.         }
    . visit 1point3acres.com for more.

  13.         return dp[candidate];
  14.     }
复制代码
dp可以解决吧。。不排序的话就是没法去重了。

评分

1

查看全部评分

回复 支持 4 反对 1

使用道具 举报

traceroute_su 发表于 2015-7-22 08:53:32 | 显示全部楼层
这应该是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.鏈枃鍘熷垱鑷1point3acres璁哄潧
转移方程 dp(i,j) = dp(i+1,j-nums[i])|| dp(i+1,j) . Waral 鍗氬鏈夋洿澶氭枃绔,
意思就是选择当前数字和不选择当前数字的 or 操作
选择当然数字的话,数字index plus,sum减少,也就是j-nums[i]
不选当然数字的话,sum不减少,数字依旧plus
result就在dp(i,candidate), i 属于[0, num.length)
只要那一列存在了true,就是true
也就是说 那一列只要有数字可以凑成candidate就返回。


评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

FH9410 发表于 2015-7-20 16:42:15 | 显示全部楼层
        public boolean isPossible(int[] nums, int target) {
                if (nums == null || nums.length == 0) {
                        return false;
                }
                Arrays.sort(nums);
                return helper(nums, target, 0);.1point3acres缃
        }
       
        private boolean helper(int[] nums, int target, int pos) {
                if (target <= 0) {
                        return target == 0;-google 1point3acres
                }
               
                for (int i = pos; i < nums.length; i++) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                        if (i != pos && nums[i] == nums[i - 1]) {
. From 1point 3acres bbs                                continue;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                        }
                        if (helper(nums, target - nums[i], i + 1)) {
                                return true;
                        }
                }
                return false;
        }
回复 支持 2 反对 0

使用道具 举报

neomiracle 发表于 2015-7-23 05:21:17 | 显示全部楼层
public class PossibleScore {
        static boolean res = false;
        public static boolean possible(int[] input, int target){
                if(input == null || input.length == 0){
                        return false;
                }
                Arrays.sort(input);
                helper(input, target, 0);
                return res;
        }. 1point 3acres 璁哄潧
. visit 1point3acres.com for more.
        private static void helper(int[] input, int target, int i) {
                if(res || target == 0){. visit 1point3acres.com for more.
                        res = true;
. from: 1point3acres.com/bbs                         return;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                }
                if(i >= input.length || input[i] > target){
                        return;
                }. more info on 1point3acres.com
                helper(input, target - input[i], i);. Waral 鍗氬鏈夋洿澶氭枃绔,
                helper(input, target, i + 1);
        }
}
回复 支持 1 反对 0

使用道具 举报

notturno 发表于 2015-7-21 01:06:08 | 显示全部楼层
这题还好吧,先sort,然后backtracking. more info on 1point3acres.com
如果start的值已经大于target,直接返回false(默认target是正数)

还有就是同一个得分能否重复使用
如果不能重复使用,就在dfs的循环里面加一个判断
如果可以重复使用,先把数组转存为一个没有duplicate的list
回复 支持 0 反对 1

使用道具 举报

 楼主| melody_qyao 发表于 2015-7-20 05:00:11 | 显示全部楼层
暂时写出来了一个recursion的方法,仅供大家参考。ps递归参数里面选择boolean[]而不是boolean的原因是单个布尔值不好传回来,所以用布尔数组代替。
. from: 1point3acres.com/bbs
       public static boolean Solution(int[] scores, int candidate){
                if(candidate<0)
                        return false;
                boolean[] flag = new boolean[1];
                return helper(scores, candidate, 0, flag);. From 1point 3acres bbs
        }. 鍥磋鎴戜滑@1point 3 acres
        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];. more info on 1point3acres.com
                }
                return flag[0];
        }
回复 支持 反对

使用道具 举报

brian1118 发表于 2015-7-20 08:15:17 | 显示全部楼层
應該還是要把possible scores sort過,這樣在helper的for loop裡面可以跳過已經用過的值

while(i < scores.length - 1 && scores[i] == scores[i+1]) ++i;
回复 支持 反对

使用道具 举报

zws0818 发表于 2015-7-20 10:15:25 | 显示全部楼层
yao, 你申的是new grad职位吗?是网申还是内推的啊?
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-20 12:11:08 | 显示全部楼层
请问candidate score是可以在possible scores中任意挑选数字组成,还是说必须选择相邻的一些数字?
回复 支持 反对

使用道具 举报

 楼主| melody_qyao 发表于 2015-7-20 14:26:39 | 显示全部楼层
stellari 发表于 2015-7-20 12:11
请问candidate score是可以在possible scores中任意挑选数字组成,还是说必须选择相邻的一些数字?

任意挑选数字
回复 支持 反对

使用道具 举报

 楼主| melody_qyao 发表于 2015-7-20 14:28:44 | 显示全部楼层
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
回复 支持 反对

使用道具 举报

 楼主| melody_qyao 发表于 2015-7-20 14:29:02 | 显示全部楼层
zws0818 发表于 2015-7-20 10:15
yao, 你申的是new grad职位吗?是网申还是内推的啊?

new grad,自己勾搭的HR,没有内推
回复 支持 反对

使用道具 举报

zws0818 发表于 2015-7-20 23:23:48 | 显示全部楼层
melody_qyao 发表于 2015-7-20 14:29
new grad,自己勾搭的HR,没有内推

HR你从哪里找到的?
回复 支持 反对

使用道具 举报

 楼主| melody_qyao 发表于 2015-7-21 02:32:28 | 显示全部楼层
zws0818 发表于 2015-7-20 23:23
HR你从哪里找到的?

Linkedin
回复 支持 反对

使用道具 举报

 楼主| melody_qyao 发表于 2015-7-21 02:34:46 | 显示全部楼层
FH9410 发表于 2015-7-20 16:42
public boolean isPossible(int[] nums, int target) {
                if (nums == null || nums.length == 0) {
                         ...

for loop里面的递归调用那里,应该是i而不是i+1吧,因为每个possible score都是可以重复用无数次的
回复 支持 反对

使用道具 举报

 楼主| melody_qyao 发表于 2015-7-21 02:37:07 | 显示全部楼层
notturno 发表于 2015-7-21 01:06 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
这题还好吧,先sort,然后backtracking
如果start的值已经大于target,直接返回false(默认target是正数)
...

不是什么难题,但我递归写不好,所以卡了很久
回复 支持 反对

使用道具 举报

nano 发表于 2015-7-21 04:21:18 | 显示全部楼层
谢谢分享,题目真的是思路不难,写起来一遍bug free很不容易
没有大米给楼主了,分享一个c++ dp解法
  1. #include <iostream>-google 1point3acres
  2. #include <vector>
  3. #include <unordered_set>
  4. #include <string.h>

  5. using namespace std;
  6. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  7. bool isPossible(int total_score, vector<int> score_list){. from: 1point3acres.com/bbs
  8. if(total_score<=0)
  9. return total_score==0;

  10. unordered_set<int> score_pool(score_list.begin(),score_list.end());
  11. bool *valid_score=new bool[total_score+1];
  12. memset(valid_score,0,total_score+1);
  13. valid_score[0]=1;

  14. for(int i=1;i<=total_score;++i){
  15.         for(int j=0;j<i;++j){
  16.                 if(valid_score[j]). 鍥磋鎴戜滑@1point 3 acres
  17.                 valid_score[i]=(score_pool.find(i-j)!=score_pool.end());
  18.                 if(valid_score[i])
  19.                 break;
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  20.         }
  21. }

  22. return valid_score[total_score];
  23. }

  24. int main() {
  25.         vector<int> score_list({3,5,3,3,5});
  26.         int total_score_list[]={6,11,7,0};
  27.        
  28.         for(int i=0;i<sizeof(total_score_list)/sizeof(int);++i){. 1point 3acres 璁哄潧
  29.                 if(isPossible(total_score_list[i],score_list))
  30.                 cout<<"candidate score: "<<total_score_list[i]<<", yes"<<endl;
  31.                 else
  32.                 cout<<"candidate score: "<<total_score_list[i]<<", no"<<endl;
  33.         }. 1point3acres.com/bbs
  34.         return 0;
  35. }
复制代码
回复 支持 反对

使用道具 举报

neomiracle 发表于 2015-7-23 00:58:37 | 显示全部楼层
感觉这个题解法基本上和经典硬币题思路一样
回复 支持 反对

使用道具 举报

chendanlan 发表于 2015-7-23 05:45:03 | 显示全部楼层
题主有在hacker rank做题目吗? 那个题目能够搜索网页做吗
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 16:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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