📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: pure0909
跳转到指定楼层
上一主题 下一主题
收起左侧

[CareerCup] 【第四轮】3.30 -4.5 Career Cup 1.3

🔗
stellari 2015-4-2 14:01:04 | 只看该作者
全局:
slaink 发表于 2015-4-2 01:48
有遇到过让你实现hashtable的吗?我现在写题都尽量不用STL 容器,不知道面试时候会不会要求实现

我没有遇到过。我相信肯定有面试官会问这种题,但是我觉得,单纯问“实现一个hashtable”这种问题,很难在一小时以内看出面试者的素质。所以他们更可能会把一个等价于hashtable的实现问题隐藏在一个更难的问题中,比如常见的scalability问题:"找出一个很长的字符串列表(长到远不能一次放进内存中)中出现次数最多的前10个”. 这时候我们可以按字符串hash值来将这个大文件分割成小文件,这个分割本质上是用硬盘实现了一个哈希表。然后取前10个的数字这个过程又用到了堆。等于在一个问题考了多个数据结构。个人认为大公司的面试官应该会偏向这种问法吧。

不管怎么说,技多不压身,掌握常见的数据结构的实现绝对是应该的。

评分

参与人数 1大米 +10 收起 理由
slaink + 10 例子非常好!

查看全部评分

回复

使用道具 举报

🔗
slaink 2015-4-3 04:35:13 | 只看该作者
全局:
stellari 发表于 2015-4-2 14:01
我没有遇到过。我相信肯定有面试官会问这种题,但是我觉得,单纯问“实现一个hashtable”这种问题,很难 ...

所谓用堆是指存一个augmented 堆吗?每个element包含字符以及他的出现次数,然后靠次数构造堆?

仔细想了一下不是非常明白为什么必须用硬盘hashtable。最后获取top10时候还是需要把所有的 字符-出现次数 载入到内存比较的吧?当然这假设了所有唯一字符可以一次载入内存。所以你说的堆实际指堆排序?

如果所有unique字符也不能一次都载入到内存里,我们必须用硬盘做hash。那么我们需要对每个小文件单独排序,之后用merge sort找到top 10?
回复

使用道具 举报

🔗
chongtianzs 2015-4-3 08:44:06 | 只看该作者
全局:
【解题思路】
先看两个string长度是否相等。若相等,扫一遍s数组,用一个int数组保存每个char出现的次数(假设string只包含ascII字符),扫一遍t数组,一次减少int数组对应的值,若小于0则return false。

【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link]
https://gist.github.com/chongtianzs/55b9374c41f09bb43fb0
【test case】(optional,如果觉得比较好,欢迎贴出来分享)

评分

参与人数 1大米 +7 收起 理由
pure0909 + 7 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
stellari 2015-4-3 10:10:42 | 只看该作者
全局:
slaink 发表于 2015-4-3 04:35
所谓用堆是指存一个augmented 堆吗?每个element包含字符以及他的出现次数,然后靠次数构造堆?

仔细 ...


我看你的回复,你否把我说的“字符串列表”(a list of strings)理解成了“字符列表”(a list of characters)?

我是下面这个意思:

如果这个字符串列表(比如:["abacus", "abandon", "abacus", "abacus", "aberrant", "abandon", ... "zebra"] )很小的话,可以用下面两步完成

1. 用一个放在内存中的hashmap来统计每一个字符串的出现频数: {"abacus"->35, "abandon" -> 7, ...}。
2. 然后建一个10个元素的min-heap,每个元素都是一个hashmap中的pair; 先将hashmap的前10个pair放入这个堆,然后遍历hashmap中剩下的pair。对每个pair,如果它的出现频数大于min-heap的top元素的出现频数的话,则把min-heap的top元素弹出,将当前这个pair压入堆。遍历完成后,min-heap中的10个元素就是最大的频率的10个元素。这和堆排序有些类似。

抱歉,你说的augmented heap我没有听说过,但是我想2中描述的是不是和你说的其实是一个东西?
--------
但是,如果字符串列表非常非常长,那么上面的第1步很可能就不能够完成。尤其是当字符串重复率低的情况下。这时候可以按照hash(x)%1000这样的公式将所有字符串写到1000个小文件里,然后对每个小文件重复上面的1,2两步,得到每个小文件中的top10;然后再对这1000个top10,也就是10000个pair做2这一步,找到全部文件的top10.

回复

使用道具 举报

🔗
daphne_ying 2015-4-3 15:01:09 | 只看该作者
全局:
[solution]
use one array of size 256 to count the occurence of each ascii char in
both string.

[time complexity]
O(n)

[space complexity]
O(1)

[gist link]
https://gist.github.com/kelly-us/b80151534341c7dbaa25

[test case]

评分

参与人数 1大米 +7 收起 理由
pure0909 + 7 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
slaink 2015-4-4 07:30:31 | 只看该作者
全局:
stellari 发表于 2015-4-3 10:10
我看你的回复,你否把我说的“字符串列表”(a list of strings)理解成了“字符列表”(a list of char ...

感谢讲解!是的,我的确是将你说的字符串列表错认为了一个很长的字符串。
这下就清楚了!感谢,另外 augmened heap就是简单指一个带argument的heap(或者其他的数据结构,上课时候老师这么用过,不知道外面是不是也这么用)
回复

使用道具 举报

🔗
Godbless 2015-4-4 11:59:29 | 只看该作者
全局:
【解题思路】Sort the strings, and see if they are equal
【时间复杂度】O(nlogn)
【空间复杂度】O(1)
【gist link]
https://github.com/StephenWeiXu/ ... blob/master/1_3.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享)
https://github.com/StephenWeiXu/ ... blob/master/1_3.cpp
回复

使用道具 举报

全局:
stellari 发表于 2015-4-2 14:01
我没有遇到过。我相信肯定有面试官会问这种题,但是我觉得,单纯问“实现一个hashtable”这种问题,很难 ...

新人求问,像这种问题,如果要用到排序之类的东西,比如想用merge sort,是要自己实现吗
因为我在solution上看到直接调用了sort函数,所以请教下这种情况在面试中一般如何处理? 谢谢啦
回复

使用道具 举报

🔗
stellari 2015-4-5 15:00:21 | 只看该作者
全局:
窗外一棵树 发表于 2015-4-5 10:03
新人求问,像这种问题,如果要用到排序之类的东西,比如想用merge sort,是要自己实现吗
因为我在soluti ...

这要分情况了。面试时需要你自己实现的一般都是考察的关键部分。比如你拿到的面试题是Subsets,这道题要求最后的结果是排好序的,所以我们要一开始先对原序列排一下序。但这不是问题的重点,重点在于你后面怎么用递归或迭代构建subsets。这种情况下,sort的实现就不重要了。

但是,比如对方就是要考你排序,这就不一样了。比如文件里有100亿个数字,问你如何排序?这种情况下,排序就是要解决的终极问题。所以你肯定要自己实现了。不过不管怎么说,常见的排序思想和算法实现都是要熟练掌握的。

评分

参与人数 1大米 +10 收起 理由
窗外一棵树 + 10 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
beer 2015-4-5 18:54:27 | 只看该作者
全局:
【解题思路】
Tips:
* 1&2. Convert String to char array first, then quick sort the array, finally to judge the if two arrays are equal
* 3. Use an int array to count the number of each char in two strings
【时间复杂度】1&2. O(N*log(N))     3. O(N^2)
【空间复杂度】1&2&3. O(N)
【gist link】https://github.com/drinkbeer/Cod ... er/src/CC150_3.java
【test case】

评分

参与人数 1大米 +7 收起 理由
pure0909 + 7 感谢分享!

查看全部评分

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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