Google面经

电面
输入是一个二维数组。要求实现 （1）set(x, y, n) 更改(x, y)值为n （2）query(x1, y1, x2, y2) 计算输出(x1, y1)为左顶点，(x2, y2)为右底点的子二维数组内所有数的和
例子：
1 2 3
4 5 6
7 8 9
query(1, 1, 2, 2) = 5 + 6 + 8 +9 = 28;
考虑（1） set很多， query很少（2）set很少，query很多

onsite
1. 给一个字典，找出两个单词满足条件（1）没有相同的字母（2）长度的乘积最大
2. Serialize an N-ary Tree 将树存到文件里，要求可以还原。
3. Stock + House robber 结合题 可以无限买卖，但卖了之后要至少隔一天才能买
4. Word Abbreviation 单词中连续的字符串可以用它的长度代替， 例如 abbreviation 可以为 a1breviation a2reviation 1bbreviation abbrevia4

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

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

]). 最后返回unhold[n-1]。当然可以优化空间啦

补充内容 (2015-9-1 10:13):
更正 上面是hold[i] = max(hold[i-1], unhold[i-2] - price[i]) 和 unhold[i] = max(uphold[i-1], hold[i-1] + price[i])

补充内容 (2015-9-1 10:21):
吞字。。。不明觉厉。。。hold[ i ] = max(hold[i-1], unhold[i-2] - price[ i ]) 和 unhold[ i ] = max(uphold[i-1], hold[i-1] + price[ i ])

吞字。。。不明觉厉。。。hold[ i ] = max(hold[i-1], unhold[i-2] - price[ i ]) 和 unhold[ i ] = max(uphold[i-1], hold[i-1] + price[ i ])

alucardzhou 发表于 2015-8-26 03:14
请问楼主能贴出网上那个答案的链接么？十分感谢

你可以搜一下树状数组，这题就是用树状数组可以达到，更新和取和都是log(n)的复杂度

哇 。 你怎么不给我加分啊

买股票的那题的代码

1. //卖完后间隔一天才能买
   
2. int stockDP(vector<int> prices) {
   
3.         if (prices.size() < 0) {
   
4.                 return 0;
   
5.         }
   
6. 
   
7.         vector<int> t(2, 0); // 0 means hold, 1 means unhold
   
8.         vector<vector<int>> dp(prices.size(), t);
   
9. 
   
10.         // dp[i][0] = max(dp[i-1][0], dp[i-2][1] - prices[i])
    
11.         // dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])
    
12.         dp[0][0] = -prices[0];
    
13.         dp[0][1] = 0;
    
14.         for (int i = 1; i < prices.size(); i ++) {
    
15.                 // Case 1: hold
    
16.                 if (i == 1) {
    
17.                         dp[i][0] = max(dp[i-1][0], -prices[i]);
    
18.                 } else {
    
19.                         dp[i][0] = max(dp[i-1][0], dp[i-2][1] - prices[i]);
    
20.                 }
    
21.                 // Case 2: unhold
    
22.                 dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
    
23.         }
    
24.         return dp[prices.size()-1][1];
    
25. }
    
26. 
    
27. void test() {
    
28.         vector<int> prices;
    
29.         prices.push_back(1);
    
30.         prices.push_back(2);
    
31.         cout << stockDP(prices) << endl; // 1
    
32.         prices.push_back(3);
    
33.         prices.push_back(4);
    
34.         cout << stockDP(prices) << endl; // 3
    
35. 
    
36.         vector<int> prices2;
    
37.         prices2.push_back(1);
    
38.         prices2.push_back(3);
    
39.         prices2.push_back(1);
    
40.         prices2.push_back(4);
    
41.         cout << stockDP(prices2) << endl; // 3
    
42. 
    
43.         vector<int> prices3;
    
44.         prices3.push_back(4);
    
45.         prices3.push_back(3);
    
46.         prices3.push_back(2);
    
47.         prices3.push_back(1);
    
48.         cout << stockDP(prices3) << endl; // 0
    
49. }

复制代码

恭喜楼主，word abbreviation 这题怎么破啊。

感觉怎么排列好像都有重复

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

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

adamru 发表于 2015-8-26 01:56
我是这么做的：
如果单词长度为N, 可以分别选0，1，2 。。。N个字母进行缩写。对于选K个字母，就是N个中 ...

膜拜，大牛，我回去好好想想。

楼主，第一题不考虑set多query少或者set少query多的话，很好做。要是考虑的话怎么破。。。。。求

adamru 发表于 2015-8-26 01:56
我是这么做的：
如果单词长度为N, 可以分别选0，1，2 。。。N个字母进行缩写。对于选K个字母，就是N个中 ...

大神，如果直接从N中取K个的话，怎么保证取出来的是连续的呢？

maxnima 发表于 2015-8-26 02:04
膜拜，大牛，我回去好好想想。

楼主很水的。。。

maxnima 发表于 2015-8-26 02:04
膜拜，大牛，我回去好好想想。

也可以这么想，每个字母可能被缩写了，也可能没被缩写，所以最后是2^n个。

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

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