s*******z
发帖数: 83 | 1 之前在这个版上看到的问题, 百思不得其解:
有一个0/1的矩阵, 找到里面的两行使得它们有最多的位置相同的0/1
比如: 00010与00100 有三个相同的. 当时同学说面试的阿三不允许pairwise的比较.
类似的题目还有：
给一个sentences的list, 找其中两个句子, 它们有最多的common words.
这类的题目觉得总避免不了pairwise的比较, 不知道有什么更好的方法 | w***g
发帖数: 5958 | 2 反正我想不出来在最差情况下比两两比较更好的办法。很好奇这是怎么搞的。
【在 s*******z 的大作中提到】
: 之前在这个版上看到的问题, 百思不得其解:
: 有一个0/1的矩阵, 找到里面的两行使得它们有最多的位置相同的0/1
: 比如: 00010与00100 有三个相同的. 当时同学说面试的阿三不允许pairwise的比较.
: 类似的题目还有：
: 给一个sentences的list, 找其中两个句子, 它们有最多的common words.
: 这类的题目觉得总避免不了pairwise的比较, 不知道有什么更好的方法
| s*******z
发帖数: 83 | 3 我也觉得不行...
是要用simhash之类的近似吗? | b****f
发帖数: 138 | | j**7
发帖数: 143 | | c*******7
发帖数: 438 | 6 这类问题就是N个set求找到两个set使其中的共同token数最多。共同点就是某个token
是否在某个set中的lookup时间为O（1）。假设每个set的size为k
两两比较的方法：对于每个set的每个token，在剩余set中查找是否存在。时间复杂度
为O(k*n^2)
逆向index的方法：对于每个token，建立一个index set，放入到一个map里，这一步需
要遍历所有token，O(n*k)。再建立一个n*n的matrix, 遍历一遍前面建立好的index
map，update matrix里面对应的common token count。worst case 也是O(k*n^2),但是
average 应该会比前面的方法好一些。 | y*****3
发帖数: 451 | 7 这种题可以用bitmap和逻辑异或解决吧？
【在 s*******z 的大作中提到】
: 之前在这个版上看到的问题, 百思不得其解:
: 有一个0/1的矩阵, 找到里面的两行使得它们有最多的位置相同的0/1
: 比如: 00010与00100 有三个相同的. 当时同学说面试的阿三不允许pairwise的比较.
: 类似的题目还有：
: 给一个sentences的list, 找其中两个句子, 它们有最多的common words.
: 这类的题目觉得总避免不了pairwise的比较, 不知道有什么更好的方法
| r******g
发帖数: 138 | 8 00010^00100 = 00110
10110^00100 = 10010
数异或后0的个数。 | s*******z
发帖数: 83 | 9 应该是高维度空间里面的最近点对问题, 一个大牛说了可以再Nlog(N)的时间里面完成,
就用类似于二维平面的分治法来做.
但是实现起来也觉得好难, 还有就是维度高的时候,一分两半以后, 就算求距中轴的最
短距离的那些点的时候, 说不定也都是N^2的了. | b*****o
发帖数: 715 | 10 vp tree
http://www.cs.iastate.edu/~honavar/nndatastructures.pdf
http://en.wikipedia.org/wiki/Vantage-point_tree
【在 s*******z 的大作中提到】
: 之前在这个版上看到的问题, 百思不得其解:
: 有一个0/1的矩阵, 找到里面的两行使得它们有最多的位置相同的0/1
: 比如: 00010与00100 有三个相同的. 当时同学说面试的阿三不允许pairwise的比较.
: 类似的题目还有：
: 给一个sentences的list, 找其中两个句子, 它们有最多的common words.
: 这类的题目觉得总避免不了pairwise的比较, 不知道有什么更好的方法
| k*****o
发帖数: 43 | | f*******r
发帖数: 976 | 12 我能相处最好的就是用bit operation，这个也只是减少前面的constant，最坏情况还
是O（N^2） |
|
