Forem: guillaumel

Building a Production-Ready Trie Search System: A 5-Day Journey 🚀

guillaumel — Fri, 03 Jan 2025 15:17:58 +0000

Welcome to SearchCorp! As our newest search infrastructure engineer, you're joining us at a critical time. Our current search system, built five years ago when we had just 100,000 users, is showing its age. With 10 million daily active users now performing an average of 50 searches each, our response times have skyrocketed from 50ms to over 500ms. Customer complaints are increasing, and our biggest client has threatened to leave if we don't fix this in the next quarter.

Your mission: revolutionize our search infrastructure by building a next-generation trie-based search system. Over the next five days, you'll transform from a trie novice to a search system architect, tackling real challenges that our production system faces. You'll learn not just the theory, but the practical aspects of building, scaling, and maintaining a system that processes hundreds of millions of queries daily.

Why Tries for Search?

Before we dive in, let's understand why tries are crucial for modern search systems. Traditional approaches like hash tables or sorted arrays have significant limitations:

Hash Tables: While offering O(1) lookup for exact matches, they can't handle prefix searches efficiently. Imagine typing "pro" and wanting to see all completions like "product", "professional", and "program".
Sorted Arrays: Binary search gives us O(log n) lookups, but prefix searches still require scanning through multiple elements.

Tries solve these problems elegantly by providing:

O(m) lookups where m is the word length (usually bounded and small)
Efficient prefix-based operations
Space-efficient storage of similar strings
Natural support for autocomplete functionality

🎯 Learning Objectives

By the end of this intensive 5-day bootcamp, you will be able to:

Design and implement a productianization-ready trie data structure
Handle real-world challenges like concurrent access and memory constraints
Implement efficient prefix search and autocomplete features
Monitor and optimize system performance
Deploy and scale your solution with confidence

Day 1: Foundation - Understanding Tries

The Library Catalog Metaphor: Understanding Trie Structure

Imagine walking into a vast library with millions of books. Instead of a traditional catalog, you encounter a unique organization system: a series of interconnected rooms, each representing a letter. To find a book titled "PYTHON", you would:

Start at the entrance (root node)
Enter the 'P' room
Follow the door marked 'Y'
Continue through 'T', 'H', 'O', and finally 'N'

This is exactly how a trie works! Each room (node) can have multiple doors (child nodes), and some rooms are marked as "book locations" (word endings). This organization makes it incredibly efficient to:

Find exact titles (search)
List all books starting with certain letters (prefix search)
Add new books (insertion)
Remove outdated books (deletion)

Library Layout (Trie Structure)
         root
       /  |  \
      A   B   C   [Each letter is a room]
     /   /     \
    /   /       \
   AT  BO        CA  [Paths form words]
   |   |         |
   ATM  BOX      CAT [Marked rooms contain complete words]

Let's translate this metaphor into code. We'll start with the basic building blocks: the rooms (TrieNode) and the library itself (Trie).

Basic Trie Implementation: Building Our Foundation

First, let's define what each "room" (node) in our structure needs:

class TrieNode:
    def __init__(self):
        # Dictionary to store child nodes (our "doors" to other "rooms")
        self.children = {}
        # Flag to mark if this node represents the end of a word
        self.is_end = False
        # We'll add more attributes here as we enhance our implementation

class Trie:
    def __init__(self):
        # Create the entrance to our library (root node)
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        """
        Add a new word to our trie, creating nodes (rooms) as needed.
        Think of this as creating a path through the library for a new book.
        """
        node = self.root
        for char in word:
            if char not in node.children:
                # If there's no door for this letter, create one
                node.children[char] = TrieNode()
            # Move to the next room
            node = node.children[char]
        # Mark this room as containing a complete word
        node.is_end = True

Let's visualize how "CAT" is inserted into our trie, step by step:

Step 1: Empty Library (Root)
     root{}
     [An empty entrance hall]

Step 2: Create 'C' Room
     root{}
       |
       C{}
     [Add first letter room]

Step 3: Add 'A' Room
     root{}
       |
       C{}
       |
       A{}
     [Add second letter room]

Step 4: Complete with 'T' Room
     root{}
       |
       C{}
       |
       A{}
       |
       T{is_end=True}
     [Add final room and mark as word end]

🏋️ Day 1 Challenge: Building the Foundation

You've just received your first task from the team lead:

Our users are reporting that the current search system doesn't handle partial matches well. Build a basic trie implementation that supports:

Word insertion

Exact word search

Prefix search

Word deletion Here's your test suite:

def test_basic_trie_operations():
    # Initialize your trie
    trie = Trie()

    # Test 1: Insert and search
    words = ["search", "sea", "shore", "complete", "company"]
    for word in words:
        trie.insert(word)
        assert trie.search(word), f"Failed to insert/find {word}"

    # Test 2: Prefix search
    sea_words = trie.get_words_with_prefix("sea")
    assert set(sea_words) == {"sea", "search"}

    # Test 3: Delete operation
    trie.delete("sea")
    assert not trie.search("sea"), "Delete failed"
    assert trie.search("search"), "Delete affected other words"

    # Test 4: Edge cases
    assert not trie.search(""), "Empty string should return False"
    assert not trie.search("selenium"), "Non-existent word should return False"

    print("All basic operations tests passed! 🎉")

# Run the tests
test_basic_trie_operations()

Your Task:

Implement the Trie class with all required methods
Make all tests pass
Document your design decisions
Bonus: Add visualizations for each operation

Hint: Start with the TrieNode class we covered earlier and build up from there.

Day 2: Advanced Operations - Scaling Our Library

The Library Catalog 2.0: Beyond Basic Search

Remember our library metaphor from Day 1? Now imagine you're helping a visitor who only remembers that the book title starts with "pro". In a traditional library, you'd need to scan through every shelf in the "P" section, checking each "pro-" book. But in our special library, once we reach the "pro-" room, we can see all connecting rooms that lead to complete books!

This is exactly what prefix search and autocomplete do in our trie system. Let's enhance our library with these advanced features.

The Tour Guide System: Understanding Prefix Search

Imagine installing a special "tour guide" system in our library that can:

Guide visitors to any room (prefix navigation)
List all books accessible from that room (word collection)
Optimize paths by combining consecutive single-door rooms (compression)

Tour Guide System (Prefix Search)
         root
       /  |  \
      P   B   C   
     /        
    PR      
   /  \     
PRO  PRA    
 |     \     
PROG   PRAM  [When visitor reaches "PR", guide can list
 |            all books: "prog", "pram"]
PROGRAM

Advanced Trie Implementation: Building the Tour Guide

Let's implement this advanced navigation system:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
        # New: Track word frequency for better autocomplete
        self.frequency = 0
        # New: Store last access timestamp for cleanup
        self.last_access = time.time()

class Trie:
    def get_words_with_prefix(self, prefix: str) -> List[str]:
        """
        Find all words starting with given prefix.
        Think of this as our tour guide listing all books from a starting room.
        """
        def collect_words(node: TrieNode, current_path: str, words: List[str]):
            if node.is_end:
                words.append(current_path)

            # Explore all doors (child nodes)
            for char, child in node.children.items():
                collect_words(child, current_path + char, words)

        # First, navigate to the prefix room
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []  # Prefix room doesn't exist
            node = node.children[char]

        # Now collect all words accessible from this room
        words = []
        collect_words(node, prefix, words)
        return words

Space-Saving Architecture: Compressed Tries

Just as a real library might combine small, single-book rooms into larger spaces, we can optimize our trie by combining nodes with single children:

class CompressedTrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
        # New: Store complete segments instead of single characters
        self.segment = ""

    def insert_compressed(self, word: str) -> None:
        """
        Add a word while maintaining compression.
        Like combining small rooms into a larger space.
        """
        node = self.root
        i = 0
        while i < len(word):
            # Find longest matching segment
            matched = False
            for child_segment, child in node.children.items():
                common = self._longest_common_prefix(word[i:], child_segment)
                if common:
                    # Handle segment splitting if needed
                    if common != child_segment:
                        self._split_node(node, child_segment, common)
                    i += len(common)
                    node = node.children[common]
                    matched = True
                    break

            if not matched:
                # Create new node with remaining characters
                new_node = CompressedTrieNode()
                new_node.segment = word[i:]
                node.children[new_node.segment] = new_node
                node = new_node
                break

        node.is_end = True

Let's visualize the compression:

Standard Trie storing "team" and "tech":
     root
      |
      t
      |
      e
     / \
    a   c
    |   |
    m   h

Compressed Trie:
     root
      |
      te
     /  \
   am    ch

🏋️ Day 2 Challenge: Enhanced Search Features

Your team lead has a new task:

Our premium customers need advanced search capabilities. Implement:

Prefix-based search with results ranked by frequency

Memory-efficient storage using compressed tries

Fuzzy search allowing one character mismatch

Bonus: Add a feature to suggest corrections for misspelled words

Here's your test suite:

def test_advanced_trie_features():
    trie = CompressedTrie()

    # Test 1: Frequency-based results
    words = [("program", 5), ("programming", 3), ("programmer", 2)]
    for word, freq in words:
        trie.insert(word, frequency=freq)

    results = trie.search_by_prefix("prog")
    assert results[0] == "program", "Highest frequency word should be first"

    # Test 2: Memory efficiency
    memory_usage = trie.get_memory_usage()
    assert memory_usage < 1000, "Trie is using too much memory"

    # Test 3: Fuzzy search
    fuzzy_results = trie.fuzzy_search("progrm")
    assert "program" in fuzzy_results, "Should find similar words"

    print("All advanced features tests passed! 🚀")

# Run the tests
test_advanced_trie_features()

Remember: In production, every byte counts, and every millisecond matters. Focus on both correctness and efficiency in your implementation.

Tomorrow, we'll tackle concurrent access and real-time updates to our trie system!

Day 3: Concurrent Access and Real-Time Updates - Making Our Library Thread-Safe

The Busy Library Metaphor: Understanding Concurrent Access

Imagine our library during peak hours: hundreds of visitors trying to access rooms simultaneously, librarians updating catalog entries, and maintenance staff removing outdated books. Without proper coordination, chaos would ensue - two people might try to enter a narrow doorway at once, or a librarian might start removing a book while someone's reading it!

This is exactly the challenge we face with concurrent trie access. Let's solve it using library-inspired solutions:

Concurrent Library Access Visualization:
         root 🔒
       /    |    \
    A 🔒   B 🔒   C 🔒   [Locks protect each room]
   /      /        \
  AT    BO         CA    [Multiple readers allowed]
  |      |          |
 ATM    BOX       CAT    [Writers need exclusive access]
 [R:3]  [W:1]     [R:2]  [R = Readers, W = Writers]

The Library Access Control System: Thread-Safe Trie

Just as a real library needs systems to manage multiple visitors, our trie needs mechanisms to handle concurrent access:

from threading import Lock, RLock
from concurrent.futures import ThreadPoolExecutor
import threading

class ThreadSafeTrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
        self.frequency = 0
        # New: Add lock for this node
        self.lock = RLock()
        # New: Track reader count
        self.reader_count = 0
        self.reader_lock = Lock()

class ThreadSafeTrie:
    def __init__(self):
        self.root = ThreadSafeTrieNode()
        # Global lock for trie-wide operations
        self.global_lock = RLock()
        # Track active operations
        self.active_readers = 0
        self.active_writers = 0

The Library Pass System: Read-Write Lock Pattern

Think of our access control like a library pass system:

Reading Passes (Shared Access):
- Multiple visitors can read simultaneously
- No modifications allowed while reading
Writing Passes (Exclusive Access):
- Only one librarian can modify at a time
- No readers allowed during modifications

class ThreadSafeTrie:
    def __enter_read(self, node: ThreadSafeTrieNode):
        """Get a reading pass for this room"""
        with node.reader_lock:
            node.reader_count += 1
            if node.reader_count == 1:
                # First reader locks against writers
                node.lock.acquire()

    def __exit_read(self, node: ThreadSafeTrieNode):
        """Return the reading pass"""
        with node.reader_lock:
            node.reader_count -= 1
            if node.reader_count == 0:
                # Last reader unlocks for writers
                node.lock.release()

    def search(self, word: str) -> bool:
        """
        Thread-safe search implementation.
        Like visitors reading catalog entries.
        """
        current = self.root
        self.__enter_read(current)
        try:
            for char in word:
                if char not in current.children:
                    return False
                next_node = current.children[char]
                self.__enter_read(next_node)
                self.__exit_read(current)
                current = next_node
            return current.is_end
        finally:
            self.__exit_read(current)

Real-Time Updates: The Living Library

Imagine our library as a living system where:

New books are constantly being added
Popular books get moved to more accessible locations
Outdated books are removed
Statistics are continuously updated

Let's implement this dynamic behavior:

class ThreadSafeTrie:
    def batch_update(self, words: List[str], operation: str):
        """
        Perform batch operations safely.
        Like coordinating multiple librarians.
        """
        with ThreadPoolExecutor() as executor:
            if operation == "insert":
                futures = [executor.submit(self.insert, word) 
                          for word in words]
            elif operation == "delete":
                futures = [executor.submit(self.delete, word) 
                          for word in words]

            # Wait for all operations to complete
            for future in futures:
                future.result()

    def update_frequencies(self):
        """
        Update word frequencies based on access patterns.
        Like reorganizing books based on popularity.
        """
        def update_node(node: ThreadSafeTrieNode):
            with node.lock:
                for child in node.children.values():
                    child.frequency = child.access_count
                    update_node(child)

        with self.global_lock:
            update_node(self.root)

🏋️ Day 3 Challenge: Building a Production-Ready Concurrent Trie

Your team lead presents today's challenge:

Our system needs to handle 10,000 concurrent users without breaking a sweat. Implement:

Thread-safe trie operations

Efficient read-write locking

Batch update capabilities

Real-time frequency updates

Bonus: Add monitoring to track concurrent access patterns

Here's your test suite:

def test_concurrent_trie_operations():
    trie = ThreadSafeTrie()

    # Test 1: Concurrent reads
    def concurrent_reads(word):
        assert trie.search(word) == True, f"Read failed for {word}"

    # Add some words
    words = ["concurrent", "threading", "safety", "locks"]
    for word in words:
        trie.insert(word)

    # Spawn 1000 concurrent readers
    with ThreadPoolExecutor(max_workers=1000) as executor:
        futures = [executor.submit(concurrent_reads, "concurrent") 
                  for _ in range(1000)]
        # Wait for all reads to complete
        for future in futures:
            future.result()

    # Test 2: Concurrent writes
    def concurrent_writes(word):
        trie.insert(word + "new")

    # Spawn 100 concurrent writers
    with ThreadPoolExecutor(max_workers=100) as executor:
        futures = [executor.submit(concurrent_writes, f"word{i}") 
                  for i in range(100)]
        for future in futures:
            future.result()

    print("All concurrent operations tests passed! 🔒")

# Run the tests
test_concurrent_trie_operations()

Performance Monitoring: The Library Analytics System

Don't forget to add monitoring! Track:

Number of active readers/writers
Lock contention rates
Operation latencies
Memory usage patterns

Tomorrow, we'll tackle distributed tries and handling system failures!

Remember: In production, every lock matters, and every deadlock is a disaster. Focus on making your implementation both safe and efficient.

Day 4: Distributed Tries - Scaling Across Libraries

The Library Network Metaphor: Understanding Distributed Tries

Imagine expanding from a single library to a nationwide network of interconnected libraries. Each library specializes in certain sections of the catalog, but visitors at any location can access the entire collection. This is exactly how a distributed trie works!

Distributed Library Network:
[Library A]     [Library B]     [Library C]
   root           root           root
   /  \           /  \           /  \
  A    B         M    N         X    Y
 [Primary]     [Primary]      [Primary]
  |    |         |    |         |    |
  C    D         O    P         Z    W
[Replica] [Replica in C] [Replica in A]

The Inter-Library System: Distributed Trie Architecture

Just as libraries need systems for sharing books and synchronizing catalogs, our distributed trie needs mechanisms for:

Partitioning data across nodes
Replicating for redundancy
Maintaining consistency
Handling node failures

from typing import Dict, Set, Optional
import uuid
import hashlib

class DistributedTrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
        # New: Node identification and ownership
        self.node_id = str(uuid.uuid4())
        self.primary_owner = None
        self.replicas: Set[str] = set()
        # New: Version control
        self.version = 0
        self.last_modified = time.time()

class DistributedTrie:
    def __init__(self, node_id: str, cluster_nodes: List[str]):
        self.root = DistributedTrieNode()
        self.node_id = node_id
        self.cluster_nodes = set(cluster_nodes)
        # Track node assignments
        self.partition_map: Dict[str, str] = {}
        # Cache for frequent lookups
        self.cache = LRUCache(1000)

Consistent Hashing: The Library Assignment System

How do we decide which library handles which sections? We use consistent hashing:

class DistributedTrie:
    def get_responsible_node(self, word: str) -> str:
        """
        Determine which node should store this word.
        Like deciding which library specializes in certain topics.
        """
        hash_value = hashlib.md5(word.encode()).hexdigest()
        # Map hash to available nodes
        points = sorted(self.cluster_nodes)
        hash_point = int(hash_value, 16) % len(points)
        return points[hash_point]

    def insert(self, word: str) -> None:
        """
        Insert word into the distributed system.
        Like adding a book to the library network.
        """
        responsible_node = self.get_responsible_node(word)
        if responsible_node == self.node_id:
            # We own this word
            self._local_insert(word)
        else:
            # Forward to responsible node
            self._forward_insert(word, responsible_node)

Replication and Consistency: The Backup System

Just as libraries maintain backup catalogs, we need replication:

class DistributedTrie:
    def replicate_node(self, node: DistributedTrieNode, 
                      replica_count: int = 2):
        """
        Create replicas of a node across the cluster.
        Like maintaining backup catalogs.
        """
        # Choose replica nodes
        available_nodes = self.cluster_nodes - {self.node_id}
        replica_nodes = random.sample(available_nodes, replica_count)

        for replica_node in replica_nodes:
            # Send node data to replica
            self._send_replica(node, replica_node)
            node.replicas.add(replica_node)

    def handle_node_failure(self, failed_node: str):
        """
        Recover from node failures.
        Like redistributing books when a library closes.
        """
        affected_words = self._get_words_owned_by(failed_node)
        new_owner = self._get_next_available_node(failed_node)

        # Redistribute affected words
        for word in affected_words:
            self.insert(word, new_owner=new_owner)

🏋️ Day 4 Challenge: Building a Resilient Distributed Trie

Your team lead's challenge:

We're expanding globally! Build a distributed trie that:

Scales horizontally across multiple nodes

Maintains consistency during updates

Handles node failures gracefully

Provides efficient cross-node searches

Bonus: Implement adaptive replication based on access patterns

Here's your test suite:

def test_distributed_trie():
    # Create a cluster of nodes
    nodes = ["node1", "node2", "node3"]
    tries = {
        node_id: DistributedTrie(node_id, nodes)
        for node_id in nodes
    }

    # Test 1: Distributed insertion
    words = ["distributed", "system", "resilient"]
    for word in words:
        tries["node1"].insert(word)

    # Verify words are accessible from all nodes
    for node_id, trie in tries.items():
        for word in words:
            assert trie.search(word), \
                f"Word {word} not found in {node_id}"

    # Test 2: Node failure recovery
    # Simulate node2 failure
    failed_node = "node2"
    for node_id, trie in tries.items():
        if node_id != failed_node:
            trie.handle_node_failure(failed_node)

    # Verify data still accessible
    for word in words:
        assert tries["node1"].search(word), \
            "Data lost after node failure"

    print("All distributed operations tests passed! 🌍")

# Run the tests
test_distributed_trie()

Performance Monitoring: The Network Analytics System

Monitor your distributed system:

Inter-node communication latency
Replication lag
Node health metrics
Load distribution
Cache hit rates

Tomorrow, for our final day, we'll tackle search ranking and relevance scoring!

Remember: In a distributed system, network is king. Every message counts, every millisecond matters, and failures are normal. Design for resilience!

Day 5: Search Ranking and Relevance - Making Results Matter

The Library Recommendation System: Understanding Search Relevance

Imagine our library network has evolved beyond just finding books - now it needs to recommend the most relevant ones. Just as a skilled librarian considers multiple factors (popularity, relevance, recency) when recommending books, our trie system needs sophisticated ranking capabilities.

Relevance Scoring System:
         root
       /  |  \
      P   B   C   [Node weights show popularity]
     /    [w:0.8]  
    PR      
   /  \     [Edit distance costs]
PRO  PRA    Cost("prog" → "prag") = 1
 |     \     
PROG   PRAM  [Term frequency stored]
[tf:85]  [tf:23]
 |
PROGRAM [Recency bonus]
[recent:0.9]

The Smart Catalog: Implementing Relevance Scoring

Let's enhance our trie with intelligent scoring capabilities:

from dataclasses import dataclass
from typing import List, Dict, Optional
import math

@dataclass
class SearchResult:
    word: str
    score: float
    frequency: int
    last_access: float
    relevance_factors: Dict[str, float]

class RankedTrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
        # Ranking factors
        self.term_frequency = 0
        self.last_access = time.time()
        self.importance_score = 1.0
        # Contextual metadata
        self.categories: Set[str] = set()
        self.related_terms: Dict[str, float] = {}

class RankedTrie:
    def __init__(self):
        self.root = RankedTrieNode()
        # Scoring weights
        self.weights = {
            'term_frequency': 0.4,
            'recency': 0.2,
            'importance': 0.2,
            'relevance': 0.2
        }

The Smart Search Algorithm: Relevance Calculation

Just as a librarian uses multiple criteria to rank recommendations:

class RankedTrie:
    def calculate_relevance_score(self, node: RankedTrieNode, 
                                query: str, word: str) -> float:
        """
        Calculate multi-factor relevance score.
        Like a librarian weighing different aspects of a book.
        """
        # Term frequency component (popularity)
        tf_score = math.log1p(node.term_frequency)

        # Recency score (freshness)
        time_diff = time.time() - node.last_access
        recency_score = 1.0 / (1.0 + math.log1p(time_diff))

        # Edit distance for fuzzy matching
        edit_distance = self._levenshtein_distance(query, word)
        similarity_score = 1.0 / (1.0 + edit_distance)

        # Combine scores with weights
        final_score = (
            self.weights['term_frequency'] * tf_score +
            self.weights['recency'] * recency_score +
            self.weights['importance'] * node.importance_score +
            self.weights['relevance'] * similarity_score
        )

        return final_score

    def search_ranked(self, query: str, 
                     max_results: int = 10) -> List[SearchResult]:
        """
        Find most relevant matches for query.
        Like getting personalized book recommendations.
        """
        results = []

        def collect_matches(node: RankedTrieNode, 
                          current_word: str, 
                          max_distance: int = 2):
            if node.is_end:
                score = self.calculate_relevance_score(
                    node, query, current_word)
                results.append(SearchResult(
                    word=current_word,
                    score=score,
                    frequency=node.term_frequency,
                    last_access=node.last_access,
                    relevance_factors={
                        'tf_score': math.log1p(node.term_frequency),
                        'recency': 1.0 / (1.0 + time.time() - 
                                        node.last_access),
                        'importance': node.importance_score
                    }
                ))

            # Explore children within edit distance threshold
            for char, child in node.children.items():
                if len(results) < max_results:
                    collect_matches(child, current_word + char)

        collect_matches(self.root, "")
        return sorted(results, key=lambda x: x.score, reverse=True)

Context-Aware Search: Understanding User Intent

Like a librarian who understands context:

class RankedTrie:
    def add_context(self, word: str, 
                   categories: List[str], 
                   related_terms: Dict[str, float]):
        """
        Enrich word with contextual information.
        Like adding metadata to library catalog entries.
        """
        node = self._find_node(word)
        if node:
            node.categories.update(categories)
            node.related_terms.update(related_terms)

    def contextualized_search(self, query: str, 
                            user_context: Dict[str, Any]) -> List[SearchResult]:
        """
        Search considering user's context.
        Like personalizing recommendations based on reading history.
        """
        base_results = self.search_ranked(query)

        for result in base_results:
            node = self._find_node(result.word)
            # Adjust score based on user context
            context_score = self._calculate_context_relevance(
                node, user_context)
            result.score *= (1 + context_score)

        return sorted(base_results, key=lambda x: x.score, reverse=True)

🏋️ Day 5 Challenge: Building a Smart Search Engine

Your final team lead challenge:

Our users need more relevant results! Build a ranking system that:

Considers multiple relevance factors

Supports personalized results

Handles fuzzy matching intelligently

Provides clear relevance explanations

Bonus: Implement machine learning-based ranking

Here's your test suite:

def test_ranked_search():
    trie = RankedTrie()

    # Test 1: Basic ranking
    words = [
        ("python", 100),  # High frequency
        ("pytorch", 50),  # Medium frequency
        ("pythagorean", 10)  # Low frequency
    ]

    for word, freq in words:
        trie.insert(word, frequency=freq)

    results = trie.search_ranked("pyt", max_results=3)
    assert results[0].word == "python", "Most popular should rank first"

    # Test 2: Context-aware search
    user_context = {
        "interests": ["machine_learning", "programming"],
        "recent_searches": ["tensorflow", "keras"]
    }

    contextualized_results = trie.contextualized_search(
        "pyt", user_context)
    assert contextualized_results[0].word == "pytorch", \
        "ML context should boost PyTorch"

    print("All ranking tests passed! 🎯")

# Run the tests
test_ranked_search()

Final Implementation Tips

Ranking Balance
- Weight factors based on user behavior
- Regularly update weights using A/B tests
- Consider seasonal and temporal patterns
Performance Optimization
- Cache popular search results
- Pre-compute static ranking factors
- Use approximate algorithms for large-scale scoring
Monitoring and Analytics
- Track search result clicks
- Measure result relevance
- Monitor ranking factor distributions
- Log user satisfaction metrics

Congratulations! You've completed the 5-day journey from trie basics to a production-ready search system. You now have the skills to:

Build efficient trie-based search
Handle concurrent access
Scale across distributed systems
Provide relevant, ranked results

Remember: A great search engine isn't just about finding matches - it's about understanding user intent and delivering value. Keep evolving your system based on user feedback and changing needs!

Building a Real-time Company Intelligence Engine with Linkup in 50 Lines of Python

guillaumel — Thu, 05 Dec 2024 15:23:11 +0000

Ever tried to research a potential client minutes before a sales call, only to find that your expensive data provider has outdated information? Yeah, me too. That's precisely why I spent last weekend building something different.

The Problem with Static Data 📊

Here's a scenario that might sound familiar:

Your sales rep is about to jump on a call with a hot prospect. They quickly look up the company in your fancy data enrichment tool and confidently mention, "I see you recently raised your Series A!" Only to hear an awkward laugh followed by "Actually, that was two years ago. We just closed our Series C last month."

Ouch.

Static databases, no matter how comprehensive, share one fundamental flaw: they're static. By the time information is collected, processed, and made available, it's often already outdated. In the fast-moving world of tech and business, that's a real problem.

A Different Approach 💡

What if instead of relying on pre-collected data, we could:

Get real-time information from across the web
Structure it exactly how we need it
Never worry about data freshness again

That's exactly what we're going to build today using Linkup's API. The best part? It's just 50 lines of Python.

Let's Build It! 🚀

Time to write some code! But don't worry - we'll break it down into bite-sized pieces that even your non-technical coworkers could understand (well, almost 😉).

1. Setting Up Our Project 📂

First, let's create our project and install the tools we need:

mkdir company-intel
cd company-intel
pip install linkup-sdk pydantic

Nothing fancy here - just creating a new folder and installing our two magical ingredients: linkup-sdk for fetching data and pydantic for making sure our data looks pretty.

2. Defining What We Want to Know 🎯

Before we start grabbing data, let's define what we actually want to know about companies. Think of this as your wishlist:

# schema.py - Our data wishlist! 🎁
from pydantic import BaseModel
from typing import List, Optional
from enum import Enum

class CompanyInfo(BaseModel):
    # The basics
    name: str = ""                      # Company name (duh!)
    website: str = ""                   # Where they live on the internet
    description: str = ""                # What they do (hopefully not just buzzwords)

    # The interesting stuff
    latest_funding: str = ""   # Show me the money! 💰
    recent_news: List[str] = []         # What's the buzz? 📰
    leadership_team: List[str]  = []    # Who's running the show? 👥
    tech_stack: List[str] = []         # The tools they love ⚡

This is like telling a restaurant exactly what you want in your sandwich. We're using pydantic to make sure we get exactly what we ordered!

3. The Magic Machine 🎩✨

Now for the fun part - the engine that makes everything work:

# company_intel.py - Where the magic happens! 🪄
from linkup import LinkupClient
from schema import CompanyInfo
from typing import List

class CompanyIntelligence:
    def __init__(self, api_key: str):
        # Initialize our crystal ball (aka Linkup client)
        self.client = LinkupClient(api_key=api_key)

    def research_company(self, company_name: str) -> CompanyInfo:
        # Craft our research question
        query = f"""
        Hey Linkup! Tell me everything fresh about {company_name}:

        🏢 The name of the company, its website, and a short description.
        🏦 Any recent funding rounds or big announcements?
        👥 Who's on the leadership team right now?
        🛠️ What tech are they using these days?
        📰 What have they been up to lately?

        PS: Only stuff from the last 3 months, please!
        """

        # Ask the question and get structured answers
        response = self.client.search(
            query=query,            # What we want to know
            depth="deep",           # Go deep, not shallow
            output_type="structured",  # Give me clean data
            structured_output_schema=CompanyInfo  # Format it like our wishlist
        )

        return response

Let's break down what's happening here:

We create a new CompanyIntelligence class (fancy name, right?)
Initialize it with our API key (the key to the kingdom)
Define a method that takes a company name and returns all the juicy details
Write a friendly query that tells Linkup exactly what we want
Get back clean, structured data that matches our wishlist

4. Making It Production-Ready 🚀

Now let's wrap it in a nice API that your whole team can use:

# api.py - Sharing is caring! 🤝
from fastapi import FastAPI

app = FastAPI()
intel = CompanyIntelligence(api_key="your-linkup-api-key")

@app.get("/company/{name}")
async def get_company_info(name: str):
    return intel.research_company(name)

What's cool here:

FastAPI makes our tool available over HTTP (fancy!)
Simple GET endpoint that anyone can use

5. Let's Take It for a Spin! 🎢

Time to see our creation in action:

# Let's try it out! 
intel = CompanyIntelligence(api_key="your-key")

# Research Vercel (because who doesn't love Next.js?)
company = intel.research_company("Vercel")

print("🔍 Here's what we found:")
print(f"💰 Latest Funding: {company.latest_funding}")
print(f"📰 Hot News: {company.recent_news[0]}")
print(f"⚡ Tech Stack: {', '.join(company.tech_stack)}")

And voilà! Fresh, real-time company data at your fingertips!

6. Fun Extensions 🎨

Want to make it even cooler? Here are some fun additions you could make:

# Add sentiment analysis to news
from textblob import TextBlob

def analyze_sentiment(news: List[str]) -> str:
    sentiment = TextBlob(news[0]).sentiment.polarity
    return "😊" if sentiment > 0 else "😐" if sentiment == 0 else "😟"

# Add company size estimation
def estimate_size(funding: str) -> str:
    if "Series C" in funding:
        return "🦕 Big player!"
    elif "Series B" in funding:
        return "🦒 Growing fast!"
    return "🐥 Startup vibes!"

Real World Impact 🌟

We've been using this in production for our sales team, and it's been a game-changer:

Pre-call research is always current
Sales reps are more confident in their outreach
We catch important company updates as they happen
Our data actually gets better over time, not worse

Why This Matters 🎯

Always Fresh: Information is gathered in real-time, not pulled from a static database
Comprehensive: Combines data from multiple sources across the web
Customizable: Structure the data exactly how your team needs it
Efficient: Fast enough for real-time lookups before calls
Maintainable: Simple code that any developer can understand and modify

Future Ideas 🚀

The possibilities are endless! Here are some ideas to take it further:

For Sales Teams:

Slack bot for instant lookups (/research company-name)
Chrome extension that shows company info on LinkedIn
Automatic CRM enrichment

For Marketing Teams:

Track competitor content strategies
Monitor industry trends
Identify potential partnership opportunities

For Product Teams:

Track competitor feature launches
Monitor customer tech stacks
Identify integration opportunities

Try It Yourself 🛠️

Ready to build your own? Here's what you need:

Get a Linkup API key
Copy the code above
Customize the schema for your needs
Deploy and enjoy always-fresh company data!

Wrapping Up 🎁

The days of static databases are numbered. In a world where companies pivot overnight, raise rounds weekly, and change their tech stacks monthly, real-time intelligence isn't just nice to have—it's essential.

What we built here is just the beginning. Imagine combining this with:

AI for automatic insights
Trend detection across industries
Predictive analytics for company growth

Have you built something similar? How do you handle the challenge of keeping company data fresh? Let me know in the comments!

python #api #saas #webdev #buildinpublic

Built with ☕ and a healthy obsession with fresh data

How to Help Your Users Embed HTML Forms Generated by Your App

guillaumel — Thu, 01 Dec 2022 16:16:57 +0000

Introduction

Are you building an app that generates HTML forms? If so, you may want to provide your users with an easy way to embed the forms on their own websites. In this post, we will show you how to help your users embed HTML forms generated by your app on their websites. We will cover different approaches for embedding the forms, including using an iframe element and a custom JavaScript and CSS solution. Read on to learn more about how to help your users embed HTML forms generated by your app.

Using an iframe Element to Embed the HTML Form

To help your users embed the HTML form they have generated, you can create a snippet of JavaScript code that they can copy and paste into their website. This code will automatically create an iframe element on the page that will display the form.

Here is an example of a JavaScript code snippet that your users can use to embed the HTML form:

<script>
  // Set the URL of the form to be embedded
  var formUrl = "http://www.example.com/form.html";

  // Create an iframe element to display the form
  var iframe = document.createElement("iframe");
  iframe.setAttribute("src", formUrl);
  iframe.setAttribute("frameborder", "0");
  iframe.setAttribute("scrolling", "no");
  iframe.setAttribute("width", "100%");
  iframe.setAttribute("height", "500");

  // Append the iframe to the document
  document.body.appendChild(iframe);
</script>

This code will create an iframe element on the page and set the URL of the form as the src attribute. The iframe will have a width of 100% and a height of 500 pixels. It will also have the frameborder and scrolling attributes set to 0 to remove the border and scrolling bars, respectively.

Your users can simply copy and paste this code into the HTML of their website, and the form will be embedded on the page. They can customize the width and height of the iframe as needed to fit the layout of their website.

Using a Custom JavaScript and CSS Solution to Embed the HTML Form

If you don't want to use an iframe to embed the HTML form on your users' websites, you can use a different approach. Instead of using an iframe, you can use a combination of JavaScript and CSS to create a custom container on the page where the form will be displayed.

Here is an example of a JavaScript code snippet that your users can use to embed the HTML form without using an iframe:

<script>
  // Set the URL of the form to be embedded
  var formUrl = "http://www.example.com/form.html";

  // Create a container element to hold the form
  var container = document.createElement("div");
  container.setAttribute("id", "form-container");

  // Create a script element to load the form
  var script = document.createElement("script");
  script.setAttribute("src", formUrl);
  script.setAttribute("type", "text/javascript");

  // Append the script to the container
  container.appendChild(script);

  // Append the container to the document
  document.body.appendChild(container);
</script>

This code will create a div element with the ID form-container on the page. It will then create a script element and set the URL of the form as the src attribute. The script element will be appended to the div container, and the div will be appended to the document.

To display the form correctly, your users will also need to add some CSS styles to their website. Here is an example of the CSS styles that they can use:

<style>
  #form-container {
    width: 100%;
    height: 500px;
    overflow: hidden;
  }
</style>

This CSS will set the width and height of the div container, and it will also add the overflow: hidden property to prevent the form from being displayed outside of the container.

Your users can simply copy and paste this code into the HTML of their website, and the form will be embedded on the page without using an iframe. They can customize the width and height of the container as needed to fit the layout of their website.

Share a javascript script

You can provide your users with a link to a JavaScript script that they can use to embed the HTML form on their website. This approach is similar to the one where you provide a snippet of JavaScript code that they can copy and paste into their website, but instead of copying and pasting the code, they can include the script in their page by using a script element with a src attribute that points to the URL of the script.

Here is an example of how your users can include a JavaScript script in their page to embed the HTML form:

<script src="http://www.example.com/form-embed.js"></script>

This code will include the script at the URL http://www.example.com/form-embed.js in the page. The script will be executed when the page loads, and it will generate the necessary HTML and JavaScript code to embed the form on the page.

You can provide your users with the URL of the script, and they can simply add this script element to their page to include the script. This approach has the advantage of making it easy for your users to include the script in their page, but it has the disadvantage of not allowing them to customize the script or the HTML and CSS styles used to display the form. If you want to allow your users to customize the script or the styles, you will need to provide them with a snippet of code that they can modify as needed.

Choose between iframe and javascript

When deciding whether to use JavaScript or an iframe element to embed an HTML form on a website, there are several factors to consider. Some of the key considerations are:

Customization: If you want to allow your users to customize the appearance of the form or the behavior of the iframe element, you will need to use JavaScript. With JavaScript, you can provide your users with a code snippet that they can modify to change the appearance or behavior of the form. With an iframe, on the other hand, the user has no control over the appearance or behavior of the form.
Performance: If performance is a key concern, you may want to use JavaScript. Because an iframe loads the form in a separate frame, it can affect the performance of the page on the user's website. With JavaScript, on the other hand, the form is loaded directly on the page, which can improve the performance of the page.
Compatibility: If you are targeting users with older web browsers or mobile devices, you may want to use an iframe. Some older web browsers and mobile devices may not support the JavaScript code needed to embed the form, whereas most modern web browsers and mobile devices support the iframe element.
User experience: If you want to provide your users with a good user experience, you may want to use JavaScript. With JavaScript, you can provide your users with a code snippet that is easy to understand and use. With an iframe, on the other hand, the user may have to edit the HTML code of the page on their website, which can be more complex and difficult for some users.

Ultimately, the decision of whether to use JavaScript or an iframe to embed an HTML form on a website will depend on your specific requirements and the needs of your users. By considering the factors mentioned above, you can make an informed decision about which approach is best for your situation.

Conclusion

In conclusion, embedding an HTML form on a website can be an effective way to collect data from users. There are several approaches to embedding a form on a website, including using an iframe element and a custom JavaScript and CSS solution. Each approach has its own advantages and disadvantages, and the best approach will depend on your specific requirements and the needs of your users. By providing your users with the right tools and instructions, you can help them to embed an HTML form on their website and start collecting data from their users. Thank you for reading this blog post and we hope you found it useful.

How to add a splash screen for a progressive web app with React ?

guillaumel — Tue, 05 Nov 2019 00:35:12 +0000

Recently I was developing a Progressive Web App (PWA). A PWA is a web app that you can install on your smartphone without downloading it from a Store, cool isn't it ? These kind of applications are not going to replace native web apps right now but it seems it has become an interesting technology.

Anyway, my problem was to add the splash screen of my application for iOS users. Now I know how to easily add a splash screen, and I will explain you how to reproduce the following exemple :

First of all, we need to create a react app :

npx create-react-app my-app

Put your logo (we will call it logo.svg) in the public folder of the newly created react app. And now we are going to actually add the plash screen capability for all types of iPhone screen size :

cd my-app/public 
npx pwa-asset-generator logo.svg ./assets -i ./index.html -m ./manifest.json

The pwa-asset-generator script (github repo) generates all the existing iPhone screen sizes and puts it in the asset folder, but also it adds in the index.html and in the manifest.json all metadata needed by the phone to choose the correct image for the screen splash ! This tool is so amazing !

Now you can start the development server, take your 📱, access to your app with safari, install it to your phone and test the splash screen !

Which pages on my site are indexed by Google?

guillaumel — Tue, 15 Oct 2019 22:14:46 +0000

Yesterday I launched my website www.mangerdurable.com and I wondered how to know if google has indexed my domain name. The simple solution is to use the Google Search Console, but there is an even easier way, just write in the google search bar:

As a result of the search you will get all the pages of your site that are actually indexed by Google.