Amazon Interview Question
SDE-2sCountry: India
I assume, when asked additional questions, the interviewer would ask to implement a logic where IP can appear in either a star form (10.0.0.*) or a CIDR form (10.0.0.0/8)
One of the possible solutions will involve creating a Trie data structure with the root pointing to all the possible numbers from 1 to 254. The entire trie will have 4 levels for each of the four 8 bit fields separated by the period.
The first time when we scan the list of blocked IP or the part of the IP, we create a node to the trie node based on the IP address sections appears in the block list.
When the request comes in with IP address information, if Trie matches either the entire 4 sections of the IP address or matches with * at the end, we block the IP.
One way can be to run a lightweight proxy on the load balancer that checks the source IP address against a local cache of blacklisted IP addresses which refreshes at fixed intervals asynchronously
- Rishi March 16, 2021