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

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

地里匿名用户
🔗
匿名用户-V1XIV  2015-3-31 13:53:16
本帖最后由 匿名 于 2015-3-31 15:02 编辑

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

评分

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

查看全部评分

回复

使用道具 举报

🔗
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大米 +7 收起 理由
pure0909 + 7 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
JamesJi 2015-3-31 22:03:56 | 只看该作者
全局:
stellari 发表于 2015-3-30 23:40
如果你面试时这么说,面试官就很可能会问:

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

额····求指教
回复

使用道具 举报

🔗
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 很有用的信息!

查看全部评分

回复

使用道具 举报

🔗
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大米 +7 收起 理由
pure0909 + 7 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
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大米 +7 收起 理由
pure0909 + 7 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
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大米 +7 收起 理由
pure0909 + 7 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
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大米 +7 收起 理由
pure0909 + 7 感谢分享!

查看全部评分

回复

使用道具 举报

🔗
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大米 +7 收起 理由
pure0909 + 7 感谢分享!

查看全部评分

回复

使用道具 举报

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

本版积分规则

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