一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 1281|回复: 18
收起左侧

google店面

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

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

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

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

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

补充内容 (2015-9-22 16:23):
1,2的我的做法贴在了下面
. 1point 3acres 璁哄潧
补充内容 (2015-9-22 16:24):
大米

评分

2

查看全部评分

本帖被以下淘专辑推荐:

坐看云起 发表于 2015-9-23 03:17:56 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
cbwcs 发表于 2015-9-23 02:19
.鐣欏璁哄潧-涓浜-涓夊垎鍦第一题:如果新的长度变短,就从前往后填;如果变长,就从后往前填。

有问题,BCAA这种情况,虽然字符串整体变短了,但是存在局部变长的情况。如果从前往后填,初始index1,index2都是0,就会出Bug;
感觉不论从前往后,还是从后往前,都不完全正确;
建议两次遍历,第一次删除A,并计算新长度和B的数量,第二次添加B
回复 支持 1 反对 0

使用道具 举报

fengkun666 发表于 2015-9-23 20:52:34 | 显示全部楼层
关注一亩三分地微博:
Warald
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];
    . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  14.         if (str[i] == 'b') str[j--] = str[i];
  15.     }
  16.     str[new_len] = '\0';. from: 1point3acres.com/bbs
  17.     return;
  18. }

  19. int f(int n) {
  20.     if (n < 2) return 1;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  21.     vector<int> dp(n+1);
  22.     dp[0] = dp[1] = 1;.1point3acres缃
  23.     for (int i=2; i<=n; i++) {
  24.         dp[i] = 0;
  25.         for (int j=0; j<n; j++)
  26.             dp[i] += dp[j]*dp[n-1-j];. 鍥磋鎴戜滑@1point 3 acres
  27.     }
  28.     return dp[n];
  29. }
复制代码
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

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++){. 1point3acres.com/bbs
  5. res+=difftype(i)*difftype(n-1-i);
  6. }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  7. return res;
  8. }
复制代码
重复计算很多 可以用动态规划记下计算过的值. from: 1point3acres.com/bbs
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]-google 1point3acres
  5. def findOpt(n, opt):. visit 1point3acres.com for more.
  6.     if n <=1:
  7.         opt[n] = 1
  8.         return 1-google 1point3acres
  9.     if opt[n]:
  10.         return opt[n]
  11.     re = 0
  12.     for i in range(0, n):
  13.         re += noOfBiTrees(i)*noOfBiTrees(n-1-i)
  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
觉得java 似乎做不到inplace c++才有机会?

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

使用道具 举报

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

使用道具 举报

头像被屏蔽
cc11328 发表于 2015-10-15 08:54:23 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

头像被屏蔽
cc11328 发表于 2015-10-15 09:19:05 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-28 09:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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