由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - F家电面:group Anagrams
相关主题
facebook telephone interview from careercupGoogle 需要bug free 么?
问一个 String array sorting 的题。Anagrams有面试碰到过么?
问一个Anagram的参考程序LC anagrams题目有问题吧?
请问我写的这个代码哪可以改进一下LC: anagram为何忽略single element?
careercup 150一题。 9.2google phone interview
仅存onsite一只。。。散尽家财求bless问一道题(8)
问个anagram的问题问个anagram的算法题
一道G家店面题请教2个 huge file的面试题
相关话题的讨论汇总
话题: string话题: anagrams话题: sort话题: anagram话题: 长度
进入JobHunting版参与讨论
1 (共1页)
l******n
发帖数: 1250
1
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
本来还想偷懒,写个O(n2)的算法了事,结果直接被面试官叫停
后来被迫想O(n)算法,好在稀了糊涂地写出来了
我45分钟之内,就写了这一道题
看板上的其他兄弟,随便就是写两道题。 我估计不是挂掉了,就得再加面一轮。
p*********g
发帖数: 2998
2
请问你这个题最后的return的数据结构是什么, 是不是return 一个hashtable, key放
string(排过序的), value放一个arraylist放所有在这个组的string?
l******n
发帖数: 1250
3
是一个bucket
{ { abcd, dcba}, {chip, ipch}, {ook}}
m******3
发帖数: 346
4
是不是用把每个string sort,得到一个排过序的string作为key, 然后原来的string作
为value插入map,有什么要注意的地方么?

【在 l******n 的大作中提到】
: Given an array of strings, return all groups of strings that are anagrams.
: Note: All inputs will be in lower-case.
: 本来还想偷懒,写个O(n2)的算法了事,结果直接被面试官叫停
: 后来被迫想O(n)算法,好在稀了糊涂地写出来了
: 我45分钟之内,就写了这一道题
: 看板上的其他兄弟,随便就是写两道题。 我估计不是挂掉了,就得再加面一轮。

l******n
发帖数: 1250
5
"得到一个排过序的string作为key, 然后原来的string作为value插入map"
这样同一个key会有很多value
x****m
发帖数: 1084
6
value is a vector

【在 l******n 的大作中提到】
: "得到一个排过序的string作为key, 然后原来的string作为value插入map"
: 这样同一个key会有很多value

x*****n
发帖数: 195
7
sort每个string里的chars的方法,这个本事是nlogn的操作,n是string的平均长度。
如果是m个string要处理,那时间复杂度是mnlogn。这个是面试官希望的么?

【在 l******n 的大作中提到】
: Given an array of strings, return all groups of strings that are anagrams.
: Note: All inputs will be in lower-case.
: 本来还想偷懒,写个O(n2)的算法了事,结果直接被面试官叫停
: 后来被迫想O(n)算法,好在稀了糊涂地写出来了
: 我45分钟之内,就写了这一道题
: 看板上的其他兄弟,随便就是写两道题。 我估计不是挂掉了,就得再加面一轮。

r********3
发帖数: 24
8
这个是先给定两个string a1, string a2,先判断是否长度相等,如果相等用radix
sort, time 复杂度 O(n*k),
n 是a1 长度,k=26,假设只有26个小写字母得话。
然后以排好序的作为一个key,放到hashtable里, 这样应该是O(n)

【在 l******n 的大作中提到】
: Given an array of strings, return all groups of strings that are anagrams.
: Note: All inputs will be in lower-case.
: 本来还想偷懒,写个O(n2)的算法了事,结果直接被面试官叫停
: 后来被迫想O(n)算法,好在稀了糊涂地写出来了
: 我45分钟之内,就写了这一道题
: 看板上的其他兄弟,随便就是写两道题。 我估计不是挂掉了,就得再加面一轮。

r******d
发帖数: 308
9
好像可以不用string长度
思路
Step1 把每个string用radix 的思路转换一下。 例如babab可以转换成a2b3(a出现2次b
出现3次)
Step2 将所有string放到一个hush table里。key 是上步转换后的string.value是list
。如果有conflict 就插入list尾端
Step3 遍历一遍所有string 打印结果

【在 r********3 的大作中提到】
: 这个是先给定两个string a1, string a2,先判断是否长度相等,如果相等用radix
: sort, time 复杂度 O(n*k),
: n 是a1 长度,k=26,假设只有26个小写字母得话。
: 然后以排好序的作为一个key,放到hashtable里, 这样应该是O(n)

x***i
发帖数: 585
10
难道这不是 leetcode 100年前的原题吗? 咋突然领出来?
am i missing sth?
相关主题
仅存onsite一只。。。散尽家财求blessGoogle 需要bug free 么?
问个anagram的问题Anagrams有面试碰到过么?
一道G家店面题LC anagrams题目有问题吧?
进入JobHunting版参与讨论
z**********e
发帖数: 12
11
正解,就是原题啊,sort一下就好啦
x****u
发帖数: 12955
12

为什么要先sort,然后再做hash?先检测长度,不同则不是。长度相同就直接挨个比较
两个string的字母,一个从前向后,一个从后向前,任何时候有不同就证明不是,中断
循环。循环正常完毕就证明是anagram。
还有应该可以把其中一个string反过来存储。然后把两个string做一个XOR。结果不是0
的就不是。

【在 r********3 的大作中提到】
: 这个是先给定两个string a1, string a2,先判断是否长度相等,如果相等用radix
: sort, time 复杂度 O(n*k),
: n 是a1 长度,k=26,假设只有26个小写字母得话。
: 然后以排好序的作为一个key,放到hashtable里, 这样应该是O(n)

l******s
发帖数: 3045
13
anagram is in different logic of palindrome

【在 x****u 的大作中提到】
:
: 为什么要先sort,然后再做hash?先检测长度,不同则不是。长度相同就直接挨个比较
: 两个string的字母,一个从前向后,一个从后向前,任何时候有不同就证明不是,中断
: 循环。循环正常完毕就证明是anagram。
: 还有应该可以把其中一个string反过来存储。然后把两个string做一个XOR。结果不是0
: 的就不是。

x****u
发帖数: 12955
14

啊。错成这样。脑子糊涂了。
不过,还是不用sort,假设字符是英文字母,就设两个个26单元的array。然后一个
string从前向后,另一个sting从后向前,见到一个字符就把对应的那个array单元加一
。最后然后比较两个array,每个单元的数字都一样的就是anagram/

【在 l******s 的大作中提到】
: anagram is in different logic of palindrome
s******x
发帖数: 417
15
直接sort,然后查找Map,找到了就把index存入map,
然后回头再把map内index array个数多于1个的打印出来即可。
O(n)
q*z
发帖数: 13362
16
应该可以design一个hash,把所有的anagram map到一个值上,这样就是o(n).
比如把字符视为27进制的数,a为1,z为26,先sort再转换,这样的hash应该是所有的
anagram map到同一个值的
hash计算可以从a到z扫描26遍,逐个进位。复杂度o(k)k为字符串长度。
注意hash变量的最大值会限制能处理的字串最大长度。

【在 l******n 的大作中提到】
: Given an array of strings, return all groups of strings that are anagrams.
: Note: All inputs will be in lower-case.
: 本来还想偷懒,写个O(n2)的算法了事,结果直接被面试官叫停
: 后来被迫想O(n)算法,好在稀了糊涂地写出来了
: 我45分钟之内,就写了这一道题
: 看板上的其他兄弟,随便就是写两道题。 我估计不是挂掉了,就得再加面一轮。

J*******o
发帖数: 741
17

同问, 面试官是不是不满意这种复杂度的?

【在 x*****n 的大作中提到】
: sort每个string里的chars的方法,这个本事是nlogn的操作,n是string的平均长度。
: 如果是m个string要处理,那时间复杂度是mnlogn。这个是面试官希望的么?

a******g
发帖数: 13519
18
不能是o(n)吧?sort的复杂度是多少?

【在 s******x 的大作中提到】
: 直接sort,然后查找Map,找到了就把index存入map,
: 然后回头再把map内index array个数多于1个的打印出来即可。
: O(n)

j**********3
发帖数: 3211
19
我都没看懂这个题什么意思,和leetcode上有什么不同?
n******n
发帖数: 12088
20
还有字符串本身长度。

【在 l******n 的大作中提到】
: Given an array of strings, return all groups of strings that are anagrams.
: Note: All inputs will be in lower-case.
: 本来还想偷懒,写个O(n2)的算法了事,结果直接被面试官叫停
: 后来被迫想O(n)算法,好在稀了糊涂地写出来了
: 我45分钟之内,就写了这一道题
: 看板上的其他兄弟,随便就是写两道题。 我估计不是挂掉了,就得再加面一轮。

s******x
发帖数: 417
21
pre-process不算复杂度。
查找的复杂度是O(n).

【在 a******g 的大作中提到】
: 不能是o(n)吧?sort的复杂度是多少?
1 (共1页)
进入JobHunting版参与讨论
相关主题
请教2个 huge file的面试题careercup 150一题。 9.2
Bloomerg 还没放弃我。 电话二面经过。仅存onsite一只。。。散尽家财求bless
一道有关String的面试题问个anagram的问题
问个简单的问题...一道G家店面题
facebook telephone interview from careercupGoogle 需要bug free 么?
问一个 String array sorting 的题。Anagrams有面试碰到过么?
问一个Anagram的参考程序LC anagrams题目有问题吧?
请问我写的这个代码哪可以改进一下LC: anagram为何忽略single element?
相关话题的讨论汇总
话题: string话题: anagrams话题: sort话题: anagram话题: 长度