一亩三分地论坛

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

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

Google二輪電面

[复制链接] |试试Instant~ |关注本帖
anguslu4786 发表于 2015-6-19 06:16:58 | 显示全部楼层 |阅读模式

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

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

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

x
這次算是撿到的二輪店面, 一輪表現其實很一般, 代碼又打的挺慢的, 幾乎一題沒follow up就時間到...能拿到第二次算是僥倖

二輪是一個美國女生, 人還滿親切的, 問了一題 給你一個string, 把char rearrange 使相鄰兩個char都不會重複,

比如ABBA ---> ABAB, BABA

假如不可能就回傳false   AA--->false

一開始還以為很簡單, 給一個算法之後發現有些case會不合,
在提示下寫出了另一種方法, 但是結束後自己檢查還是有case不合, 感覺應該是跪了.... 鍥磋鎴戜滑@1point 3 acres

评分

4

查看全部评分

shuishuimiao 发表于 2015-6-19 07:04:50 | 显示全部楼层
请问下这个in place 不用extra memory 有好的方法吗
回复 支持 反对

使用道具 举报

glaciersilent 发表于 2015-6-19 08:01:36 | 显示全部楼层
想到个笨方法不知对不对,先把string变成字符数列然后排序,扫描这个数列用一个linkedhashmap记录字符和occurrence,如果出现最多次数的字母出现次数>(length+1)/2 返回false 否则建立一个linkedlist向里面根据map插入字母
回复 支持 反对

使用道具 举报

love1point 发表于 2015-6-19 08:25:09 | 显示全部楼层
glaciersilent 发表于 2015-6-19 08:01
想到个笨方法不知对不对,先把string变成字符数列然后排序,扫描这个数列用一个linkedhashmap记录字符和occ ...

否则建立一个linkedlist向里面根据map插入字母

这部分能描述详细一点吗?谢谢
回复 支持 反对

使用道具 举报

milanelllo13 发表于 2015-6-19 08:42:27 | 显示全部楼层
见到一个onsite的同学报过这道题。 他说用的greedy的方法。
回复 支持 反对

使用道具 举报

 楼主| anguslu4786 发表于 2015-6-20 02:54:22 | 显示全部楼层
今天早上收到了onsite通知...只能說google注重的真的不是標準答案...
. From 1point 3acres bbs
這題後來想到要用一個2d array, length 是重複次數最多的char, 寬是n,  然後把character依照出現次數desc sort, 然後從最多次的char對first column填滿, 填完所有char, 最後從row append完所有char.
回复 支持 反对

使用道具 举报

 楼主| anguslu4786 发表于 2015-6-20 03:00:02 | 显示全部楼层
glaciersilent 发表于 2015-6-19 08:01
想到个笨方法不知对不对,先把string变成字符数列然后排序,扫描这个数列用一个linkedhashmap记录字符和occ ...

面試官提示我就是這個思路, 但這方法還是有case會錯唷

鏉ユ簮涓浜.涓夊垎鍦拌鍧. 比如AABBCC

output will be ABABCC...
回复 支持 反对

使用道具 举报

glaciersilent 发表于 2015-6-20 06:33:38 | 显示全部楼层
anguslu4786 发表于 2015-6-20 03:00
面試官提示我就是這個思路, 但這方法還是有case會錯唷

比如AABBCC

我想的插入比较繁琐。。就是先插入出现最多的字母比如AABBCC就是先变成AA,之后要向它的空隙中插字母变成ABAB 等到出现最多的AA完全被BB隔开基本就安全了,接着往空隙中塞字母就完事变成ACBCAB。麻烦的是如果是AAAABBCDE这种出现第二多的BB不够把四个A全部隔开,还要用出现第三多以及之后的字母,直到可以把出现最多的字母A全部分隔开,感觉非常繁琐,应该有更好的算法。。。
回复 支持 反对

使用道具 举报

outtime 发表于 2015-6-20 07:06:43 | 显示全部楼层
anguslu4786 发表于 2015-6-20 03:00
面試官提示我就是這個思路, 但這方法還是有case會錯唷

比如AABBCC

不该输出ABCABC么
回复 支持 反对

使用道具 举报

会编程的猪先生 发表于 2015-6-20 09:37:18 | 显示全部楼层
anguslu4786 发表于 2015-6-20 02:54
今天早上收到了onsite通知...只能說google注重的真的不是標準答案...

這題後來想到要用一個2d array, le ...

楼主能稍稍再详细一点说说你的算法吗?看不懂耶

比如我们有AABBCC
那么那个2d array是什么?排序之后那个array是啥样子?填了index 0之后那个array啥样子?谢啦!
回复 支持 反对

使用道具 举报

ahwhdsl 发表于 2015-6-21 16:28:53 | 显示全部楼层
为什么你一天就收到onsite了? 我花了两个月
回复 支持 反对

使用道具 举报

jaly50 发表于 2015-6-21 20:32:07 | 显示全部楼层
我的想法是 建一个class: key是 char, value是出现的次数. more info on 1point3acres.com
建一个prorityQueue来维护这些字符,head of the queue  will always be the char with highest frequency
每次把queue的头减一,queue内部自己再重新排。直到queue is empty

关键就是自己写一个comparator,按value desc sorting
回复 支持 反对

使用道具 举报

jaly50 发表于 2015-6-21 20:41:04 | 显示全部楼层
会编程的猪先生 发表于 2015-6-20 09:37
楼主能稍稍再详细一点说说你的算法吗?看不懂耶

比如我们有AABBCC
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
她的意思大概是: . visit 1point3acres.com for more.
2维数组,你的AABBCC就会变成: . more info on 1point3acres.com
int[][] {{'A','B','C'},
            {'A','B','C'},}
然后就可以构建String啦,row从上往下, 每次取first column的值,取完 left+1,再取第二列的值... 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

再举个例子: BCBAAA会变成:
int[][]{{'A','B'},
          {'A','B'},
          {'A','C'}}
我们填入数组是竖着填的,因为x[A]=3, x[B] =2, x[C]=1
所以我们会建一个3行的数组,第一列是全部A. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第二列先填完B, 发现还有空位,继续填C
回复 支持 反对

使用道具 举报

会编程的猪先生 发表于 2015-6-22 09:47:55 | 显示全部楼层
jaly50 发表于 2015-6-21 20:41
她的意思大概是:
2维数组,你的AABBCC就会变成:
int[][] {{'A','B','C'},

谢啦!. visit 1point3acres.com for more.

回复12垅:
也可以先把hash table变成一个list, 再利用Collections.sort,用一个comparator

补充内容 (2015-6-22 09:58):
我指单读排序一次,你的不断排序有意义吗?每次最高frequency有什么用?比如AAAAAABCDEFGHI前几次得到的都是A

补充内容 (2015-6-22 10:12):
刚刚小结的时候又想到数组的方法非常像ZigZag 可以搞个array of StringBuilder
回复 支持 反对

使用道具 举报

readman 发表于 2015-6-22 11:38:49 | 显示全部楼层
回复 支持 反对

使用道具 举报

robinho364 发表于 2015-6-22 13:44:15 | 显示全部楼层
readman 发表于 2015-6-22 11:38
- - 老题. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. more info on 1point3acres.com
http://stackoverflow.com/questions/25285792/generate-all-permutations-of-a-list-without- ...

正解

smartsman是你兄弟吗?id好像,感觉是一个系列的。

不知道有没有runningman
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-20 05:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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