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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 每一个entry是boolean,不用XOR吧,count多少个true不就好了,这个不算pairwise : comparison吧。
|
s*****u 发帖数: 151 | 7 n维向量算cosin然后推角度,角度差最小的两个向量就是了? |
R******1 发帖数: 58 | 8 我完全看错题目了……
也只能想到XOR,肯定是pairwise operation,但不算是comparison吧……
【在 m**********j 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 000111跟111000 相似度是0啊
|
l*n 发帖数: 529 | 9 不允许pairwise是指的不能1比2,2比3,1比3这样的全组合吧。
【在 R******1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我完全看错题目了…… : 也只能想到XOR,肯定是pairwise operation,但不算是comparison吧……
|
m**********j 发帖数: 610 | 10
是这个意思
我觉得epic这种公司不至于第一轮就搞太bt的算法吧,除非是三哥存心要把我做掉
还只给半分钟时间考虑
【在 l*n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不允许pairwise是指的不能1比2,2比3,1比3这样的全组合吧。
|
|
|
f*******4 发帖数: 64 | 11 按最后一列对table排序,划分为上下两子块,分别计算子块及他们的交叉
可能是考察递归或DP吧
【在 m**********j 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 每一个entry是boolean,不用XOR吧,count多少个true不就好了,这个不算pairwise : comparison吧。
|
s*****u 发帖数: 151 | 22 n维向量算cosin然后推角度,角度差最小的两个向量就是了? |
R******1 发帖数: 58 | 23 我完全看错题目了……
也只能想到XOR,肯定是pairwise operation,但不算是comparison吧……
【在 m**********j 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 000111跟111000 相似度是0啊
|
l*n 发帖数: 529 | 24 不允许pairwise是指的不能1比2,2比3,1比3这样的全组合吧。
【在 R******1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我完全看错题目了…… : 也只能想到XOR,肯定是pairwise operation,但不算是comparison吧……
|
m**********j 发帖数: 610 | 25
是这个意思
我觉得epic这种公司不至于第一轮就搞太bt的算法吧,除非是三哥存心要把我做掉
还只给半分钟时间考虑
【在 l*n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不允许pairwise是指的不能1比2,2比3,1比3这样的全组合吧。
|
f*******4 发帖数: 64 | 26 按最后一列对table排序,划分为上下两子块,分别计算子块及他们的交叉
可能是考察递归或DP吧
【在 m**********j 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 | |