一亩三分地论坛

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

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

Google11.11电面

[复制链接] |试试Instant~ |关注本帖
wh920419 发表于 2015-11-12 04:58:30 | 显示全部楼层 |阅读模式

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

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

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

x


我要来吐槽这个interviewer, 从来没有经历过这么unpleasant的面试。
一上来打个招呼然后问问题。整个面试的过程中,他就只把问题放那儿,然后我敲代码,然后就下一道题,然后我在敲,再下一道。。。
没有任何feedback, 我甚至觉得他的心思根本就不在这儿。至少说下答得对不对啊,别的interviewer 还会提醒optimization啥的啊, 他怎么就感觉像在应付了事?
最后还剩十分钟他让我问问题,我让他稍微评价下我的答案。他拒绝了。我又问我答案是对的吗,他说他只feedback给HR,让我问HR。我有一种我全做错了他已经懒得纠正我让我洗洗睡的赶脚。

事实也是,一结束我就发现我的代码犯了一个很严重的错误。他还真的一点点都没有提醒我啊,就暗里嘚瑟地默默的把我做错的记下来了?. 鍥磋鎴戜滑@1point 3 acres


问题:
1. Two sum, Three sum.
2. 字符串重新排列,让里面不能有相同字母在一起。比如aaabbb非法的,要让它变成ababab。给一种即可
3. 设计2d数据结构,要set(i, j)和query(a,b,c,d)来修改里面的数值,和查询以(a, b,c,d)为四个顶点的矩形里面数字的和。
. visit 1point3acres.com for more.
我感觉这个面试官相当不喜欢我啊,说话也不客气,问问题也敷衍不爱回答。我从来没见过啥都不说,想知道做得对不对去问HR的面试官。

你们说我要不要跟HR complain这件事?这种单方面拷问,让我心里跟吃了shit似的堵得慌。


补充内容 (2015-11-20 05:01):
onsite了~

评分

5

查看全部评分

本帖被以下淘专辑推荐:

freemail165 发表于 2015-12-22 12:25:43 | 显示全部楼层
bobzhang2004 发表于 2015-12-22 10:46
请问楼主 设计2d数据结构是写了O(lgn), O(lgn)的代码吗?

这题不可能lgn吧

补充内容 (2015-12-22 12:29):
感觉上
1) set() O(1), then query() O(M*N)
2) set() O(M), then query() O(N)
3) set() O(M*N) then query() O(1)
回复 支持 1 反对 0

使用道具 举报

yx1232287 发表于 2015-11-12 06:16:15 | 显示全部楼层
zwcelesta 发表于 2015-11-12 05:28. 1point3acres.com/bbs
嗯。存好char->count。但是每次找max of count的时候都得扫一遍?
. 1point 3acres 璁哄潧
用一个堆一直维护着
回复 支持 1 反对 0

使用道具 举报

zwcelesta 发表于 2015-11-12 05:05:55 | 显示全部楼层
第二题啥思路?
回复 支持 反对

使用道具 举报

 楼主| wh920419 发表于 2015-11-12 05:08:52 | 显示全部楼层

比如 aabbcc, 要变成abcabc , 或bcacab之类的,总之重新调整让他没有连续相同的字符
回复 支持 反对

使用道具 举报

bill701 发表于 2015-11-12 05:10:24 | 显示全部楼层

greedy可以解
回复 支持 反对

使用道具 举报

yx1232287 发表于 2015-11-12 05:14:24 | 显示全部楼层

贪心算法找重复最多的先排

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-11-12 05:19:10 | 显示全部楼层
wh920419 发表于 2015-11-12 05:08
比如 aabbcc, 要变成abcabc , 或bcacab之类的,总之重新调整让他没有连续相同的字符

是不是可以这样?
hash《char, count》// scan to fill the hash
while(hash。size != 0){
   if(hash.size > 1){
   for(
k: keys){. more info on 1point3acres.com
     if(hash.get(k) != 0){
. From 1point 3acres bbs        str + hash.get(k)
        hash.put(k, hash.get(k) - 1);
     } else{
       hash.remove(k);
     }
  }. visit 1point3acres.com for more.
  }else{. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    // insert remaining single char to str
  }
}. from: 1point3acres.com/bbs
回复 支持 反对

使用道具 举报

zwcelesta 发表于 2015-11-12 05:28:21 | 显示全部楼层
yx1232287 发表于 2015-11-12 05:14
贪心算法找重复最多的先排

嗯。存好char->count。但是每次找max of count的时候都得扫一遍?
回复 支持 反对

使用道具 举报

mumu007 发表于 2015-11-12 05:46:00 | 显示全部楼层
第二题,two pointer是不是可以解。假设字符串s, 如果s = s[i-1],那么让j 从 i+1开始搜索,找到不同于s的字符后跟s互换位置。复杂度O(n^2), 不需要额外空间。-google 1point3acres
. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2015-11-12 05:56):
需要从前往后扫一次,然后从后往前扫一次,因为会有aacbcbb这种情况。

补充内容 (2015-11-12 05:59):. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
本来敲的是"假设字符串s, 如果s = s[i-1],那么让j 从 i+1开始搜索,找到不同于s的字符后跟s互换位置。复杂度O(n^2), 不需要额外空间。"
回复 支持 反对

使用道具 举报

mumu007 发表于 2015-11-12 06:00:55 | 显示全部楼层
mumu007 发表于 2015-11-12 05:46
第二题,two pointer是不是可以解。假设字符串s, 如果s = s,那么让j 从 i+1开始搜索,找到不同于s的字符后 ...

“假设字符串s, 如果s[i] = s[i-1],那么让j 从 i+1开始搜索,找到不同于s[i]的字符后跟s[i]互换位置。复杂度O(n^2), 不需要额外空间。”再试一遍.鏈枃鍘熷垱鑷1point3acres璁哄潧
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-11-12 07:13:23 | 显示全部楼层
同遇到过这种面试官,这可能就是霉运吧,哎,有时面试真是运气成分很大,很看面试官
回复 支持 反对

使用道具 举报

marthew777 发表于 2015-11-12 07:18:54 | 显示全部楼层
30分钟把这三题写完bugfree,不容易。楼主你已经很牛B了,建议complain~~
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-11-12 07:36:42 | 显示全部楼层
yx1232287 发表于 2015-11-12 05:14
贪心算法找重复最多的先排

能详细说说嘛? 重复的先排是什么意思?
回复 支持 反对

使用道具 举报

yx1232287 发表于 2015-11-12 07:40:19 | 显示全部楼层
hyliu0000 发表于 2015-11-12 07:36-google 1point3acres
能详细说说嘛? 重复的先排是什么意思?

就是要避免到最后只剩一种字符然后排不开了
比如"aabbcccc"如果先排"abab"后面就只剩c了
回复 支持 反对

使用道具 举报

queeniejing 发表于 2015-11-12 07:50:15 | 显示全部楼层
后面两个题不简单啊, LZ 30分钟能搞定很牛了  patpat
回复 支持 反对

使用道具 举报

oneshot 发表于 2015-11-12 07:51:34 | 显示全部楼层
第二题可不可以先把这个字符串sort一下, 变成aaabbb,然后从新组合,组合方法是从最前面拿出一个char, 然后从最后面拿出一个 char, 然后继续最前面拿出一个最后面拿出一个那样,结果是ababab, 最后就没有相同的char挨着了.
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-11-12 07:55:57 | 显示全部楼层
yx1232287 发表于 2015-11-12 07:40
就是要避免到最后只剩一种字符然后排不开了
比如"aabbcccc"如果先排"abab"后面就只剩c了
. 鍥磋鎴戜滑@1point 3 acres
那如果是这个“aabbcccc”,按照你的思路是怎么排的?
回复 支持 反对

使用道具 举报

yx1232287 发表于 2015-11-12 07:58:28 | 显示全部楼层
hyliu0000 发表于 2015-11-12 07:55
那如果是这个“aabbcccc”,按照你的思路是怎么排的?

cacbcacb
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-11-12 08:02:07 | 显示全部楼层

麻烦给个演变过程。
回复 支持 反对

使用道具 举报

yx1232287 发表于 2015-11-12 08:14:01 | 显示全部楼层
hyliu0000 发表于 2015-11-12 08:02. visit 1point3acres.com for more.
麻烦给个演变过程。

就是把当前剩余数量最多的字符优先排。
先统计每个字符出现的次数,用一个最大堆维护着可以快速取得当前剩余最大字符。(应该已经不能更详细了)
这个之前面经里挺多的,你之后继续看面经就又能见到。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 23:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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