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？
相关阅读
今天算是见到最精炼的Integer to Roman的解法了拿到了新的offer，旧的公司什么时候辞职？雅虎真有意思求整理过的G家面试题A和G的contractor多吗？千万不要纠结帮我们的人有否私心，看看孔子怎么说的 (转载)请教一个多线程设计的面试题说到老中相轻，我突然回想到ICC这帮骗子Bloomberg 电面+onsite 。。已挂求大数加1题目的细节印度小将鼓吹美国生活丰富多彩，10万年薪顶印度的三十万 (转载)在期望国人帮忙的时候也多为对方考虑求大家 linked in 内推~~~排一下湾区最垃圾和最友好的公司吧请问 Apple家backgroundcheck都查什么求intel等实习内推ASIC数字电路full time求内推~！小弟必知恩图报！这种情况咋办？Member of Technical Staff是什么职位？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。