一亩三分地论坛

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

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

Snapchat面经

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

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

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

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

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

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

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

面经大法好,求人品,求onsite。。。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

.鐣欏璁哄潧-涓浜-涓夊垎鍦
-google 1point3acres

补充内容 (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.鐣欏璁哄潧-涓浜-涓夊垎鍦
请教第二题,这几个数字的顺序能不能改变,加减乘除有没有操作优先级,如果有的话,应该很难吧这题。
. 1point3acres.com/bbs
数字的顺序可以变,加减乘除有操作优先级,就是可以任意组合算式,比如1,2,3,4可以有(1+2) * (3+4)的组合。
回复 支持 反对

使用道具 举报

yabay91 发表于 2015-11-10 13:34:54 | 显示全部楼层
第二题试着写了下,不知道满足不满足要求。。或者有没有更好的办法- -. from: 1point3acres.com/bbs
  1.         private static boolean game(int[] nums){
  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);
    . more info on 1point3acres.com
  7.                 return res.contains(24);. Waral 鍗氬鏈夋洿澶氭枃绔,
  8.         }
  9.         private static void gameHelper(int[] nums,boolean[] visited,List<Integer> elem,HashSet<Integer> res){. 1point 3acres 璁哄潧
  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++){. 鍥磋鎴戜滑@1point 3 acres
  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;. 1point 3acres 璁哄潧
  20.                         gameHelper(nums,visited,elem,res);.1point3acres缃
  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>();. 鍥磋鎴戜滑@1point 3 acres
  27.                 if(begin==end){
  28.                         res.add(elem.get(begin));
  29.                         return res;
  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). more info on 1point3acres.com
  35.                                 for(int y:right){
  36.                                         res.add(x+y);
  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. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  3.         private boolean compute(int[] nums, int target) {. from: 1point3acres.com/bbs
  4.                 boolean[] visit = new boolean[nums.length];
  5.                 return helper(nums, visit, target, nums.length);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  6.         }

  7.         private boolean helper(int[] nums, boolean[] visit, int target, int c) {
  8.                 if (c == 1) {
  9.                         for (int i = 0; i < nums.length; i++) {
  10.                                 if (!visit[i]) {
  11.                                         return nums[i] == target;. visit 1point3acres.com for more.
  12.                                 }
  13.                         }
  14.                 } else {
  15.                         for (int i = 0; i < nums.length; i++) {
  16.                                 if (visit[i])
  17.                                         continue;
  18.                                 for (int j = i + 1; j < nums.length; j++) {
  19.                                         if (visit[j])
  20.                                                 continue;. 1point3acres.com/bbs
  21.                                         int n1 = nums[i];
  22.                                         int n2 = nums[j];. 鍥磋鎴戜滑@1point 3 acres
  23.                                         visit[j] = true;
  24.                                         nums[i] = n1 + n2;. Waral 鍗氬鏈夋洿澶氭枃绔,
  25.                                         if (helper(nums, visit, target, c - 1))
  26.                                                 return true;
  27.                                         nums[i] = n1 - n2;
  28.                                         if (helper(nums, visit, target, c - 1))
  29.                                                 return true;
  30.                                         nums[i] = n2 - n1;
  31.                                         if (helper(nums, visit, target, c - 1))
  32.                                                 return true;
  33.                                         nums[i] = n1 * n2;
  34.                                         if (helper(nums, visit, target, c - 1))
  35.                                                 return true;
  36.                                         if (n2 != 0) {
  37.                                                 nums[i] = n1 / n2;
  38.                                                 if (helper(nums, visit, target, c - 1)). more info on 1point3acres.com
  39.                                                         return true;
  40.                                         }
  41.                                         if (n1 != 0) {
  42.                                                 nums[i] = n2 / n1;. 1point 3acres 璁哄潧
  43.                                                 if (helper(nums, visit, target, c - 1))
  44.                                                         return true;
  45.                                         }
  46.                                         nums[i] = n1;
  47.                                         visit[j] = false;
  48.                                 }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  49.                         }
  50.                 }
  51.                 return false;. 1point3acres.com/bbs
  52.         }. 鍥磋鎴戜滑@1point 3 acres

  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. }. Waral 鍗氬鏈夋洿澶氭枃绔,
复制代码
回复 支持 反对

使用道具 举报

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. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
看到楼主说“每次计算得到新的数之后最好加入数组”,试着写了如下代码

额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):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
另外直接取会不会有大量重复?
回复 支持 反对

使用道具 举报

 楼主| 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, 2016-12-11 11:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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