"""
1. Suppose you have a library of books. Each book is represented as a list of strings (words in the book), 
and the library is an array of these lists of strings. Return a list of the words that occur in every book.

2. Return a list of the top K frequent words in the library.
"""

def getWordsInAllBooks(library):
    result = []
    if not library:
        return result
    distinctWordsSoFar = set(library[0])
    for bookNum in range(1, len(library)):
        currentBook = library[bookNum]
        wordsInCurrentBookAndPreviousBooks = set()
        for word in currentBook:
            if word in distinctWordsSoFar:
                wordsInCurrentBookAndPreviousBooks.add(word)
        distinctWordsSoFar = wordsInCurrentBookAndPreviousBooks
        if len(distinctWordsSoFar) == 0:
            return result
    result = list(distinctWordsSoFar)
    return result

def getTopKFrequentWords(library, k):
    if not library:
        return []
    wordFreqs = {}
    for book in library:
        for word in book:
            wordFreqs[word] = wordFreqs.get(word, 0) + 1
    #Use selection sort on the frequences for linear sorting of top k, otherwise use a heap
    heap = []
    for word, freq in wordFreqs.items():
        heapq.heappush(heap, (freq, word))
        if len(heap) > k:
            heapq.heappop(heap)
    result = []
    for _ in range(len(heap)):
        #Python heaps are min heaps
        word = heapq.heappop(heap)[1] #Get the word
        result.append(word)
    #If you want them in descending order, then call result.reverse()
    return result