title: DNS look up, hash tables
body: <p>Below image is the final homework in our data structures course. </p>
  
  <p>The problem is to write a DNS lookup program that maps domains into their ip addresses using the registered domain name servers.  </p>
  
  <p>I have some ideas but I wonder if these are among the correct way of implementing this program.</p>
  
  <p>I thought I could make use of a hash table for registering domain name servers. Then <code>registerDNS</code>, and <code>deleteDNS</code> methods would be <strong>constant time</strong>.</p>
  
  <p>For registering URLs, again a hash table. But the thing bothering me here is they give a <code>vector&lt;string&gt; &amp;dnsChain</code>, which provides information about how to go to the DNS that holds the URL. </p>
  
  <p>Now <code>registerURL</code> and <code>deleteURL</code> are <strong>constant time</strong> too. But we are storing a vector in each cell of our hash table, which I believe increases <strong>space complexity</strong>.(What if you had a million URL, with a <code>dnsChain</code> with million elements in each cell?)</p>
  
  <p>For the <code>access</code> method, I believe we should lookup in DNS hash table to make sure that every DNS in  <code>dnsChain</code> of that URL are registered. That makes accessing <strong>O(N)</strong>, if  you have N domain name servers in the <code>dnsChain</code>. Is this acceptable?</p>
  
  <p>Also there is this merge method that merge two DNS. My idea is to use a vector in each cell of DNS hashtable. If we merge DNS2 to DNS1, then we can push DNS2 to the vector of DNS1, which implies DNS1 also contains DNS2.</p>
  
  <p>May the space complexity be reduced? Do we have to store <code>dnsChain</code> in each cell of URL hashtable?</p>
  
  <p>Do we have to traverse through each DNS in <code>dnsChain</code> to access a URL?(if 10^6 DNS to access a URL, wouldn't it be slow?)</p>
  
  <p>Or is there any other helper data structure or technique(trie, extendible hashing, BST) I can use in this case?</p>
  
  <p><img src="https://i.imgur.com/3jNbTOt.png" alt="dns manager"></p>