Implement a firewall class (e.g., IpFirewall) that is initialized with an ordered list of rules, where each rule is a pair of [action, cidr]. The action is either "ALLOW" or "DENY". The CIDR can be a plain IP address (e.g., "1.2.3.4") or a network CIDR block (e.g., "192.168.0.0/16"). A CIDR block IP/N means the first N bits of the IP are fixed (network portion) and the remaining 32-N bits are the host portion.
Implement allowAccess(String ip): returns true if the given IP is allowed by the first rule it matches; returns false if it matches a DENY rule first. It is guaranteed the IP matches at least one rule. Rules are evaluated in priority order — later rules do not override earlier matches.
Follow-up: Change allowAccess so that the parameter is a CIDR block instead of a single IP. For the CIDR input to be ALLOWED, every IP in the input range must be covered by an ALLOW rule (no part of the range may be covered by a DENY rule). This requires checking range intersection rather than simple point membership.
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 to handle large volumes of firewall log queries?
| Approach | Notes |
|---|---|
| Trie (binary prefix tree) | Build a binary trie over the 32 bits of each rule IP; lookup is O(32) = O(1) per query regardless of number of rules, vs O(N*32) linear scan. However, storing rule priority order in a trie is complex, and implementing a trie correctly under interview time pressure is difficult; interviewers have debated whether this is actually better given the need to preserve rule ordering. |
| Convert to integer range / interval tree | Each CIDR maps to a contiguous integer range [start, end]. For the follow-up, this makes the problem a standard interval intersection/coverage problem (similar to LeetCode 'Range Module'). Cleanly handles CIDR-vs-CIDR matching but requires careful conversion from CIDR notation to integer ranges. |
| Brute force enumeration (follow-up only) | For the follow-up, enumerate every IP in the query CIDR and check it individually. Correct but exponentially expensive for large prefix lengths (e.g., /8 = 16 million IPs); interviewers expect candidates to identify this inefficiency and propose the interval approach. |
Common mistakes: Bit-operator precedence bugs: forgetting to parenthesize expressions like (1 << N) - 1 or mixing up shift and comparison precedence, leading to incorrect masks and long debugging sessions.; Not finishing the base problem fast enough, leaving no time for the follow-up — the follow-up is expected to at least be discussed.; Proposing brute-force enumeration of every IP in a CIDR range for the follow-up without pivoting to an interval/range approach when prompted.; Solving the problem correctly but failing to explain the reasoning behind each step, which interviewers flagged as insufficient code clarity.; Not recognizing that the CIDR follow-up requires processing rules strictly in order (not just checking if the union of ALLOW rules covers the range), because a DENY appearing before an ALLOW on an overlapping portion must immediately return false.
Interviewer hints: Interviewers typically explain what CIDR means and walk through an example before asking the candidate to start coding, to ensure the concept is understood.; When a candidate proposes brute-force enumeration of all IPs for the CIDR follow-up, the interviewer asks whether there is a more efficient data structure or approach for range checking.; If time runs out before the candidate can write full code for the follow-up, the interviewer will accept pseudocode for the overlap/matching condition.; The interviewer asks the candidate to explain specific sections of code and the reasoning behind them during or after writing — not just at the end.
What passers do: Finishing the base IP-matching problem quickly and cleanly, leaving time to discuss the CIDR follow-up even if only at the pseudocode or high-level level.; Converting CIDRs to integer intervals and framing the follow-up as an interval-coverage problem (similar to Range Module), rather than trying to enumerate individual IPs.; Explaining the bit-masking logic clearly while writing it — candidates who coded correctly but did not narrate their reasoning were flagged for poor code explanation even when tests passed.; Verifying understanding of CIDR before starting to code; good interviewers explicitly confirm the candidate grasps the concept, and candidates who asked clarifying questions or worked through examples were treated well.
Why people fail: Writing slowly, debugging for a long time, and not reaching the follow-up at all; Completing the code but being unable to explain the bitwise logic clearly; For the follow-up, only proposing brute-force enumeration without recognizing the interval approach; Not writing tests or writing tests that miss boundary conditions; Missing the follow-up entirely due to time spent on base problem; Misunderstanding the follow-up semantics (e.g., requiring only partial coverage instead of full coverage for ALLOW)
Edge cases probed: IP exactly on the boundary of a CIDR range (first or last address in range); Overlapping CIDR rules — later rule should NOT override earlier match (first-match-wins semantics); Plain IP rule with no prefix notation (effectively /32); CIDR with prefix /0 (matches all IPs); CIDR with prefix /32 (matches exactly one IP); Two's complement / signed integer overflow issues when creating bitmasks (e.g., 1 << 32 in Java/Python); Operator precedence in bitwise expressions causing subtle bugs; Query CIDR that partially overlaps an ALLOW rule and partially overlaps a DENY rule; Query CIDR that is fully covered by multiple non-contiguous ALLOW rules; Empty or no-match scenario (problem states guaranteed match, but interviewers probed for awareness)
What you just read — canonical solution, follow-up arc, what passing candidates actually did — exists for all 57 Databricks questions, refreshed monthly from new candidate reports.