由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 老问题了,网上竟然找不到答案
相关主题
找2个sorted array中的第K小的元素,有O(lgn)方法吗?新鲜C3 energy面经
merge a1,a2,..b1,b2 to a1b1a2b2..问道面试题
被Facebook的面试的一道题目难倒了Google的这一道题的最优解?继续求助@!
两个Sorted Array,找K smallest elementMS a0, a1, ..., b0, b1... 问题
问一下deep copy和shallow copy的问题(C#)问一道题(2)
Find the intersection of two sorted arrays【扩展】如何计算recursion的空间复杂度
请教一下external sorting的问题一个特别的inplace merge two sorted arrays
a question算法题:min heap inplace变 BST
相关话题的讨论汇总
话题: arrays话题: find话题: array1话题: array2话题: space
进入JobHunting版参与讨论
1 (共1页)
R***r
发帖数: 120
1
无意中看到这道题,google了一下竟然发现很多提问但没一个可靠的答案,大家帮忙看
看。
Given two arrays of numbers, find if each of the two arrays have the same
set of integers? Suggest an algo which can run faster than NlogN without
extra space?
C**********n
发帖数: 100
2
是不是问两个数组都是由同样的数字组成?

【在 R***r 的大作中提到】
: 无意中看到这道题,google了一下竟然发现很多提问但没一个可靠的答案,大家帮忙看
: 看。
: Given two arrays of numbers, find if each of the two arrays have the same
: set of integers? Suggest an algo which can run faster than NlogN without
: extra space?

S**Y
发帖数: 136
3
o(1) space and o(n) time? doesn't seem possible...

【在 R***r 的大作中提到】
: 无意中看到这道题,google了一下竟然发现很多提问但没一个可靠的答案,大家帮忙看
: 看。
: Given two arrays of numbers, find if each of the two arrays have the same
: set of integers? Suggest an algo which can run faster than NlogN without
: extra space?

g*******y
发帖数: 1930
4
本来觉得这类题要提高时间性能,用hash是很好的。不过要求不用extra space,难道用in place 开放寻址的hashing?

【在 R***r 的大作中提到】
: 无意中看到这道题,google了一下竟然发现很多提问但没一个可靠的答案,大家帮忙看
: 看。
: Given two arrays of numbers, find if each of the two arrays have the same
: set of integers? Suggest an algo which can run faster than NlogN without
: extra space?

R***r
发帖数: 120
5


【在 C**********n 的大作中提到】
: 是不是问两个数组都是由同样的数字组成?
C**********n
发帖数: 100
6
以前见过一个家伙说过
可以两个数组互减,然后将差相加,如果为0,则相同。
比如a=[1,3,6,4],b=[6,1,4,3]
差为[-5,2,2,1],相加为0。
这种方法对否?

【在 R***r 的大作中提到】
: 对
S**Y
发帖数: 136
7
cant u just verify?
[0 0 0 0]
[2 2 -2 -2]
[-2 -2 2 2] sum = 0
do u think they equal?

【在 C**********n 的大作中提到】
: 以前见过一个家伙说过
: 可以两个数组互减,然后将差相加,如果为0,则相同。
: 比如a=[1,3,6,4],b=[6,1,4,3]
: 差为[-5,2,2,1],相加为0。
: 这种方法对否?

g*******y
发帖数: 1930
8
ft
这个只是判断了两个数组的和相等啊
另外,这题关于duplicate的数字是怎么要求的?
比如,A ={1,2,2}
B ={1,2}
是否output true?

【在 C**********n 的大作中提到】
: 以前见过一个家伙说过
: 可以两个数组互减,然后将差相加,如果为0,则相同。
: 比如a=[1,3,6,4],b=[6,1,4,3]
: 差为[-5,2,2,1],相加为0。
: 这种方法对否?

C**********n
发帖数: 100
9
是不是还得用一个数组表示各个数字用了多少次?

【在 g*******y 的大作中提到】
: ft
: 这个只是判断了两个数组的和相等啊
: 另外,这题关于duplicate的数字是怎么要求的?
: 比如,A ={1,2,2}
: B ={1,2}
: 是否output true?

S**Y
发帖数: 136
10
i guess not hehe

【在 g*******y 的大作中提到】
: ft
: 这个只是判断了两个数组的和相等啊
: 另外,这题关于duplicate的数字是怎么要求的?
: 比如,A ={1,2,2}
: B ={1,2}
: 是否output true?

相关主题
Find the intersection of two sorted arrays【扩展】新鲜C3 energy面经
请教一下external sorting的问题问道面试题
a questionGoogle的这一道题的最优解?继续求助@!
进入JobHunting版参与讨论
f**e
发帖数: 1269
11
把两个数组的数字都xor起来,如果等于0的话就return true。

【在 R***r 的大作中提到】
: 无意中看到这道题,google了一下竟然发现很多提问但没一个可靠的答案,大家帮忙看
: 看。
: Given two arrays of numbers, find if each of the two arrays have the same
: set of integers? Suggest an algo which can run faster than NlogN without
: extra space?

S**Y
发帖数: 136
12
still not correct.
easy find counter cases

【在 f**e 的大作中提到】
: 把两个数组的数字都xor起来,如果等于0的话就return true。
N*D
发帖数: 3641
13
ft

【在 f**e 的大作中提到】
: 把两个数组的数字都xor起来,如果等于0的话就return true。
s********y
发帖数: 3811
14
set1: 22
set2: 11

【在 f**e 的大作中提到】
: 把两个数组的数字都xor起来,如果等于0的话就return true。
g*******y
发帖数: 1930
15
yes只能说明 A 并 B的集合里面,每个元素都出现了偶数次
当然,如果你明确的知道A,B中的元素都是unique的话,这个方法可以。

【在 S**Y 的大作中提到】
: still not correct.
: easy find counter cases

o*o
发帖数: 404
16
像这种要求without extra space,是指不能用任何temporary变量吗?
比如求和的sum。

【在 R***r 的大作中提到】
: 无意中看到这道题,google了一下竟然发现很多提问但没一个可靠的答案,大家帮忙看
: 看。
: Given two arrays of numbers, find if each of the two arrays have the same
: set of integers? Suggest an algo which can run faster than NlogN without
: extra space?

f*********r
发帖数: 68
17
我认为可以从"例证法"考虑. 因为集合中的数都是整数, 找到最大最小值后, 先比较,
如果不同, 原集合不一样, 否则的话, 可以根据这两个最值找一个或几个数(floating
point), 然后和每一个集合中的数相减, 然后计算差的平方和, 判断是否相等. 至于
这几个用来例证的数怎么找, 有些trick, 还没有完全想明白.
z***e
发帖数: 5393
18
actually don't need to use b-search, you can make decision while sorting.
find a common number, using quick sort, the firt iteration will divide to:
A: array1, array2
B: array1, array2
if (A.array1.size == B.array1.size && A.array2.size == B.array2.size)
recursively do this until the array size is different.
if A == B, the complexity is at most O(nlgn) (quick sort);
otherwise it's smaller.
so the total complexity <=O(nlgn)
c****l
发帖数: 1280
19
find a common number?

【在 z***e 的大作中提到】
: actually don't need to use b-search, you can make decision while sorting.
: find a common number, using quick sort, the firt iteration will divide to:
: A: array1, array2
: B: array1, array2
: if (A.array1.size == B.array1.size && A.array2.size == B.array2.size)
: recursively do this until the array size is different.
: if A == B, the complexity is at most O(nlgn) (quick sort);
: otherwise it's smaller.
: so the total complexity <=O(nlgn)

1 (共1页)
进入JobHunting版参与讨论
相关主题
算法题:min heap inplace变 BST问一下deep copy和shallow copy的问题(C#)
heapifying an unordered arrayFind the intersection of two sorted arrays【扩展】
Facebook interview questions请教一下external sorting的问题
做道有序数组元素求最大和题?a question
找2个sorted array中的第K小的元素,有O(lgn)方法吗?新鲜C3 energy面经
merge a1,a2,..b1,b2 to a1b1a2b2..问道面试题
被Facebook的面试的一道题目难倒了Google的这一道题的最优解?继续求助@!
两个Sorted Array,找K smallest elementMS a0, a1, ..., b0, b1... 问题
相关话题的讨论汇总
话题: arrays话题: find话题: array1话题: array2话题: space