DEV Community

Saras Growth Space
Saras Growth Space

Posted on

LLD Data Structures in Design Context: Why Some Problems Need Prefix Matching Instead of Exact Lookup

#lld #systemdesign #softwareengineering #codinginterview

"Not every software problem asks, 'Can you find this exact value?' Sometimes the real question is, 'What starts like this?'"

So far in this series, we've explored four fundamental design problems.

A HashMap helps us find an exact object quickly.

A Heap helps us identify the next most important item.

A Queue helps us process work in order.

A Stack helps us preserve and restore recent context.

Now let's explore a completely different kind of problem.

Imagine you're building an application where users don't always know the complete value they're searching for.

Instead, they type only the beginning.

The system must immediately suggest possible matches.

This isn't an exact lookup problem.

It's a prefix matching problem.

This is where another powerful data structure enters the picture—the Trie.

A Simple Example

Open any search engine.

You type:

sys
Enter fullscreen mode Exit fullscreen mode

Before you finish typing, suggestions appear.

system design

system architecture

system calls

system programming
Enter fullscreen mode Exit fullscreen mode

The application isn't waiting for the complete word.

It starts helping as soon as it recognizes the prefix.

Another Everyday Example

Imagine searching for a contact on your phone.

You type:

An
Enter fullscreen mode Exit fullscreen mode

Immediately you see:

Andrew

Ananya

Angela

Ankit
Enter fullscreen mode Exit fullscreen mode

The application isn't looking for one exact name.

It's looking for everything that begins with the same prefix.

A Different Kind of Design Problem

Notice how different this is from previous data structures.

A HashMap asks:

Where is this exact object?
Enter fullscreen mode Exit fullscreen mode

A Heap asks:

Which item has the highest priority?
Enter fullscreen mode Exit fullscreen mode

A Queue asks:

Which task should be processed next?
Enter fullscreen mode Exit fullscreen mode

A Stack asks:

What is the current working context?
Enter fullscreen mode Exit fullscreen mode

A Trie asks something entirely different.

What begins with this prefix?
Enter fullscreen mode Exit fullscreen mode

That's a completely different business requirement.

Why Exact Lookup Isn't Enough

Imagine storing product names in a HashMap.

iPhone 16

iPad Air

iMac

iWatch
Enter fullscreen mode Exit fullscreen mode

Now the user types:

iP
Enter fullscreen mode Exit fullscreen mode

A HashMap can efficiently answer:

Find "iPhone 16"
Enter fullscreen mode Exit fullscreen mode

But it cannot naturally answer:

Find everything starting with "iP"
Enter fullscreen mode Exit fullscreen mode

The system would have to examine many stored values.

As the dataset grows, this approach becomes increasingly inefficient.

The business requirement itself is different.

The Mental Model

Imagine a road network.

Every character represents another road.

        Root
       /    \
      a      s
     /        \
    p          y
   /
  p
 /
l
/
e
Enter fullscreen mode Exit fullscreen mode

Every shared beginning follows the same path.

Words that share prefixes also share most of their journey.

Instead of storing repeated beginnings over and over again, the structure stores them once.

Recognizing This Kind of Problem

Certain business requirements should immediately make you think about prefix matching.

Examples include:

  • Search suggestions
  • Auto-complete
  • Contact search
  • Command suggestions
  • Product search while typing
  • Dictionary lookups
  • Code completion

Notice the common pattern.

The user isn't searching for a complete value.

They're searching using partial information.

How This Changes Your LLD Design

When designing such features, don't immediately think:

"Where should I store these strings?"

Instead ask:

"Will users search using incomplete input?"

If the answer is yes, consider introducing a dedicated search component optimized for prefix matching.

User Types Prefix

↓

Search Component

↓

Prefix Index

↓

Matching Suggestions
Enter fullscreen mode Exit fullscreen mode

Instead of making every service scan the complete dataset, one component becomes responsible for efficient prefix-based searches.

Common Beginner Mistakes

Mistake 1 — Treating Prefix Search Like Exact Search

Finding one exact value and finding everything beginning with a prefix are two different problems.

They often require different solutions.

Mistake 2 — Scanning Every Stored Value

Checking every string may work for small datasets.

It doesn't scale well as the amount of data grows.

Mistake 3 — Choosing Storage Before Understanding Search Behavior

The important question isn't:

"Where should I store these words?"

It's:

"How will users search for them?"

Mistake 4 — Assuming Every Search Needs a Trie

If users always search using complete identifiers, a HashMap is usually simpler.

A Trie becomes valuable only when prefix-based search is a core business requirement.

Engineering Perspective

Experienced engineers don't hear the words "search feature" and immediately think "Trie."

Instead, they recognize requirements like:

  • Suggest results while typing.
  • Match incomplete input.
  • Find everything starting with these characters.
  • Help users discover possible values.

Those are signals that the system isn't performing exact lookup anymore.

It's performing prefix discovery.

The Most Important Insight

A Trie isn't designed to make exact searches faster.

It's designed to make prefix-based discovery efficient.

That's why it powers so many features that help users find information before they've finished typing.

One-Line Takeaway

Great engineers don't choose a Trie because it stores strings—they choose it when the business revolves around discovering values from partial input.

Top comments (0)