Title: How to Implement Reverse DNS Look Up Cache? Source: www.geeksforgeeks.org
Reverse DNS look up is using an internet IP address to find a domain name. For example, if you type 74.125.200.106 in browser, it automatically redirects to google.in.
How to implement Reverse DNS Look Up cache? Following are the operations needed from cache.
1) Add a IP address to URL Mapping in cache.
2) Find URL for a given IP address.
One solution is to use Hashing.
In this post, a Trie based solution is discussed. One advantage of Trie based solutions is, worst case upper bound is O(1) for Trie, for hashing, the best possible average case time complexity is O(1). Also, with Trie we can implement prefix search (finding all urls for a common prefix of IP addresses).
The general disadvantage of Trie is large amount of memory requirement, this is not a major problem here as the alphabet size is only 11 here. Ten characters are needed for digits from ‘0’ to ‘9’ and one for dot (‘.’).
The idea is to store IP addresses in Trie nodes and in the last node we store the corresponding domain name.
Java solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
/* http://www.geeksforgeeks.org/implement-reverse-dns-look-cache/ */ import java.util.HashMap; import java.util.Map; public class ReverseDNSLookup { public void insert(TrieNode node, String[] ipAdd, String[] urls) { for(int i=0;i<ipAdd.length;i++) this.insertUtil(node, ipAdd[i], urls[i], 0); } public void insertUtil(TrieNode node, String ipAddr, String url, int pos) { TrieNode temp = null; if(node.child.containsKey(ipAddr.charAt(pos))) { temp = node.child.get(ipAddr.charAt(pos)); } else { temp = new TrieNode(); node.child.put(ipAddr.charAt(pos), temp); } if(pos==ipAddr.length()-1) { temp.url = url; return; } this.insertUtil(temp, ipAddr, url, pos+1); } public String search(TrieNode node, String ipAddr, int pos) { TrieNode temp = null; if(pos==ipAddr.length()-1) { temp = node.child.get(ipAddr.charAt(pos)); if(temp!=null) return temp.url; } if(node.child.containsKey(ipAddr.charAt(pos))) { temp = node.child.get(ipAddr.charAt(pos)); return this.search(temp, ipAddr, pos+1); } return "No url associated/Invalid IP address"; } public static void main(String []args) { ReverseDNSLookup r = new ReverseDNSLookup(); String[] ipAdd = {"107.108.11.123", "107.109.123.255", "74.125.200.106"}; String[] urls = {"www.samsung.com", "www.samsung.net", "www.google.in"}; TrieNode root = new TrieNode(); r.insert(root, ipAdd, urls); //System.out.println(root); System.out.println("74.125.200.106 : "+ r.search(root, "74.125.200.106", 0)); System.out.println("107.109.123.245 : "+ r.search(root, "107.109.123.245", 0)); } } class TrieNode { Map<Character, TrieNode> child; String url; TrieNode() { this.child = new HashMap<>(); } public String toString() { return child.toString()+" : "+url; } } |