推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 5479|回复: 38
收起左侧

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

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

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. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
candidate score: 0, yes
我感觉这题有点像leetcode combination sum那题,但是那题是用回溯求出所有可能解,这题是判断是否可以,想写个recursion的方法,试了几次还是弄不好,求各位大神帮忙。

评分

4

查看全部评分

AndyLiu0429 发表于 2015-7-20 17:18:26 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
  1. public static boolean isValid(int[] scores, int candidate) {
  2.         if (candidate < 0) {. from: 1point3acres.com/bbs
  3.             return false;
  4.         }

  5.         boolean[] dp = new boolean[candidate + 1];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  6.         dp[0] = true;

  7.         for (int score : scores) {
  8.             for (int k = score; k <= candidate; k++) {
  9.                 dp[k] |= dp[k - score];
  10.             }
  11.         }

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

评分

1

查看全部评分

回复 支持 4 反对 1

使用道具 举报

traceroute_su 发表于 2015-7-22 08:53:32 | 显示全部楼层
关注一亩三分地微博:
Warald
这应该是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就返回。
.鏈枃鍘熷垱鑷1point3acres璁哄潧

评分

1

查看全部评分

回复 支持 3 反对 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);
        }
       
        private boolean helper(int[] nums, int target, int pos) {
                if (target <= 0) {
                        return target == 0;. 鍥磋鎴戜滑@1point 3 acres
                }
               
                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;
        }
回复 支持 2 反对 0

使用道具 举报

neomiracle 发表于 2015-7-23 05:21:17 | 显示全部楼层
public class PossibleScore {.鏈枃鍘熷垱鑷1point3acres璁哄潧
        static boolean res = false;
        public static boolean possible(int[] input, int target){
                if(input == null || input.length == 0){
                        return false;
                }. more info on 1point3acres.com
                Arrays.sort(input);
                helper(input, target, 0);. 鍥磋鎴戜滑@1point 3 acres
                return res; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
        }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
.鏈枃鍘熷垱鑷1point3acres璁哄潧
        private static void helper(int[] input, int target, int i) {
                if(res || target == 0){
                        res = true;
                        return;
                }
                if(i >= input.length || input[i] > target){
                        return;
                }
                helper(input, target - input[i], i);
                helper(input, target, i + 1);
        }
}
回复 支持 1 反对 0

使用道具 举报

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

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

使用道具 举报

 楼主| melody_qyao 发表于 2015-7-20 05:00:11 | 显示全部楼层
暂时写出来了一个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];. From 1point 3acres bbs
        }
回复 支持 反对

使用道具 举报

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. 1point 3acres 璁哄潧
應該還是要把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>. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  2. #include <vector>
  3. #include <unordered_set>
  4. #include <string.h>

  5. using namespace std;

  6. bool isPossible(int total_score, vector<int> score_list){. 1point3acres.com/bbs
  7. if(total_score<=0)
  8. return total_score==0;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

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

  13. for(int i=1;i<=total_score;++i){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  14.         for(int j=0;j<i;++j){
  15.                 if(valid_score[j]). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  16.                 valid_score[i]=(score_pool.find(i-j)!=score_pool.end());
  17.                 if(valid_score[i])
  18.                 break;
  19.         }
  20. }.鏈枃鍘熷垱鑷1point3acres璁哄潧

  21. return valid_score[total_score];
  22. }

  23. int main() {
  24.         vector<int> score_list({3,5,3,3,5});
  25.         int total_score_list[]={6,11,7,0};
  26.        
  27.         for(int i=0;i<sizeof(total_score_list)/sizeof(int);++i){
  28.                 if(isPossible(total_score_list[i],score_list)). Waral 鍗氬鏈夋洿澶氭枃绔,
  29.                 cout<<"candidate score: "<<total_score_list[i]<<", yes"<<endl;
  30.                 else
  31.                 cout<<"candidate score: "<<total_score_list[i]<<", no"<<endl;
  32.         }
  33.         return 0;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  34. }
复制代码
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-24 08:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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