Hash Table Simplified

A very basic explanation of a Hash Table Data Structure

Let us consider the problem of storing a large number of words so that insertion and search operations can be performed in O (1) time complexity

If the words are stored in a simple array, then the operation will have time complexity of O (n) where n is the number of words.

We can solve the above problem by using a Hash Table data structure

What is a hash table?

A hash table is a set of key-value pairs where key is unique and a particular key cab hold a certain value.

A key is generated by a hash function.

For our example, let us consider that the hashing function works in the following manner:

1. The letters of the word are assigned a particular integer value. For example: a -> 1, b -> 2, c -> 3 and so on.

2. The integers corresponding to the letters present in a particular word are added.

3. This sum is taken as a key

4. Let us assume the number of keys formed in this way is k (which is constant). There is a catch* here which is discussed later. For now assume that the maximum number of possible keys is a constant k.

5. Let us also assume that the number of words corresponding to a single key is constant which equals to w on an average.

Now let us consider the following words and the corresponding sums which will be the keys.

Word	Sum which will be used as key
abc	6
ae	6
abcd	10
ade	10

  

Sample Hash Table storage:

Now to search for a word ade:

1. First the sum is determined which is O (1). Please note that the complexity of finding the sum for a given word having m letters is negligible compared to the complexity of finding a word in an array containing n such words.

2. Now this key can be searched in the key linked list in O(k) which in Big O notation boils down to O(1).

3. Once the key is determined, the word can be searched in O(w) which in Big O notation again boils down to O(1).

So the Search operation can be performed on such a data structure with time complexity of O (n).

Similarly for inserting a word acf:

1. First the sum is determined which is O (1). Please note that the complexity of finding the sum for a given word having m letters is negligible compared to the complexity of finding a word in an array containing n such words.

2. Now this key can be searched in the key linked list in O(k) which in Big O notation boils down to O(1).

3. Once the key is determined, the word can be inserted in O(w) which in Big O notation again boils down to O(1).

So the Insertion operation can be performed on such a data structure with time complexity of O (n).

*Catch: The choice of the hashing function needs to be made very carefully so as to maintain the following two criteria:

1. The number of unique keys generated by the hashing function should not become too high.

2. The number of words or entities needed to be stored in one linked list should not become too large.

Note: This is an attempt to explain the hash table data structure in a very simple terms. Actual implementations are much more complex and use details of the available memory storage.

References:
https://en.wikipedia.org/wiki/Hash_table

Interview Questions and their approach

1. Find if there is a loop in a single linked-list and if yes, remove it.
Approach-1: Take a slow and fast pointer and see if they ever meet.
Time Complexity: O(n)
Space Complexity: O(1)

Approach-2: Go on storing all the addresses and if a stored address is met.
Time Complexity: O(n)
Space Complexity: O(n)

Approach-3: Reverse the linked-list. And then again reverse the linked-list.
Time Complexity: O(n)
Space Complexity: O(1)

2. Given an array of integers, find the pair of integers that add up to a given number.
Approach-1: Store the integers in a hash-table and see if the difference is present in the hash-table.
Time Complexity: O(n)
Space Complexity: O(n)

Approach-2: Find all the possible pairs in the array.
Time Complexity: O(n-square)
Space Complexity: O(1)

Approach-3:
a) Sort all the numbers (Time: nlogn Space: O(1)).
b) At each element, search for the difference using binary search in the same array (Time: nlogn Space: O(1))
Total time-complexity: O(nlogn)

3. Given a single linked-list, find out if it is a palindrome or not.
Approach-1: Push half the nodes in a stack and traverse the rest of the linked-list, while popping the elements from the stack. At any point, if there is a mismatch, then it is not a palindrome.
Time Complexity: O(n)
Space Complexity: O(n)

Approach-2: Reach the mid element of the linked-list. And reverse the rest of the linked-list. Then traverse both the linked lists in parallel. At any point, if there is a mismatch, then it is not a palindrome.
Time Complexity: O(n)
Space Complexity: O(1)

4. Given a string S and a number n, rotate the string the given number of times.
Example input: S: abcdef, n: 2
Example output: efabcd

Approach-1: Start a loop at twice the given number from the end of the string. Swap the next n characters with the nth character from current position. Repeat this till the starting point reaches the beginning of the string.
Time Complexity: O(n)
Space Complexity: O(1)

Approach-2: Reverse the entire string. Then reverse the characters between 0 to n. And then reverse the characters between n+1 to length of string.
Time Complexity: O(n)
Space Complexity: O(1)  
  

Reverse the adjacent nodes in a linked list

Reverse the adjacent nodes of a linked list as described below in the sample input and output:
Input 1: 1->2->3->4->5
Output1: 2->1->4->3->5
Input2: 1->2->3->4->5->6
Output2: 2->1->4->3->6->5

#include<iostream>
#include<stdlib.h>
using namespace std;

struct node
{
    int data;
    struct node* next;
};

struct node* createlist(int length)
{
    struct node *root=NULL,*end=NULL;
    for(int i=1;i<=length;i++)
    {
        struct node* new_node = (struct node*)malloc(sizeof(struct node));
        new_node->data=i;
        new_node->next=NULL;
        if(i==1)
        {
            root=new_node;
            end=root;
        }
        else
        {
            end->next=new_node;
            end=new_node;
        }
    }
    return root;
}
struct node* reverseadjacent(struct node* root)
{
    int length=0;
    struct node *temp=root;
    while(temp!=NULL)
    {
        length++;
        temp=temp->next;
    }
    if(length<2)
    {
        return root;
    }
    struct node *first=root,*sec=first->next,*third=sec->next;
    root=first->next;
    if(length==2)
    {
        sec->next=first;
        first->next=NULL;
    }
    else if(length%2==0)
    {
        while(third!=NULL)
        {
            first->next=third->next;
            sec->next=first;
            first=third;
            sec=third->next;
            third=sec->next;
        }
        sec->next=first;
        first->next=NULL;
    }
    else
    {
        while(third->next!=NULL)
        {
            first->next=third->next;
            sec->next=first;
            first=third;
            sec=third->next;
            third=sec->next;
        }
        sec->next=first;
        first->next=third;
    }
    return root;
}
void printlist(struct node* root)
{
    struct node* temp=root;
    while(temp!=NULL)
    {
        cout<<temp->data<<"->";
        temp=temp->next;
    }
    cout<<endl;
}
int main()
{
    struct node* root=createlist(5);
    cout<<"The given list\n";
    printlist(root);
    struct node* new_root=reverseadjacent(root);
    cout<<"The new list\n";
    printlist(new_root);
}