《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1736|回复: 18
收起左侧

google店面

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

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

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

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

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


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

补充内容 (2015-9-22 16:24):
大米

评分

2

查看全部评分

本帖被以下淘专辑推荐:

坐看云起 发表于 2015-9-23 03:17:56 | 显示全部楼层
cbwcs 发表于 2015-9-23 02:19
第一题:如果新的长度变短,就从前往后填;如果变长,就从后往前填。

有问题,BCAA这种情况,虽然字符串整体变短了,但是存在局部变长的情况。如果从前往后填,初始index1,index2都是0,就会出Bug;. 1point3acres.com/bbs
感觉不论从前往后,还是从后往前,都不完全正确;
建议两次遍历,第一次删除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;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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;. more info on 1point3acres.com

  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.     }. 1point 3acres 璁哄潧
  16.     str[new_len] = '\0';
  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;
  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];
  27.     }
  28.     return dp[n];
  29. }
复制代码
回复 支持 反对

使用道具 举报

goo 发表于 2015-9-22 15:29:19 | 显示全部楼层
感谢分享 要求边打电话边写代码吗
第二题我的代码不知道对不对
  1. int difftype(int n){.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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. }-google 1point3acres
  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:
  7.         opt[n] = 1
  8.         return 1
  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. visit 1point3acres.com for more.
有问题,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缃
觉得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 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-24 13:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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