a********1
发帖数: 750 | 1 早上电面的题目，
比如 "a" "c" 和"a" "b" "a"
要求输出“a”
第一想法是用hash table, 把smaller array的element都放进去。然后遍历array2。
忘了处理array2本身的重复情况，被面试官指出来了。
第二想法是sort
后来面试官问不用external ,能不能linear , 没想法。又提示说对于“a” "b" "a"的
第二个a如何知道已经被找过了，，不sort不用external storage还是没想法
最后问了问两个的复杂度，他说ok 就让我问他问题了
感觉很不好 |
r*******y
发帖数: 1081 | 2 第二个数组有重复也不会影响输出结果吧？
输出的不还是啊 'a'吗？
【在 a********1 的大作中提到】
: 早上电面的题目，
: 比如 "a" "c" 和"a" "b" "a"
: 要求输出“a”
: 第一想法是用hash table, 把smaller array的element都放进去。然后遍历array2。
: 忘了处理array2本身的重复情况，被面试官指出来了。
: 第二想法是sort
: 后来面试官问不用external ,能不能linear , 没想法。又提示说对于“a” "b" "a"的
: 第二个a如何知道已经被找过了，，不sort不用external storage还是没想法
: 最后问了问两个的复杂度，他说ok 就让我问他问题了
: 感觉很不好
|
k*j
发帖数: 153 | 3 同不理解如果array2有重复。为什么需要特别处理？
【在 a********1 的大作中提到】
: 早上电面的题目，
: 比如 "a" "c" 和"a" "b" "a"
: 要求输出“a”
: 第一想法是用hash table, 把smaller array的element都放进去。然后遍历array2。
: 忘了处理array2本身的重复情况，被面试官指出来了。
: 第二想法是sort
: 后来面试官问不用external ,能不能linear , 没想法。又提示说对于“a” "b" "a"的
: 第二个a如何知道已经被找过了，，不sort不用external storage还是没想法
: 最后问了问两个的复杂度，他说ok 就让我问他问题了
: 感觉很不好
|
t*******i
发帖数: 4960 | 4 估计是要处理数组中某字符和另外一个数组的元素不重复，但是和自己树组里的元素重
复的问题。 |
t*******i
发帖数: 4960 | 5 如果都是ｌｅｔｔｅｒ的话，c里面就那么２６个ｌｅｔｔｅｒ，固定一个ｌｅｔｔｅｒ,从a-z扫描一遍两个数组
，count一下就知道是不是重复了。复杂度是 ２６（元素总和），也是 ｏ(ｎ)吧
当然如果用个树组 ａｒｒ［２６］就可以扫一遍了。 |
a********1
发帖数: 750 | 6 有，因为第二个a还是会和hash table里面的array1的a重复，所以结果是"a""a"
需要在重复的时候删除hash item或者结果也放在hash table然后to array
【在 r*******y 的大作中提到】
: 第二个数组有重复也不会影响输出结果吧？
: 输出的不还是啊 'a'吗？
|
a********1
发帖数: 750 | 7 array of string.
ｅｒ,从a-z扫描一遍两个数组
【在 t*******i 的大作中提到】
: 如果都是ｌｅｔｔｅｒ的话，c里面就那么２６个ｌｅｔｔｅｒ，固定一个ｌｅｔｔｅｒ,从a-z扫描一遍两个数组
: ，count一下就知道是不是重复了。复杂度是 ２６（元素总和），也是 ｏ(ｎ)吧
: 当然如果用个树组 ａｒｒ［２６］就可以扫一遍了。
|
t*******i
发帖数: 4960 | 8 ａｒｒａｙ ｏｆ ｓｔｒｉｎｇ??
那是要找出重复的字符串？
比如，ａｒｒａｙ １: ｛"ａｂｃ", "ｅｄ", “ａｄｆ"｝
ａｒｒａｙ ２: ｛"ａｂｃ"｝
输出 ａｂｃ
【在 a********1 的大作中提到】
: array of string.
:
: ｅｒ,从a-z扫描一遍两个数组
|
a********1
发帖数: 750 | 9 对啊
【在 t*******i 的大作中提到】
: ａｒｒａｙ ｏｆ ｓｔｒｉｎｇ??
: 那是要找出重复的字符串？
: 比如，ａｒｒａｙ １: ｛"ａｂｃ", "ｅｄ", “ａｄｆ"｝
: ａｒｒａｙ ２: ｛"ａｂｃ"｝
: 输出 ａｂｃ
|
t*******i
发帖数: 4960 | 10 不会。
【在 a********1 的大作中提到】
: 对啊
|
|
|
r*******g
发帖数: 1335 | 11 为什么不是先对两个数组排序，然后按照顺序比较，这样就可以linear给出duplicate
了，但是需要额外空间。
【在 a********1 的大作中提到】
: 对啊
|
a********1
发帖数: 750 | 12 排序怎么可能linear?
duplicate
【在 r*******g 的大作中提到】
: 为什么不是先对两个数组排序，然后按照顺序比较，这样就可以linear给出duplicate
: 了，但是需要额外空间。
|
r*******g
发帖数: 1335 | 13 你说的对，我的错。
【在 a********1 的大作中提到】
: 排序怎么可能linear?
:
: duplicate
|
r*******g
发帖数: 1335 | 14 他也许是想你用trie来维护，但是空间达不到要求。
【在 a********1 的大作中提到】
: 排序怎么可能linear?
:
: duplicate
|
h**6
发帖数: 4160 | 15 再用一个哈希表把每次的输出存起来。
对于每个数组2的元素，如果存在于数组1对应的哈希表，而不存在另一个输出哈希表，那么添加到哈希表中并输出。 |
a********1
发帖数: 750 | 16 有一定道理，当时没想到trie
【在 r*******g 的大作中提到】
: 他也许是想你用trie来维护，但是空间达不到要求。
|
t*******i
发帖数: 4960 | 17 排序本身的复杂度？
duplicate
【在 r*******g 的大作中提到】
: 为什么不是先对两个数组排序，然后按照顺序比较，这样就可以linear给出duplicate
: 了，但是需要额外空间。
|
d***n
发帖数: 65 | 18 楼主是想说不使用external storage还是不使用extra space，还是要求O(1)空间复杂
度？ |
a********1
发帖数: 750 | 19 面试官的原话是external storage ,当然在当时的context里面就是指我说的hash
table, 可以理解为O(1) 空间复杂度吧
【在 d***n 的大作中提到】
: 楼主是想说不使用external storage还是不使用extra space，还是要求O(1)空间复杂
: 度？
|
d****z
发帖数: 53 | 20 如果是字符的话，就int64的vector bit记录出现了哪些字符，然后两个and一下就知道
有没有duplicate了，O（1）space，linear time
【在 a********1 的大作中提到】
: 早上电面的题目，
: 比如 "a" "c" 和"a" "b" "a"
: 要求输出“a”
: 第一想法是用hash table, 把smaller array的element都放进去。然后遍历array2。
: 忘了处理array2本身的重复情况，被面试官指出来了。
: 第二想法是sort
: 后来面试官问不用external ,能不能linear , 没想法。又提示说对于“a” "b" "a"的
: 第二个a如何知道已经被找过了，，不sort不用external storage还是没想法
: 最后问了问两个的复杂度，他说ok 就让我问他问题了
: 感觉很不好
|
|
|
y******n
发帖数: 47 | 21 如果数组元素只是ASCII字符的话, 只有255个可能的字符, 那么hashtable不就是o(1)
space的么?
这样就行了 int a [256];
【在 a********1 的大作中提到】
: 面试官的原话是external storage ,当然在当时的context里面就是指我说的hash
: table, 可以理解为O(1) 空间复杂度吧
|
y******n
发帖数: 47 | 22 counting sort
【在 a********1 的大作中提到】
: 排序怎么可能linear?
:
: duplicate
|
c**********6
发帖数: 105 | 23 答得挺好的
这题不用external storage没有linear解法！
【在 a********1 的大作中提到】
: 早上电面的题目，
: 比如 "a" "c" 和"a" "b" "a"
: 要求输出“a”
: 第一想法是用hash table, 把smaller array的element都放进去。然后遍历array2。
: 忘了处理array2本身的重复情况，被面试官指出来了。
: 第二想法是sort
: 后来面试官问不用external ,能不能linear , 没想法。又提示说对于“a” "b" "a"的
: 第二个a如何知道已经被找过了，，不sort不用external storage还是没想法
: 最后问了问两个的复杂度，他说ok 就让我问他问题了
: 感觉很不好
|
