m*****n
发帖数: 9 | 1 找出maximum adjacent subsequence length in 2-dimensional matrics (M=n*n).
for example, 下面这个最大的长度是4， 因为8的周围4个数是连着的：2，3，4，5.
数字没有重复的。
1 3 6 7
2 8 5 10
9 4 11 12
13 14 15 16
数字要一个接一个。2，3，4，5就是连接着的。就是找一个数的adjacent elements，
然后看这些adjacent elements有几个相邻的。比如数字8的adjacent elements就是2,3
,4,5（上下左右），然后这些数连着的数字就是4个，所以长度是4.
比如4的adjacent elements就是8,9,11,14,然后连着的数字就是8和9，所以长度是2.
我直接用brute force. 开销O(M*L*Log(L)),L的范围是1<=L<=4(因为每个相邻节点最多
是4个)，所以就忽略为O(M)。计算每个点的周围节点，然后把这些节点排序，当然也可
以用其它的来算出是不是连着的。
代码有点点问题，没写完，被叫停，但框架出来了，稍微修改修改就可以。也没叫我优
化，可以没给我任何暗示，没说我的方法哪里不好。开始问我怎么做，然后我说了，然
后叫我计算时间开销，我也一步一步说解释。最后开始代码（框架出来，代码有点点小
问题），然后被叫停说没时间。。面试官是个印度的人。感觉不太友好，要赶时间回去
上班。没什么说的，碰到不太喜欢你的面试官也没办法。可能我开始的思路就和他不对
路，但是我感觉应该给点提示如果不对的话，我不是一开始就写代码的。
嗨，move on了。祝大家好运 |
s**********k
发帖数: 88 | 2 不是很懂题目。
subsequence里的数要从小到大一个接一个吗？
还有，2,3,4,5只是角相邻而不是边相邻，这样也可以吗？
【在 m*****n 的大作中提到】
: 找出maximum adjacent subsequence length in 2-dimensional matrics (M=n*n).
: for example, 下面这个最大的长度是4， 因为8的周围4个数是连着的：2，3，4，5.
: 数字没有重复的。
: 1 3 6 7
: 2 8 5 10
: 9 4 11 12
: 13 14 15 16
: 数字要一个接一个。2，3，4，5就是连接着的。就是找一个数的adjacent elements，
: 然后看这些adjacent elements有几个相邻的。比如数字8的adjacent elements就是2,3
: ,4,5（上下左右），然后这些数连着的数字就是4个，所以长度是4.
|
m*****n
发帖数: 9 | 3 subsequence里的数要从小到大一个接一个吗？
是的，数字要一个接一个。2，3，4，5就是连接着的。
就是找一个数的adjacent elements，然后看这些adjacent elements有几个相邻的。比
如数字8的adjacent elements就是2,3,4,5（上下左右），然后这些数连着的数字就是4
个，所以长度是4.
比如4的adjacent elements就是8,9,11,14,然后连着的数字就是8和9，所以长度是2.
=======================================
不是很懂题目。
subsequence里的数要从小到大一个接一个吗？
还有，2,3,4,5只是角相邻而不是边相邻，这样也可以吗？ |
l*********8
发帖数: 4642 | 4 所以"maximum adjacent subsequence length"可能的长度是 0 到4 之间？
是4
【在 m*****n 的大作中提到】
: subsequence里的数要从小到大一个接一个吗？
: 是的，数字要一个接一个。2，3，4，5就是连接着的。
: 就是找一个数的adjacent elements，然后看这些adjacent elements有几个相邻的。比
: 如数字8的adjacent elements就是2,3,4,5（上下左右），然后这些数连着的数字就是4
: 个，所以长度是4.
: 比如4的adjacent elements就是8,9,11,14,然后连着的数字就是8和9，所以长度是2.
: =======================================
: 不是很懂题目。
: subsequence里的数要从小到大一个接一个吗？
: 还有，2,3,4,5只是角相邻而不是边相邻，这样也可以吗？
|
m*****n
发帖数: 9 | 5 所以"maximum adjacent subsequence length"可能的长度是 0 到4 之间？
是的。应该是1到4之间。如果提早得到4的话可以提早结束循环。可能我就是没和他沟
通这个。 |
l*********8
发帖数: 4642 | 6 这样的话，你的思路（加上提早得到4的话可以提早结束循环）应该可以啊。
总共给你多少时间做这道题目？
【在 m*****n 的大作中提到】
: 所以"maximum adjacent subsequence length"可能的长度是 0 到4 之间？
: 是的。应该是1到4之间。如果提早得到4的话可以提早结束循环。可能我就是没和他沟
: 通这个。
|
m*****n
发帖数: 9 | 7 总共给你多少时间做这道题目？
开始大部分时间在和我讨论怎么做，计算时间开销。估计编程就10到15分钟左右最多，
我没注意多少时间，就这一个题目。开始讨论些其他的东西。这个题目总共应该有25分
钟吧（包括开始讨论怎么做和计算时间开销的时间）。
我没说得到4可以提早结束，我还在想他可能要问怎么优化。然后时间就没了。然后说
时间其实早超过了，他一直没说话。然后说，还有没有什么问题在我回去工作之前要问
。 感觉就是急着走。 |
l*********8
发帖数: 4642 | 8 那么这应该是第二道题目了。 第一题做得不错的话，可能有希望。
编程10-15分钟没写完，还是稍微慢了一些。
【在 m*****n 的大作中提到】
: 总共给你多少时间做这道题目？
: 开始大部分时间在和我讨论怎么做，计算时间开销。估计编程就10到15分钟左右最多，
: 我没注意多少时间，就这一个题目。开始讨论些其他的东西。这个题目总共应该有25分
: 钟吧（包括开始讨论怎么做和计算时间开销的时间）。
: 我没说得到4可以提早结束，我还在想他可能要问怎么优化。然后时间就没了。然后说
: 时间其实早超过了，他一直没说话。然后说，还有没有什么问题在我回去工作之前要问
: 。 感觉就是急着走。
|
m*****n
发帖数: 9 | 9 没，就一个题目。开始就瞎砍，聊项目，聊背景。这个估计有10到15分钟吧感觉。恩，
是速度慢了，我觉得应该编程应该有15分钟。的确是慢了。G家的要求，我就不多说了
。move on，下次再战。回去修炼了
===============================================================
那么这应该是第二道题目了。 第一题做得不错的话，可能有希望。编程10-15分钟没写
完，还是稍微慢了一些。 |
w******e
发帖数: 1621 | 10 这题版上发过，我记得上次发的时候说意思是找一条最长路径，路径上的数是
consecutive的。lz想想是不是这个意思啊 |
m*****n
发帖数: 9 | 11 是的，他也说了要consecutive。
=======================================================
这题版上发过，我记得上次发的时候说意思是找一条最长路径，路径上的数是
consecutive的。lz想想是不是这个意思啊 |
l*********8
发帖数: 4642 | 12 consecutive 最长路径比这道题目难
【在 m*****n 的大作中提到】
: 是的，他也说了要consecutive。
: =======================================================
: 这题版上发过，我记得上次发的时候说意思是找一条最长路径，路径上的数是
: consecutive的。lz想想是不是这个意思啊
|
T*****u
发帖数: 7103 | |
