Q4 - MongoDB Query Matcher (Implementing find())

We believe this interview question and close variations of it have frequently appeared in MongoDB's software engineering interviews.

This one sits right at the center of what the database does. Every db.collection.find(query) runs a matcher: it walks the documents and decides, one at a time, whether each satisfies the query. It looks nothing like a textbook LeetCode exercise, yet it is built entirely from fundamentals you already know (a loop over documents and a check per field). Get the matcher right and you have implemented the core of MongoDB's read path.

A query is itself a document. find({ status: 1, plan: 2 }) returns every document whose status is 1 and whose plan is 2, an implicit AND across the fields. Add operators, find({ age: { $gte: 18, $lt: 65 } }), and the same matcher expresses ranges and sets. You will build it in two steps: plain equality first, then the operators.

A document is a set of fields, each mapping a name to a value. Real MongoDB documents hold strings, arrays, and nested sub-documents, but the matching logic that actually decides things, the thresholds and ranges, lives on the numeric fields. So for this problem every value is an integer: think age, price, timestamp, quantity.

Your matcher takes a list of documents and a query, and returns the documents that match, in their original order. A document matches only if it satisfies every part of the query at once.

documents:
  { id: 1, age: 25, score: 80, plan: 2 }
  { id: 2, age: 17, score: 95, plan: 1 }
  { id: 3, age: 40, score: 60, plan: 2 }
  { id: 4, age: 30, score: 80 }              <- no "plan" field

find( { plan: 2 } )  ->  documents 1 and 3      (both have plan == 2; document 4 has no plan at all)

Part 1: Equality Matching (~10 minutes)

Implement find_matches(docs, query). The query is a document of field: value pairs. A document matches when, for every field in the query, it has that field and its value equals the query's value. Return the matching documents, in input order.

The rules:

Implicit AND: every field in the query must match, not just one.
A missing field is a miss. If the query asks for plan and a document has no plan, that document fails.
An empty query {} matches every document (there are no conditions to fail).

Example 1

Input:
docs = [
  { id: 1, age: 25, score: 80, plan: 2 },
  { id: 2, age: 17, score: 95, plan: 1 },
  { id: 3, age: 40, score: 60, plan: 2 },
  { id: 4, age: 30, score: 80 },
]
query = { plan: 2 }

Output: documents 1 and 3
Explanation: Documents 1 and 3 both have plan == 2. Document 4 has no plan field, so it fails.

Example 2

Input: query = { score: 80, plan: 2 }

Output: document 1
Explanation: Document 1 has score 80 and plan 2. Document 3 has plan 2 but score 60. Document 4
has score 80 but no plan. Only document 1 satisfies both fields.

Example 3

Input: query = { }

Output: documents 1, 2, 3, 4
Explanation: An empty query has no conditions to fail, so every document matches.

Solution - Part 1

One pass over the documents. For each one, check that it satisfies every field in the query: the field must be present and its value must equal the query's value. Keep the document only if all of them hold. Two details are worth saying out loud, because the hidden tests will probe them: a missing field is an automatic miss, and an empty query matches everything (checking "all of zero conditions" is true).

Why a missing field must fail. In MongoDB a document has no fixed schema, so "does this document even have a plan?" is a real question every match must answer. Treating an absent field as a non-match (rather than, say, a zero) is what keeps find({ plan: 2 }) from silently returning documents that never had a plan.

def find_matches(docs: list, query: dict) -> list:
    matches = []
    for doc in docs:
        # every queried field must be present and equal; an empty query matches all
        if all(field in doc and doc[field] == value for field, value in query.items()):
            matches.append(doc)
    return matches

Complexity Analysis

Time Complexity: O(N · F), for N documents and F fields in the query, each a hash lookup.
Space Complexity: O(1) beyond the matched documents you return.

Part 2: Query Operators (~15 minutes)

Real queries do more than test equality. A condition can compare with $eq, $ne, $gt, $gte, $lt, $lte, or test membership with $in. Generalize the matcher to handle them.

So you can focus on the matching (not the parsing), the query arrives already flattened into a list of conditions, each a triple (field, op, operands):

MongoDB query:  { age: { $gte: 18, $lt: 40 }, plan: { $in: [1, 2] } }

as a list of conditions:
  ( age,  $gte, [18]  )
  ( age,  $lt,  [40]  )
  ( plan, $in,  [1, 2] )

The rules:

$eq, $ne, $gt, $gte, $lt, $lte compare the field's value against operands[0].
$in matches when the field's value is one of operands.
Conditions are an implicit AND, and one field may appear in several conditions (that is how a range like age $gte 18 and age $lt 40 is expressed).
Missing-field rule: if a document lacks a condition's field, it fails every operator except $ne. A value that is not there is "not equal" to anything, which is exactly how MongoDB's $ne treats a missing field.

Example 1 (a range)

Conditions: [ (age, $gte, [18]), (age, $lt, [40]) ]

Output: documents 1 and 4
Explanation: age at least 18 and below 40. Document 1 (25) and document 4 (30) qualify;
document 2 (17) is too young; document 3 (40) is not below 40.

Example 2 ($in)

Conditions: [ (plan, $in, [1, 2]) ]

Output: documents 1, 2, 3
Explanation: plan is one of 1 or 2. Documents 1, 2, and 3 match; document 4 has no plan field,
so $in fails.

Example 3 ($ne against a missing field)

Conditions: [ (plan, $ne, [2]) ]

Output: documents 2 and 4
Explanation: plan not equal to 2. Document 2 (plan 1) matches. Document 4 has no plan at all,
and a missing value is "not equal" to anything, so it matches too. Documents 1 and 3 have plan 2 and fail.

Solution - Part 2

The shape is the same, one pass over the documents, but each condition now carries an operator. Pull the operator apart and dispatch on it: $eq and $ne compare for equality, $gt / $gte / $lt / $lte compare order, and $in tests membership in the operand list. The one subtlety, and the thing an interviewer is watching for, is the missing field. Check it first: if the document does not have the field, every operator fails except $ne. Getting that single rule right is what separates a careful matcher from a naive one.

conditions: [ (plan, $ne, [2]) ]

  document 1   plan = 2    ->  2 != 2 is false             ->  no match
  document 2   plan = 1    ->  1 != 2 is true              ->  match
  document 3   plan = 2    ->  2 != 2 is false             ->  no match
  document 4   (no plan)   ->  field missing, op is $ne    ->  match   (absent is "not equal" to 2)

def matches(doc: dict, field: str, op: str, operands: list) -> bool:
    if field not in doc:
        return op == "$ne"            # a missing value is "not equal" to anything
    v = doc[field]
    if op == "$eq":  return v == operands[0]
    if op == "$ne":  return v != operands[0]
    if op == "$gt":  return v > operands[0]
    if op == "$gte": return v >= operands[0]
    if op == "$lt":  return v < operands[0]
    if op == "$lte": return v <= operands[0]
    if op == "$in":  return v in operands
    return False

def find_matches(docs: list, conditions: list) -> list:
    result = []
    for doc in docs:
        if all(matches(doc, field, op, operands) for field, op, operands in conditions):
            result.append(doc)
    return result

Complexity Analysis

Time Complexity: O(N · C), for N documents and C conditions (an $in also scans its operand list).
Space Complexity: O(1) beyond the matched documents you return.

Final Notes

We believe this problem, and close variations of it, come up in MongoDB's interviews, because it is the database's own read path in miniature. The same matching logic runs inside every find() and every $match aggregation stage. Naming that connection turns a clean coding answer into a "this person understands our database" answer.

A few things that turn a correct answer into a strong one:

1. State the two easy-to-miss rules up front. Before you code, say them out loud: a missing field is a miss, and an empty query matches everything. These are exactly the cases the hidden tests probe, and naming them signals you are thinking about correctness, not just the happy path.

2. Missing fields are where $ne gets interesting. Check presence before you compare. Every operator fails on an absent field except $ne, which matches it, because a value that is not there is not equal to anything. That is MongoDB's real behaviour, and it is the single most common thing to get wrong here.

3. One field, several conditions, is a range. age $gte 18 and age $lt 65 together mean "18 to 64." Because the conditions are an implicit AND, you need no special range handling: the same per-condition loop just works, which is a nice thing to point out.

4. Know that a real database does not scan. Your matcher walks every document, which is right for the interview, but say the next sentence anyway: in production MongoDB uses an index to jump straight to the candidate documents instead of scanning the whole collection, and the matcher then runs only on those. Mentioning you would index the queried fields shows you know where this goes at scale.

The bottom line: a small, database-native problem with two sharp edges, the missing-field rule and the empty-query case. Handle the documents in one clean pass, check presence before you compare, and connect it to find() and indexing out loud. That is the everyday matching logic MongoDB runs billions of times a day.