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

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

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
1.3 Given two strings, write a method to decide if one is a permutation of the other.

请参加活动的童鞋跟帖回复自己的解法,回复请参考以下格式:

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link]
【test case】(optional,如果觉得比较好,欢迎贴出来分享)

Notice:
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子,除了贴解法,欢迎探讨各种follow up questions,集思广益
4、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改



上一篇:【第四轮】3.30 - 4.5 Career Cup 1.2
下一篇:【第四轮】3.30- 4.5 Career Cup 1.4
推荐
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 例子非常好!

查看全部评分

回复

使用道具 举报

推荐
stellari 2015-3-31 23:52:43 | 只看该作者
全局:

所以我觉得你一开始就说自己用了排序的方法是O(nlogn)好了。这时对方应该会让你改进,你就可以上hashtable的解法。要是你说了排序的方法是O(n),对方会觉得有两种可能:
1. 你错误地认为一般排序算法都是O(n),
2. 你知道O(n)的解法。
所以他多半会进一步追问确认。如果到了这一步,你又无法证明你是情况2,那面试官很可能对你的印象会变差了。O(n)的排序算法的确实存在,比如Bucket sort,counting sort等。但是,你最后会发现这些O(n)的算法对这道问题而言,其实和hashtable没有本质区别,还不如一开始就老实用hashtable好了。

评分

参与人数 1大米 +3 收起 理由
JamesJi + 3 很有用的信息!

查看全部评分

回复

使用道具 举报

推荐
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.

回复

使用道具 举报

🔗
JamesJi 2015-3-30 21:00:41 | 只看该作者
全局:
【解题思路】
可以先将两个string排序,然后按位比较
【时间复杂度】
O(n^2)
【空间复杂度】
O(1)
【gist link]
https://gist.github.com/JamesJi9277/65f609a02218ff9cdd61

评分

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

查看全部评分

回复

使用道具 举报

🔗
stellari 2015-3-30 22:17:05 | 只看该作者
全局:
JamesJi 发表于 2015-3-30 21:00
【解题思路】
可以先将两个string排序,然后按位比较
【时间复杂度】


排序后逐位比较的算法,为什么时间复杂度会是O(n^2)?
回复

使用道具 举报

🔗
JamesJi 2015-3-31 00:35:50 | 只看该作者
全局:
stellari 发表于 2015-3-30 09:17
排序后逐位比较的算法,为什么时间复杂度会是O(n^2)?

不好意思,应该是O(n)
回复

使用道具 举报

🔗
Fiona杀G 2015-3-31 01:43:01 | 只看该作者
全局:
1.3 Given two strings, write a method to decide if one is a permutation of the other.

[solution]
use two array of size 256 to count the appear time of each ascii char in
both string.

[time complexity]
O(n)

[space complexity]
O(1)

[gist link]
https://gist.github.com/FionaT/bf63252875f31dd1bacb

[test case]

评分

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

查看全部评分

回复

使用道具 举报

🔗
laonong15 2015-3-31 05:06:09 | 只看该作者
全局:
【解题思路】
create a hashtable <Integer,Integer> Key is the char of the String element, value is the count of char in the string
traverse first  string to initial the hashtable.
use the hashtable to compare the second string chars if any value become 0 return false finally return true;
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link]
https://gist.github.com/michaelniu/52defe4d1bb7b373b00d
【test case】
https://gist.github.com/michaelniu/52defe4d1bb7b373b00d  (main function)

评分

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

查看全部评分

回复

使用道具 举报

🔗
babysor 2015-3-31 07:20:28 | 只看该作者
全局:
JamesJi 发表于 2015-3-31 00:35
不好意思,应该是O(n)

排序是nlogn
回复

使用道具 举报

🔗
kateheart 2015-3-31 10:35:54 | 只看该作者
全局:
【解题思路】
把其中一个,叫A把,复制两边。比如 trings 变成 tringstring, 然后看另外一个是不是它的substring
【时间复杂度】
【空间复杂度】
【gist link]
【test case】(optional,如果觉得比较好,欢迎贴出来分享)

点评

关于如何使用gist链接可以看本版的帖子哦~~  发表于 2015-4-7 02:00
回复

使用道具 举报

🔗
stellari 2015-3-31 12:40:53 | 只看该作者
全局:
JamesJi 发表于 2015-3-31 00:35
不好意思,应该是O(n)

如果你面试时这么说,面试官就很可能会问:

“常见的排序算法,比如quicksort,mergesort等的时间复杂度都是O(nlogn)的,你说你的程序复杂度是O(n),就是说你可以在O(n)时间之内实现排序?那么你是如何做到这一点的?”

你会怎么回答这个问题?
回复

使用道具 举报

🔗
stellari 2015-3-31 12:42:27 | 只看该作者
全局:
kateheart 发表于 2015-3-31 10:35
【解题思路】
把其中一个,叫A把,复制两边。比如 trings 变成 tringstring, 然后看另外一个是不是它的su ...

这个不行的。permutation的意思是字符的排列顺序可以任意打乱,而你这个算法仅考虑了字符串整体(有循环)偏移的情况。
回复

使用道具 举报

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

本版积分规则

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