l****p
发帖数: 397 | 1 先是面试官自我介绍，然后让我描述一个近期的项目。接着开始做题。题目和我在面试
时写的代码都在http://collabedit.com/w9muy
前面那道我说先可以去掉非字母的字符，然后倒排，然后再和倒排前比较，复杂度是O(
n)。他说能不能不用多余空间，于是我得出后来的解法。刚才在整理代码时才发现，还
有一个要求我居然看错了：case insensitive我看成了case sensitive
后面那道我先是得出O(m*n*log(n))的解法，他让我优化，于是我说可以对getSig()进
行优化，用哈希表记录各个字符出现的次数，然后算出整个哈希表的hashcode，作为
signature，这样可以达到O(m*n)。面试官又问，重复的字符串怎么办，我这才看到题
目中有要求去重复，于是把存anagram的数组改成了集合
题目不难，但把我的粗心暴露无遗
整理过可运行的代码在https://gist.github.com/linzhp/7035991 |
b**********5
发帖数: 7881 | |
b*******w
发帖数: 56 | 3 不是网站的会员， 楼主还是把第一题贴一下吧， 谢谢！ |
w********s
发帖数: 214 | 4 第二题貌似可以先把每个string变成 char array,然后排序，再变成string，然后存到
hashmap里。
,排序后的string做key, value就是一个string ()数组; 每个string都有同样的sorted
char array 也就是key.
最后把hashmap一个一个的值倒出来就是返回值了，时间复杂度是 O(m*nlg*n),空间复
杂度是O(n).
代码应该不长而且符合要求。 |
l****p
发帖数: 397 | 5 bool isPalindrome(string s);
A palindrome is a string that is the same when read backwards or forwards.
For example, "aba", "abba", and "racecar" are all palindromes.
You will implement a method to determine whether a string is a palindrome.
- Palindromes are case insensitive, so "Aba" is a palindrome.
- Palindromes ignore non a-z characters, so "a0ba" and "a- #&#b*b-a" are
palindromes
- The empty string "" and strings with no letters, e.g. "123" are not
palindromes.
【在 b*******w 的大作中提到】
: 不是网站的会员， 楼主还是把第一题贴一下吧， 谢谢！
|
s********u
发帖数: 1109 | 6 这个不是cc150原题么？我上次看一个老印写的办法很有意思，就是不用sort array。
而是将每个字符对应一个素数，hashtable的key就是素数的乘积。如果两个string对应
的key相同，就一定是anagram。 |
e***a
发帖数: 1661 | 7 what is ur qualification? |
g*********e
发帖数: 14401 | 8 这个办法是很好 就是数组长了加起来会很大
【在 s********u 的大作中提到】
: 这个不是cc150原题么？我上次看一个老印写的办法很有意思，就是不用sort array。
: 而是将每个字符对应一个素数，hashtable的key就是素数的乘积。如果两个string对应
: 的key相同，就一定是anagram。
|
p******4
发帖数: 31 | 9
O(
【在 l****p 的大作中提到】
: 先是面试官自我介绍，然后让我描述一个近期的项目。接着开始做题。题目和我在面试
: 时写的代码都在http://collabedit.com/w9muy
: 前面那道我说先可以去掉非字母的字符，然后倒排，然后再和倒排前比较，复杂度是O(
: n)。他说能不能不用多余空间，于是我得出后来的解法。刚才在整理代码时才发现，还
: 有一个要求我居然看错了：case insensitive我看成了case sensitive
: 后面那道我先是得出O(m*n*log(n))的解法，他让我优化，于是我说可以对getSig()进
: 行优化，用哈希表记录各个字符出现的次数，然后算出整个哈希表的hashcode，作为
: signature，这样可以达到O(m*n)。面试官又问，重复的字符串怎么办，我这才看到题
: 目中有要求去重复，于是把存anagram的数组改成了集合
: 题目不难，但把我的粗心暴露无遗
|
s********u
发帖数: 1109 | 10 你的意思是字符串长了会很大？其实只要不超过long long的值，还是绝对划算的，因
为不用对字符串排序了。
【在 g*********e 的大作中提到】
: 这个办法是很好 就是数组长了加起来会很大
|
l*n
发帖数: 529 | 11 http://en.wikipedia.org/wiki/Computational_complexity_of_mathem
真的long起来了，效率不是你想的O(1)啊。
【在 s********u 的大作中提到】
: 你的意思是字符串长了会很大？其实只要不超过long long的值，还是绝对划算的，因
: 为不用对字符串排序了。
|
