j*********6
发帖数: 407 | 1 题目觉得不难 但是脑子很不给力 想了好半天也没想好 发出来大家看看
给一个
class Node{
public Node next();
}
就是说你不能修改这个list
一个list， A->B->C->D->E->F->G->........->Z (当然这只是个例子 list 无序)
给几个 list中的nodes, C, A, B, E, G
求 cluster 的个数
Cluster1: A->B->C
Cluster2: E
Cluster3: G
所以三个
然后要考虑 list size 为 1M node数量为10 的情况, 也就是说你牛别给我iterate
list了 |
z*********8
发帖数: 2070 | 2 leetcode有类似的吧， 不过那个是数组可以双向搜索， 比这个简单点 |
j*********6
发帖数: 407 | 3 求链接 这样的话 我就撞死得了 看来一遍果然不顶用 都记不住 啊 |
n****e
发帖数: 678 | 4 版内的面经有这道题
【在 j*********6 的大作中提到】
: 题目觉得不难 但是脑子很不给力 想了好半天也没想好 发出来大家看看
: 给一个
: class Node{
: public Node next();
: }
: 就是说你不能修改这个list
: 一个list， A->B->C->D->E->F->G->........->Z (当然这只是个例子 list 无序)
: 给几个 list中的nodes, C, A, B, E, G
: 求 cluster 的个数
: Cluster1: A->B->C
|
l*n
发帖数: 529 | 5 并查集吧，
C, A, B, E, G
C的next不认识，所以root是自己；
A的next是B，所以root是B；
B的next是C，所以root是C；
E的next不认识，root是E；
G的next不认识，root是G。
cluster数目是root位自己的点的个数。
【在 j*********6 的大作中提到】
: 题目觉得不难 但是脑子很不给力 想了好半天也没想好 发出来大家看看
: 给一个
: class Node{
: public Node next();
: }
: 就是说你不能修改这个list
: 一个list， A->B->C->D->E->F->G->........->Z (当然这只是个例子 list 无序)
: 给几个 list中的nodes, C, A, B, E, G
: 求 cluster 的个数
: Cluster1: A->B->C
|
n****e
发帖数: 678 | 6 把给的nodes放入set nodes里面
int count=0;
set::iterator iter = nodes.end();
while (!nodes.empty()) {
if (iter == nodes.end())
iter = nodes.begin();
Node temp = iter->next();
nodes.erase(iter);
iter = nodes.find(temp);
if (iter == nodes.end()) {
count++;
}
}
return count;
【在 j*********6 的大作中提到】
: 题目觉得不难 但是脑子很不给力 想了好半天也没想好 发出来大家看看
: 给一个
: class Node{
: public Node next();
: }
: 就是说你不能修改这个list
: 一个list， A->B->C->D->E->F->G->........->Z (当然这只是个例子 list 无序)
: 给几个 list中的nodes, C, A, B, E, G
: 求 cluster 的个数
: Cluster1: A->B->C
|
l****i
发帖数: 2772 | 7 一个set，每个node过一次，看看有几个node.next不存在。 |
j*********6
发帖数: 407 | 8 赞！ 看来还是自己的算法不过关~
【在 l*n 的大作中提到】
: 并查集吧，
: C, A, B, E, G
: C的next不认识，所以root是自己；
: A的next是B，所以root是B；
: B的next是C，所以root是C；
: E的next不认识，root是E；
: G的next不认识，root是G。
: cluster数目是root位自己的点的个数。
|
f********a
发帖数: 165 | 9 我觉得把list还要存成hash table 这样每次找node.next就不必从头找，基本思路和那
个数组里面最长递增序列是差不多
★ 发自iPhone App: ChineseWeb 8.1
【在 l****i 的大作中提到】
: 一个set，每个node过一次，看看有几个node.next不存在。
|
q******0
发帖数: 15 | 10 //N is the number of nodes
HashMap hmap;
Node* pNode[N];
bool isClusterHeader[N]
for (int i=0; i
hmap[pNode[i]] = i;
isClusterHeader[i] = true;
}
for (int i=0; i
if (lookup(hmap, pNode[i]->next) { //its next is in hashmap
isClusterHeader[hmap[pNode[i]->next] = false; //link to next
}
}
for (int i=0; i
if (isClusterHeader[i]) {
print(pNode[i])
//continue print its next until lookup(hmap, next) == true,
//which means a new cluster starts
}
} |
|
|
s**x
发帖数: 7506 | 11 我觉得跟数组整数求连续子续列个数是一样的题。
就是放hash table , 慢慢相邻的grow and merge. |
l****h
发帖数: 1189 | 12 请问这个list没有存value的地方，怎么知道是ABCDE的，即每一个节点有何记号？ |
d*******8
发帖数: 30 | 13 这个不对吧，比如C会加１，到A不加，但是到B的时候C已经移走了，所以又会加一
【在 n****e 的大作中提到】
: 把给的nodes放入set nodes里面
: int count=0;
: set::iterator iter = nodes.end();
: while (!nodes.empty()) {
: if (iter == nodes.end())
: iter = nodes.begin();
: Node temp = iter->next();
: nodes.erase(iter);
: iter = nodes.find(temp);
: if (iter == nodes.end()) {
|
d***n
发帖数: 832 | 14 O(n)的算法,n为链表中所有的节点数，可能比较大
空间为O(m), m为toFind的node数，m比较小
一旦所有的toFind的node找到就可以终止
所以平均时间应该会比较快
C#
public class Node
{
public Node Next;
}
public static int GetNumOfClusters(Node node, List toFind)
{
HashSet hs = new HashSet();
foreach (Node n in toFind) hs.Add(n);
int numNodes = toFind.Count, result = 0;
bool previousInHS = false;
while (numNodes > 0 && node != null)
{
if (hs.Contains(node))
{
numNodes--;
if (!previousInHS) result++;
previousInHS = true;
}
else
{
previousInHS = false;
}
node = node.Next;
}
return result;
} |
n****e
发帖数: 678 | 15 恩，你说的对。
如果是double linked list就好了，我记得以前的面经是double linked list的
这题是singly linked list
【在 d*******8 的大作中提到】
: 这个不对吧，比如C会加１，到A不加，但是到B的时候C已经移走了，所以又会加一
|
w*******s
发帖数: 96 | 16 不太清楚题目意思啊，大侠解释一下？另外对应leetcode中那个题，完全没有yinxiang
... |
d***n
发帖数: 832 | 17 用题目中的输入，到我之前的code走一遍就明白了
yinxiang
【在 w*******s 的大作中提到】
: 不太清楚题目意思啊，大侠解释一下？另外对应leetcode中那个题，完全没有yinxiang
: ...
|
s******e
发帖数: 493 | 18 interesting question. how about sth like this:
1. for any m, hashes the given nodes, and then sorts the nodes based on the
list order. time will be O(n). finally, O(m) time to figure out the clusters
from the sorted node list.
2. if m << n, and every node is in the list, there is no need to check the
list, build the graphic relation from m directly. |
t******d
发帖数: 1383 | |
n*****f
发帖数: 17 | 20 1.如果没有环：只把查询的node加到hash表里去，然后BFS。BFS开始时把查询的node都
加到队列里去，这样相当于每个node都按相同的速度向后扩展，每扩展一个节点，判断
一下是否在hash表里，如果在，总的cluster数就减1。扩展不下去了或cluster数减到1
了就停止。
2.如果有环：其实我感觉面试官更有可能考察的是有环的情况。这个题就相当于一个图
有n个点，每个点有一条出边，问构成了几个连通分量。它能构成的图有两种情况，一
种是一条链，一种是一个环上加若干条链，就像仙人掌一样。不管是哪种情况都可以用
上面那个BFS的方法来解决，唯一的不同是hash表里需要记每个遍历到的点防止遇到了
环会死循环。 |
c********p
发帖数: 1969 | |
