一亩三分地论坛

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

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

G家的onsite

[复制链接] |试试Instant~ |关注本帖
hj735 发表于 2015-5-29 12:35:56 | 显示全部楼层 |阅读模式

2015(4-6月) 码农类 硕士 全职@Google - Other - Onsite |Passfresh grad应届毕业生

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

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

x
5月8号面的,刚确认了offer,回馈地里
round 1.1point3acres缃
leetcode原题,矩阵最小路径和,从矩阵左上角走到右下角,每一步往右或者往下
两个链表 求最大的公共后缀

round 2
求一个数组的 h index
h-index 就是这样的一个数 如果数组中有n个数的值大于n,并且没有n+1个数的值大于n+1,那么n就是h-index.1point3acres缃

round 3
设计一个作业调度的API,我写了一个类似os里面线程调度的scheduler
给一个数,要求把这个数分解成一些平方数的和,并且要求使用最短的平方数list 如 13 = 9 + 4 而不是 13 = 4+4+4+1
貌似这题leetcode有类似的题目,好久没做leetcode新题都没关注。

round 4. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
给一个字符串,该字符串由一些可能会重复的字符组成,重新排列这个字符串使得没有相邻的字符是相同字符。如aab变成aba. Waral 鍗氬鏈夋洿澶氭枃绔,

找工作忙碌了一年终于结束了,最后祝大家好运。

评分

5

查看全部评分

本帖被以下淘专辑推荐:

 楼主| hj735 发表于 2015-6-11 13:31:15 | 显示全部楼层
Kimurate 发表于 2015-6-11 13:23. Waral 鍗氬鏈夋洿澶氭枃绔,
所以题目中的数组是有序的咯?

对的 数组是有序的
回复 支持 1 反对 0

使用道具 举报

 楼主| hj735 发表于 2015-6-11 11:57:06 | 显示全部楼层
[1,3,4,7,8,9]的结果是3,至少有3个数大于3,题目说明里面应该加个至少
回复 支持 1 反对 0

使用道具 举报

yinloveslele 发表于 2015-6-10 11:01:13 | 显示全部楼层
楼主请问 链表公共后缀的话,是不是要先求的两个链表的长度,然后对齐之后再递归啊
回复 支持 反对

使用道具 举报

milanelllo13 发表于 2015-6-10 13:43:45 | 显示全部楼层
请问楼主round2  意思就是求第(n - h)大的数吗 , 那可以用quick select吗。 就是leetcode第215题。谢谢~!
回复 支持 反对

使用道具 举报

milanelllo13 发表于 2015-6-10 14:16:24 | 显示全部楼层
milanelllo13 发表于 2015-6-10 13:43. 鍥磋鎴戜滑@1point 3 acres
请问楼主round2  意思就是求第(n - h)大的数吗 , 那可以用quick select吗。 就是leetcode第215题。谢谢~ ...

哈 不好意思楼主 我才发现我看错了题意~
回复 支持 反对

使用道具 举报

milanelllo13 发表于 2015-6-10 14:34:17 | 显示全部楼层
楼主,我想再问一下,n是不一定是数组中的数对吗
回复 支持 反对

使用道具 举报

wy_19900814 发表于 2015-6-10 15:48:30 | 显示全部楼层
首先十分感谢楼主分享的题目,然后我想问一下有没有哪个大神给点最后一题的思路。

这题诈一想是想贪心,是想建立一个hash表,然后从里面挨个取出元素然后输出。但是如果一个字母出现过多这种方法就崩。

第二个想法还是贪心,根据字母出现频率排序。每次让频率最多的先跟其他字母一个接一个的输出,比如a 10,b 5, c 3, d 2,处理方法就是a接着b然后a接着c,轮着来。但后来发现这种方法无论怎么贪心最后都有特殊情况解决不了,所以想问一下应该用什么思路来想这个题。

补充内容 (2015-6-10 16:09):
你好,最终在stack overflow上看到了一种贪心法。还是把字符出现频率统计出来,扔在一个堆里。每次取出前两个频率高的字母,配成一对,次数减一,扔回堆。(只要写的时候注意下相邻字母不要一样就好)
回复 支持 反对

使用道具 举报

 楼主| hj735 发表于 2015-6-11 01:40:01 | 显示全部楼层
yinloveslele 发表于 2015-6-10 11:01
楼主请问 链表公共后缀的话,是不是要先求的两个链表的长度,然后对齐之后再递归啊

你这种思路可以的,我是直接把链表遍历一遍,然后倒过来求公共前缀
回复 支持 反对

使用道具 举报

 楼主| hj735 发表于 2015-6-11 01:41:58 | 显示全部楼层
milanelllo13 发表于 2015-6-10 14:34. From 1point 3acres bbs
楼主,我想再问一下,n是不一定是数组中的数对吗
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
对的,n不一定是数组中的,n就是这个数组中有多少个数比n大,让n最大。思路是binary search的变种,不是quick select。
回复 支持 反对

使用道具 举报

 楼主| hj735 发表于 2015-6-11 01:51:24 | 显示全部楼层
wy_19900814 发表于 2015-6-10 15:48
首先十分感谢楼主分享的题目,然后我想问一下有没有哪个大神给点最后一题的思路。

这题诈一想是想贪心, ...

首先贪心的思路是对的,我的实现方法是,首先统计各个字母出现的概率,然后存在一个map里面,key是字母,value是出现次数。然后取出最多出现的字母从map里面删掉,然后把剩下的字母按照出现的次数,每次都把map里面出现次数最多的字母取出来一个,插到前面删除的字母组成的字符串的空隙当中,直到没有空隙(这个过程是动态的,例如此时map里面有a出现3次b出现3次,那么先插个a,下一次要插个b,一直保持拿出最多的字母)。然后递归,把map传到下一次调用,直至map里面只有一个字母,如果剩下的一个字母出现的次数为1那么把它取出加到结果最后,如果出现次数大于1那么无解。
回复 支持 反对

使用道具 举报

 楼主| hj735 发表于 2015-6-11 02:00:19 | 显示全部楼层
wy_19900814 发表于 2015-6-10 15:48
首先十分感谢楼主分享的题目,然后我想问一下有没有哪个大神给点最后一题的思路。

这题诈一想是想贪心, ...

这种用大根堆的算法更简单易懂,我实现完之后跟面试官解释了很久,然后又演示了几个case他才明白
回复 支持 反对

使用道具 举报

milanelllo13 发表于 2015-6-11 04:11:38 | 显示全部楼层
hj735 发表于 2015-6-11 01:41
对的,n不一定是数组中的,n就是这个数组中有多少个数比n大,让n最大。思路是binary search的变种,不是q ...

嘿嘿 谢谢楼主~
回复 支持 反对

使用道具 举报

milanelllo13 发表于 2015-6-11 04:25:18 | 显示全部楼层
wy_19900814 发表于 2015-6-10 15:48. Waral 鍗氬鏈夋洿澶氭枃绔,
首先十分感谢楼主分享的题目,然后我想问一下有没有哪个大神给点最后一题的思路。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

这题诈一想是想贪心, ...

能不能提供下stackoverflow的这道的地址~ 谢谢~!!
回复 支持 反对

使用道具 举报

wy_19900814 发表于 2015-6-11 05:21:59 | 显示全部楼层
hj735 发表于 2015-6-11 01:51. 1point 3acres 璁哄潧
首先贪心的思路是对的,我的实现方法是,首先统计各个字母出现的概率,然后存在一个map里面,key是字母, ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
回楼主,你这个贪心方法我想到了,但是有问题,比如aaabbbccc这种做法就挂了……
回复 支持 反对

使用道具 举报

wy_19900814 发表于 2015-6-11 05:23:03 | 显示全部楼层
milanelllo13 发表于 2015-6-11 04:25
能不能提供下stackoverflow的这道的地址~ 谢谢~!!

http://stackoverflow.com/questions/25726950/how-to-efficiently-rearrange-characters-in-a-string-so-that-there-are-no-pairs
回复 支持 反对

使用道具 举报

 楼主| hj735 发表于 2015-6-11 05:30:16 | 显示全部楼层
wy_19900814 发表于 2015-6-11 05:21
回楼主,你这个贪心方法我想到了,但是有问题,比如aaabbbccc这种做法就挂了……

我的算法是可以的

结果是 a b a c a b (第一次递归) c b c (第二次递归)
回复 支持 反对

使用道具 举报

 楼主| hj735 发表于 2015-6-11 05:32:35 | 显示全部楼层
wy_19900814 发表于 2015-6-11 05:21
回楼主,你这个贪心方法我想到了,但是有问题,比如aaabbbccc这种做法就挂了……
.1point3acres缃
我每次取最多的字母插缝,用的类似的大根堆的算法,拿一个次数减一然后重新放回去,其实这个过程中谁被拿出来不固定的。
回复 支持 反对

使用道具 举报

milanelllo13 发表于 2015-6-11 06:02:51 | 显示全部楼层
wy_19900814 发表于 2015-6-11 05:23
http://stackoverflow.com/questions/25726950/how-to-efficiently-rearrange-characters-in-a-string-so ...

多谢~~~~
回复 支持 反对

使用道具 举报

UmassJin 发表于 2015-6-11 08:26:14 | 显示全部楼层
请问楼主,round2 的题目,n可能取的最大值为input数组的长度对吗? 比如说input array是[3,6,7,9,10,13,15,20],n可能取的最大数值为8,有可能8个数比8大,但是比9大的不可能超过8,如果用binary search解法,我们应该从(0+len(input_arr))/2 开始比较吗? 麻烦楼主能不能说一下你的思路?
回复 支持 反对

使用道具 举报

 楼主| hj735 发表于 2015-6-11 08:43:23 | 显示全部楼层
[3,6,7,9,10,13,15,20] 对于这个数组的h index是6 因为数组里面有6个数比6大,而没有7个数比7大
回复 支持 反对

使用道具 举报

 楼主| hj735 发表于 2015-6-11 09:01:36 | 显示全部楼层
UmassJin 发表于 2015-6-11 08:26
请问楼主,round2 的题目,n可能取的最大值为input数组的长度对吗? 比如说input array是[3,6,7,9,10,13,15, ...

具体思路如下,其实就是binary search。 首先根据start和end得出mid,看A[mid]值是否大于数组长度减去mid(假设A.length-mid = distance),如果是那么distance有可能成为h index. 因为数组有序,如果distance小于A[mid],那么有distance个元素的值大于distance。 此时如果A[mid]值小于distance,那么继续向高位找,start=mid+1。如果A[mid]值大于distance,那么继续向低位找end=mid-1。如果低位找到更大的distance,那么返回低位的,如果低位没找到更大的,就返回现在的distance。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 21:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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