一亩三分地论坛

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

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

G家电面

[复制链接] |试试Instant~ |关注本帖
merayxu 发表于 2014-12-5 08:22:12 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Other

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

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

x
1.括号匹配
一开始用了O(N)的空间, 后来要求用O(1)的空间完成
follow up, 不同types的括号匹配 {,[,(. visit 1point3acres.com for more.
2.Arraylist去重
一开始忘了数组remove要O(n),所以写了个O(n^2)的方法后来被要求实现O(n). 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
感觉难度比面经简单了不少,不过还是犯了脑残的错误,求RP 求onsite = =!

atlas1017 发表于 2014-12-9 05:15:46 | 显示全部楼层
O(1)只要用一个count就可以了吧 每次( 的时候count++,  )的时候count--, count小于零就直接return false 最后return count==0
回复 支持 2 反对 0

使用道具 举报

yzl232 发表于 2014-12-5 09:02:32 | 显示全部楼层
难得看到G家出简单题。
回复 支持 反对

使用道具 举报

latioswang 发表于 2014-12-6 19:06:20 | 显示全部楼层
请问楼主也是女孩嘛?Google面了这么简单的题目?之前看到的面经都好难啊
回复 支持 反对

使用道具 举报

cauchyc 发表于 2014-12-6 20:00:20 | 显示全部楼层
感觉不像是google的题...楼主是女生么
回复 支持 反对

使用道具 举报

tianyangche 发表于 2014-12-7 03:28:37 | 显示全部楼层
楼主不好意思,请问第一题如果用O(1)怎么做。。。
回复 支持 反对

使用道具 举报

houqingniao 发表于 2014-12-7 12:40:16 | 显示全部楼层
tianyangche 发表于 2014-12-7 03:28
楼主不好意思,请问第一题如果用O(1)怎么做。。。

同求 O(1) 空间解法
回复 支持 反对

使用道具 举报

 楼主| merayxu 发表于 2014-12-8 00:12:36 | 显示全部楼层
houqingniao 发表于 2014-12-7 12:40
同求 O(1) 空间解法

用一个top指针标记最顶端的左括号,然后每次这个左括号匹配了之后backward去找下一个最近的左括号的指针标记为top,用堆栈其实每次用到的也只是它最顶端的元素哈~
回复 支持 反对

使用道具 举报

suonan 发表于 2014-12-8 01:27:30 | 显示全部楼层
赞一个O(1)空间解法
回复 支持 反对

使用道具 举报

houqingniao 发表于 2014-12-8 05:14:49 | 显示全部楼层
merayxu 发表于 2014-12-8 00:12
用一个top指针标记最顶端的左括号,然后每次这个左括号匹配了之后backward去找下一个最近的左括号的指针 ...
. 1point 3acres 璁哄潧
nice。
但是你得track 前一个没有匹配的左括号,还得需要空间去记录呢
回复 支持 反对

使用道具 举报

ydybati 发表于 2014-12-9 05:05:31 | 显示全部楼层
houqingniao 发表于 2014-12-8 05:14
nice。
但是你得track 前一个没有匹配的左括号,还得需要空间去记录呢

我也在想同样的问题。。。难道匹配好就把这一对删了。。。
回复 支持 反对

使用道具 举报

houqingniao 发表于 2014-12-9 05:29:48 | 显示全部楼层
atlas1017 发表于 2014-12-9 05:15
O(1)只要用一个count就可以了吧 每次( 的时候count++,  )的时候count--, count小于零就直接return false  ...

这个只限于一种括号吧
三种一起的 O(1),感觉不简单,试了试 都不work

有人能上code嘛?
回复 支持 反对

使用道具 举报

atlas1017 发表于 2014-12-9 06:49:58 | 显示全部楼层
houqingniao 发表于 2014-12-9 05:29. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
这个只限于一种括号吧
三种一起的 O(1),感觉不简单,试了试 都不work
. Waral 鍗氬鏈夋洿澶氭枃绔,
觉得楼主的意思就是一个括号降到O(1)。。。 follow up 之后需要O(N),, ,被问过这个问题 后面还有follow up是怎么do in parallel叻 所以觉得应该没有更好的做法。 当然有的话 欢迎分享哈!
回复 支持 反对

使用道具 举报

 楼主| merayxu 发表于 2014-12-9 07:57:04 | 显示全部楼层
atlas1017 发表于 2014-12-9 06:49
觉得楼主的意思就是一个括号降到O(1)。。。 follow up 之后需要O(N),, ,被问过这个问题 后面还有follo ...

对的,= =,字数字数
回复 支持 反对

使用道具 举报

houqingniao 发表于 2014-12-9 13:51:06 | 显示全部楼层
merayxu 发表于 2014-12-9 07:57
对的,= =,字数字数

make sense.. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
那就是一个计数就可以了。
我以为三个呢~~~ 搞了我好长时间。。
回复 支持 反对

使用道具 举报

houqingniao 发表于 2014-12-9 13:51:20 | 显示全部楼层
merayxu 发表于 2014-12-9 07:57
对的,= =,字数字数

make sense.
那就是一个计数就可以了。
我以为三个呢~~~ 搞了我好长时间。。
回复 支持 反对

使用道具 举报

lhh_NJU 发表于 2014-12-9 14:07:11 | 显示全部楼层
atlas1017 发表于 2014-12-9 06:49
觉得楼主的意思就是一个括号降到O(1)。。。 follow up 之后需要O(N),, ,被问过这个问题 后面还有follo ...

如果是三个的话就必须用栈咯?
回复 支持 反对

使用道具 举报

atlas1017 发表于 2014-12-10 05:55:02 | 显示全部楼层
lhh_NJU 发表于 2014-12-9 14:07
如果是三个的话就必须用栈咯?

不确定是不是一定要用栈 但是觉得用栈是很自然的想法把= =!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 18:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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