http://www.1point3acres.com/bbs/thread-148690-1-1.html
第一题: 给一个network of computers, each computer only see its neighbors and can send package to them. Design a protocol to tell how many computer are in the network.
就是实现一个protocol, 实现任何一台computer都可以知道网络中有多少computer。
第一题 估计是个 BFS, package 里面如下 变量 一个 global count 计算 目前 visited 的计算机总数, 一个 变量标志本计算机是否已经被访问过, 这样一个 BFS就可以计算所有的计算机了。
我刚开始就说bfs 被打枪了 最后面试官说是dfs
递归的时候把那个set传参就好了
而实际上这个传参的过程也就对应着数据包的流动
个人观点,DFS的call stack操作正好对应数据包的流动。
多走一层递归就意味着把数据包往未遍历的节点传递。
return则代表把数据包往已遍历的节点返回。
中间操作代表修改数据包的内容。
最后出发点是可以收到一个数据包的。
至于BFS么……你可以记录一个节点的指针,代码可以直接去找那个节点,可是数据包飞不过去
第一题 应当是每个节点保存拓扑图 每当收到相邻节点的拓扑更新 和本地比较 如果有新的更新 就更新本地 然后再把更新后的拓扑图发给相邻节点 最终 每个节点都有完整的拓扑 再count一下vertex
第一题: 给一个network of computers, each computer only see its neighbors and can send package to them. Design a protocol to tell how many computer are in the network.
就是实现一个protocol, 实现任何一台computer都可以知道网络中有多少computer。
第一题 估计是个 BFS, package 里面如下 变量 一个 global count 计算 目前 visited 的计算机总数, 一个 变量标志本计算机是否已经被访问过, 这样一个 BFS就可以计算所有的计算机了。
我刚开始就说bfs 被打枪了 最后面试官说是dfs
递归的时候把那个set传参就好了
而实际上这个传参的过程也就对应着数据包的流动
个人观点,DFS的call stack操作正好对应数据包的流动。
多走一层递归就意味着把数据包往未遍历的节点传递。
return则代表把数据包往已遍历的节点返回。
中间操作代表修改数据包的内容。
最后出发点是可以收到一个数据包的。
至于BFS么……你可以记录一个节点的指针,代码可以直接去找那个节点,可是数据包飞不过去
第一题 应当是每个节点保存拓扑图 每当收到相邻节点的拓扑更新 和本地比较 如果有新的更新 就更新本地 然后再把更新后的拓扑图发给相邻节点 最终 每个节点都有完整的拓扑 再count一下vertex