一亩三分地论坛

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

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

2016.4.5 google phone interview

[复制链接] |试试Instant~ |关注本帖
newFeeling 发表于 2016-4-7 06:56:22 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
4月5号电面的google。 面我的是个白人大哥,说是在google已经工作了五年, 一上来问我有什么问题问一个在google工作了五年的engineer(囧 这不应该结束时在问吗), 我就把我准备好的general question 问了下, 然后简单的说了下做过的project。 然后就是在google doc上题。。。
题目是: 写一个function 求 一个数(可以是任意数) 的 root of squre。。。。 当时我就懵了,但感觉是用divide and conquer, 然后我想了一下,说了下自己的想法,然后写code. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. 1point3acres.com/bbs
我的code是
. 鍥磋鎴戜滑@1point 3 acres
public double findRoot(double n){
  int x = n;
  int y = 1;
  while(x >y){
    x = (x+y)/2;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    y = n/x;. from: 1point3acres.com/bbs
  }
  return x;
}

然后他说要我演示一下, 然后给我100让我演示, 然后我一步步演示了,证明这是可行的。-google 1point3acres

然后他要我分析下time complexity, 然后我当时挺纠结的, 纠结是不是logn,然后我说了下我的怎么想的,然后他说他觉得是logn,然后我说我不确定,我觉得可能是loglogn,然后他就没说话了。
然后他让我给几个test cases, 然后我发现我忽略了input 小于1的情况。 然后我有想了下并没有想出来, 结束后一想,发现只要把while里的condition 改成 Math.abs(x-y)>0就可以handle输入数小于1的情况了,反正当时死活没想出来。
后来在网上搜了下,好像还要考虑精度的,反正我是没考虑到这么多。  
然后时间就到了,互相说了thank you。。。。。。。我觉得我这情况应该是没戏了。。。。。。 哎,感觉这题五花八门啊,和平时刷leetcode的题都不太一样。。。。囧。。。结果还没出来,但已经不报希望了,只能说积累了些经验。大家如果有什么疑问可以问我。


补充内容 (2016-4-13 03:53):
刚刚收到google的电话, 进入onsite了, 好好准备吧

评分

1

查看全部评分

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 45
boyshone 发表于 2016-4-7 07:03:43 | 显示全部楼层
leetcode 69
回复 支持 反对

使用道具 举报

 楼主| newFeeling 发表于 2016-4-7 07:13:46 | 显示全部楼层

但leetcode 69 是给的int 输出也是int。他给的是可以是任何数,输出也可以是小数。。。应该不一样吧
回复 支持 反对

使用道具 举报

boyshone 发表于 2016-4-7 07:19:45 | 显示全部楼层
newFeeling 发表于 2016-4-7 07:13
但leetcode 69 是给的int 输出也是int。他给的是可以是任何数,输出也可以是小数。。。应该不一样吧

原理上没有任何区别阿
回复 支持 反对

使用道具 举报

Chi2829 发表于 2016-4-7 21:11:24 | 显示全部楼层
楼主是怎么想到loglogn的?... 估计大哥醉了 :p
回复 支持 反对

使用道具 举报

Alice0701 发表于 2016-4-7 22:30:04 | 显示全部楼层
感觉大思路是对的啊 白人大哥行行好说不定就过了
回复 支持 反对

使用道具 举报

 楼主| newFeeling 发表于 2016-4-7 23:13:10 | 显示全部楼层
Chi2829 发表于 2016-4-7 21:11
楼主是怎么想到loglogn的?... 估计大哥醉了 :p
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
我当时想的是如果y一直保持不变,那么就是logn。。。反正当时我感觉不是logn,总之就是没算出来
回复 支持 反对

使用道具 举报

 楼主| newFeeling 发表于 2016-4-7 23:14:34 | 显示全部楼层
Alice0701 发表于 2016-4-7 22:30
感觉大思路是对的啊 白人大哥行行好说不定就过了

希望如你所说啊:),但整个过程感觉磕磕绊绊的,而且答得不是很好,
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-4-7 23:52:23 | 显示全部楼层
楼主你的code返回的是int啊
回复 支持 反对

使用道具 举报

 楼主| newFeeling 发表于 2016-4-8 00:04:05 | 显示全部楼层
adiggo 发表于 2016-4-7 23:52 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
楼主你的code返回的是int啊

不好意思,我打的时候疏忽了, code里x和y都是double
回复 支持 反对

使用道具 举报

zpinthehouse 发表于 2016-4-8 00:18:40 | 显示全部楼层
如果不是int的话,n=0.04这种情况怎么考虑呢。。是不是先得把小于1的数转化为大于1的,算出来结果再转回去。。
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-4-8 00:21:13 | 显示全部楼层
zpinthehouse 发表于 2016-4-8 00:18
如果不是int的话,n=0.04这种情况怎么考虑呢。。是不是先得把小于1的数转化为大于1的,算出来结果再转回去 ...

设个precision0.01 条件是abs(x-y)> precision
回复 支持 反对

使用道具 举报

bin 发表于 2016-4-8 00:34:09 | 显示全部楼层
一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖!被警告三次,系统会自动封杀ID!

想支持楼主,请点击帖子下方的"好苗""分享""收藏"键,酌情给楼主加大米(系统不扣你自己的分)。
积分不够看不了帖子,请参考论坛导航里的"帮助","新手提纲"里有攒积分指南
回复 支持 反对

使用道具 举报

zpinthehouse 发表于 2016-4-8 00:44:10 | 显示全部楼层
adiggo 发表于 2016-4-8 00:21
设个precision0.01 条件是abs(x-y)> precision
. more info on 1point3acres.com
恩,这样更合理。。
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-4-8 01:22:42 | 显示全部楼层
楼主, 这个是babylonian method, running time 应该是log(log(n/p)) p是precision 比如0.01, http://stackoverflow.com/questio ... r-babylonian-method
回复 支持 反对

使用道具 举报

 楼主| newFeeling 发表于 2016-4-8 01:27:07 | 显示全部楼层
adiggo 发表于 2016-4-8 01:22. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
楼主, 这个是babylonian method, running time 应该是log(log(n/p)) p是precision 比如0.01, http://sta ...

正解!
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-4-8 01:32:40 | 显示全部楼层
newFeeling 发表于 2016-4-8 01:27. 鍥磋鎴戜滑@1point 3 acres
正解!
-google 1point3acres
我怎么觉得当时面试官肯定很囧呢。。。。哈哈
回复 支持 反对

使用道具 举报

hison7463 发表于 2016-4-8 02:01:54 | 显示全部楼层
我记得好像Java如果你直接用x>y的话会自动帮你处理精度的问题
回复 支持 反对

使用道具 举报

Chi2829 发表于 2016-4-8 02:33:53 | 显示全部楼层
newFeeling 发表于 2016-4-7 23:13-google 1point3acres
我当时想的是如果y一直保持不变,那么就是logn。。。反正当时我感觉不是logn,总之就是没算出来

楼主,是我没仔细想,不过就是仔细想估计也分析不出来。。下次如果碰到这个问题直接就扔个wiki page给面试官吧。。
回复 支持 反对

使用道具 举报

Hualiang 发表于 2016-4-11 17:03:53 | 显示全部楼层
就一题呀?祝楼主onsite
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 16:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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