一亩三分地论坛

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

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

GG电面

[复制链接] |试试Instant~ |关注本帖
sxh53 发表于 2015-11-14 09:59:05 | 显示全部楼层 |阅读模式

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

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

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

x
一个原题 感谢原楼主贴的面经
http://www.1point3acres.com/bbs/ ... D311%26searchoption[3089][value][3]%3D3%26searchoption[3089][type]%3Dcheckbox%26searchoption[3046][value]%3D1%26searchoption[3046][type]%3Dradio%26sortid%3D311

考官介绍自己,5分钟左右。
考的是第一题. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第一轮: 给一个 M * N的screen,和一个String,比如“Hello World", 请问整个screen能放下多少个string。
note: 如果有一个词在一行放不下,放到下一行。
这一轮感觉就是纯的字符串处理。

问的是多少个而不是怎么放。. from: 1point3acres.com/bbs
然而虽然是原题LZ还是写了好多bug...不过貌似人家不在意。这里大约用去了10分钟。
然后人工跑test case,这里用去了15分钟,然后找到了3个bug :(
Follow up是如果M和N巨大(比如1M)怎么办。。。。电面感觉的到对面想法设法的提醒可是楼主还是不会。最后瞎猜了一个好像猜对了也没听清,电话吵得不得了。所以上来问问大家,这个题怎么做,复杂度不希望是基本的O(MN),而是希望更小,比如O(NL) where L = # words in the string.
. From 1point 3acres bbs
算了就这个水平还要什么自行车...



补充内容 (2015-11-13 21:00):
http://www.1point3acres.com/bbs/thread-147302-1-1.html 原帖地址。

评分

1

查看全部评分

sheepmiemies 发表于 2016-3-19 00:07:19 | 显示全部楼层
一回头的温柔 发表于 2016-3-13 17:13
有没有人能解释一下这个题的意思么? 放多少个的话,难道不是m*n/string.length() ????

看题目描述没有那么简单啊,我觉得可以想象成自动换行的记事本。. 1point 3acres 璁哄潧
(1)最好的情况是一行刚好放一个string,余下的空位不足以放string的第一个word,一共M个string。
(2)但如果最后一个或者多个word无法放在同一行,肯定会换行放在行首;
. 1point3acres.com/bbs(3)如果一行空间放下一个string还有剩余,可以把该string的前面一个或者多个word放在这一行;
情况(2)和(3)会导致每放一个string,剩余空间都是不一样的。如果string里包含 '\n' 会更复杂一些?
.鐣欏璁哄潧-涓浜-涓夊垎鍦
感觉可以这么做:
虽然每次放一个string,最后一行的剩余空间会有变化,但实际上会形成一个循环,这个循环最长不会超过L (number of word in string),因为每一行必然是以string中的某个word开头,所以我们只需要找到一个循环,就能知道 M*N能放多少个string了。

首先是遍历一边string拿到每个word的长度存进数组,wordSize[L]。然后依然分三种情况:
.鐣欏璁哄潧-涓浜-涓夊垎鍦
(1) N刚好装下整数k个string,k = N/(string.size + 1) > 0  
    Case 1: N%(string.size + 1) == string.size,剩下空间刚好放下最后一个string
    Case 2: N%(string.size + 1) < wordSize[0],剩下空间刚不足以放下第一个word.鏈枃鍘熷垱鑷1point3acres璁哄潧

对于情况(2)(3),用一个set保存每次行首的word,作为循环结束的大条件。
(2)可以放下整数k个string,并且还能放下一个或多个word。这种情况我们需要用一个map保存“如果我们有 i 行空间可以放多少个string”。找到一个循环后,即可得到一个循环C行可放下的string数量 I,用M/C*I 得到所有循环能放下的数量,再加上从map中找到M%C剩余的行数能保存的string数量即可。

(3)如果N < string.size,我们则应该计算每多放一个string需要多少行,进一步得到一个循环需要C行可以放下I个string,同样用M/C*I, 以及之后剩下M%C行可以保存的string数量。
. from: 1point3acres.com/bbs
对于时间复杂度,因为每次计算剩余空间可以放多少个word,我们需要遍历word的长度表,所以是O(L),为了找出一个循环,我们需要L rounds,所以总共时间复杂度应该是O(L^2)。

对于空间复杂度,我们需要保存word的size --> O(L),寻找循环的时候需要一个map一个set都是O(L)。所以总的复杂度应该是O(L)。

求讨论看算法是否正确,或者有没有更好的方法~
回复 支持 1 反对 0

使用道具 举报

xiaoniuona 发表于 2015-11-14 11:09:42 | 显示全部楼层
请问楼主google doc上写code的话是怎么跑test的哈?
回复 支持 反对

使用道具 举报

 楼主| sxh53 发表于 2015-11-14 11:18:50 | 显示全部楼层
xiaoniuona 发表于 2015-11-13 22:09. 1point 3acres 璁哄潧
请问楼主google doc上写code的话是怎么跑test的哈?

“人工跑测试”的意思就是人肉debugger。就是自己一行一行的跑。
回复 支持 反对

使用道具 举报

xiaoniuona 发表于 2015-11-14 11:20:00 | 显示全部楼层
sxh53 发表于 2015-11-14 11:18. 1point3acres.com/bbs
“人工跑测试”的意思就是人肉debugger。就是自己一行一行的跑。

就是带着面试官一行一行讲自己的code嚒。。。
回复 支持 反对

使用道具 举报

westsnow 发表于 2015-11-14 11:39:05 | 显示全部楼层
拜大神,沾喜气
回复 支持 反对

使用道具 举报

tltzhsajsdr 发表于 2015-11-14 12:07:38 | 显示全部楼层
note: 如果有一个词在一行放不下,放到下一行。 这里是说有一个词放不下,把这个词放到下一行,还是把当前整个string放到下一行?
回复 支持 反对

使用道具 举报

eko910817 发表于 2015-11-16 13:23:53 | 显示全部楼层
O(NL)是面试官要求的吗?
回复 支持 反对

使用道具 举报

 楼主| sxh53 发表于 2015-11-17 01:53:53 | 显示全部楼层
eko910817 发表于 2015-11-16 00:23
O(NL)是面试官要求的吗?
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
反正这个没答上来 最后今天的通知是加面一轮T T
回复 支持 反对

使用道具 举报

eko910817 发表于 2015-11-17 01:54:47 | 显示全部楼层
sxh53 发表于 2015-11-16 09:53
反正这个没答上来 最后今天的通知是加面一轮T T

LZ加油哈!
回复 支持 反对

使用道具 举报

xnature 发表于 2015-11-17 02:40:27 | 显示全部楼层
第一题能举个例子么?
回复 支持 反对

使用道具 举报

jade86 发表于 2015-11-17 09:50:56 | 显示全部楼层
好像可以达到 O(L log L), L = number of words :
算法是用DP:. from: 1point3acres.com/bbs
存两个L长的数列.1point3acres缃
第一, i th entry:一行如果从第i个word开始能存多少个整句  O(L)
i.e. a_1,......,a_L
第二, i th entry:一行如果从第i个word开始会到第几个word ( binary search ? ) O(L log L)
i.e. b_1,......,b_L  . 鍥磋鎴戜滑@1point 3 acres
接下来有点像recurrent decimal, 每行开始的word i 会重复,比方说:
1 , 3,5,7,1,3,5,7。。。1, 3
找重复的cycle length:  这个例子是4...  O(L)
最后算total:  O(L). Waral 鍗氬鏈夋洿澶氭枃绔,
number of lines = (M/4) * ( a_1 + a_3 + a_5 + a_7 + 3) + a_1 + a_3 + 1. from: 1point3acres.com/bbs

不确定这方法有没有错,请大神帮忙看看^^
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-7 05:48:51 | 显示全部楼层
请问楼主,输入形式是(String str, int m, int n)吗?这个string中得word时可以分开放是吧?两个word间的都是空格个开?那做的时候是str.split(" +")?
回复 支持 反对

使用道具 举报

一回头的温柔 发表于 2016-3-13 17:13:52 | 显示全部楼层
有没有人能解释一下这个题的意思么? 放多少个的话,难道不是m*n/string.length() ????
回复 支持 反对

使用道具 举报

一回头的温柔 发表于 2016-3-13 17:14:20 | 显示全部楼层
sxh53 发表于 2015-11-14 11:18. Waral 鍗氬鏈夋洿澶氭枃绔,
“人工跑测试”的意思就是人肉debugger。就是自己一行一行的跑。

楼主,能解释一下这个题的意思么
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 23:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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