Asana OA

感谢楼主分享， 最后一题可以当作two sum来处理， 这样复杂度可以降到 O(32n) 或者 O(64n)

第四题时间复杂度O（31N）的解法

1.     public static int pairSummingToPowerOfTwo(int[] a) {
   
2.         int n = a.length;
   
3.         int count = 0;
   
4.         int[] powerOfTwos = new int[31];
   
5.         for (int i = 0; i < 31; i++) {
   
6.             powerOfTwos[i] = (int)Math.pow(2, i);
   
7.         }
   
8. 
   
9.         Set<Integer> visited = new HashSet<>();
   
10.         for (int num : a) {
    
11.             if ((num & (num - 1)) == 0) count++;
    
12.             for (int powerOfTwo : powerOfTwos) {
    
13.                 if (visited.contains(powerOfTwo - num)) count++;
    
14.             }
    
15.             visited.add(num);
    
16.         }
    
17. 
    
18.         return count;
    
19.     }

复制代码

第二题的算法可以优化一下，Divide And Conquer
时间复杂度和空间复杂度都优化了，而且更容易理解和讲清楚。

1. arr = [7,234,58100]
   
2. 
   
3. output = 18939
   
4. 
   
5. def helper(arr):
   
6.     result = 0
   
7.     for c in arr:
   
8.         result += int(reverse(c))
   
9.     return result
   
10. 
    
11. def reverse(c):
    
12.     temp = ''
    
13.     zero = ''
    
14.     while c > 0:
    
15.         if c%10 == 0 and temp == '':
    
16.             zero += str(c%10)
    
17.             c = c // 10
    
18.         else:
    
19.             temp += str(c%10)
    
20.             c = c // 10
    
21.     return temp + zero

复制代码

只能用python吗？还是可以换语言？

Smilingon 发表于 2020-9-17 03:41
只能用python吗？还是可以换语言？

可以选 zszs

damonguo 发表于 2020-9-16 14:14
可以选 zszs

Codesignal是不是看面经没用？他们随机抽题？

Smilingon 发表于 2020-9-17 05:49
Codesignal是不是看面经没用？他们随机抽题？

这个不一定吧，之前Robinhood也是codesignal，和面经有重合

第三题用preSum矩阵可以优化到O（K^2 *N), 不知道可不可以优化到O（N^2)

非常有用的信息

这家是白嫖OA吗