一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 1524|回复: 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會不合,. Waral 鍗氬鏈夋洿澶氭枃绔,
在提示下寫出了另一種方法, 但是結束後自己檢查還是有case不合, 感覺應該是跪了...

评分

4

查看全部评分

shuishuimiao 发表于 2015-6-19 07:04:50 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
请问下这个in place 不用extra memory 有好的方法吗
回复 支持 反对

使用道具 举报

glaciersilent 发表于 2015-6-19 08:01:36 | 显示全部楼层
关注一亩三分地微博:
Warald
想到个笨方法不知对不对,先把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注重的真的不是標準答案...

這題後來想到要用一個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
. 1point 3acres 璁哄潧
不该输出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. more info on 1point3acres.com
每次把queue的头减一,queue内部自己再重新排。直到queue is empty

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

使用道具 举报

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

比如我们有AABBCC

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

再举个例子: BCBAAA会变成:
int[][]{{'A','B'},
          {'A','B'},. from: 1point3acres.com/bbs
          {'A','C'}}
我们填入数组是竖着填的,因为x[A]=3, x[B] =2, x[C]=1
.1point3acres缃所以我们会建一个3行的数组,第一列是全部A. 鍥磋鎴戜滑@1point 3 acres
第二列先填完B, 发现还有空位,继续填C
回复 支持 反对

使用道具 举报

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

谢啦!

回复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 | 显示全部楼层
- - 老题
.鏈枃鍘熷垱鑷1point3acres璁哄潧
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
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-4-30 23:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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