Q3 - Is This URL Crawlable? (Reading robots.txt)

We believe a variation of this interview question has recently been asked by Google to software engineering candidates. It hands you a tool the whole company runs on, the crawler's robots.txt reader, and the real test is not a clever algorithm but discipline: parse a loosely specified real-world file, then get the matching rules exactly right, longest match wins, Allow breaks ties, wildcards, with just enough subtlety to catch anyone who skims.

Scenario: Before Googlebot fetches a URL, it has to obey the site's robots.txt. You are building the piece that answers one question: given a site's robots.txt, a crawler's user-agent, and a URL path, is the crawler allowed to fetch that path?

A robots.txt file is a list of groups. Each group names one or more crawlers with User-agent: lines, then lists Allow: and Disallow: rules, each holding a path pattern. A # begins a comment. For example:

User-agent: Googlebot
Disallow: /private/
Allow: /private/press/

User-agent: *
Disallow: /

To decide whether a crawler may fetch a path, you follow three steps:

Pick the group. If some group names the user-agent exactly (case-insensitive), use it. Otherwise use the * group, the catch-all. If there is no * group either, nothing restricts this crawler, so allow everything.
Find the most specific matching rule. Among the rules whose pattern matches the path, the one with the longest pattern wins. If an Allow and a Disallow tie on length, Allow wins.
If no rule matches, the path is allowed by default.

🧩 The spec has soft spots, so say your assumptions out loud. A real robots.txt prompt leaves gaps, and naming them is part of the job: how do you break an Allow/Disallow tie (we use "Allow wins")? Is user-agent matching exact or a prefix (we use exact, case-insensitive)? What does an empty Disallow: mean (it restricts nothing)? What is the default when no rule matches (allowed)? State the rule you are using and move; correctness on the rules you commit to is what is being graded.

Part 1: Parse the File and Decide

For Part 1 a pattern matches a path when it is a prefix of it, so Disallow: /private/ blocks /private/data and everything under it. Here is the behavior we are building, then the three steps that produce it.

Example: Part 1 (prefix matching)

robots.txt:
   # BigCorp crawl rules
   User-agent: Googlebot
   Disallow: /private/
   Allow: /private/press/
   Disallow: /tmp/

   User-agent: *
   Disallow: /

isAllowed(txt, "Googlebot",  "/private/data.html")     ->  false   (Disallow /private/)
isAllowed(txt, "Googlebot",  "/private/press/q3.html") ->  true    (Allow /private/press/ is longer)
isAllowed(txt, "Googlebot",  "/tmp/cache")             ->  false   (Disallow /tmp/)
isAllowed(txt, "Googlebot",  "/index.html")            ->  true    (no rule matches, so allowed)
isAllowed(txt, "ScraperBot", "/index.html")            ->  false   (not named, so * group: Disallow /)

Step 1: Parse the file into groups

One pass over the lines. Strip the # comment and trim, a User-agent: line sets the current crawler (lowercased), and every following Allow:/Disallow: line attaches a rule to it. We assume each crawler's rules sit together in one group, the common shape.

parse the file into  user-agent -> [ rules ] :

   "googlebot"  ->  [ Disallow /private/,  Allow /private/press/,  Disallow /tmp/ ]
   "*"          ->  [ Disallow / ]

Step 2: Pick the crawler's group

Match the user-agent exactly (case-insensitive). If no group names it, fall back to the * catch-all. If there is no * group either, nothing restricts this crawler, so everything is allowed.

pick the group for the incoming crawler:

   "Googlebot"   ->  exact match       ->  use the googlebot rules
   "ScraperBot"  ->  no exact match    ->  fall back to the "*" rules
   (no "*" group either  ->  allow everything)

Step 3: Keep the longest matching rule

Scan the chosen group. A rule applies when its pattern is a prefix of the path. Among the ones that apply, the longest pattern wins, and on a length tie Allow beats Disallow. Seed the answer with "allowed" so that if nothing matches, the path stays crawlable by default.

path = /private/press/q3.html

   Disallow /private/        prefix? yes  (len 9)   ->  best so far: BLOCK
   Allow    /private/press/  prefix? yes  (len 15)  ->  longer, best flips: ALLOW
   Disallow /tmp/            prefix? no             ->  skip
   verdict = ALLOW

Watch that scan run. Each rule is tested against the path, the longest prefix match is kept, and the running verdict updates until the winner is clear:

The Googlebot group rules and the path to test, with no match yet so the default verdict is allow

1 / 5

def parse(robots_txt):
    groups = {}                                 # user-agent -> list of (is_allow, pattern)
    agent = None
    for raw in robots_txt.split("\n"):
        line = raw.split("#", 1)[0].strip()     # drop the comment, trim
        if ":" not in line:
            continue
        field, value = (part.strip() for part in line.split(":", 1))
        field = field.lower()
        if field == "user-agent":
            agent = value.lower()
            groups.setdefault(agent, [])
        elif field in ("allow", "disallow") and agent is not None:
            groups[agent].append((field == "allow", value))
    return groups

def matches(pattern, path):
    return pattern != "" and path.startswith(pattern)   # a rule pattern is a path prefix

def is_allowed(robots_txt, user_agent, path):
    groups = parse(robots_txt)
    agent = user_agent.lower()
    rules = groups[agent] if agent in groups else groups.get("*", [])   # exact agent, else "*"
    best_length, best_allow = -1, True          # nothing matched -> allowed by default
    for is_allow, pattern in rules:
        if matches(pattern, path):
            # longest pattern wins; on a length tie, Allow beats Disallow
            if len(pattern) > best_length or (len(pattern) == best_length and is_allow):
                best_length, best_allow = len(pattern), is_allow
    return best_allow

⏱️ Heads up: Google builds these up one part at a time. You get the plain version working, then they hand you the wildcards. So keep the decision logic and the matches check in separate functions, because the next part changes only matches and leaves everything else alone.

Part 2: Wildcards

🎯 Good news first: get Part 1 working and clean, and you have basically passed this round already. Most people never even see Part 2. It only comes out if you blew through Part 1 with time to spare, and it is really there to tell a strong hire from a good one. So take the pressure off: you are playing with house money here. Even if all you do is talk through how you would handle * and $ before the clock runs out, you are in great shape.

Real robots.txt patterns are not plain prefixes. Two special characters show up:

* matches any run of characters (including none). So Disallow: /assets/*/tmp blocks /assets/img/tmp and /assets/anything/tmp.
A trailing $ anchors the pattern to the end of the path. So Disallow: /*.pdf$ blocks any path that ends in .pdf, but not /report.pdf?v=2.

Everything from Part 1, parsing, group selection, longest-pattern-wins, stays exactly the same. Only matches changes.

The new matches is three steps: split the pattern on *, anchor its first piece at the start of the path, then greedily find the rest while honoring a trailing $.

Example: Part 2 (wildcards * and $)

robots.txt:
   User-agent: Googlebot
   Disallow: /*.pdf$
   Disallow: /assets/*/tmp
   Allow: /assets/public/tmp

isAllowed(txt, "Googlebot", "/report.pdf")        ->  false   (ends in .pdf)
isAllowed(txt, "Googlebot", "/report.pdf?v=2")    ->  true    (does NOT end in .pdf, so $ fails)
isAllowed(txt, "Googlebot", "/assets/img/tmp")    ->  false   (/assets/*/tmp matches)
isAllowed(txt, "Googlebot", "/assets/public/tmp") ->  true    (the longer Allow wins)
isAllowed(txt, "Googlebot", "/home")              ->  true    (nothing matches)

Step 1: Peel the $, then split on *

A trailing $ means the match must reach the path's end, so note it and strip it off. Then split what remains on * into literal pieces. A * is just "anything can go here," so the pieces are what actually has to appear, in order.

/*.pdf$        ->  $ present (must reach the end),  split "/*.pdf"  ->  [ "/", ".pdf" ]
/assets/*/tmp  ->  no $,                            split          ->  [ "/assets/", "/tmp" ]

Step 2: Anchor the first piece at the start

The path must begin with the first piece, since there is no * before it. If it does not, the rule cannot match. If it does, remember where that piece ends and continue from there.

first piece "/assets/"  must start  "/assets/img/tmp"  ->  yes, continue from position 8

Step 3: Greedily find the rest, and honor $

Walk the remaining pieces left to right, finding each at the earliest spot after the previous one (* absorbs whatever sits in between, so leftmost is always safe). The last piece is special: with a trailing $ it must land exactly at the path's end; without one, finding it anywhere is enough, because a rule only has to match a prefix.

find "/tmp" in "/assets/img/tmp" from position 8   ->  found at the end   ->  match

with $, the last piece must end the path:
   ".pdf" ends "/report.pdf"      ->  yes  ->  match
   ".pdf" ends "/report.pdf?v=2"  ->  no   ->  no match  ($ fails)

Here is /*.pdf$ matched against a path, step by step, including the contrasting case where the $ makes it fail:

The pattern /*.pdf$ has its trailing $ stripped and is split on * into the segments slash and .pdf

1 / 4

# Part 2: swap in this matches; parse and is_allowed are unchanged.
def matches(pattern, path):
    if pattern == "":
        return False
    anchored_end = pattern.endswith("$")        # "$": the pattern must reach the path's end
    if anchored_end:
        pattern = pattern[:-1]
    # "/assets/*/tmp" -> ["/assets/", "/tmp"]
    segments = pattern.split("*")
    if not path.startswith(segments[0]):        # first piece is anchored at the start
        return False
    pos = len(segments[0])
    for i in range(1, len(segments)):
        segment = segments[i]
        if i == len(segments) - 1:              # last piece
            if segment == "":
                return True                     # pattern ended in "*": it soaks up the rest
            if anchored_end:
                return path.endswith(segment) and len(path) - len(segment) >= pos
            return path.find(segment, pos) != -1
        found = path.find(segment, pos)         # greedy: leftmost spot after the previous piece
        if found == -1:
            return False
        pos = found + len(segment)
    return path == segments[0] if anchored_end else True

Complexity Analysis

parse: O(F) for a robots.txt of F characters, one pass over the lines into a hash map keyed by user-agent.
matches: prefix matching is O(len(pattern)). The wildcard version is O(len(path) * pieces) in the worst case, since each literal piece is searched for inside the remaining path.
isAllowed: an O(1) group lookup, then O(total pattern length) to test every rule in that group and keep the longest match. This is comfortably fast; a robots.txt is small and read constantly, so a clean linear pass is exactly right.

Final Notes

We believe this robots.txt question, and close variations of it, have appeared in recent Google interviews for software engineers. It rewards the unglamorous half of the job: reading a fuzzy real-world format into a clean model, then implementing matching rules whose edge cases (longest match, tie-breaking, wildcards, defaults) are exactly where bugs hide.

Parsing is a short loop, not a state machine. Map each user-agent to its list of rules and attach every Allow/Disallow to the current agent; the rest is trimming and splitting. Sharing one rule block across several User-agent: lines is a clean extension to raise out loud.
Specificity is length, and Allow breaks ties. "Most specific rule wins" means the longest matching pattern, and a tie goes to Allow. Skimming past that one tie rule is the classic way to get /private/press/ wrong.
Default allow is the safety net. When nothing matches, the path is crawlable. Seeding your decision with "allowed" and only overriding it on a match keeps that rule from becoming a special case.
* and $ are all Part 2 adds. Split the pattern on *, anchor the first piece at the start, walk the rest greedily, and let a trailing $ force the last piece to the end. Because you kept matches separate, the parsing and the decision never had to change, which is the whole reason to structure it that way. This is the kind of small, exact string code a crawler actually ships. 🚀