Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
How to Implement Reverse DNS Look Up Cache?
3.
Approach
4.
Explanation of some of the important functions:
4.1.
Creating the Trie and adding new nodes.
4.2.
Inserting the IP addresses and their URLs in our DNS cache.
4.3.
Searching for a specific IP address in our DNS cache and returning the URL.
5.
 
6.
 
7.
 
8.
 
9.
 
10.
 
11.
 
12.
C++ implementation of Reverse DNS Look Up Cache
13.
OUTPUT
14.
 
15.
Complexities
15.1.
Time Complexity
15.2.
Space Complexity
16.
Frequently Asked Questions
17.
Key Takeaways
Last Updated: Mar 27, 2024

Implement Reverse DNS Look Up Cache

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

I am sure many of you must have heard of the term IP address and wonder what it is? It is a set of numbers separated by dots in a specific format that helps you connect to a website. IP address stands for Internet Protocol address. When we type an IP address in our browser and press enter, we go to the corresponding website. For example, if we type 74.125.200.106 in our browser and hit enter, we will be automatically taken to google.in. This is no magic at all; in fact, we are simply searching for our IP in the DNS cache and returning the corresponding URL. This technique where we enter an IP address and get the URL is known as Reverse DNS look up. 

 

Now you might wonder what the term DNS cache means. It is a sort of storage where the IP addresses of various domains and their URLs are stored so that we can search for an IP address and get the URL.

 

This article covers the topic of how to Implement Reverse DNS Look Up Cache; if you want, you can check how to Implement Forward DNS Look Up Cache here

 

How to Implement Reverse DNS Look Up Cache?

In this article, we are going to discuss how to implement Reverse DNS Look Up Cache. As explained earlier, the process of searching for a URL by inputting an IP address is known as Reverse DNS Look Up. Similar to what we did in the Forward DNS Look Up blog, we will store the IP addresses and their corresponding URLs in Tries. In our code, we store the URLs at the leaf nodes of corresponding IP addresses; thus, to get a URL, we simply traverse the Trie and search for the IP address and return the URL if it is present.

 

Either Hashmaps or Tries can do the task of storing the IP addresses and URLs. The solution in this article is done using Tries because the worst-case upper bound for a Trie is O(1), while for hashmaps,the best possible  average case complexity is O(1). The only drawback of Tries is the space complexity as it takes up a considerable amount of space. 

 

Prerequisite: The implementation in this article is done with the help of Tries Data Structure. It is highly recommended to study Tries before proceeding. You can do so by reading this highly informative blog: Using Trie in Data Structures.

 

Hopefully, you are now well-versed with Tries; if not, please go through the recommended blog once more. Let’s now proceed to the main topic - how to implement Reverse DNS look up cache. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach

According to our problem, we have to perform two primary operations:

  1. Create a DNS cache by storing the IP addresses along with their URLs.
  2. Try to get the URL of a site by entering and searching the IP address.

 

Generally, an IP address consists of numbers [0 to 9] separated by dots. This makes things easier because the nodes of our Trie will consist of a combination of 11 characters only - [0 to 9] and dot (‘.’).  The approach in this article creates a Trie that stores the IP addresses as nodes and their corresponding URLs as the leaf node. So without any further ado, let’s hop into our solution of how to implement Reverse DNS Look Up cache. 

Explanation of some of the important functions:

Creating the Trie and adding new nodes.

We create a struct named ‘trieNode’ which will be our Trie for DNS cache.

struct Trie
{
    bool isLeaf;
    char *URL;
    struct Trie* child[CHARS];
};

 

We first update a leaf node as a non-leaf node for adding a new node and then add the new node. This operation is shown in the code snippet below:

struct Trie* newNode(void)
{
    struct Trie* newNode = new Trie;
    newNode->isLeaf = false;
    newNode->URL = NULL;
    for (int i=0; i<CHARS; i++)
        newNode->child[i] = NULL;
    return newNode;
}

Inserting the IP addresses and their URLs in our DNS cache.

 

This function takes the root node, the char array of IP addresses, and the char array of URLs as function arguments. The main use of this function is to insert an IP address and the corresponding URL in the Trie. The last node in the Trie contains the URL. 

void insert(struct Trie* root, char *ipAdd, char *URL)
{
    int len = strlen(ipAdd);
    struct Trie* pCrawl = root;

    for (int level=0; level<len; level++)
    {
        int index = getIndex(ipAdd[level]);

        if (!pCrawl->child[index])
            pCrawl->child[index] = newNode();

        pCrawl = pCrawl->child[index];
    }

    pCrawl->isLeaf = true;
    pCrawl->URL = new char[strlen(URL) + 1];
    strcpy(pCrawl->URL, URL);
}

 

Searching for a specific IP address in our DNS cache and returning the URL.

 

This function takes the root node and the IP address that has to be found in the DNS cache as function arguments. It returns the URL of that IP address; thus, it has the return type as char. We perform a simple search operation in our Trie to find the given IP address in our DNS cache. If found, we return the corresponding URL; else, we return NULL. The below-mentioned code snippet shows the searchDNSCache() function.

char* searchDNSCache(struct Trie* root, char *ipAdd)
{

    struct Trie* pCrawl = root;
    int  len = strlen(ipAdd);

    for (int level=0; level<len; level++)
    {
        int index = getIndex(ipAdd[level]);
        if (!pCrawl->child[index])
            return NULL;
        pCrawl = pCrawl->child[index];
    }
 
    if (pCrawl!=NULL && pCrawl->isLeaf)
        return pCrawl->URL;
 
    return NULL;
}

 

 

 

 

 

 

 

C++ implementation of Reverse DNS Look Up Cache

 

// C based program on how to implement reverse DNS lookup cache
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define CHARS 11
#define MAX 50

int getIndex(char c) { return (c == '.')? 10: (c - '0'); }
 
char getCharFromIndex(int i) { return (i== 10)? '.' : ('0' + i); }
 
struct Trie
{
    bool isLeaf;
    char *URL;
    struct Trie* child[CHARS];
};

struct Trie* newNode(void)
{
    struct Trie* newNode = new Trie;
    newNode->isLeaf = false;
    newNode->URL = NULL;
    for (int i=0; i<CHARS; i++)
        newNode->child[i] = NULL;
    return newNode;
}

void insert(struct Trie* root, char *ipAdd, char *URL)
{
    int len = strlen(ipAdd);
    struct Trie* pCrawl = root;

    for (int level=0; level<len; level++)
    {
        int index = getIndex(ipAdd[level]);

        if (!pCrawl->child[index])
            pCrawl->child[index] = newNode();

        pCrawl = pCrawl->child[index];
    }

    pCrawl->isLeaf = true;
    pCrawl->URL = new char[strlen(URL) + 1];
    strcpy(pCrawl->URL, URL);
}
 
char* searchDNSCache(struct Trie* root, char *ipAdd)
{

    struct Trie* pCrawl = root;
    int  len = strlen(ipAdd);

    for (int level=0; level<len; level++)
    {
        int index = getIndex(ipAdd[level]);
        if (!pCrawl->child[index])
            return NULL;
        pCrawl = pCrawl->child[index];
    }
 
    if (pCrawl!=NULL && pCrawl->isLeaf)
        return pCrawl->URL;
 
    return NULL;
}
 
int main()
{
    char ipAdd[][MAX] = { "172.217.166.68", "157.240.218.35", "78.155.223.109", "150.99.125.46"};
    char URL[][50] = { "www.google.com", "www.facebook.com", "www.youtube.com", "www.yahoo.com"};
    int n = sizeof(ipAdd)/sizeof(ipAdd[0]);
    struct Trie* root = newNode();

    for (int i=0; i<n; i++)
        insert(root,ipAdd[i],URL[i]);

    char ip1[] = "157.240.218.35";
    char *res_url1 = searchDNSCache(root, ip1);
    printf(" Performing Reverse look up in the DNS cache ...\n");
    if (res_url1 != NULL)
        printf(" Reverse DNS look up cache Successful ! \n IP address: %s --> Hostname: %s", ip1, res_url1);
    else
        printf("Reverse DNS look up cache unsuccessful ! IP address not present in DNS cache");
        
    printf("\n\n");
    
char ip2[] = "198.166.74.152";
    char *res_url2 = searchDNSCache(root, ip2);
    printf(" Performing Reverse look up in the DNS cache ...\n");
    if (res_url2 != NULL)
        printf(" Reverse DNS look up cache Successful ! \n IP address: %s --> Hostname: %s", ip2, res_url2);
    else
        printf(" Reverse DNS look up cache unsuccessful ! IP address not present in DNS cache");
        
    return 0;
}

 

OUTPUT

In the above code, we search for two IP addresses in our DNS cache. The one which exists gave us the proper URL corresponding to that IP address. The other IP address, which was not present in our DNS cache, gave an appropriate error message.

 

Performing Reverse look up in the DNS cache ...
Reverse DNS look up cache Successful !
IP address: 157.240.218.35 --> Hostname: www.facebook.com

Performing Reverse look up in the DNS cache ...
Reverse DNS look up cache unsuccessful ! IP address not present in DNS cache

 

 

Complexities

Time Complexity

In the above implementation, we use Tries to store the IP addresses and their corresponding URLs. To do so we traverse the whole IP address once. Thus time complexity is:

T(n) = O(n),

where n is the length of the IP address to be inserted.

Space Complexity

In the above implementation, we store all the IP addresses and their corresponding URLs in Tries. Thus, 

Space complexity = O(RN),

 where R is the number of entries and N is the number of characters

Check out this problem - Longest Common Prefix

Frequently Asked Questions

 

Q1.) What do you mean by DNS look up cache? 

Ans.) When we search for a URL by typing its IP address or vice-versa in a DNS cache, it is known as DNS look up cache. It is of two types - Forward look up and Reverse look up. This article is primarily concerned with how to Implement Reverse DNS Look Up Cache. 

 

Key Takeaways

This article covers many aspects related to DNS caching. To summarize, we have learned about DNS caching in brief and how to Implement Reverse DNS Look Up Cache with the help of suitable explanations and code snippets.  

 

Confident enough about tries? Click here Implement Trie to go to our Coding Ninjas Studio and test out your knowledge on Tries.

 

Want to know more about URLs? Check out this blog: URI Vs URL: Most Important Differences You Must Know

 

Previous article
Implement Forward DNS Look Up Cache
Next article
Longest Common Prefix Matching
Live masterclass