苹果谷歌电面题目

一个单链表拓扑结构的网络(每个节点度为2),每个节点只能和左右邻居通讯。已知
有函数:
bool isLeftMost();
bool isRightMost();
void SendLeft(Message m);//如果是最左边的节点调用会抛出异常
void SendRight(Message m); //如果是最右边的节点调用会抛出异常
完成class NodeCount实现计算网络中节点总数。

public class NodeCount
{
    private bool isLeftMost();
    private bool isRightMost();
    private void SendLeft(Message m);
    private void SendRight(Message m);

    public void run(){}

    private void ReceiveFromLeft(Message m){}

    private void ReceiveFromRight(Message m){}
}

话说怎么电面现在都不面leetcode传统算法题了,搞得有leetcode白刷了的感觉。

1 Like

isLeftMost() 和isRightMost()是什么意思呢?链表的head已知吗?已知head的话是不是用bfs就可以知道节点总数?

应该是说在拓扑结构是位置是不是最左还是最右
这题谷歌也考过

不知道,这也不能算链表

老师可以大概讲一下思路吗?还是没明白这题应该怎么做。

这题其实是系统设计,今年暑期会开系统设计班,到时候看是否要讲这题

要考虑的是message类怎么设计。
我记得是选任意一个node作为开始,怎么populate信息到所有的node,并保证所有node都收到信息。需要acknowledge等机制。

这里一个关键问题是,怎么知道所有node都收到信息了。在peer to peer的架构下,没法通过global的变量track。那么如果每个node保证它左右node收到该信息,信息有uuid,是否应该可以满足。
另外就是如果有node没收到信息,没有response,如何最终判断。