The Linear Scan

Lets start off with something simple first – a brute-force Linear Scan.

Yes, it’s an O(n) disaster waiting to happen. Yes, if we ingest 10 million documents the server will catch fire. But Starting with a Linear Scan lets us define our API structure and understand the basic search flow before optimizing it with more advanced data structures.

Your Task

1. Ingest endpoint (POST /document/{id}): Read the flat text from the request body and store it in memory. A simple map of Document ID -> Text is ideal here. If a document with the same {id} already exists, simply overwrite the old text with the new text. Return 201 Created.

   For example, we will use the following three text files. We will use their filenames as the Document IDs:

   red_apple.txt     -> The red apple is a sweet apple.
   green_apple.txt   -> The Green Apple is sour!
   rolling.txt       -> The red apples are rolling.
   

2. Search endpoint (GET /search?q={term}&limit={k}): When a query comes in, loop through every single document in memory. Check if the query string is a substring of the document text. Return a comma-separated list of the Document IDs that matched (e.g., red_apple.txt,rolling.txt). If the number of matches exceeds {k}, truncate the list to length {k}. Return 200 OK.

3. Reset endpoint (DELETE /index): When called, simply clear the in-memory map/array. This ensures that the automated evaluation suite can run tests repeatedly against a clean slate without stale data bleeding over. Return 200 OK.

Warning

Do not worry about lowercase, punctuation, or complex tokenization yet. If the document says Hello, World! and the query is world, it should not match (because of the lowercase w). Keep it strictly literal. Substring matching and basic array slicing for the limit is perfectly fine for this stage.

Important

Run the below docker command to test your solution.

docker run \
  --rm \
  --add-host host.docker.internal:host-gateway \
  codeberg.org/level0/buildit/search-engine:latest \
  --addr host.docker.internal:8080 \
  --until linear_scan