10月28,K神开讲数据科学:AB Test/实验设计


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 5483|回复: 11
收起左侧

Snapchat面经

[复制链接] |试试Instant~ |关注本帖
jxyfwrj 发表于 2015-11-5 07:10:32 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Snapchat - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚刚面完十分钟 就过来写面经了。。。

1. permutation i。leetcode原题,没有任何改变。
2. 24点游戏。给你几个数字,判断他们做加减乘除运算是否可以得到24,顺序可以是任意的。dfs搜索搞定。。。但是这里要注意一些细节,每次计算得到新的数之后最好加入数组做下一次搜索,不然容易出错。

面我的是个中国小哥,感觉人特别nice,一直引导我。还聊到学objc的事,我是真心想学学app开发啊。。。

面经大法好,求人品,求onsite。。。
.鏈枃鍘熷垱鑷1point3acres璁哄潧


. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2015-11-20 03:28):. 1point 3acres 璁哄潧
面完第二天拿了onsite 预约十二月初面 不得不说snapchat的效率真的非常高

评分

2

查看全部评分

siyuan808 发表于 2015-11-6 06:57:28 | 显示全部楼层
请教第二题,这几个数字的顺序能不能改变,加减乘除有没有操作优先级,如果有的话,应该很难吧这题。
回复 支持 反对

使用道具 举报

 楼主| jxyfwrj 发表于 2015-11-6 08:06:25 | 显示全部楼层
siyuan808 发表于 2015-11-6 06:57
请教第二题,这几个数字的顺序能不能改变,加减乘除有没有操作优先级,如果有的话,应该很难吧这题。
-google 1point3acres
数字的顺序可以变,加减乘除有操作优先级,就是可以任意组合算式,比如1,2,3,4可以有(1+2) * (3+4)的组合。
回复 支持 反对

使用道具 举报

yabay91 发表于 2015-11-10 13:34:54 | 显示全部楼层
第二题试着写了下,不知道满足不满足要求。。或者有没有更好的办法- -
  1.         private static boolean game(int[] nums){. From 1point 3acres bbs
  2.                 if(nums==null).鐣欏璁哄潧-涓浜-涓夊垎鍦
  3.                                 return false;
  4.                 Arrays.sort(nums);
  5.                 HashSet<Integer> res=new HashSet<Integer>();
  6.                 gameHelper(nums,new boolean[nums.length],new ArrayList<Integer>(),res);
  7.                 return res.contains(24); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  8.         }. 鍥磋鎴戜滑@1point 3 acres
  9.         private static void gameHelper(int[] nums,boolean[] visited,List<Integer> elem,HashSet<Integer> res){
  10.                 if(elem.size()==nums.length){
  11.                         for(int x:cal(elem,0,elem.size()-1)). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  12.                                 res.add(x);
  13.                         return ;
  14.                 }
  15.                 for(int i=0;i<nums.length;i++){
  16.                         if(visited[i]||i>0&&nums[i]==nums[i-1]&&!visited[i-1])
  17.                                 continue;
  18.                         elem.add(nums[i]);
  19.                         visited[i]=true;
  20.                         gameHelper(nums,visited,elem,res);. visit 1point3acres.com for more.
  21.                         elem.remove(elem.size()-1);
  22.                         visited[i]=false;
  23.                 }
  24.         }
  25.         private static List<Integer> cal(List<Integer> elem, int begin,int end){
  26.                 List<Integer> res=new ArrayList<Integer>();
  27.                 if(begin==end){
  28.                         res.add(elem.get(begin));
  29.                         return res;. visit 1point3acres.com for more.
  30.                 }               
  31.                 for(int i=begin;i<end;i++){
  32.                         List<Integer> left=cal(elem,begin,i);.鐣欏璁哄潧-涓浜-涓夊垎鍦
  33.                         List<Integer> right=cal(elem,i+1,end);
  34.                         for(int x:left)
  35.                                 for(int y:right){
  36.                                         res.add(x+y);. 鍥磋鎴戜滑@1point 3 acres
  37.                                         res.add(x-y);
  38.                                         res.add(x*y);
  39.                                         if(y!=0).鏈枃鍘熷垱鑷1point3acres璁哄潧
  40.                                                 res.add(x/y);
  41.                                 }
  42.                 }
  43.                 return res;
  44.         }
复制代码
回复 支持 反对

使用道具 举报

cgpzmxcc 发表于 2015-11-15 11:44:37 | 显示全部楼层
看到楼主说“每次计算得到新的数之后最好加入数组”,试着写了如下代码
  1. . 1point 3acres 璁哄潧
  2. public class Solution {. 鍥磋鎴戜滑@1point 3 acres
  3. . 鍥磋鎴戜滑@1point 3 acres
  4.         private boolean compute(int[] nums, int target) {
  5.                 boolean[] visit = new boolean[nums.length];. from: 1point3acres.com/bbs
  6.                 return helper(nums, visit, target, nums.length);
  7.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  8.         private boolean helper(int[] nums, boolean[] visit, int target, int c) {
  9.                 if (c == 1) {
  10.                         for (int i = 0; i < nums.length; i++) {
  11.                                 if (!visit[i]) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  12.                                         return nums[i] == target;
  13.                                 }
  14.                         }
  15.                 } else {
  16.                         for (int i = 0; i < nums.length; i++) {
  17.                                 if (visit[i])
  18.                                         continue;-google 1point3acres
  19.                                 for (int j = i + 1; j < nums.length; j++) {
  20.                                         if (visit[j])
  21.                                                 continue;. From 1point 3acres bbs
  22.                                         int n1 = nums[i];
  23.                                         int n2 = nums[j];
  24.                                         visit[j] = true;
  25.                                         nums[i] = n1 + n2;
  26.                                         if (helper(nums, visit, target, c - 1))
  27.                                                 return true;. from: 1point3acres.com/bbs
  28.                                         nums[i] = n1 - n2;
  29.                                         if (helper(nums, visit, target, c - 1))
  30.                                                 return true;
  31.                                         nums[i] = n2 - n1;
  32.                                         if (helper(nums, visit, target, c - 1))
  33.                                                 return true;
  34.                                         nums[i] = n1 * n2;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  35.                                         if (helper(nums, visit, target, c - 1)). visit 1point3acres.com for more.
  36.                                                 return true;
  37.                                         if (n2 != 0) {
  38.                                                 nums[i] = n1 / n2;
  39.                                                 if (helper(nums, visit, target, c - 1))
  40.                                                         return true;
  41.                                         }. 1point3acres.com/bbs
  42.                                         if (n1 != 0) {
  43.                                                 nums[i] = n2 / n1;
  44.                                                 if (helper(nums, visit, target, c - 1))
  45.                                                         return true;. visit 1point3acres.com for more.
  46.                                         }
  47.                                         nums[i] = n1;
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  48.                                         visit[j] = false;
  49.                                 }
  50.                         }
  51.                 }
  52.                 return false;
  53.         }. from: 1point3acres.com/bbs
  54. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  55.         public static void main(String args[]) {
  56.                 Solution s = new Solution();
  57.                 System.out.println(s.compute(new int[] { 2, 3, 2, 1 }, 24));
  58.         }
  59. }
复制代码
回复 支持 反对

使用道具 举报

740919074 发表于 2015-11-20 01:41:51 | 显示全部楼层
cgpzmxcc 发表于 2015-11-15 11:44
看到楼主说“每次计算得到新的数之后最好加入数组”,试着写了如下代码

这个不行啊做除法9/2后面再乘以2就等于8了
回复 支持 反对

使用道具 举报

kennethinsnow 发表于 2015-11-23 09:07:49 | 显示全部楼层
jxyfwrj 发表于 2015-11-6 08:06
数字的顺序可以变,加减乘除有操作优先级,就是可以任意组合算式,比如1,2,3,4可以有(1+2) * (3+4 ...

带括号的就不能dfs了吧,必须用dp了。请问你怎么用dfs搞定的?谢谢
回复 支持 反对

使用道具 举报

 楼主| jxyfwrj 发表于 2015-11-23 09:12:52 | 显示全部楼层
cgpzmxcc 发表于 2015-11-15 11:44. visit 1point3acres.com for more.
看到楼主说“每次计算得到新的数之后最好加入数组”,试着写了如下代码

额python代码很简单的就十来行。。。 反正只要你编几个典型的例子看看corner case没问题就应该没错了
回复 支持 反对

使用道具 举报

 楼主| jxyfwrj 发表于 2015-11-23 09:15:45 | 显示全部楼层
kennethinsnow 发表于 2015-11-23 09:07
带括号的就不能dfs了吧,必须用dp了。请问你怎么用dfs搞定的?谢谢

. 鍥磋鎴戜滑@1point 3 acres哪有这种说法。。。 这题拿dp我觉得还真不知道咋做 而且没什么必要,dfs的话原帖子里写了啊:
每次取两个数,算出其加或减或乘或除后,把原来两个数pop出数组并将新结果push进去,然后从新的数组在看下一层,直到剩下一个数看看是不是和24相等,就没了。。 这样括号就也被考虑进来了
回复 支持 反对

使用道具 举报

kennethinsnow 发表于 2015-11-23 09:24:01 | 显示全部楼层
yabay91 发表于 2015-11-10 13:34
第二题试着写了下,不知道满足不满足要求。。或者有没有更好的办法- -

你这个可以优化一下,cal的时候最好输入是string, 然后可以做一个map<String, Set<Integer>>纪录相同string可以产生的所有值。
. from: 1point3acres.com/bbs
另外dfs到任意一个完整组合时,计算结果里面包含24,就应该马上退出。
回复 支持 反对

使用道具 举报

kennethinsnow 发表于 2015-11-23 10:08:53 | 显示全部楼层
jxyfwrj 发表于 2015-11-23 09:15 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
哪有这种说法。。。 这题拿dp我觉得还真不知道咋做 而且没什么必要,dfs的话原帖子里写了啊:
每次取两 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
除法要考虑能不能整除吗?

补充内容 (2015-11-23 10:11):
另外直接取会不会有大量重复?
回复 支持 反对

使用道具 举报

 楼主| jxyfwrj 发表于 2015-11-23 10:57:43 | 显示全部楼层
kennethinsnow 发表于 2015-11-23 10:08
除法要考虑能不能整除吗?

补充内容 (2015-11-23 10:11):

这里只考虑整数除法,不考虑浮点数。。。 重复是肯定的,当时没什么时间了,弄出来之后小哥就说OK了。想去重复的话,想办法剪枝就好。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-10-20 14:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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