Question:

Given an input table with IP address ranges and cities, return the city that falls within the IP range.

Ex:
1.0.0.1, 1.0.0.10 LA
5.0.0.255, 7.0.1.0 NY
200.0.0.0 210.1.2.3 DC

• We skipped the parsing of input (e.g string to int conversions, etc). Interviewer just wanted to know how I would store it, not how I would build the table.

1. I was initially thinking of using a bitwise mask. Was overthinking it and wasted time there. Iterviewer gave me a hint saying to consider the IP address as an int. E.g. '1.2.3.4' -> (4x255^1) + (3x255^2) + (2x255^3) + (2x255^4). With this, it becomes a problem of indexing our table.

2. I stored the ip addresses into a pair within a pair. e.g:

   std::pair<std::pair<int,int>,std:;string> //first int -> lower bound, second int -> upper bound, string -> city name

3. I then placed this within a set (so we sort by lower bound), so we can call std::lower_bound to get the iterator to the lower bound that is less than the target IP value.

    auto low = std::lower_bound(table.begin(), table.end(), target_ip_value); //returns iterator
    

4. Then compare lower bound, upper bound with target_ip_value, and if in range return the city name
   //psuedocode
   if(greater than lower bound, and less than upper bound)
   return (*it).second;

This solution gives O(n) for each input. So n inputs = O(n^2). I was struggling to think of a faster way.