一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1032|回复: 18
收起左侧

google店面

[复制链接] |试试Instant~ |关注本帖
flexwang 发表于 2015-9-22 14:44:26 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
刚放下电话:
1. 给一个字符串,删除其中的a,然后把b变成bb,需要inplace的做;
2. n个节点的二叉树,有多少种结构;
3. 有多个用户反映网站太慢,请问有哪些原因?


补充内容 (2015-9-22 16:23):
1,2的我的做法贴在了下面

补充内容 (2015-9-22 16:24):. From 1point 3acres bbs
大米

评分

2

查看全部评分

本帖被以下淘专辑推荐:

坐看云起 发表于 2015-9-23 03:17:56 | 显示全部楼层
cbwcs 发表于 2015-9-23 02:19.1point3acres缃
第一题:如果新的长度变短,就从前往后填;如果变长,就从后往前填。
. from: 1point3acres.com/bbs
有问题,BCAA这种情况,虽然字符串整体变短了,但是存在局部变长的情况。如果从前往后填,初始index1,index2都是0,就会出Bug;
感觉不论从前往后,还是从后往前,都不完全正确;
建议两次遍历,第一次删除A,并计算新长度和B的数量,第二次添加B
回复 支持 1 反对 0

使用道具 举报

fengkun666 发表于 2015-9-23 20:52:34 | 显示全部楼层
if (new_len > len) return; 是字符串长度不能变长,只能变小吗?
回复 支持 1 反对 0

使用道具 举报

zwcelesta 发表于 2015-9-22 23:21:11 | 显示全部楼层
if (new_len > len) return; 是字符串长度不能变长,只能变小吗?因为必须inplace?
回复 支持 1 反对 0

使用道具 举报

 楼主| flexwang 发表于 2015-9-22 15:08:40 | 显示全部楼层
  1. void process(char *str, int len) {
  2.     int cnta = 0, cntb = 0;
  3.     for (int i=0; i<len; i++). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  4.         if (str[i] == 'a')
  5.             cnta++;
  6.         else if (str[i] == 'b') cntb++;
  7.         
  8.     int new_len = len-cnta+cntb;
  9.     if (new_len > len) return;

  10.     for (int i=aidx,j=aidx; i<len; i++)
  11.         if (str[i] != 'a') str[j++] = str[i];
  12.     for (int i=len-cnta-1,j=new_len-1; i>=0; i--) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  13.         str[j--] = str[i];-google 1point3acres
  14.         if (str[i] == 'b') str[j--] = str[i];
  15.     }
  16.     str[new_len] = '\0';
  17.     return;
  18. }
  19. .1point3acres缃
  20. int f(int n) {
  21.     if (n < 2) return 1;
  22.     vector<int> dp(n+1);
  23.     dp[0] = dp[1] = 1;
  24.     for (int i=2; i<=n; i++) {
  25.         dp[i] = 0;.1point3acres缃
  26.         for (int j=0; j<n; j++)
  27.             dp[i] += dp[j]*dp[n-1-j];
  28.     }
  29.     return dp[n];
  30. }
复制代码
回复 支持 反对

使用道具 举报

goo 发表于 2015-9-22 15:29:19 | 显示全部楼层
感谢分享 要求边打电话边写代码吗
第二题我的代码不知道对不对
  1. int difftype(int n){
  2. if(n==0) return 1;
  3. int res=0;
  4. for(int i=0;i<=n-1;i++){
  5. res+=difftype(i)*difftype(n-1-i);
  6. }
  7. return res;
  8. }
复制代码
重复计算很多 可以用动态规划记下计算过的值
1,3 期待大神解答
回复 支持 反对

使用道具 举报

mkcing 发表于 2015-9-23 01:14:46 | 显示全部楼层
3题, 一个原因, 可能是访问的人太多,  加一个load balancer,  然后后面多加几个服务器, 用load balancer 分流到这几个服务器上
回复 支持 反对

使用道具 举报

storm_hair 发表于 2015-9-23 01:21:42 | 显示全部楼层
楼主牛逼 感谢分享
回复 支持 反对

使用道具 举报

坐看云起 发表于 2015-9-23 01:37:36 | 显示全部楼层
1. 首先计算新字符串的长度,然后从后边往前填入?(java党,只能当成字符数组了)
2. 递归结局?如果要快速一些的话,可以记录搜索过的值,但是要用额外空间
回复 支持 反对

使用道具 举报

cbwcs 发表于 2015-9-23 02:19:05 | 显示全部楼层
第一题:如果新的长度变短,就从前往后填;如果变长,就从后往前填。
回复 支持 反对

使用道具 举报

snklee 发表于 2015-9-23 03:23:54 | 显示全部楼层
  1. def noOfBiTrees(n):
  2.     opt = [False for i in range(0, n+1)]
  3.     findOpt(n, opt)
  4.     return opt[n]
  5. def findOpt(n, opt):
  6.     if n <=1:. 1point 3acres 璁哄潧
  7.         opt[n] = 1
  8.         return 1
  9.     if opt[n]:
  10.         return opt[n]-google 1point3acres
  11.     re = 0
  12.     for i in range(0, n):
  13.         re += noOfBiTrees(i)*noOfBiTrees(n-1-i). 鍥磋鎴戜滑@1point 3 acres
  14.     opt[n] = re
  15.     return re
复制代码
DP with memorization
回复 支持 反对

使用道具 举报

小柯西 发表于 2015-9-23 03:34:41 | 显示全部楼层
第三题,用户反映网站过慢,有可能是因为server到用户的距离太远、网页脚本性能不好、页面需要加载的资源过大、server overload。
回复 支持 反对

使用道具 举报

cbwcs 发表于 2015-9-23 03:53:50 | 显示全部楼层
坐看云起 发表于 2015-9-23 03:17
有问题,BCAA这种情况,虽然字符串整体变短了,但是存在局部变长的情况。如果从前往后填,初始index1,ind ...

嗯有道理
回复 支持 反对

使用道具 举报

say543 发表于 2015-9-23 13:15:12 | 显示全部楼层
坐看云起 发表于 2015-9-23 03:17
有问题,BCAA这种情况,虽然字符串整体变短了,但是存在局部变长的情况。如果从前往后填,初始index1,ind ...

觉得java 似乎做不到inplace c++才有机会?
回复 支持 反对

使用道具 举报

say543 发表于 2015-9-23 13:16:40 | 显示全部楼层
第二题因该就是leetcode 的unique binary tree 但是只要计算总数卡特兰树因该可解?
回复 支持 反对

使用道具 举报

坐看云起 发表于 2015-9-23 13:37:09 | 显示全部楼层
say543 发表于 2015-9-23 13:15. 1point3acres.com/bbs
觉得java 似乎做不到inplace c++才有机会?

Java可能会给你一个较大的数组,让你利用后面的空间来实现
回复 支持 反对

使用道具 举报

mint0715 发表于 2015-9-23 13:40:31 | 显示全部楼层
对,第二题的形式解就是 Catalan
回复 支持 反对

使用道具 举报

cc11328 发表于 2015-10-15 08:54:23 | 显示全部楼层
第二题是catalyn number典型题  可以上wiki上查下
回复 支持 反对

使用道具 举报

cc11328 发表于 2015-10-15 09:19:05 | 显示全部楼层
  1. void changeStr(string &s) {
  2.     for(auto iter = s.begin(); iter != s.end();) {
  3.         if(*iter == 'a') {
  4.             iter = s.erase(iter);.1point3acres缃
  5.             continue;
  6.         }
  7.         if(*iter == 'b') {
  8.             iter = s.insert(iter, 'b');
  9.             iter = iter+2;
  10.             continue;
  11.         }
  12.         iter++;
  13.     }
  14. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 11:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表