Scamming the coding interview : Problem 014 : Maximum frequency path in a graph

maximum_frequency_value_graph_path.py

"""
Scamming the coding interview. Problem 014

Subscribe to our newsletter at https://scammingthecodinginterview.com/
to get a coding or design problem daily in your inbox and become exceptionally good at
coding interviews.
"""


class Node(object):

    def __init__(self, value):
        self.value = value


def custom_merge(d1, d2):
    """
    Merges two dict in such a way that we take max values of a key if it's
    available in both the dics
    """
    merged = {}

    for k, v in d1.items():
        v2 = d2.get(k, -1)
        merged[k] = max(v2, v)

        if v2 != -1:
            d2.pop(k)

    merged.update(**d2)

    return merged


def find_frequency(node, graph_adjacency_list, cache):
    """
    For a given node, returns a dict having maximum frequency of each letter
    by going through all possible paths
    """
    neighbours = graph_adjacency_list[node]

    freq_count = {}

    for n in neighbours:

        res = cache.get(n)

        if not res:
            res = find_frequency(n, graph_adjacency_list, cache)

        freq_count = custom_merge(freq_count.copy(), res.copy())

        cache[n] = res

    freq_count[node.value] = freq_count.get(node.value, 0) + 1

    cache[node] = freq_count

    return freq_count


if __name__ == '__main__':

    node_1 = Node("A")
    node_2 = Node("B")
    node_3 = Node("A")
    node_4 = Node("B")
    node_5 = Node("C")
    node_6 = Node("C")
    node_7 = Node("A")
    node_8 = Node("A")
    node_9 = Node("A")
    node_10 = Node("A")
    node_11 = Node("C")
    node_12 = Node("D")

    graph_adjacency_list = {
        node_1: [node_4, node_2],
        node_2: [node_5, node_3],
        node_3: [node_5, node_6],
        node_4: [node_11, node_7],
        node_5: [node_8, node_9],
        node_6: [node_10],
        node_7: [],
        node_8: [],
        node_9: [],
        node_10: [node_5],
        node_11: [],
        node_12: [node_8]
    }

    cache = {}

    nodes = list(graph_adjacency_list.keys())

    answer = None

    find_res = {}

    while True:

        n = nodes.pop()

        res = find_frequency(n, graph_adjacency_list, cache)

        find_res = custom_merge(find_res.copy(), res.copy())

        visited = list(cache.keys())

        unvisited = set(nodes) - set(visited)

        if unvisited:
            nodes = list(unvisited)
        else:
            break

    answer = max(list(find_res.values()))

    print(answer)