一亩三分地论坛

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

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

Snapchat面经

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

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

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

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

x
刚刚面完十分钟 就过来写面经了。。。. more info on 1point3acres.com
-google 1point3acres
1. permutation i。leetcode原题,没有任何改变。
2. 24点游戏。给你几个数字,判断他们做加减乘除运算是否可以得到24,顺序可以是任意的。dfs搜索搞定。。。但是这里要注意一些细节,每次计算得到新的数之后最好加入数组做下一次搜索,不然容易出错。. 1point 3acres 璁哄潧

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

面经大法好,求人品,求onsite。。。

. 1point3acres.com/bbs


补充内容 (2015-11-20 03:28):.鐣欏璁哄潧-涓浜-涓夊垎鍦
面完第二天拿了onsite 预约十二月初面 不得不说snapchat的效率真的非常高

评分

2

查看全部评分

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

使用道具 举报

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

数字的顺序可以变,加减乘除有操作优先级,就是可以任意组合算式,比如1,2,3,4可以有(1+2) * (3+4)的组合。
回复 支持 反对

使用道具 举报

yabay91 发表于 2015-11-10 13:34:54 | 显示全部楼层
第二题试着写了下,不知道满足不满足要求。。或者有没有更好的办法- -
  1.         private static boolean game(int[] nums){
  2.                 if(nums==null)
  3.                                 return false;
  4.                 Arrays.sort(nums);. from: 1point3acres.com/bbs
  5.                 HashSet<Integer> res=new HashSet<Integer>();
  6.                 gameHelper(nums,new boolean[nums.length],new ArrayList<Integer>(),res);
  7.                 return res.contains(24);
  8.         }
  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++){
    . visit 1point3acres.com for more.
  16.                         if(visited[i]||i>0&&nums[i]==nums[i-1]&&!visited[i-1]). more info on 1point3acres.com
  17.                                 continue;
  18.                         elem.add(nums[i]);
  19.                         visited[i]=true;
  20.                         gameHelper(nums,visited,elem,res);
  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){
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  28.                         res.add(elem.get(begin));
  29.                         return res;
  30.                 }                . 鍥磋鎴戜滑@1point 3 acres
  31.                 for(int i=begin;i<end;i++){. 1point3acres.com/bbs
  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);. Waral 鍗氬鏈夋洿澶氭枃绔,
  37.                                         res.add(x-y);
  38.                                         res.add(x*y);
  39.                                         if(y!=0)
  40.                                                 res.add(x/y);
  41.                                 }
  42.                 }
  43.                 return res;
  44.         }
复制代码
回复 支持 反对

使用道具 举报

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

  1. public class Solution {

  2.         private boolean compute(int[] nums, int target) {. 鍥磋鎴戜滑@1point 3 acres
  3.                 boolean[] visit = new boolean[nums.length];
  4.                 return helper(nums, visit, target, nums.length);
    . 1point 3acres 璁哄潧
  5.         }.1point3acres缃

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

使用道具 举报

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. Waral 鍗氬鏈夋洿澶氭枃绔,
数字的顺序可以变,加减乘除有操作优先级,就是可以任意组合算式,比如1,2,3,4可以有(1+2) * (3+4 ...

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

使用道具 举报

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

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

使用道具 举报

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

哪有这种说法。。。 这题拿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可以产生的所有值。

另外dfs到任意一个完整组合时,计算结果里面包含24,就应该马上退出。
回复 支持 反对

使用道具 举报

kennethinsnow 发表于 2015-11-23 10:08:53 | 显示全部楼层
jxyfwrj 发表于 2015-11-23 09:15
哪有这种说法。。。 这题拿dp我觉得还真不知道咋做 而且没什么必要,dfs的话原帖子里写了啊:
每次取两 ...

除法要考虑能不能整除吗?

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

使用道具 举报

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

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

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-19 12:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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