LintCode: Maximum Association Set

Maximum Association Set



Similar Problems:


Amazon sells books, every book has books which are strongly associated with it. Given ListA and ListB,indicates that ListA [i] is associated with ListB [i] which represents the book and associated books. Output the largest set associated with each other(output in any sort). You can assume that there is only one of the largest set.

Notice

  • The number of books does not exceed 5000.

Example

Given ListA = ["abc","abc","abc"], ListB = ["bcd","acd","def"], return["abc","acd","bcd","dfe"].

Explanation:
abc is associated with bcd, acd, dfe, so the largest set is the set of all books
Given ListA = ["a","b","d","e","f"], ListB = ["b","c","e","g","g"], return ["d","e","f","g"].

Explanation:
The current set are [a, b, c] and [d, e, g, f], then the largest set is [d, e, g, f]

Github: code.dennyzhang.com

Credits To: LintCode.com

Leave me comments, if you have better ways to solve.


## Blog link: https://code.dennyzhang.com/maximum-association-set
#!/usr/bin/env python
class Solution:
    """
    @param ListA: The relation between ListB's books
    @param ListB: The relation between ListA's books
    @return: The answer
    """
    def maximumAssociationSet(self, ListA, ListB):
        ## Basic Ideas: Use hashmap
        ## Complexity: Time O(n), Space O(n)
        m = {}
        length = len(ListA)
        # Build relationship
        for i in range(0, length):
            bookA, bookB = ListA[i], ListB[i]
            if bookA in m:
                m[bookA].add(bookB)
            else:
                m[bookA] = set([bookB])

            if bookB in m:
                m[bookB].add(bookA)
            else:
                m[bookB] = set([bookA])

        visited = set([])
        max_count, res = 0, []
        # Only need to scan ListA
        for i in range(0, length):
            if ListA[i] in visited: continue
            queue, l = [], []
            queue.append(ListA[i])
            l.append(ListA[i])
            visited.add(ListA[i])
            count = 1
            while len(queue) != 0:
                for k in range(0, len(queue)):
                    book = queue[-1]
                    del queue[-1]
                    # find the next candidates
                    for node in m[book]:
                        if node in visited: continue
                        queue.append(node)
                        visited.add(node)
                        l.append(node)
                        count += 1
                # collect result
                if count > max_count:
                    max_count = count
                    res = l
        return res

# s = Solution()
# print(s.maximumAssociationSet(["abc","abc","abc"], ["bcd","acd","def"]))
# print(s.maximumAssociationSet(["a","b","d","e","f"], ["b","c","e","g","g"]))
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.