d********t
发帖数: 9628 | 1 array A中含1到N-1的数，要求找到最长的S(k) = A_k, A_A_k ...
看起来就像找一个graph的最大loop.
要求O_n |
l*********8
发帖数: 4642 | 2 dfs, 用一个长度为N的visited数组
【在 d********t 的大作中提到】
: array A中含1到N-1的数，要求找到最长的S(k) = A_k, A_A_k ...
: 看起来就像找一个graph的最大loop.
: 要求O_n
|
l*****a
发帖数: 14598 | 3 what is A_k
what is A_A_K
A[k], A[A[k]]?
and O_n
你这表示法很不通俗啊
【在 d********t 的大作中提到】
: array A中含1到N-1的数，要求找到最长的S(k) = A_k, A_A_k ...
: 看起来就像找一个graph的最大loop.
: 要求O_n
|
d********t
发帖数: 9628 | 4 手机上打不出【】
【在 l*****a 的大作中提到】
: what is A_k
: what is A_A_K
: A[k], A[A[k]]?
: and O_n
: 你这表示法很不通俗啊
|
l*****a
发帖数: 14598 | 5 T家所有职位都要online test?
几道题，多长时间
【在 d********t 的大作中提到】
: array A中含1到N-1的数，要求找到最长的S(k) = A_k, A_A_k ...
: 看起来就像找一个graph的最大loop.
: 要求O_n
|
l*****a
发帖数: 14598 | 6 走到一个已经用过的点就不能走了？
【在 d********t 的大作中提到】
: array A中含1到N-1的数，要求找到最长的S(k) = A_k, A_A_k ...
: 看起来就像找一个graph的最大loop.
: 要求O_n
|
d********t
发帖数: 9628 | 7 不知道啊，也没说啥位子，两道题，60分。
跪了就不去想了。
【在 l*****a 的大作中提到】
: T家所有职位都要online test?
: 几道题，多长时间
|
l*****a
发帖数: 14598 | 8 你这是什么复杂度？
【在 l*********8 的大作中提到】
: dfs, 用一个长度为N的visited数组
|
t**********h
发帖数: 2273 | 9 没说叫我做题啊
我现在手上叫做题的，都拖着，没搞。做题太枯燥了，
【在 d********t 的大作中提到】
: array A中含1到N-1的数，要求找到最长的S(k) = A_k, A_A_k ...
: 看起来就像找一个graph的最大loop.
: 要求O_n
|
d********t
发帖数: 9628 | 10 估计我太弱所以叫做题哈哈，结果挂了。
【在 t**********h 的大作中提到】
: 没说叫我做题啊
: 我现在手上叫做题的，都拖着，没搞。做题太枯燥了，
|
|
|
k****s
发帖数: 16 | 11
这是正解。
【在 l*********8 的大作中提到】
: dfs, 用一个长度为N的visited数组
|
m****9
发帖数: 492 | 12 用图的遍历可做，找largest strongly connected component. 反正各个点都只有一个
degree，BFS/DFS都一样。
用python写个:
visited=[0 for i in range(n)]
max_loop_number = 0
k = 0
for i in range(n):
loop_number = 0
while visited[i] == 0:
loop_number += 1
visited[i]=1
i = A[i]
if loop_number > max_loop_number:
max_loop_number = loop_number
k = i
return k
每个点都只遍历一遍，时间theta(n) |
d********t
发帖数: 9628 | 13 哎，没想到用一个visited array
【在 m****9 的大作中提到】
: 用图的遍历可做，找largest strongly connected component. 反正各个点都只有一个
: degree，BFS/DFS都一样。
: 用python写个:
: visited=[0 for i in range(n)]
: max_loop_number = 0
: k = 0
: for i in range(n):
: loop_number = 0
: while visited[i] == 0:
: loop_number += 1
|
f*****e
发帖数: 2992 | 14 这好像是给fresh graduate做的。experienced还做online test？
【在 d********t 的大作中提到】
: 哎，没想到用一个visited array
|
c********p
发帖数: 1969 | |
f*****e
发帖数: 2992 | 16 A[i]存储可以跳的步数，如果i+A[i]已经visited了，或掉在0-N外就不算。
【在 c********p 的大作中提到】
: 没看懂
|
s*********n
发帖数: 191 | 17 这个。。。
两道题过不了70%的话， recruiter会觉得你太菜不会继续安排电面的。
【在 d********t 的大作中提到】
: 不知道啊，也没说啥位子，两道题，60分。
: 跪了就不去想了。
|
d********t
发帖数: 9628 | 18 第一题很简单，两题觉得不是同一个层次的。
【在 s*********n 的大作中提到】
: 这个。。。
: 两道题过不了70%的话， recruiter会觉得你太菜不会继续安排电面的。
|
r****7
发帖数: 2282 | 19 You should use undirected graph for SCC detection.
【在 m****9 的大作中提到】
: 用图的遍历可做，找largest strongly connected component. 反正各个点都只有一个
: degree，BFS/DFS都一样。
: 用python写个:
: visited=[0 for i in range(n)]
: max_loop_number = 0
: k = 0
: for i in range(n):
: loop_number = 0
: while visited[i] == 0:
: loop_number += 1
|
l********y
发帖数: 1068 | 20 T家是哪一家？
【在 d********t 的大作中提到】
: array A中含1到N-1的数，要求找到最长的S(k) = A_k, A_A_k ...
: 看起来就像找一个graph的最大loop.
: 要求O_n
|
|
|
d********t
发帖数: 9628 | 21 不是TMobile
【在 l********y 的大作中提到】
: T家是哪一家？
|
c********r
发帖数: 107 | |
a****o
发帖数: 25 | |
d********t
发帖数: 9628 | 24 while的i把for里的i重新赋值了有问题吗？
【在 m****9 的大作中提到】
: 用图的遍历可做，找largest strongly connected component. 反正各个点都只有一个
: degree，BFS/DFS都一样。
: 用python写个:
: visited=[0 for i in range(n)]
: max_loop_number = 0
: k = 0
: for i in range(n):
: loop_number = 0
: while visited[i] == 0:
: loop_number += 1
|
