一亩三分地论坛

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

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

狗狗跪经

[复制链接] |试试Instant~ |关注本帖
Tsien 发表于 2016-12-1 09:47:57 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Google - 内推 - 技术电面 Onsite |Failfresh grad应届毕业生

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

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

x
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
phone screen:
    • 听口音像是国女,上来就问有没有打开google doc,问题:add two arrays,recursion+iterative,跑了两个test cases,然后就结束了,全程30分钟左右。。。
      .鐣欏璁哄潧-涓浜-涓夊垎鍦


onsite:
  • 第一轮:韩国小哥,非常nice,humble
    • 固定正则式: a* b *, star means zero or more preceding character
    • 输入:任意字符串
    • 输出:最小replace的次数
    • 例子:
      • bbb -> 0次,因为bbb match a * b *
      • bba -> 1次,通过一次replace,得到bbb match a * b *
    • follow up:
      • 要求linear time + constant space
      • 固定正则式改为: a * b * c *, 要求linear time + constant space
      • more characters: e.g., a * b * c * d *....
      • 固定正则式的*改为+, + means at least one preceding character,do the above problems again
      • mix of * and + 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  • 第二轮:国人小哥+白人shado
    • 上来就直接做题:1D binary indexed tree; 早上刚刚做过2D的,所以很快就秒了,然后花了几分钟BIT是怎么work的。我看到小哥手中的纸有topcoder讲解BIT那章的图
    • follow up:. 鍥磋鎴戜滑@1point 3 acres
      • 实现insert(int index, int val)
      • 优化时间复杂度
  • 第三轮:国人大哥,很严肃,搞得我全程很紧张。。
    • 自我介绍
    • 莫斯code table:
      • A : * -
      • B : - * -
      • * 是1ms, -是3毫秒,每个码之间有gap,字母内的码gap=1ms,字母间的码gap=3ms
    • 输入 :莫斯code table, 一个用整型表示的莫斯code,比如[1,1,3,3,3,1,1,1,3]代表AB
    • 输出:一个用string表示的decode结果
    • 这个很简单,就说了一下,没写code
    • follow up:
      • 如果code在传输过程中发生error,假设* 变为 -的概率是p, -变为*的概率是(1-p)
      • 求概率最大的decdoe结果
      • 这个code没写完,下一轮的面试官来了,大哥跟他说要延长10分钟....鏈枃鍘熷垱鑷1point3acres璁哄潧
    • 这轮做的不好的地方是,一开始没有做好clarification
  • 第四轮:印度小哥
    • 由于上一轮延长了,这轮小哥上来就出题
    • 第一题:LC163 missing range
    • 第二题:题目背景是LC320. Generalized Abbreviation;
      • 第一小问:没让我求所有abbreviation,让我直接算一个长度为n的input string总共有多少不同的abbreviation, 2^n
      • 第二小问:给一个word list L和一个abbreviation A,求word list L中有哪几个word可以被缩写为A



Additional interview: 这个帖子里的第四轮:http://www.1point3acres.com/bbs/ ... 6orderby%3Ddateline. 1point 3acres 璁哄潧
当时看到了没怎么仔细想,没想在到谷歌的最后一个面试出现了,跪。。。. 1point 3acres 璁哄潧


评分

3

查看全部评分

本帖被以下淘专辑推荐:

 楼主| Tsien 发表于 2016-12-2 06:15:36 | 显示全部楼层
catinclay 发表于 2016-12-2 03:47
可以请问第一轮的思路吗...想了一天了
求指导呀

我当时的思路是:找一个split point, 使得这个split point左边a的个数加上右边b的个数的和最大化,这样replace的次数就是最小的了。
follow up中 a * b * c *这种情况,要从string末尾开始统计,用三个变量A, B, C分别代表使得输入string match "a*b*c*", "b*c*", "c*"这三种正则式所需要最小的replace次数,然后就是考虑指针移动时如何update这三个变量:
比如if s == 'c', then C = C, B = min(B + 1, C), A = min(A + 1, B);
其他case做类似的update
回复 支持 1 反对 0

使用道具 举报

七七要加油 发表于 2016-12-1 09:54:53 | 显示全部楼层
感觉楼主答得挺好的,怎么会跪了呢,因为headcount的问题嘛,而且onsite也答得不错,怎么还会加面。。。
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-12-1 10:35:21 | 显示全部楼层
天啊 我怎么觉得第一轮得这么难.... 鍥磋鎴戜滑@1point 3 acres

先从a*b*开始
把开头的a跟结尾的b都删除之后. 鍥磋鎴戜滑@1point 3 acres
纪录下剩下的a的总数跟b的总数. Waral 鍗氬鏈夋洿澶氭枃绔,

然后设定一个 i = 0 ~ n (n = 剩下的总长)
每次计算把i的左边全部replace成a跟i的右边全部replace b需要的次数. 1point3acres.com/bbs

这样是O(n)

然后follow up...就不会了
求教学

补充内容 (2016-12-1 12:09):. Waral 鍗氬鏈夋洿澶氭枃绔,

其实不用先删除头尾也没关系
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-12-1 12:55:08 | 显示全部楼层
为啥 感觉回答挺好的
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-12-2 03:47:31 | 显示全部楼层
可以请问第一轮的思路吗...想了一天了
求指导呀
回复 支持 反对

使用道具 举报

 楼主| Tsien 发表于 2016-12-2 06:16:19 | 显示全部楼层
七七要加油 发表于 2016-12-1 09:54
感觉楼主答得挺好的,怎么会跪了呢,因为headcount的问题嘛,而且onsite也答得不错,怎么还会加面。。。
. From 1point 3acres bbs
主要是follow up都答的不好。。。
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-12-2 07:22:27 | 显示全部楼层
Tsien 发表于 2016-12-2 06:15
我当时的思路是:找一个split point, 使得这个split point左边a的个数加上右边b的个数的和最大化,这样re ...

这方法真是太聪明了..
面试能想到真的是吊炸天....
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 15:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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