logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
问一个 String array sorting 的题。
avatar
问一个 String array sorting 的题。# JobHunting - 待字闺中
W*u
1 楼
原题是,Write a method to sort an array of strings so that all the anagrams
are next to each other.
看到的靠谱的方法是 先 sort 每一个string，然后给每一个sorted后的string
generate 一个key 然后用hashtable 来找到 anagrams的String. 我的问题是这个hash
table 如何生成，能够保证，解决conflicts，并且保证O(1)的查找呢？
本人菜鸟，对hashtable的理解还在寻找hash function 然后每一个key 对应一个
value的层次。简单的就是在知道key的范围的时候用数组实现，当不知道key值范围的
时候就不知道怎么搞了？ 看到C++里的hashtable 实现都是 按照pair 插
入进去的，真心不知道这样的查找怎么能够保证O(1).
求各位前辈高人解疑释惑。 拜谢！
avatar
p*2
2 楼

hash
不是150上的题吗？面试不会考吧？我从来没想过这题。

【在 W***u 的大作中提到】
: 原题是,Write a method to sort an array of strings so that all the anagrams
: are next to each other.
: 看到的靠谱的方法是 先 sort 每一个string，然后给每一个sorted后的string
: generate 一个key 然后用hashtable 来找到 anagrams的String. 我的问题是这个hash
: table 如何生成，能够保证，解决conflicts，并且保证O(1)的查找呢？
: 本人菜鸟，对hashtable的理解还在寻找hash function 然后每一个key 对应一个
: value的层次。简单的就是在知道key的范围的时候用数组实现，当不知道key值范围的
: 时候就不知道怎么搞了？ 看到C++里的hashtable 实现都是 按照pair 插
: 入进去的，真心不知道这样的查找怎么能够保证O(1).
: 求各位前辈高人解疑释惑。 拜谢！
avatar
M*7
3 楼
一般面试Java C#不需要实现哈希。
对于哈希算法单独准备一下各种情况的应对和原理，有兴趣的话找语言中的实现代码读
一下。

hash

【在 W***u 的大作中提到】
: 原题是,Write a method to sort an array of strings so that all the anagrams
: are next to each other.
: 看到的靠谱的方法是 先 sort 每一个string，然后给每一个sorted后的string
: generate 一个key 然后用hashtable 来找到 anagrams的String. 我的问题是这个hash
: table 如何生成，能够保证，解决conflicts，并且保证O(1)的查找呢？
: 本人菜鸟，对hashtable的理解还在寻找hash function 然后每一个key 对应一个
: value的层次。简单的就是在知道key的范围的时候用数组实现，当不知道key值范围的
: 时候就不知道怎么搞了？ 看到C++里的hashtable 实现都是 按照pair 插
: 入进去的，真心不知道这样的查找怎么能够保证O(1).
: 求各位前辈高人解疑释惑。 拜谢！
avatar
W*u
4 楼
不是150上的

【在 p*****2 的大作中提到】
:
: hash
: 不是150上的题吗？面试不会考吧？我从来没想过这题。
avatar
M*7
5 楼
第四版9.2
话说回来，在工作的还要背题真的挺悲催的，工作中的问题和这些问题基本没交集，就
是hashmap用的多。

【在 W***u 的大作中提到】
: 不是150上的
avatar
r*d
6 楼
仍然按照一般的排序办法给字符串数组排序，只是判断两个字符串大小时候，不比较字
符串本身，而是比较两个字符串的字母拆开重新排序后形成的两个字符串。
这样anagram就会排在一起。

hash

【在 W***u 的大作中提到】
: 原题是,Write a method to sort an array of strings so that all the anagrams
: are next to each other.
: 看到的靠谱的方法是 先 sort 每一个string，然后给每一个sorted后的string
: generate 一个key 然后用hashtable 来找到 anagrams的String. 我的问题是这个hash
: table 如何生成，能够保证，解决conflicts，并且保证O(1)的查找呢？
: 本人菜鸟，对hashtable的理解还在寻找hash function 然后每一个key 对应一个
: value的层次。简单的就是在知道key的范围的时候用数组实现，当不知道key值范围的
: 时候就不知道怎么搞了？ 看到C++里的hashtable 实现都是 按照pair 插
: 入进去的，真心不知道这样的查找怎么能够保证O(1).
: 求各位前辈高人解疑释惑。 拜谢！
avatar
W*u
7 楼
谢谢LS各位回答，有人能指点第二点问的关于 hashtable的问题么？ 谢谢！
avatar
h*3
8 楼
c++里面是用map,复杂度是O(nlogn),是用tree实现的。没有hash的直接函数。
avatar
w*f
10 楼
有没有C++ 的hashtable implementation？

【在 h*****3 的大作中提到】
: c++里面是用map,复杂度是O(nlogn),是用tree实现的。没有hash的直接函数。
avatar
f*n
11 楼
TR1 或 C++11里有hash table
但是hash table也无法“保证O(1)的查找”。hash table的worst case是O(n)查找。
binary search tree的worst case是O(log n)

【在 w****f 的大作中提到】
: 有没有C++ 的hashtable implementation？
相关阅读
Glassdoor上的工资准吗？HM回信说wish you the very best是不是就挂了？开始工作之前打算回趟国，relocation的机票和回国机票怎么办？强烈抗议Jimmy Kimmel事件的白宫签名网址 (转载)聘请part time 销售数名，高抽成offer letter上面的title说写错了来，周末福利，cap理论里面的三种策略 (转载)有人面过 skype 的 resercher 岗位吗有没有在Dexcom工作的前辈SAS job opportunity有办法在收到EAD卡之前知道开始日期吗？请教那个scramble string的题目read4 / read4k 实现readAny复杂吗？曾经的生物学老千，如今的年薪10多万美金资深BI专家的网上交流会Qualcomm San Diego 求内推工作中如何保持面试水平？签了offer还能再签一个别的地方的contract 吗OPT终于批了！flickr 新鲜电面请教一个O－1的问题 (转载)
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。