一亩三分地论坛

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

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

G家11.13 MTV onsite 面筋

[复制链接] |试试Instant~ |关注本帖
yx1232287 发表于 2015-12-10 08:29:46 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 猎头 - Onsite |Passfresh grad应届毕业生

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

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

x
今天刚接了offer,反馈一下地里~
1. 烙印,开始聊天时以为是recruiter,结果聊着聊着忽然说我来出道题吧.....Number of Islands 2, 那天面完试leetcode上就有了这道题
2. 白人,设计乌龟,一开始有两个方法,往前走一步,右转90度。然后说设计个方法可以执行一串命令:e.g., "FRRF"代表走、转、转、走。然后命令要支持括号和数字:e.g., "F97[RF[F]]"代表走一步,然后执行括号里的命令9*7次。
中午和一位三哥吃的饭,三哥看起来似乎不是很开心,可能吃完饭回去有任务...
3. 烙印,这位三哥全程笑呵呵,看起来心情很好。最简单的验证括号合法性:"3r(2)(2(3))"就合法着。然后再说如果字符串很长怎么办,我说把字符串分段然后多线程啊,然后写。完了三哥说你写太快了没题了要不出去喝点什么。最后在等下一位面试官的时候问了我很多小问题,诸如服务器不关掉的情况下升级、java8新特性、python多线程,我都没意识到还在面试,很多都随便的说不清楚,然后他就给我讲.....最后说“咦,你这代码好像写的是单线程的(汗),没事不用改了我知道你会”。
4. 国人面试官和一个好像是ABT的shadow,直接出题。一个无序非负(?)数组,找包含最少个数组元素的subset,使其和大于等于整个数组和的1%.. 1point 3acres 璁哄潧

评分

6

查看全部评分

本帖被以下淘专辑推荐:

 楼主| yx1232287 发表于 2015-12-14 04:20:57 | 显示全部楼层
xiaoniuona 发表于 2015-12-14 03:20
谢谢楼主分享~请问第三轮multithreading的code要怎么写哈?能不能share一下code~

我说下大概思路吧,先是把string平均切成n份,对每份进行同样的处理:从左往右扫一遍,count遇到左括号加一,遇到右括号减一。每段处理后返回的结果包括:count的最终值sum,count的最小值min,这段string的index(第一段index就是0,第二段就是1)。
完了后,依据顺序往后走,
for index:
    if 前面累加的sum + 这一段的min < 0
        return false
    sum += 这一段的sum
if sum > 0:
    return false
return true
回复 支持 1 反对 0

使用道具 举报

budlover 发表于 2015-12-10 09:38:10 | 显示全部楼层
一个无序非负(?)数组,找包含最少个数组元素的subset,使其和大于等于整个数组和的1%.

楼主可以说的详细点么? 最少个元素,听起来像从最大的开始挑,直到和超过1%?
回复 支持 反对

使用道具 举报

 楼主| yx1232287 发表于 2015-12-10 11:18:51 | 显示全部楼层
budlover 发表于 2015-12-10 09:38
一个无序非负(?)数组,找包含最少个数组元素的subset,使其和大于等于整个数组和的1%.

楼主可以说的详细 ...

我差不多就是这个思路,然后用quick select的方法可以O(n)找出来。
不过面试官说这不是他想要的方法,但让我继续写下去了。
回复 支持 反对

使用道具 举报

七夜雪 发表于 2015-12-10 14:05:01 | 显示全部楼层
LZ第三题字符串分段是平均分段吗?这样的话每段应该要记录下没有左括号对应的右括号的数量吧?比如说有一个线程看到的符号组合是 )))(() 这样就记录为3,然后看上一个线程跑完剩下多少个左括号。

第五题所以用quick select的复杂度是O(kN)吗?k就是最后subset的size? 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我一开始看到非负我以为就是用radix sort...
回复 支持 反对

使用道具 举报

 楼主| yx1232287 发表于 2015-12-10 16:52:19 | 显示全部楼层
七夜雪 发表于 2015-12-10 14:05
LZ第三题字符串分段是平均分段吗?这样的话每段应该要记录下没有左括号对应的右括号的数量吧?比如说有一个 ...

第三题大概思路差不多,我是用右括号数减左括号数,然后每段返回两个值:1)右减左的最终值2)右减左过程中最小值。
第四题quick sort做了shuffle后平均复杂度是O(n)。radix复杂度就和数字的值有关了。

补充内容 (2015-12-10 16:53):
左括号数减右括号数....
回复 支持 反对

使用道具 举报

linsang90 发表于 2015-12-11 07:07:51 | 显示全部楼层
通知offer是电话通知的吗?之前hr还会发点什么给你吗
回复 支持 反对

使用道具 举报

 楼主| yx1232287 发表于 2015-12-11 07:44:11 | 显示全部楼层
先通知过了HC,再通知过了exec review。都是先电话约时间,再打过来,HR的个人习惯。
回复 支持 反对

使用道具 举报

LifeGoesOn 发表于 2015-12-11 17:32:57 | 显示全部楼层
F97[RF[F]] 括号里表示什么呢 RF [F], 第二个括号前没有数字怎么解决
回复 支持 反对

使用道具 举报

 楼主| yx1232287 发表于 2015-12-11 17:41:04 | 显示全部楼层
括号就相当是一个嵌套,没有数字就当是1
回复 支持 反对

使用道具 举报

xiaoniuona 发表于 2015-12-14 03:20:42 | 显示全部楼层
谢谢楼主分享~请问第三轮multithreading的code要怎么写哈?能不能share一下code~
回复 支持 反对

使用道具 举报

xiaoniuona 发表于 2015-12-15 12:21:42 | 显示全部楼层
yx1232287 发表于 2015-12-14 04:20. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我说下大概思路吧,先是把string平均切成n份,对每份进行同样的处理:从左往右扫一遍,count遇到左括号加 ...

谢谢!为什么sum>0的时候要return false呢?sum是一段里多出来的左括号吧,连着2段有多出来的左括号不行嚒?后面几段还可以补右括号的呀
回复 支持 反对

使用道具 举报

 楼主| yx1232287 发表于 2015-12-15 12:25:38 | 显示全部楼层
xiaoniuona 发表于 2015-12-15 12:21
谢谢!为什么sum>0的时候要return false呢?sum是一段里多出来的左括号吧,连着2段有多出来的左括号不行 ...

sum > 0的判断是在for循环外面了,最后判断一下
回复 支持 反对

使用道具 举报

xiaoniuona 发表于 2015-12-15 13:20:58 | 显示全部楼层
yx1232287 发表于 2015-12-15 12:25
sum > 0的判断是在for循环外面了,最后判断一下

好的,我明白了,thx~
回复 支持 反对

使用道具 举报

lcl3356897 发表于 2015-12-30 07:45:32 | 显示全部楼层
楼主能分享下最后一题的思路么

怎么来 quick select?
回复 支持 反对

使用道具 举报

杰西Jesse 发表于 2015-12-30 11:37:05 | 显示全部楼层
lcl3356897 发表于 2015-12-30 07:45
楼主能分享下最后一题的思路么

怎么来 quick select?

同不理解。。。我想可能是这样,还请大家看看。。。
1. 先随意用个pivot, quickselect,然后把pivot右边的数加一下。
if满足要求了,从右边选第二个pivot,继续做=>减少subset内部的数量.1point3acres缃
else不满足要求,从左取pivot。。

但是这样怎么样才算结束呢。。。总觉得很麻烦啊。。。求LZ和大家指导TT
回复 支持 反对

使用道具 举报

 楼主| yx1232287 发表于 2015-12-30 19:01:09 | 显示全部楼层
杰西Jesse 发表于 2015-12-30 11:37
同不理解。。。我想可能是这样,还请大家看看。。。. more info on 1point3acres.com
1. 先随意用个pivot, quickselect,然后把pivot右 ...

我大体上就是个这思路。
每次加pivot右边的和target比较,大于target继续处理右边,小于target继续处理左边。. 鍥磋鎴戜滑@1point 3 acres
结束条件是右边加起来和target相等,或者加起来比target小但是左边为空了(此时结果要包含pivot),细节记不太清了,大概是这么写的
回复 支持 反对

使用道具 举报

airywu 发表于 2015-12-31 22:28:14 | 显示全部楼层
楼主,我多线程的东西不太懂,可以说说多线程的相关面试问题吗?谢谢!
回复 支持 反对

使用道具 举报

aiwojiujiu 发表于 2016-1-20 10:44:30 | 显示全部楼层
楼主是妹子吗?  我觉得女生不会被问这么难的题目吧。。。
回复 支持 反对

使用道具 举报

aiwojiujiu 发表于 2016-1-20 10:48:32 | 显示全部楼层
aiwojiujiu 发表于 2016-1-20 10:44
楼主是妹子吗?  我觉得女生不会被问这么难的题目吧。。。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
请问楼主可以分享一下第二题的思路吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 04:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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