一亩三分地论坛

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

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

G电面

[复制链接] |试试Instant~ |关注本帖
dg7743 发表于 2016-7-14 10:05:51 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 本科 全职@Google - 网上海投 - 技术电面 |Pass在职跳槽

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

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

x
今天早上刚完成G的电面。
题目格外的简单。
第一题就是LeetCode No.66 Plus One。唯一的区别在于argument和return value是string。
string plusOne(string s) {
  ...
  return s;
}

我写的代码就是讨论区里最高票的那个版本。
需要注意的是,写完后,问我time complexity。best case O(1),worst case O(n)都很简单明了。
average case我回答错了。只有digit是9的情况我们才会遍历next digit,如果不是9我们就直接返回结果。
而每一位digit是9的概率是10%,对于任意input来说,average runtime 的期望是1 + 0.1(1 + 0.1(1 + 0.1(1 + 0.1(......)))) => 1.11111111.....。
. visit 1point3acres.com for more.而这个结果是一个常数,所以average case是O(1)。
然后又问我,return s是不是一个额外的O(n)的操作。
我回答,对于C++11来说,这是一个O(1)的操作,因为我们return的是一个local variable,compiler会对此进行RVO (return value optimization)。. from: 1point3acres.com/bbs
他听后十分激动的说"you are the only one that gets the right answer in a very long time!"听到这句话我觉得拿到onsite应该没问题了。
然后又让我写了写BST最基本的操作。
让我问问题时,我就问了问google c++ style guide中不鼓励使用exception,那你们平常工作中怎么handle errors。
下午recruitor就告诉我拿到onsite了。


补充内容 (2016-7-14 12:16):. from: 1point3acres.com/bbs
这里RVO的意义不准确,勘误见地基。
readman 发表于 2016-7-14 10:15:37 | 显示全部楼层
那个...所以return s在java中是o(n)?
回复 支持 反对

使用道具 举报

 楼主| dg7743 发表于 2016-7-14 10:22:39 | 显示全部楼层
readman 发表于 2016-7-14 10:15
那个...所以return s在java中是o(n)?

copy string的操作是O(n),他之所以问是不是O(n),其实是想问返回时会不会有一个额外的copy操作。C++11有个优化,节省了这个操作,古老的C++是没有这个优化的。我不了解Java,但我觉得这个优化Java应该很早就有。用Java应该也不会被问这个问题吧。.鐣欏璁哄潧-涓浜-涓夊垎鍦
回复 支持 反对

使用道具 举报

readman 发表于 2016-7-14 10:35:18 | 显示全部楼层
dg7743 发表于 2016-7-14 10:22
copy string的操作是O(n),他之所以问是不是O(n),其实是想问返回时会不会有一个额外的copy操作。C++11有 ...

java里string immutable的..返回一个改动后的string, 确实需要copy下.难道这个也考.....
回复 支持 反对

使用道具 举报

 楼主| dg7743 发表于 2016-7-14 11:08:26 | 显示全部楼层
readman 发表于 2016-7-14 10:35
java里string immutable的..返回一个改动后的string, 确实需要copy下.难道这个也考.....
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
主要我这个面试官本身就是C++ library组的,我又使用C++解题,他可能就比较扣细节。看地里面经Google一般也不问这么细。
回复 支持 反对

使用道具 举报

sfsttz 发表于 2016-7-14 11:12:37 | 显示全部楼层
rvo和是不是c++11没有关系
回复 支持 反对

使用道具 举报

 楼主| dg7743 发表于 2016-7-14 12:15:11 | 显示全部楼层
sfsttz 发表于 2016-7-14 11:12
rvo和是不是c++11没有关系

对,我这里说错了,我对RVO理解有误。我当时回答没有提到RVO。我的意思是,比如string res = plusOne(string in); 当plusOne返回时,compiler会把plusOne的返回值最为RValue Reference来看待,然后传到res的operator=中。res会直接用这个返回值,而不是再新建一个。
回复 支持 反对

使用道具 举报

say543 发表于 2016-7-15 12:28:08 | 显示全部楼层
time complexity的期望值 照LZ 的分析 不是因该是 0.9 * 1 + 0.1(2+0.1(3+0.1(.....)) ? 还是我想错
回复 支持 反对

使用道具 举报

 楼主| dg7743 发表于 2016-7-15 14:05:31 | 显示全部楼层
say543 发表于 2016-7-15 12:28
time complexity的期望值 照LZ 的分析 不是因该是 0.9 * 1 + 0.1(2+0.1(3+0.1(.....)) ? 还是我想错

1是指一次比较的操作,不管digit是不是9,我们都会做这步操作。如果digit是9,我们至少会再进行一次O(1)的比较。所以是1 + 0.1(1 + 0.1(1 + ......))
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 06:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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