苹果谷歌电面题目

Job Hunting Interview
, , , , , , ,
1

一个单链表拓扑结构的网络（每个节点度为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
2

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

3

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

4

不知道，这也不能算链表

5

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

6

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

7

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

8

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