一亩三分地论坛

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

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

11.12 Snapchat电面

[复制链接] |试试Instant~ |关注本帖
qxynimo 发表于 2015-11-17 12:38:57 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Snapchat - 内推 - 技术电面 |Fail在职跳槽

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

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

x
面试用的google hangout video call.看起来像个国人大叔,稍微迟到了几分钟.
随便聊了一句之前干的啥直接上题。

注意他家的题目是在一个可编译运行的在线coding界面上写,需要自己写 header, main函数,test cases...

第一题是找Amicable Number Pairs
就是 数A 的所有因数(包括1,不包括A) 之和 等于 B。B的所有因数之和又刚好为A。 且 A != B.
求[1, N] 中所有符合条件的pair

这题没见过,上来没想到有什么好方法就用了brute force. 问时间复杂度,答N^2, 问能否改进,答不上来。
他说那就先来第二道,有时间再回来想。. visit 1point3acres.com for more.

第二题是basic calculater II 的简化版,. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
给一个string, 保证里面仅有+ - * / 四种符号,且数字均只有1位(0~9)。没有空格和其他invalid char. 求结果。
跪在这里了。。
一开始想错了,不知道为啥上来就用了recursive, 写好了后写了几个test case 发现不对,有点慌。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
然后慢慢debug,终于发现应该用iterative,正在改就没时间了。。
. from: 1point3acres.com/bbs
总结:一定要冷静想好了在开始coding。。。

第一题后来面试想到了一个NlogN的方法,估计应该是他想要的了。。。。

最后祝大家招工顺利!

评分

3

查看全部评分

silenceleaf 发表于 2015-11-17 15:14:46 | 显示全部楼层
第二题我写了下代码,就是第一遍先算所有乘除,第二遍算加减,楼主你说的iterative是这样吗?另外我不明白为什么规定每个数字只有一位,经过运算之后不就超过一位了吗?我没用到这个条件不知道对不对。忘楼主指点!
另外第一题求nlongn解法,完全没思路啊!
  1. class Solution{
  2.     public static int basicCalculator(String s){
  3.         if(s==null||s.length()==0)
  4.             return 0;
  5.         int numOneStart, numOneEnd, numTwoStart, numTwoEnd;
  6.         numOneStart = numOneEnd = numTwoStart = numTwoEnd = 0;. 1point3acres.com/bbs
  7.         while(numOneStart<s.length()){
    . visit 1point3acres.com for more.
  8.             numOneEnd = numOneStart;. Waral 鍗氬鏈夋洿澶氭枃绔,
  9.             while(numOneEnd<s.length()&&s.charAt(numOneEnd)>='0'&&s.charAt(numOneEnd)<='9') numOneEnd++;
  10.             if(numOneEnd==s.length())
  11.                 break;
  12.             char symbol = s.charAt(numOneEnd); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  13.             if(symbol=='+'||symbol=='-'){
  14.                 numOneStart = numOneEnd+1;
  15.                 continue;
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  16.             }
  17.             numTwoStart = numTwoEnd = numOneEnd+1;
  18.             while(numTwoEnd<s.length()&&s.charAt(numTwoEnd)>='0'&&s.charAt(numTwoEnd)<='9') numTwoEnd++;
  19.             int num1 = Integer.parseInt(s.substring(numOneStart, numOneEnd));
  20.             int num2 = Integer.parseInt(s.substring(numTwoStart, numTwoEnd));
  21.             int result = calculator(num1, num2, symbol);
  22.             s = s.substring(0, numOneStart)+Integer.toString(result)+s.substring(numTwoEnd, s.length());
  23.         }-google 1point3acres
  24.         
  25.         numOneStart = numOneEnd = numTwoStart = numTwoEnd = 0;
  26.         while(numOneStart<s.length()){
  27.             //System.out.println("bbb");
  28.             numOneEnd = numOneStart;
  29.             while(numOneEnd<s.length()&&s.charAt(numOneEnd)>='0'&&s.charAt(numOneEnd)<='9') numOneEnd++;
  30.             if(numOneEnd==s.length())
  31.                 return Integer.parseInt(s.substring(numOneStart, numOneEnd));
  32.             char symbol = s.charAt(numOneEnd);
  33.             numTwoStart = numTwoEnd = numOneEnd+1;
  34.             while(numTwoEnd<s.length()&&s.charAt(numTwoEnd)>='0'&&s.charAt(numTwoEnd)<='9') numTwoEnd++;
  35.             int num1 = Integer.parseInt(s.substring(numOneStart, numOneEnd));
  36.             int num2 = Integer.parseInt(s.substring(numTwoStart, numTwoEnd));
  37.             int result = calculator(num1, num2, symbol);
  38.             s = s.substring(0, numOneStart)+Integer.toString(result)+s.substring(numTwoEnd, s.length());
  39.         }        . 1point 3acres 璁哄潧
  40.         return 0;
  41.     }
  42.     . visit 1point3acres.com for more.
  43.     private static int calculator(int num1, int num2, char symbol){
  44.         switch (symbol){
  45.             case '+':
  46.                 return num1+num2;
  47.             case '-':
  48.                 return num1-num2;
  49.             case '*':
  50.                 return num1*num2;
  51.             case '/':
  52.                 if(num2==0)
  53.                     throw new IllegalArgumentException("Argument 'divisor' is 0");
  54.                 return num1/num2;
  55.         }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  56.         return 0;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  57.     }
  58.     . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  59.     public static void main(String[] argv){
  60.         String input = "11+22*3/11/2";
  61.         System.out.println(basicCalculator(input));
  62.     }
  63. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| qxynimo 发表于 2015-11-18 03:51:25 | 显示全部楼层
silenceleaf 发表于 2015-11-17 15:14
第二题我写了下代码,就是第一遍先算所有乘除,第二遍算加减,楼主你说的iterative是这样吗?另外我不明白 ...

一位指的是 每个number只有一位 即 0<= num <= 9

这只是稍微简化了一下题目, 本质上 和 Leetcode 的 Basic Calculater II 没有任何区别。你可以稍微改一下你的 code去测那道题。
. from: 1point3acres.com/bbs
第一题 从 每个因数开始 sum up出每个数的和:
对于因数 1, 每个数字都有1, 所以每个数字的和++;  iterative N 次-google 1point3acres
对于因数 2, 4,6,8,10,12.... 有2, 这些数字的和 +=2; iterative N/2 次. from: 1point3acres.com/bbs
对于因数 3, 6,9,12,15,18.... 有3, 这些数字的和 +=3; iterative N/3 次. more info on 1point3acres.com
.
.
对于因数N/2 只有N有, N的和 += N; iterative 1 次

总次数: O(N * (1 + 1/2 + 1/3 + .... 1/N)) = O(N(logN))
. from: 1point3acres.com/bbs
补充内容 (2015-11-18 03:53):.1point3acres缃
最后一个 应该是 += N/2, 写错了
回复 支持 反对

使用道具 举报

silenceleaf 发表于 2015-11-18 04:23:48 | 显示全部楼层
qxynimo 发表于 2015-11-18 03:51. more info on 1point3acres.com
一位指的是 每个number只有一位 即 0

受教了!多谢!楼主加油!
回复 支持 反对

使用道具 举报

yjfox 发表于 2015-11-18 05:53:14 | 显示全部楼层
O(N * (1 + 1/2 + 1/3 + .... 1/N)) = O(N(logN))

这个要用到调和级数相关知识吧
回复 支持 反对

使用道具 举报

 楼主| qxynimo 发表于 2015-11-18 06:05:18 | 显示全部楼层
yjfox 发表于 2015-11-18 05:53. from: 1point3acres.com/bbs
O(N * (1 + 1/2 + 1/3 + .... 1/N)) = O(N(logN))

这个要用到调和级数相关知识吧

我感觉当N很大时: 1 + 1/2 + 1/3 + .... 1/N 约等于 对1/x 从 1到N 积分
回复 支持 反对

使用道具 举报

yjfox 发表于 2015-11-18 09:19:49 | 显示全部楼层
qxynimo 发表于 2015-11-18 06:05
我感觉当N很大时: 1 + 1/2 + 1/3 + .... 1/N 约等于 对1/x 从 1到N 积分

有个公式好像是 S(n) = 1 + 1/2 + 1/3 + ,,,+ 1/n = ln(n + 1) + r(常数,~0.5). 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

pennlio 发表于 2015-11-19 00:08:13 | 显示全部楼层
qxynimo 发表于 2015-11-18 03:51. 1point3acres.com/bbs
一位指的是 每个number只有一位 即 0

nlog(n)的方法很巧妙。但是太理解产生pair的过程,特此请教。我的理解是logn的时间可以算出所有1-N的数字的因数和。但是产生pair的话,还需对有共同因数和的数字,逐个比较。最差的情况是不是还是O(n^2)的遍历啊?
回复 支持 反对

使用道具 举报

 楼主| qxynimo 发表于 2015-11-19 05:39:51 | 显示全部楼层
pennlio 发表于 2015-11-19 00:08
nlog(n)的方法很巧妙。但是太理解产生pair的过程,特此请教。我的理解是logn的时间可以算出所有1-N的数字 ...

算的时候就把每个数的因数和存到一个数组里,int factorSum[N].
对 1 <= i <= N, 比较 i 是否等于 factorSum[factorSum] 即可 这一步是O(N)
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
补充内容 (2015-11-19 05:41):
i == factorSum [ [ factorSum [ i ] ]
回复 支持 反对

使用道具 举报

haifengc 发表于 2016-1-22 01:41:17 | 显示全部楼层
第一题brute force不怎么理解是O(n^2)

如果两两比较的话,感觉应该是O(n^2×sqrt(n)).鐣欏璁哄潧-涓浜-涓夊垎鍦
O(n^2.5)

是这样理解吗,谢谢楼主
回复 支持 反对

使用道具 举报

 楼主| qxynimo 发表于 2016-1-22 02:49:47 | 显示全部楼层
haifengc 发表于 2016-1-22 01:41
第一题brute force不怎么理解是O(n^2)

如果两两比较的话,感觉应该是O(n^2×sqrt(n))
. Waral 鍗氬鏈夋洿澶氭枃绔,
算出每个数字的因数和是O(N^2)
算出来当即存到hashmap里,把hashmap过一遍找pair是O(N)
总共就是O(N^2)
回复 支持 反对

使用道具 举报

haifengc 发表于 2016-1-22 03:06:30 | 显示全部楼层
qxynimo 发表于 2016-1-22 02:49
算出每个数字的因数和是O(N^2)
算出来当即存到hashmap里,把hashmap过一遍找pair是O(N)
总共就是O(N^2)

谢谢楼主,
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 02:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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