Interview Code

main.py

# -*- coding:utf-8 -*-
__author__ = 'XU ZHANGXUAN'


# This method should be pre-defined
def is_include(name1, name2):
    pass


class Node(object):
    def __init__(self, name, parent=None, children=[]):
        self.name = name
        self.parent = parent
        self.children = children

    def add_child(self, node):
        self.children.append(node)
        node.parent = self

    def rm_child(self, node):
        self.children.remove(node)
        node.parent = None

    def is_include(self, node):
        return is_include(self.name, node.name)

    def get_child(self, name):
        if not is_include(self.name, name):
            return None
        node = self
        while True:
            for n in node.children:
                if n.name == name:
                    return n
                if is_include(n.name, name):
                    node = n
                    break


class Map(object):
    def __init__(self):
        self.root = Node('Earth')

    def add_node(self, name):
        node = self.root
        new_node = Node(name)
        while True:
            is_child = False
            for n in node.children:
                if n.is_include(new_node):
                    is_child = True
                    node = n
            if not is_child:
                break
        for n in node.children:
            if new_node.is_include(n):
                node.rm_child(n)
                new_node.add_child(n)
        node.add_child(new_node)

    def add_nodes(self, names):
        for n in names:
            self.add_node(n)

    def get_refer(self, name):
        node = self.root.get_child(name)
        if not node:
            return []
        refer = [node.name]
        while node.parent:
            refer.append(node.parent.name)
            node = node.parent
        refer.reverse()
        return refer