《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 3037|回复: 12
收起左侧

11.12 Snapchat电面

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

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

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

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

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

注意他家的题目是在一个可编译运行的在线coding界面上写,需要自己写 header, main函数,test cases....鏈枃鍘熷垱鑷1point3acres璁哄潧

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

这题没见过,上来没想到有什么好方法就用了brute force. 问时间复杂度,答N^2, 问能否改进,答不上来。.鐣欏璁哄潧-涓浜-涓夊垎鍦
他说那就先来第二道,有时间再回来想。

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

总结:一定要冷静想好了在开始coding。。。

第一题后来面试想到了一个NlogN的方法,估计应该是他想要的了。。。。
. Waral 鍗氬鏈夋洿澶氭枃绔,
最后祝大家招工顺利!

评分

3

查看全部评分

silenceleaf 发表于 2015-11-17 15:14:46 | 显示全部楼层
第二题我写了下代码,就是第一遍先算所有乘除,第二遍算加减,楼主你说的iterative是这样吗?另外我不明白为什么规定每个数字只有一位,经过运算之后不就超过一位了吗?我没用到这个条件不知道对不对。忘楼主指点!
另外第一题求nlongn解法,完全没思路啊!
  1. class Solution{
  2.     public static int basicCalculator(String s){-google 1point3acres
  3.         if(s==null||s.length()==0)
  4.             return 0;. visit 1point3acres.com for more.
  5.         int numOneStart, numOneEnd, numTwoStart, numTwoEnd;
  6.         numOneStart = numOneEnd = numTwoStart = numTwoEnd = 0;
  7.         while(numOneStart<s.length()){
  8.             numOneEnd = numOneStart;
  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;
  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.         }
  24.         
  25.         numOneStart = numOneEnd = numTwoStart = numTwoEnd = 0;
  26.         while(numOneStart<s.length()){. visit 1point3acres.com for more.
  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.         }        
  40.         return 0;
  41.     }
  42.    
  43.     private static int calculator(int num1, int num2, char symbol){
  44.         switch (symbol){
  45.             case '+':
  46.                 return num1+num2;
  47.             case '-':-google 1point3acres
  48.                 return num1-num2;
  49.             case '*':
  50.                 return num1*num2;
  51.             case '/':
  52.                 if(num2==0). From 1point 3acres bbs
  53.                     throw new IllegalArgumentException("Argument 'divisor' is 0");
  54.                 return num1/num2;
  55.         }
  56.         return 0;
  57.     }. From 1point 3acres bbs
  58.    
  59.     public static void main(String[] argv){
  60.         String input = "11+22*3/11/2";. Waral 鍗氬鏈夋洿澶氭枃绔,
  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去测那道题。

第一题 从 每个因数开始 sum up出每个数的和:. more info on 1point3acres.com
对于因数 1, 每个数字都有1, 所以每个数字的和++;  iterative N 次. Waral 鍗氬鏈夋洿澶氭枃绔,
对于因数 2, 4,6,8,10,12.... 有2, 这些数字的和 +=2; iterative N/2 次
对于因数 3, 6,9,12,15,18.... 有3, 这些数字的和 +=3; iterative N/3 次
.
.
对于因数N/2 只有N有, N的和 += N; iterative 1 次

总次数: O(N * (1 + 1/2 + 1/3 + .... 1/N)) = O(N(logN))

补充内容 (2015-11-18 03:53):
最后一个 应该是 += N/2, 写错了
回复 支持 反对

使用道具 举报

silenceleaf 发表于 2015-11-18 04:23:48 | 显示全部楼层
qxynimo 发表于 2015-11-18 03:51
一位指的是 每个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 1point 3acres 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. 鍥磋鎴戜滑@1point 3 acres
我感觉当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)
回复 支持 反对

使用道具 举报

pennlio 发表于 2015-11-19 00:08:13 | 显示全部楼层
qxynimo 发表于 2015-11-18 03:51
一位指的是 每个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].. visit 1point3acres.com for more.
对 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)). 1point 3acres 璁哄潧
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))

算出每个数字的因数和是O(N^2)
算出来当即存到hashmap里,把hashmap过一遍找pair是O(N). From 1point 3acres bbs
总共就是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)

谢谢楼主,
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-25 04:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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