Bloomberg 新鲜面经

xihaokai1 发表于 2016-8-4 00:24
compute a[1...27] such that a is the list of numbers 100-999 whose digit sum equals i; concatenate e ...

大神 没太看懂 能仔细说说嘛？

何打发123 发表于 2016-8-14 09:31
大神 没太看懂 能仔细说说嘛？

思路是这样的：
遍历一遍100到999的数字，对每个数字分别求三位数的和，比如100的和就是1，101的和是2，999的和是27，将这些结果放入一个表里面：
1：100
2：101，110
3：111
...
26: 998, 989, 899
27: 999
然后遍历表的每一行，对每一行中的每一个元素进行组合，比如行26，就会有这样的组合998-989, 998-899, 989-899，把结果都放到一个vector里面最后return。

flex 发表于 2016-8-14 22:29
思路是这样的：
遍历一遍100到999的数字，对每个数字分别求三位数的和，比如100的和就是1，101的和是2， ...

机智！！  如果有n位的话 9^n 个数字分类 然后再对前面的9^n配对 这里是o（1）？ 然后整体复杂度就是9^n 这样分析对吗~

何打发123 发表于 2016-8-14 23:39
机智！！  如果有n位的话 9^n 个数字分类 然后再对前面的9^n配对 这里是o（1）？ 然后整体复杂 ...

如果题目是n位的话，要求前n/2个数字和与后n/2个数字和相等，那么遍历一半的复杂度就是n/2 * 10^(n/2），然后总共有n/2 * 10个entry，假设每个entry最多会有m个元素（理论上m会很小），则整体复杂度为O(n / 2 * 10^(n/2) * n/2 * 10 * m ^2)，当n = 6的case：3*1000*30*m^2，小于暴力解法 (999999-100000) * 6
这道题有一个tricky的地方就是组合的时候，前半部的数字不能以0开头。

写了一个 求斧正~~~

1. //把1 ~999分成27组
   
2.         public void print3(){
   
3.                 HashMap<Integer, ArrayList<String>> map = new HashMap<Integer, ArrayList<String>>();
   
4.                 for(int i = 1; i <= 999; i++){
   
5.                         int sum = getSum(i);
   
6.                         ArrayList<String> arr = map.get(sum);
   
7.                         if(arr == null){
   
8.                                 arr = new ArrayList<String>();
   
9.                                 map.put(sum, arr);
   
10.                         }
    
11.                        
    
12.                         String cur = i + "";
    
13.                         //统一往前加0 否则前后都加有重复
    
14.                         while(cur.length() < 3){
    
15.                                 cur = '0' + cur;
    
16.                         }
    
17.                         arr.add(cur);
    
18.                 }
    
19.                
    
20.                 int m = 0;
    
21.                 for(int i = 100; i <= 999; i++){
    
22.                         int sum = getSum(i);
    
23.                         ArrayList<String> list = map.get(sum);
    
24.                         for(String str : list){
    
25.                                 String temp = i + str;
    
26.                                 m++;
    
27.                                 System.out.println(m + "  " + temp);
    
28.                                
    
29.                         }
    
30.                 }
    
31.         }
    
32. 
    
33. private int getSum(int k){
    
34.                 int sum = 0;
    
35.                 while(k > 0){
    
36.                         sum = sum + k%10;
    
37.                         k = k/10;
    
38.                 }
    
39.                 return sum;
    
40.         }

复制代码

何打发123 发表于 2016-8-15 00:36
写了一个 求斧正~~~

第二段的逻辑会遍历100到999并重复计算getSum，遍历HashMap应该会更好些，因为总共27个Entry，每个Entry也就几个做全排列，复杂度会好一些。我写了一个版本，和暴力法的结果验证一致，供50412种情况：

1. int getSum(int num) {
   
2.     int sum = 0;
   
3.     while (num != 0) {
   
4.         sum += num % 10;
   
5.         num = num / 10;
   
6.     }
   
7.     return sum;
   
8. }
   
9. 
   
10. vector<int> getNum() {
    
11.     vector<int> result;
    
12.     unordered_map<int, vector<int>> parts;
    
13.     for (int i = 1 ; i <= 999; i++) {
    
14.         int sum = getSum(i);
    
15.         parts[sum].push_back(i);
    
16.     }
    
17.    
    
18.     // 遍历Hash表
    
19.     for (auto entry : parts) {
    
20.         vector<int>& elements = entry.second;
    
21.         // 得到Entry中一对元素的全排列
    
22.         for (int i = 0; i < elements.size(); i++) {
    
23.             for (int j = 0; j < elements.size(); j++) {
    
24.                 int num = elements[i] * 1000 + elements[j];
    
25.                
    
26.                 // 去除0开头的数字
    
27.                 if (num >= 100000) {
    
28.                     result.push_back(num);
    
29.                 }
    
30.             }
    
31.         }
    
32.     }
    
33.    
    
34.     return result;
    
35. }

复制代码

flex 发表于 2016-8-14 22:29
思路是这样的：
遍历一遍100到999的数字，对每个数字分别求三位数的和，比如100的和就是1，101的和是2， ...

感觉是不是可以bucket select 啊？
List<Integer>[]

这题好难啊。。。怎么这么难，45分钟写一道就差不多了。

flex 发表于 2016-8-14 22:29
思路是这样的：
遍历一遍100到999的数字，对每个数字分别求三位数的和，比如100的和就是1，101的和是2， ...

100010 这个种情况怎么办呢？

cicean 发表于 2016-9-13 03:58
100010 这个种情况怎么办呢？

恩，不好意思之前有笔误，应该遍历1到999的数字，具体实现请看我之前贴的程序。
没有想到这个最优解不用担心，我当时就是暴力解，也闯到Onsite拿到Offer了。毕竟电话面试还有其他的题目，这道题的最优解算是Bonus吧。

三位和最小是1，最大是27。

当三位和为1时，有三种情况100100 100010 100001

如果给出一个三位和为n的数，如果 n < 27，则可以生成9个三位和为n+1的数，就是把这个数加上: 100100 100010 100001 10100 10010 10001 1100 1010 1001

生成过程中会有重复，用set去重

目测是对的，没细想。。。但不知道这样会快么？