bloomberg 电面

刚挂的电话。面试官国人大哥，人很好一直给我提示，可是本人太水第二道还是没做出来

1. 在一个先上升后下降的数组里找target， 要求 speed < O(n)
e.g. 在数组 [1,2,3,4,5,19,18,17,16,15] 中找16，
做法是先O(log(n)) 找到peak， 然后if peak == target, return peak index; else if target < peak, 在peak的左边binary search;

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

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

估计是挂了，move on...



补充内容 (2017-8-4 09:41):
不好意思刚复习第二题时发现做法是错的，因为如果每次都把前三位的所有组合算进后三位的组合数里的话会出现重复。比如123的话如果把六个组合都加到后三位里，循环到321的时候又会放一遍。字数不够了解决办法放回复

1. private static int getSameSum() {
   
2.         int[] mapLeft = new int[27];
   
3.         int[] mapRight = new int[27];
   
4. 
   
5.         int seed = 1;
   
6.         while (seed < 1000) {
   
7.             int sum = seed / 100 + seed / 10 % 10 + seed % 10;
   
8.             if (seed >= 100) mapLeft[sum - 1]++;
   
9.             mapRight[sum - 1]++;
   
10.             seed++;
    
11.         }
    
12. 
    
13.         int res = 0;
    
14.         for (int i = 0; i < 27; i++) {
    
15.             res += mapLeft[i] * mapRight[i];
    
16.         }
    
17.         return res;
    
18.     }

复制代码

可以用dp做，生成两个dp matrix, 一个记前3位，一个记后3位。dp[i][j] 就是前i位digit 和为j的方案数。  两个dp matrix 初始化稍微不一样。
时间复杂度O(3*28*10)

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. using namespace std;
   
5. 
   
6. int sumDigit(int x) {
   
7.     int ans = 0;
   
8.     while(x != 0) {
   
9.         ans += x % 10;
   
10.         x /= 10;
    
11.     }
    
12.     return ans;
    
13. }
    
14. 
    
15. int brutalForce() {
    
16.     int ans = 0;
    
17.     for(int i = 100; i <= 999; i++) {
    
18.         for(int j = 1; j <= 999; j++) {
    
19.             if(sumDigit(i) == sumDigit(j)) {
    
20.                 ans++;
    
21.             }
    
22.         }
    
23.     }
    
24.     return ans;
    
25. }
    
26. 
    
27. int betterSoln() {
    
28.     vector<vector<int>> firstHalf(3, vector<int>(28, 0)), secondHalf(3, vector<int>(28, 0)); // firstHalf[i][j], 前i位digit 和为j的方案
    
29.     for(int j = 0; j <= 9; j++) {
    
30.         if(j > 0) firstHalf[0][j] = 1;
    
31.         secondHalf[0][j] = 1;
    
32.     }
    
33.     for(int i = 1; i < 3; i++) {
    
34.         for(int j = 0; j <= 27; j++) {
    
35.             for(int d = 0; d <= 9; d++) {
    
36.                 if(j-d >= 0) {
    
37.                     firstHalf[i][j] += firstHalf[i-1][j-d];
    
38.                     secondHalf[i][j] += secondHalf[i-1][j-d];
    
39.                 }
    
40.             }
    
41.         }
    
42.     }
    
43.     int ans = 0;
    
44.     for(int s = 1; s <= 27; s++) {
    
45.         ans += firstHalf[2][s] * secondHalf[2][s];
    
46.     }
    
47.     return ans;
    
48. }
    
49. 
    
50. int main(int argc, const char * argv[]) {
    
51.     // insert code here...
    
52.     cout << brutalForce() << endl;
    
53.     cout << betterSoln() << endl;
    
54.     return 0;
    
55. }
    

复制代码

第一题似乎如果peak != target, 需要两边各自跑一个binary search，而不是if else

谢谢 楼主分享啦 感觉第二题比一般的BB onsite的题都要难一点 楼主加油

chaseqi 发表于 2017-7-3 14:56
谢谢 楼主分享啦 感觉第二题比一般的BB onsite的题都要难一点 楼主加油

那道题是BB的高频题，很多组都用，尤其是MARS组，面之前一定要看这道。。。

您好！
本帖隐藏的内容需要积分高于 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

请问下这个题目leetcode上有原题么？

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

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

请问楼主bb不同的组，可以连续面没有冷冻期的吗？