11.12 Snapchat电面

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

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

第一题是找Amicable Number Pairs
就是 数A 的所有因数(包括1

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

正在改就没时间了。。

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

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

最后祝大家招工顺利！

第二题我写了下代码，就是第一遍先算所有乘除，第二遍算加减，楼主你说的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;
   
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()){
    
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 '-':
    
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;
    
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. }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

qxynimo 发表于 2015-11-18 03:51
一位指的是 每个number只有一位 即 0

受教了！多谢！楼主加油！

O(N * (1 + 1/2 + 1/3 + .... 1/N)) = O(N(logN))

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

yjfox 发表于 2015-11-18 05:53
O(N * (1 + 1/2 + 1/3 + .... 1/N)) = O(N(logN))

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

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

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）

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

第一题brute force不怎么理解是O(n^2）

如果两两比较的话，感觉应该是O(n^2×sqrt(n))
O(n^2.5)

是这样理解吗，谢谢楼主