【生活质量系列】评测几款用过的咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 7202|回复: 31
收起左侧

狗狗电面八成跪经

[复制链接] |试试Instant~
我的人缘0
listen8019 发表于 2016-11-1 02:07:30 | 显示全部楼层 |阅读模式
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  95% (291)
 
 
4% (13)  踩

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

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

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

x
非中印小哥,一上来,通话质量极差,我直接让对面在google docs上打题,就这样电话中间还断了。。。. visit 1point3acres for more.
. Waral 博客有更多文章,
1. 实现浮点数数组求平均值,明显不可能加和这么简单,多问了一句是否保证不溢出,果然不保证,于是保存当前平均值,记录count,用加权的方式做的,感觉没问题,但是他还是说有问题,让我看,我没看出来,就过了。。。

2. 第二题是字符串判断是否由重复字符串组成,感觉leetcode做过,可我属于一面试就极紧张的,脑子一片空白,问最直接的暴力算法行不行,他说先实现最好,我觉给了个暴力算法直接不同长度试,然后还有10分钟让我优化,想了个DP的方法不知道对不对,repeat数组存当前字符结尾的重复字符串的长度。。

写完代码他说我觉得很clear了,时间到了,你有什么想问我的吗?问了自己比较关心的,你认为在狗狗一个好的SDE最重要的是什么素质?他说要能够搞清楚自己应该做什么的能力,还有沟通能力,当然smart也很重要。.本文原创自1point3acres论坛
. 留学申请论坛-一亩三分地
虽然刷了2遍leetcode。。。但是心理素质差,一面试就慌,脑子空白,不抱希望了,发个面经攒人品希望上周亚麻群面能过就好。。。


补充内容 (2016-11-1 04:37):
DP算法最后证明不对,欢迎各位大神提供思路。

评分

参与人数 3大米 +38 收起 理由
xiaoaideng + 3 感谢分享!
wjc + 5 感谢分享!
zzwcsong + 30

查看全部评分


上一篇:Bloomberg on campus
下一篇:万圣节 谷歌oa

本帖被以下淘专辑推荐:

我的人缘0
prodigalr 发表于 2016-11-1 02:45:12 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (24)
 
 
4% (1)  踩
楼主能具体说下第二题是什么意思吗,没看懂。
回复

使用道具 举报

我的人缘0
 楼主| listen8019 发表于 2016-11-1 02:50:14 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (291)
 
 
4% (13)  踩
prodigalr 发表于 2016-11-1 02:45.1point3acres网
楼主能具体说下第二题是什么意思吗,没看懂。
. 1point3acres
比如abab,返回真,aba,返回假,a返回假,就这个意思。
回复

使用道具 举报

我的人缘0
hellojay 发表于 2016-11-1 03:15:08 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (48)
 
 
7% (4)  踩
前排占个座,看看大神们有没有好解法,感谢楼主分享
回复

使用道具 举报

我的人缘0
reboot329 发表于 2016-11-1 03:17:54 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (84)
 
 
4% (4)  踩
pat pat...重复的那个好像LC上见过,记不清了。。

我也是心理素质超差,第一次面试的时候,碰到没做过的题,感觉自己当时完全失去思考能力……

许久才恢复……

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
destinyomgwz 发表于 2016-11-1 03:19:00 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  83% (5)
 
 
16% (1)  踩
LZ已经很好了...我和你大概同时面的,遇到新题脑海一片空白,各种往复杂想,在结束时候才发现是easy级别热身题...十成已跪。
回复

使用道具 举报

我的人缘0
 楼主| listen8019 发表于 2016-11-1 03:20:23 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (291)
 
 
4% (13)  踩
楼主的DP算法刚才在eclipse里试了下,一般测例都能跑通,O(n)复杂度,就是不知道面试小哥当时听没听懂,因为当时时间不够了。。。

补充内容 (2016-11-1 03:55):
要代码的抱歉,楼主还是怕同一考官问同一问题的概率。。。所以这道题,我会在收到拒信或者onsite后再贴出第二题DP代码。. 1point 3acres 论坛

补充内容 (2016-11-1 04:23):. 留学申请论坛-一亩三分地
哈哈,楼主发现算法是错的。不用担心小哥没听懂了。
回复

使用道具 举报

我的人缘0
南慕伦 发表于 2016-11-1 03:28:23 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (18)
 
 
0% (0)  踩
第一题楼主的做法是前k个平均数为a_k, 然后前k+1个就变成(k*a_k + n_(k+1)) / (k+1) ?. 1point 3acres 论坛
感觉这样大数a_k*k加小数n_(k+1)会导致精度丢失,特别是k大的时候

如果要精度的话 一般是分治来做吧,不过这时候复杂度就上去了

第二个感觉就是二分答案。首先把长度做因数分解,找到所有可能的子串长度,然后用二分法对某个子串长度做线性验证。所以总复杂度O(n * f(length))

f(length)是个啥函数我还没想清楚,但上界应该是log(length)

补充内容 (2016-11-1 03:48):
想了想二分答案不对……不知道你加了长度判定的优化没有。
回复

使用道具 举报

我的人缘0
 楼主| listen8019 发表于 2016-11-1 03:33:52 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (291)
 
 
4% (13)  踩
南慕伦 发表于 2016-11-1 03:28
第一题楼主的做法是前k个平均数为a_k, 然后前k+1个就变成(k*a_k + n_(k+1)) / (k+1) ?. 牛人云集,一亩三分地
感觉这样大数a_k*k ...

对,面试完了我想到涉及浮点数肯定有精度问题。。。但是面试的时候没想到。。。
回复

使用道具 举报

我的人缘0
hellojay 发表于 2016-11-1 03:39:25 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  92% (48)
 
 
7% (4)  踩
listen8019 发表于 2016-11-1 03:20
楼主的DP算法刚才在eclipse里试了下,一般测例都能跑通,O(n)复杂度,就是不知道面试小哥当时听没听懂,因 ...

楼主能贴一下程序吗
回复

使用道具 举报

我的人缘0
zhan1612 发表于 2016-11-1 05:21:09 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (2)
 
 
0% (0)  踩
第一题的话(k*a_k + n_(k+1)) / (k+1) 这样做是不是还会有溢出, 假设前k+1个数全部是最大浮点数这样就溢出了, 我想了一下但是没有办法处理精度, 大家给看看精度怎么处理:
第一个是 average(k) + (nums[k+1] -average(k))/(k+1) 这个也会溢出, 在average(K) 为最小的负数, nums[k+1] 为最大正数的时候
第二个是 nums[0]/len + nums[1]/len + .....+ nums[n-1]/n  这个不会溢出但是精度就太差了。. 牛人云集,一亩三分地
.本文原创自1point3acres论坛
麻烦问下楼主第二题的 如果字符串是“ababa”这时候结果应该返回什么, 因为“ababa"重复字符串是aba

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-11-1 06:24:13 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
1% (1)  踩
listen8019 发表于 2016-11-1 03:20
楼主的DP算法刚才在eclipse里试了下,一般测例都能跑通,O(n)复杂度,就是不知道面试小哥当时听没听懂,因 ...

第二题:查了一下,n的divisor的个数是O(log n/log(log n)),每个divisor都可能是repeating pattern的length L. 对于每个L对原始string s做if (s == s[i%L])的check (O(n)),最终时间复杂度O(n*log n/log(log n)).
若用dp(i) = s.substr(0, i)的最短repeating pattern length的话,那么光从dp(1)循环到dp(n)就是O(n)的,每次计算dp(k)的时候还是得检查每个i的divisor啊,那么DP怎么做到整体时间为O(n)呢?还是把 O(log n/log(log n))直接看成常数?
我的非DP算法(未debug):
  1. bool hasRepeatingPattern(string& s) {
  2.   int n = s.length();

  3.   // get all divisors < n: divisors.size() = O(log n/log(log n))
  4.   vector<int> divisors; int divisor = 1;
  5.   while (divisor++ <= n/2) if (n%divisor == 0) divisors.push_back(divisor);

  6.   // check repeating pattern of length for each divisor. 留学申请论坛-一亩三分地
  7.   for (int d : divisors) { // O(log n/log(log n)). Waral 博客有更多文章,
  8.     int i = 0;
  9.     while (i < n) if (s[i] != s[i%d]) break; else i++; // O(n). Waral 博客有更多文章,
  10.     if (i == n) return true; // repeating pattern has length d
  11.   }
  12.   return false; // no repeating pattern
  13. }
复制代码
回复

使用道具 举报

我的人缘0
 楼主| listen8019 发表于 2016-11-1 06:26:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (291)
 
 
4% (13)  踩
zhan1612 发表于 2016-11-1 05:21-google 1point3acres
第一题的话(k*a_k + n_(k+1)) / (k+1) 这样做是不是还会有溢出, 假设前k+1个数全部是最大浮点数这样就溢出 ...

这个可能要当场喝面试官确认吧,我没想到这种情况。。。
回复

使用道具 举报

我的人缘0
sophie0815 发表于 2016-11-1 06:50:02 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (7)
 
 
12% (1)  踩
在geekforgeek上看到这道题 http://www.geeksforgeeks.org/find-given-string-can-represented-substring-iterating-substring-n-times/ 用的是KMP构造prefix array  感觉要现场想很难吧?
回复

使用道具 举报

我的人缘0
33847682 发表于 2016-11-1 07:19:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  68% (77)
 
 
31% (35)  踩
楼上正解 这题刚看感觉是可能跟kmp有关但是后面具体怎么算面试的时候真心很难想出来啊
回复

使用道具 举报

我的人缘0
sophie0815 发表于 2016-11-1 07:35:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (7)
 
 
12% (1)  踩
33847682 发表于 2016-11-1 07:19
楼上正解 这题刚看感觉是可能跟kmp有关但是后面具体怎么算面试的时候真心很难想出来啊

同觉得 感觉和prefix suffix有关 想到这个 关键对这个算法不是很熟 不是很会用呀  
回复

使用道具 举报

我的人缘0
33847682 发表于 2016-11-1 07:48:10 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  68% (77)
 
 
31% (35)  踩
sophie0815 发表于 2016-11-1 07:35
同觉得 感觉和prefix suffix有关 想到这个 关键对这个算法不是很熟 不是很会用呀
. 牛人云集,一亩三分地
哎 真心看人品 话说最近貌似狗家很多题都是从g4g上面扒下来的
回复

使用道具 举报

我的人缘0
lby1989825 发表于 2016-11-1 07:49:08 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (36)
 
 
12% (5)  踩
zhan1612 发表于 2016-11-1 05:21
第一题的话(k*a_k + n_(k+1)) / (k+1) 这样做是不是还会有溢出, 假设前k+1个数全部是最大浮点数这样就溢出 ...

我也觉得这题好难啊,溢出和精度是无法同时保证的
回复

使用道具 举报

我的人缘0
zzgzzm 发表于 2016-11-1 11:17:51 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (63)
 
 
1% (1)  踩
sophie0815 发表于 2016-11-1 06:50
在geekforgeek上看到这道题 http://www.geeksforgeeks.org/find-given-string-can-represented-substring-i ...
. 一亩-三分-地,独家发布
感觉除非是自己和面试官提前都知道这个算法,否则就算当时讲都讲不清楚啊。这真的是电面吗……
回复

使用道具 举报

我的人缘0
yhatl 发表于 2016-11-2 09:58:59 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  33% (3)
 
 
66% (6)  踩
listen8019 发表于 2016-11-1 02:50
比如abab,返回真,aba,返回假,a返回假,就这个意思。
. more info on 1point3acres
aba不该是真吗?是要substring.size()>1吗
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

GMT+8, 2018-9-21 04:22

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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