class IpFirewall:
Databricks' CIDR firewall question, reported as a phone screen and as an onsite algorithm round. A firewall is an ordered list of rules. Each rule is an action, "ALLOW" or "DENY", and a CIDR block. A block a.b.c.d/N covers every IPv4 address whose first N bits (of 32) equal the first N bits of a.b.c.d; a rule can also be a plain IP such as "8.8.8.8", which covers that one address. One candidate quoted a firewall of DENY 255.0.0.8/29 and ALLOW 117.145.102.64/30; another gave the rules ("192.168.1.0/24" : "ALLOW"), ("8.8.8.8" : "DENY"), under which 192.168.1.5 is allowed.
Our setup — ask your interviewer. Reports name the API differently: a prep-site statement that one candidate said matched their question has a class whose allowAccess method takes the IP and returns a boolean, and another report has a function get_status that takes the rules and the IP and returns the status. The tests here call:
class IpFirewall:
def __init__(self, rules: list): ... # rules = [[action, cidr], ...] in priority order
def allow_access(self, ip: str): ... # Part 1
def allow_access_cidr(self, cidr: str): ... # Part 2 (or let allow_access take a CIDR)
Each answer may be True/False or 'ALLOW'/'DENY'; the tests accept both.
Part 1 — Single IP, first match wins
allow_access(ip) returns the action of the first rule, in list order, whose block contains ip. A later rule that overlaps an earlier one never overrides it. The prep-site statement guarantees that every queried IP matches some rule, and the Part 1 tests only query addresses that do. The tests build firewalls with IpFirewall(rules) and call allow_access(ip) with a dotted IPv4 string.
Not graded
get_status, taking the rules as (cidr, status) pairs and an IP, returning the status string of the first rule that matches.A CIDR stands for every address in it, so the block is allowed only if every address is allowed. One report describes walking the rules in order: if a rule is ALLOW and overlaps the query, remove the overlap; if a DENY overlaps the part not yet removed, return false; the block is allowed when nothing is left. Order matters because a DENY earlier in the list can fail a block that the ALLOW rules cover between them. One candidate proposed checking every address; the interviewer asked whether some data structure makes range checks easy, and the candidate passed without answering. Another candidate compared the follow-up to Range Module.
Standard explanation — no candidate report records what the interviewer accepted here.
Reports do not record an answer. Our list: the first and last address of a block and one past each end, overlapping rules in both orders, a plain-IP rule, /0 and /32, and the extreme addresses 0.0.0.0 and 255.255.255.255.
In one report the interviewer, short on time, asked for pseudocode for the follow-up and seemed satisfied. Two ranges [a, b] and [c, d] overlap when a <= d and c <= b; removing an ALLOW overlap from a piece leaves at most a left and a right remainder.
Standard explanation — no candidate report records what the interviewer accepted here.
No answer is recorded. Our analysis: a binary trie that stores the smallest rule index per node answers single-IP queries in O(32) while keeping first-match order; cache repeated lookups; shard queries across machines that each hold one copy of the rules.
Frequently reported: we count 34 threads, including two probable matches and one thin one. Reports place it in both screening and onsite algorithm rounds. Two of the 34 only say 'IP to CIDR' or describe a LeetCode-like bit-mask problem, so they probably, but not certainly, describe this round, and one more only names it as an 'IP to CIDR' variant. Some reports use the shorthand 'IP to CIDR', and one compares it with LeetCode 751.
In four reports, the interviewer explained CIDR and checked the candidate's understanding before coding. In one report the interviewer asked up front what data structure you would define; in another, the interviewer asked the candidate to explain several parts of the code and then write their own tests, followed by 'what other test cases would you write'. Test cases were provided in one report. One candidate passed every test but was rejected after getting one initialization line wrong; another, who needed time to debug, guessed the bar is bug-free from the start.
The CIDR-block follow-up comes up in about 13 threads; one poster says there was no follow-up and another was never asked it. Whether it must be coded varies: one poster says yes and to move fast on Part 1, one says explaining the approach out loud was enough, one interviewer settled for pseudocode, and one poster thinks it can be skipped and still pass. A commenter says their interviewer had never seen anyone write the follow-up. One poster says they solved it and were still failed. Another report describes the follow-up as the block having to satisfy every rule; that candidate expected to fail, but the outcome is not given. Other reported follow-ups: 'what other test cases would you write' and 'how would you scale it' (no answer recorded).
Databricks' CIDR firewall question, reported as a phone screen and as an onsite algorithm round. A firewall is an ordered list of rules. Each rule is an action, "ALLOW" or "DENY", and a CIDR block. A block a.b.c.d/N covers every IPv4 address whose first N bits (of 32) equal the first N bits of a.b.c.d; a rule can also be a plain IP such as "8.8.8.8", which covers that one address. One candidate quoted a firewall of DENY 255.0.0.8/29 and ALLOW 117.145.102.64/30; another gave the rules ("192.168.1.0/24" : "ALLOW"), ("8.8.8.8" : "DENY"), under which 192.168.1.5 is allowed.
Our setup — ask your interviewer. Reports name the API differently: a prep-site statement that one candidate said matched their question has a class whose allowAccess method takes the IP and returns a boolean, and another report has a function get_status that takes the rules and the IP and returns the status. The tests here call:
class IpFirewall:
def __init__(self, rules: list): ... # rules = [[action, cidr], ...] in priority order
def allow_access(self, ip: str): ... # Part 1
def allow_access_cidr(self, cidr: str): ... # Part 2 (or let allow_access take a CIDR)
Each answer may be True/False or 'ALLOW'/'DENY'; the tests accept both.
Part 1 — Single IP, first match wins
allow_access(ip) returns the action of the first rule, in list order, whose block contains ip. A later rule that overlaps an earlier one never overrides it. The prep-site statement guarantees that every queried IP matches some rule, and the Part 1 tests only query addresses that do. The tests build firewalls with IpFirewall(rules) and call allow_access(ip) with a dotted IPv4 string.
Part 2 — CIDR query, whole block must be allowed
Reported in about 13 threads; sometimes discussed rather than coded. The query is now a CIDR block, and it is allowed only if every address in it is allowed. The rules are still taken in order: an address that no rule matches is not allowed, and a DENY rule only matters for the addresses that no earlier rule has already decided. So a block that the ALLOW rules cover between them is still denied when a DENY ahead of one of those ALLOW rules hits part of it. One report words the follow-up differently (the block must satisfy every rule); this page follows the in-order reading another report spells out, so ask your interviewer. Write allow_access_cidr(cidr), or make allow_access accept a CIDR as one report describes: the tests call allow_access_cidr if your class defines it and allow_access otherwise.
Checking every address one by one is the brute force: a block /N holds 2^(32−N) addresses. In one report the interviewer asked for a data structure that makes range checks easy; the two candidates who report proposing the brute force both still passed. The tests use small blocks and do not grade speed.
Not graded
get_status, taking the rules as (cidr, status) pairs and an IP, returning the status string of the first rule that matches.What if the query is a CIDR block instead of a single IP? When should it return ALLOW?
What test cases would you write for this?
Can you write pseudocode for the CIDR-vs-CIDR matching condition and the overlap check?
How would you scale this?
| Approach | Notes |
|---|---|
| Binary trie over rule prefixes | Forum commenters suggested a trie for O(32) lookups instead of an O(R) scan, and another asked how a trie keeps the rule order; nobody answered in the thread. Our analysis: store at each node the smallest index of a rule ending there and take the smallest index seen along the query's 32-bit path, which keeps first-match order. One commenter who tried a trie for the follow-up could not finish it. |
| Integer ranges with interval subtraction | Each CIDR is a contiguous integer range, so the follow-up becomes an interval problem. One candidate compared it to Range Module; a commenter calls it an ordinary interval problem with no segment tree needed. Worst case O(R^2) for R rules. |
| Brute force enumeration (follow-up only) | Apply the single-IP check to every address in the query block. It gives the same answers but costs 2^(32-N) lookups for a /N block, which is large for short prefixes (a /8 is about 16.7 million addresses). In one report the interviewer then asked for a data structure for range checks; the two candidates who report proposing it both passed. |
Common mistakes: Bit-operator precedence bugs, such as a missing pair of parentheses in (1 << N) - 1: one candidate wrote the solution quickly, then debugged for a long time over operator precedence.; Not finishing the base problem fast enough: one candidate whose tests passed had no time left for the follow-up and was rejected.; Proposing only brute-force enumeration for the follow-up: in one report the interviewer then asked for a data structure for range checks (that candidate still passed).; Code that passes but is not explained: one candidate got feedback that their explanation was not clear enough, was given an extra round, and passed it.; Checking only whether the ALLOW rules together cover the block: one report says the rules must be processed in order, because a DENY earlier in the list can make the answer false.; Signed comparisons (a reported implementation issue, not an edge case the interviewer probed): one report that probably describes this round blames 'the 2's complement thing' for comparisons that went wrong.
Interviewer hints: In four reports, the interviewer explained CIDR and checked the candidate's understanding with examples before coding.; In one report, after the candidate described brute-force enumeration for the follow-up, the interviewer asked whether some data structure makes range checks easy.; In one report, with time running short, the interviewer asked for pseudocode for the follow-up.; One interviewer asked the candidate to explain several parts of the code while they wrote it.
What passers do: Doing the base problem fast enough to reach the follow-up: one poster says the follow-up had to be implemented and to do the first part quickly.; Treating each CIDR as an integer range and the follow-up as an interval problem (one candidate compared it to Range Module).; Explaining the bit manipulation while writing it: one candidate whose explanation was called unclear passed an extra round after explaining carefully.; Making sure you understand CIDR before coding: in four reports the interviewer explained it and checked with examples first.
Why people fail: Writing slowly or debugging for long and not reaching the follow-up (two rejected reports); Going over time on the base problem even with passing tests: one algorithm round was failed and redone; Passing every test with one initialization line wrong: one candidate was rejected; Rusty bit masking: one candidate who failed the onsite says they did not do the CIDR question well
Edge cases probed: Overlapping rules: a later entry never overrides an earlier one (stated in one report's prompt); A plain IP as a rule, covering a single address (in two reports' examples); A query block that is partly allowed and partly denied (follow-up, one report); One interviewer kept asking about corner cases; the report does not list them
Send them this page. It is free to read, no account needed.
What you just read — canonical solution, follow-up arc, what passing candidates actually did — exists for all 34 Databricks questions, refreshed monthly from new candidate reports.