一亩三分地论坛

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

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

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

[复制链接] |试试Instant~ |关注本帖
pure0909 发表于 2015-3-30 10:16:17 | 显示全部楼层 |阅读模式

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

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

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、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改


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

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

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

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

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

查看全部评分

回复 支持 1 反对 0

使用道具 举报

JamesJi 发表于 2015-3-30 21:00:41 | 显示全部楼层
【解题思路】
可以先将两个string排序,然后按位比较
【时间复杂度】
O(n^2)
【空间复杂度】
O(1)
【gist link]
https://gist.github.com/JamesJi9277/65f609a02218ff9cdd61

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

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

查看全部评分

回复 支持 反对

使用道具 举报

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

查看全部评分

回复 支持 反对

使用道具 举报

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,如果觉得比较好,欢迎贴出来分享)
回复 支持 反对

使用道具 举报

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的意思是字符的排列顺序可以任意打乱,而你这个算法仅考虑了字符串整体(有循环)偏移的情况。
回复 支持 反对

使用道具 举报

alikewmk 发表于 2015-3-31 13:53:16 | 显示全部楼层
本帖最后由 alikewmk 于 2015-3-31 15:02 编辑

【解题思路】
对两个string进行快速排序, 然后比较
【时间复杂度】
O(nlogn)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/alikewmk ... eckpermutation-java

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

A30041839 发表于 2015-3-31 18:17:38 | 显示全部楼层
[思路1]
sort the two strings, if the sorted strings are equal, then s1 is permutation of s2
[time complexity]
O(nlogn)
[space complexity]
O(1)

[思路2]
hash table, count frequency of each char
[time complexity]
O(n)
[space complexity]
O(n)

[gist]
https://gist.github.com/A30041839/0bc863eda105ad58edab

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

JamesJi 发表于 2015-3-31 22:03:56 | 显示全部楼层
stellari 发表于 2015-3-30 23:40
如果你面试时这么说,面试官就很可能会问:

“常见的排序算法,比如quicksort,mergesort等的时间复杂 ...

额····求指教
回复 支持 反对

使用道具 举报

iker01 发表于 2015-4-1 12:00:41 | 显示全部楼层
解题思路】
using the sort method first, then compare the two sorted string
【时间复杂度】
O(NlogN)
【空间复杂度】
O(1)
【gist link]
python solution
https://gist.github.com/zhangjiang2013/3b552f9f067156f0d713
【test case】(optional,如果觉得比较好,欢迎贴出来分享)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Godbless 发表于 2015-4-1 12:12:07 | 显示全部楼层
iker01 发表于 2015-3-31 23:00
解题思路】
using the sort method first, then compare the two sorted string
【时间复杂度】

【解题思路】Create an array of 256 boolean values to represent the 256 unique characters in ASCII code.
                Sequentially visit each character of the string to see if repeat characters occur.
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link]
https://github.com/StephenWeiXu/ ... blob/master/1_1.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享)
https://github.com/StephenWeiXu/ ... blob/master/1_1.cpp

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

outtime 发表于 2015-4-1 18:27:49 | 显示全部楼层
【解题思路】
count the number of characters in two strings, use an array of 256 to save, +1 for each char in the first string, -1 for the second
in the end, the array is all zero if the two strings are permutation of each other;
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link]
https://gist.github.com/seeeking/815b9b229dc5c96ed6c1
【test case】(optional,如果觉得比较好,欢迎贴出来分享)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

slaink 发表于 2015-4-2 01:47:04 | 显示全部楼层
【解题思路】
Bin sort or heap sort. If value range is large, then we should use hash table instead of bin sort.
【时间复杂度】
O(n) for bin
O(nlogn) for heap sort
【空间复杂度】
O(1) for bin
O(n) for heap sort
【gist link] https://github.com/bxshi/intervi ... ing_permutation.cpp
【test case】(optional,如果觉得比较好,欢迎贴出来分享)https://github.com/bxshi/intervi ... c/test/1_3_test.cpp

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

slaink 发表于 2015-4-2 01:48:56 | 显示全部楼层
stellari 发表于 2015-3-31 23:52
所以我觉得你一开始就说自己用了排序的方法是O(nlogn)好了。这时对方应该会让你改进,你就可以上hashtabl ...

有遇到过让你实现hashtable的吗?我现在写题都尽量不用STL 容器,不知道面试时候会不会要求实现
回复 支持 反对

使用道具 举报

mything 发表于 2015-4-2 10:09:14 | 显示全部楼层
本帖最后由 mything 于 2015-4-2 10:14 编辑

【解题思路】
1、用Hash Table(Unicode)或256长的数组(Extend ASCII),保存每个字母的出现频率
2、第一次用第一个字符串填写这个数组,第二次用第二个字符串减少计数器,如果发现出现负值则返回false

如果不用额外数据并且输入可变,则排序之后比较,O(NLogN)
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link]
https://gist.github.com/n2iw/c1e56af0ef1bd17f4522
【test case】(optional,如果觉得比较好,欢迎贴出来分享)

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 03:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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