一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 1242|回复: 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不合, 感覺應該是跪了...

评分

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 ...
-google 1point3acres
否则建立一个linkedlist向里面根据map插入字母

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

使用道具 举报

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

使用道具 举报

 楼主| anguslu4786 发表于 2015-6-20 02:54:22 | 显示全部楼层
今天早上收到了onsite通知...只能說google注重的真的不是標準答案...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
這題後來想到要用一個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
. 1point 3acres 璁哄潧
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會錯唷
. 1point 3acres 璁哄潧
比如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是出现的次数
建一个prorityQueue来维护这些字符,head of the queue  will always be the char with highest frequency-google 1point3acres
每次把queue的头减一,queue内部自己再重新排。直到queue is empty

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

使用道具 举报

jaly50 发表于 2015-6-21 20:41:04 | 显示全部楼层
会编程的猪先生 发表于 2015-6-20 09:37
楼主能稍稍再详细一点说说你的算法吗?看不懂耶
. Waral 鍗氬鏈夋洿澶氭枃绔,
比如我们有AABBCC

她的意思大概是: . visit 1point3acres.com for more.
2维数组,你的AABBCC就会变成:
int[][] {{'A','B','C'},
            {'A','B','C'},}
然后就可以构建String啦,row从上往下, 每次取first column的值,取完 left+1,再取第二列的值...

再举个例子: BCBAAA会变成:.鏈枃鍘熷垱鑷1point3acres璁哄潧
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'},

谢啦!. From 1point 3acres bbs
. 1point3acres.com/bbs
回复12垅:
也可以先把hash table变成一个list, 再利用Collections.sort,用一个comparator-google 1point3acres

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

补充内容 (2015-6-22 10:12):.鐣欏璁哄潧-涓浜-涓夊垎鍦
刚刚小结的时候又想到数组的方法非常像ZigZag 可以搞个array of StringBuilder
回复 支持 反对

使用道具 举报

readman 发表于 2015-6-22 11:38:49 | 显示全部楼层
- - 老题
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
http://stackoverflow.com/questio ... cent-equal-elements
回复 支持 反对

使用道具 举报

robinho364 发表于 2015-6-22 13:44:15 | 显示全部楼层
readman 发表于 2015-6-22 11:38. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
- - 老题

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, 2016-12-4 08:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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