Design Search Engine (Typeahead)

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
        self.frequency = 0  # কতবার search হয়েছে

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str, freq: int = 1):
        node = self.root
        for char in word.lower():
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
        node.frequency = freq

    def autocomplete(self, prefix: str, limit: int = 5) -> list:
        # Prefix node খুঁজে বের করুন
        node = self.root
        for char in prefix.lower():
            if char not in node.children:
                return []  # কোনো match নেই
            node = node.children[char]

        # Prefix node থেকে সব words collect করুন
        results = []
        self._dfs(node, prefix, results)

        # Frequency দিয়ে sort করুন (popular first)
        results.sort(key=lambda x: x[1], reverse=True)
        return [word for word, _ in results[:limit]]

    def _dfs(self, node, current, results):
        if node.is_end:
            results.append((current, node.frequency))
        for char, child in node.children.items():
            self._dfs(child, current + char, results)

# Usage example:
trie = Trie()
trie.insert("apple", freq=1000000)
trie.insert("application", freq=500000)
trie.insert("apply", freq=200000)

print(trie.autocomplete("app"))
# → ["apple", "application", "apply"]  (by frequency)

# 3টা document আছে:
# Doc 1: "apple iphone review"
# Doc 2: "apple macbook laptop"
# Doc 3: "samsung galaxy review"

# Inverted Index (simplified):
inverted_index = {
    "apple":   [1, 2],       # Doc 1 এবং 2 এ আছে
    "iphone":  [1],          # শুধু Doc 1 এ
    "review":  [1, 3],       # Doc 1 এবং 3 এ
    "macbook": [2],          # শুধু Doc 2 এ
    "samsung": [3],          # শুধু Doc 3 এ
    "galaxy":  [3],          # শুধু Doc 3 এ
}

# Search "apple review" করলেন:
# apple → [1, 2]
# review → [1, 3]
# Intersection → [1] ← Most relevant!

def search(query: str) -> list:
    words = query.lower().split()
    # প্রতিটা word-এর document list নাও
    doc_lists = [set(inverted_index.get(w, [])) for w in words]
    # Intersection করুন (সব word আছে এমন docs)
    result = doc_lists[0].intersection(*doc_lists[1:])
    return sorted(result)