一亩三分地论坛

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

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

狗狗电面八成跪经

[复制链接] |试试Instant~ |关注本帖
listen8019 发表于 2016-11-1 02:07:30 | 显示全部楼层 |阅读模式

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

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

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

x
非中印小哥,一上来,通话质量极差,我直接让对面在google docs上打题,就这样电话中间还断了。。。

1. 实现浮点数数组求平均值,明显不可能加和这么简单,多问了一句是否保证不溢出,果然不保证,于是保存当前平均值,记录count,用加权的方式做的,感觉没问题,但是他还是说有问题,让我看,我没看出来,就过了。。。

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

写完代码他说我觉得很clear了,时间到了,你有什么想问我的吗?问了自己比较关心的,你认为在狗狗一个好的SDE最重要的是什么素质?他说要能够搞清楚自己应该做什么的能力,还有沟通能力,当然smart也很重要。

虽然刷了2遍leetcode。。。但是心理素质差,一面试就慌,脑子空白,不抱希望了,发个面经攒人品希望上周亚麻群面能过就好。。。
-google 1point3acres

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

评分

1

查看全部评分

本帖被以下淘专辑推荐:

prodigalr 发表于 2016-11-1 02:45:12 | 显示全部楼层
楼主能具体说下第二题是什么意思吗,没看懂。
回复 支持 反对

使用道具 举报

 楼主| listen8019 发表于 2016-11-1 02:50:14 | 显示全部楼层
prodigalr 发表于 2016-11-1 02:45
楼主能具体说下第二题是什么意思吗,没看懂。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
比如abab,返回真,aba,返回假,a返回假,就这个意思。
回复 支持 反对

使用道具 举报

hellojay 发表于 2016-11-1 03:15:08 | 显示全部楼层
前排占个座,看看大神们有没有好解法,感谢楼主分享
回复 支持 反对

使用道具 举报

reboot329 发表于 2016-11-1 03:17:54 | 显示全部楼层
pat pat...重复的那个好像LC上见过,记不清了。。

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

许久才恢复……
回复 支持 反对

使用道具 举报

destinyomgwz 发表于 2016-11-1 03:19:00 | 显示全部楼层
LZ已经很好了...我和你大概同时面的,遇到新题脑海一片空白,各种往复杂想,在结束时候才发现是easy级别热身题...十成已跪。
回复 支持 反对

使用道具 举报

 楼主| listen8019 发表于 2016-11-1 03:20:23 | 显示全部楼层
楼主的DP算法刚才在eclipse里试了下,一般测例都能跑通,O(n)复杂度,就是不知道面试小哥当时听没听懂,因为当时时间不够了。。。. 1point 3acres 璁哄潧

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

补充内容 (2016-11-1 04:23):
哈哈,楼主发现算法是错的。不用担心小哥没听懂了。
回复 支持 反对

使用道具 举报

南慕伦 发表于 2016-11-1 03:28:23 | 显示全部楼层
第一题楼主的做法是前k个平均数为a_k, 然后前k+1个就变成(k*a_k + n_(k+1)) / (k+1) ?
感觉这样大数a_k*k加小数n_(k+1)会导致精度丢失,特别是k大的时候
. from: 1point3acres.com/bbs
如果要精度的话 一般是分治来做吧,不过这时候复杂度就上去了

第二个感觉就是二分答案。首先把长度做因数分解,找到所有可能的子串长度,然后用二分法对某个子串长度做线性验证。所以总复杂度O(n * f(length)) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
f(length)是个啥函数我还没想清楚,但上界应该是log(length)

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

使用道具 举报

 楼主| listen8019 发表于 2016-11-1 03:33:52 | 显示全部楼层
南慕伦 发表于 2016-11-1 03:28
第一题楼主的做法是前k个平均数为a_k, 然后前k+1个就变成(k*a_k + n_(k+1)) / (k+1) ?
感觉这样大数a_k*k ...

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

使用道具 举报

hellojay 发表于 2016-11-1 03:39:25 | 显示全部楼层
listen8019 发表于 2016-11-1 03:20
楼主的DP算法刚才在eclipse里试了下,一般测例都能跑通,O(n)复杂度,就是不知道面试小哥当时听没听懂,因 ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
楼主能贴一下程序吗
回复 支持 反对

使用道具 举报

zhan1612 发表于 2016-11-1 05:21:09 | 显示全部楼层
第一题的话(k*a_k + n_(k+1)) / (k+1) 这样做是不是还会有溢出, 假设前k+1个数全部是最大浮点数这样就溢出了, 我想了一下但是没有办法处理精度, 大家给看看精度怎么处理:
第一个是 average(k) + (nums[k+1] -average(k))/(k+1) 这个也会溢出, 在average(K) 为最小的负数, nums[k+1] 为最大正数的时候. more info on 1point3acres.com
第二个是 nums[0]/len + nums[1]/len + .....+ nums[n-1]/n  这个不会溢出但是精度就太差了。

麻烦问下楼主第二题的 如果字符串是“ababa”这时候结果应该返回什么, 因为“ababa"重复字符串是aba
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-1 06:24:13 | 显示全部楼层
listen8019 发表于 2016-11-1 03:20. visit 1point3acres.com for more.
楼主的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(); . From 1point 3acres bbs

  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))
  8.     int i = 0;
  9.     while (i < n) if (s[i] != s[i%d]) break; else i++; // O(n)
  10.     if (i == n) return true; // repeating pattern has length d
  11.   }
  12.   return false; // no repeating pattern
  13. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| listen8019 发表于 2016-11-1 06:26:01 | 显示全部楼层
zhan1612 发表于 2016-11-1 05:21. visit 1point3acres.com for more.
第一题的话(k*a_k + n_(k+1)) / (k+1) 这样做是不是还会有溢出, 假设前k+1个数全部是最大浮点数这样就溢出 ...

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

使用道具 举报

sophie0815 发表于 2016-11-1 06:50:02 | 显示全部楼层
在geekforgeek上看到这道题 http://www.geeksforgeeks.org/find-given-string-can-represented-substring-iterating-substring-n-times/ 用的是KMP构造prefix array  感觉要现场想很难吧?
回复 支持 反对

使用道具 举报

33847682 发表于 2016-11-1 07:19:37 | 显示全部楼层
楼上正解 这题刚看感觉是可能跟kmp有关但是后面具体怎么算面试的时候真心很难想出来啊
回复 支持 反对

使用道具 举报

sophie0815 发表于 2016-11-1 07:35:01 | 显示全部楼层
33847682 发表于 2016-11-1 07:19
楼上正解 这题刚看感觉是可能跟kmp有关但是后面具体怎么算面试的时候真心很难想出来啊

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

使用道具 举报

33847682 发表于 2016-11-1 07:48:10 | 显示全部楼层
sophie0815 发表于 2016-11-1 07:35
同觉得 感觉和prefix suffix有关 想到这个 关键对这个算法不是很熟 不是很会用呀

哎 真心看人品 话说最近貌似狗家很多题都是从g4g上面扒下来的
回复 支持 反对

使用道具 举报

lby1989825 发表于 2016-11-1 07:49:08 | 显示全部楼层
zhan1612 发表于 2016-11-1 05:21
第一题的话(k*a_k + n_(k+1)) / (k+1) 这样做是不是还会有溢出, 假设前k+1个数全部是最大浮点数这样就溢出 ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
我也觉得这题好难啊,溢出和精度是无法同时保证的
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-11-1 11:17:51 | 显示全部楼层
sophie0815 发表于 2016-11-1 06:50
在geekforgeek上看到这道题 http://www.geeksforgeeks.org/find-given-string-can-represented-substring-i ...

感觉除非是自己和面试官提前都知道这个算法,否则就算当时讲都讲不清楚啊。这真的是电面吗……
回复 支持 反对

使用道具 举报

yhatl 发表于 2016-11-2 09:58:59 | 显示全部楼层
listen8019 发表于 2016-11-1 02:50
比如abab,返回真,aba,返回假,a返回假,就这个意思。

aba不该是真吗?是要substring.size()>1吗
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 04:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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