m**********j
发帖数: 610 | 1 epic，电面，第一轮
给一个2D table，每一个entry是boolean
find rows with most entries in common (could be two or more)
比如说有2行分别是011011， 011010， 在6个column里面有5个相同
没说具体复杂度要求，不过不让对每行做pairwise comparison
对面的三哥说给你半分钟思考
没想出来要hint也不给 |
k****a
发帖数: 32 | 2 bit operation.
011011 ^ 011010 = 000001
然后数有几个1 就有几个不同 |
m**********j
发帖数: 610 | 3
怎么避免行之间pairwise comparison
【在 k****a 的大作中提到】
: bit operation.
: 011011 ^ 011010 = 000001
: 然后数有几个1 就有几个不同
|
l*n
发帖数: 529 | 4 首先xor肯定是要用的，然后就是看O(n)比较能否有O(n^2)的效果。
011011
011010
001011
1和2xor是111110 (xor搞反了，将就着看吧，能看懂)
2和3xor是101110
1和3xor是101111,可见是(A[1]^A[2])^(A[2]^A[3])。所以你看其实绕远了，1^3=1^2^2
^3，搞定。
ps.实际上还是O(n^2)，这个没法降低。
【在 m**********j 的大作中提到】
: epic，电面，第一轮
: 给一个2D table，每一个entry是boolean
: find rows with most entries in common (could be two or more)
: 比如说有2行分别是011011， 011010， 在6个column里面有5个相同
: 没说具体复杂度要求，不过不让对每行做pairwise comparison
: 对面的三哥说给你半分钟思考
: 没想出来要hint也不给
|
R******1
发帖数: 58 | 5 每一个entry是boolean，不用XOR吧，count多少个true不就好了，这个不算pairwise
comparison吧。
【在 m**********j 的大作中提到】
: epic，电面，第一轮
: 给一个2D table，每一个entry是boolean
: find rows with most entries in common (could be two or more)
: 比如说有2行分别是011011， 011010， 在6个column里面有5个相同
: 没说具体复杂度要求，不过不让对每行做pairwise comparison
: 对面的三哥说给你半分钟思考
: 没想出来要hint也不给
|
m**********j
发帖数: 610 | 6
000111跟111000 相似度是0啊
【在 R******1 的大作中提到】
: 每一个entry是boolean，不用XOR吧，count多少个true不就好了，这个不算pairwise
: comparison吧。
|
s*****u
发帖数: 151 | 7 n维向量算cosin然后推角度，角度差最小的两个向量就是了？ |
R******1
发帖数: 58 | 8 我完全看错题目了……
也只能想到XOR，肯定是pairwise operation，但不算是comparison吧……
【在 m**********j 的大作中提到】
:
: 000111跟111000 相似度是0啊
|
l*n
发帖数: 529 | 9 不允许pairwise是指的不能1比2，2比3，1比3这样的全组合吧。
【在 R******1 的大作中提到】
: 我完全看错题目了……
: 也只能想到XOR，肯定是pairwise operation，但不算是comparison吧……
|
m**********j
发帖数: 610 | 10
是这个意思
我觉得epic这种公司不至于第一轮就搞太bt的算法吧，除非是三哥存心要把我做掉
还只给半分钟时间考虑
【在 l*n 的大作中提到】
: 不允许pairwise是指的不能1比2，2比3，1比3这样的全组合吧。
|
|
|
f*******4
发帖数: 64 | 11 按最后一列对table排序，划分为上下两子块，分别计算子块及他们的交叉
可能是考察递归或DP吧
【在 m**********j 的大作中提到】
: epic，电面，第一轮
: 给一个2D table，每一个entry是boolean
: find rows with most entries in common (could be two or more)
: 比如说有2行分别是011011， 011010， 在6个column里面有5个相同
: 没说具体复杂度要求，不过不让对每行做pairwise comparison
: 对面的三哥说给你半分钟思考
: 没想出来要hint也不给
|
u*****l
发帖数: 444 | 12 我有个很笨的法子。
第一次按照第一位排序，然后记录那些第一位是相同的行，然后记录到一个n*n的表格
里，
然后对第二位排序，同样做记录。
做n次记录之后检查表格，表格里找到最大的数字，然后检查他们的行和列，就得出相
应的相关最大的序列。 |
t*********h
发帖数: 941 | 13 hash一下行不
【在 m**********j 的大作中提到】
: epic，电面，第一轮
: 给一个2D table，每一个entry是boolean
: find rows with most entries in common (could be two or more)
: 比如说有2行分别是011011， 011010， 在6个column里面有5个相同
: 没说具体复杂度要求，不过不让对每行做pairwise comparison
: 对面的三哥说给你半分钟思考
: 没想出来要hint也不给
|
u*****l
发帖数: 444 | 14 我有个很笨的法子。
第一次按照第一位排序，然后记录那些第一位是相同的行，然后记录到一个n*n的表格
里，
然后对第二位排序，同样做记录。
做n次记录之后检查表格，表格里找到最大的数字，然后检查他们的行和列，就得出相
应的相关最大的序列。 |
S******6
发帖数: 55 | 15 有那个不能两两比较的限制，一时没想起来，多谢分享 |
m**********j
发帖数: 610 | 16 epic，电面，第一轮
给一个2D table，每一个entry是boolean
find rows with most entries in common (could be two or more)
比如说有2行分别是011011， 011010， 在6个column里面有5个相同
没说具体复杂度要求，不过不让对每行做pairwise comparison
对面的三哥说给你半分钟思考
没想出来要hint也不给 |
k****a
发帖数: 32 | 17 bit operation.
011011 ^ 011010 = 000001
然后数有几个1 就有几个不同 |
m**********j
发帖数: 610 | 18
怎么避免行之间pairwise comparison
【在 k****a 的大作中提到】
: bit operation.
: 011011 ^ 011010 = 000001
: 然后数有几个1 就有几个不同
|
l*n
发帖数: 529 | 19 首先xor肯定是要用的，然后就是看O(n)比较能否有O(n^2)的效果。
011011
011010
001011
1和2xor是111110 (xor搞反了，将就着看吧，能看懂)
2和3xor是101110
1和3xor是101111,可见是(A[1]^A[2])^(A[2]^A[3])。所以你看其实绕远了，1^3=1^2^2
^3，搞定。
ps.实际上还是O(n^2)，这个没法降低。
【在 m**********j 的大作中提到】
: epic，电面，第一轮
: 给一个2D table，每一个entry是boolean
: find rows with most entries in common (could be two or more)
: 比如说有2行分别是011011， 011010， 在6个column里面有5个相同
: 没说具体复杂度要求，不过不让对每行做pairwise comparison
: 对面的三哥说给你半分钟思考
: 没想出来要hint也不给
|
R******1
发帖数: 58 | 20 每一个entry是boolean，不用XOR吧，count多少个true不就好了，这个不算pairwise
comparison吧。
【在 m**********j 的大作中提到】
: epic，电面，第一轮
: 给一个2D table，每一个entry是boolean
: find rows with most entries in common (could be two or more)
: 比如说有2行分别是011011， 011010， 在6个column里面有5个相同
: 没说具体复杂度要求，不过不让对每行做pairwise comparison
: 对面的三哥说给你半分钟思考
: 没想出来要hint也不给
|
|
|
m**********j
发帖数: 610 | 21
000111跟111000 相似度是0啊
【在 R******1 的大作中提到】
: 每一个entry是boolean，不用XOR吧，count多少个true不就好了，这个不算pairwise
: comparison吧。
|
s*****u
发帖数: 151 | 22 n维向量算cosin然后推角度，角度差最小的两个向量就是了？ |
R******1
发帖数: 58 | 23 我完全看错题目了……
也只能想到XOR，肯定是pairwise operation，但不算是comparison吧……
【在 m**********j 的大作中提到】
:
: 000111跟111000 相似度是0啊
|
l*n
发帖数: 529 | 24 不允许pairwise是指的不能1比2，2比3，1比3这样的全组合吧。
【在 R******1 的大作中提到】
: 我完全看错题目了……
: 也只能想到XOR，肯定是pairwise operation，但不算是comparison吧……
|
m**********j
发帖数: 610 | 25
是这个意思
我觉得epic这种公司不至于第一轮就搞太bt的算法吧，除非是三哥存心要把我做掉
还只给半分钟时间考虑
【在 l*n 的大作中提到】
: 不允许pairwise是指的不能1比2，2比3，1比3这样的全组合吧。
|
f*******4
发帖数: 64 | 26 按最后一列对table排序，划分为上下两子块，分别计算子块及他们的交叉
可能是考察递归或DP吧
【在 m**********j 的大作中提到】
: epic，电面，第一轮
: 给一个2D table，每一个entry是boolean
: find rows with most entries in common (could be two or more)
: 比如说有2行分别是011011， 011010， 在6个column里面有5个相同
: 没说具体复杂度要求，不过不让对每行做pairwise comparison
: 对面的三哥说给你半分钟思考
: 没想出来要hint也不给
|
u*****l
发帖数: 444 | 27 我有个很笨的法子。
第一次按照第一位排序，然后记录那些第一位是相同的行，然后记录到一个n*n的表格
里，
然后对第二位排序，同样做记录。
做n次记录之后检查表格，表格里找到最大的数字，然后检查他们的行和列，就得出相
应的相关最大的序列。 |
t*********h
发帖数: 941 | 28 hash一下行不
【在 m**********j 的大作中提到】
: epic，电面，第一轮
: 给一个2D table，每一个entry是boolean
: find rows with most entries in common (could be two or more)
: 比如说有2行分别是011011， 011010， 在6个column里面有5个相同
: 没说具体复杂度要求，不过不让对每行做pairwise comparison
: 对面的三哥说给你半分钟思考
: 没想出来要hint也不给
|
u*****l
发帖数: 444 | 29 我有个很笨的法子。
第一次按照第一位排序，然后记录那些第一位是相同的行，然后记录到一个n*n的表格
里，
然后对第二位排序，同样做记录。
做n次记录之后检查表格，表格里找到最大的数字，然后检查他们的行和列，就得出相
应的相关最大的序列。 |
S******6
发帖数: 55 | 30 有那个不能两两比较的限制，一时没想起来，多谢分享 |
|
|
e***a
发帖数: 1661 | |
