Hashing.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "d735073d",
   "metadata": {},
   "source": [
    "# Hashing\n",
    "\n",
    "Hashing is a technique or process of mapping keys, and values into the hash table by using a hash function. It is done for faster access to elements. The efficiency of mapping depends on the efficiency of the hash function used.\n",
    "\n",
    "* Search\n",
    "* Insert\n",
    "* Delete\n",
    "> All operations are done in O(1) on average in hashing\n",
    "\n",
    "*Not Useful for*\n",
    "1. Finding closest value (AVL Tree Data Structure used)\n",
    "2. Sorted Data (AVL Tree Data Structure used)\n",
    "3. Prefix Searching (Trie Data Structure used )\n",
    "\n",
    "*Collision Handling*\n",
    "\n",
    "1. Chaining\n",
    "2. Open Addressing \n",
    "    1. Linear Probing\n",
    "        \n",
    "    2. Quadratic Probing\n",
    "    3. Double Hashing\n",
    "    \n",
    "    \n",
    "**Problems**\n",
    "\n",
    "#### Make the below links workable?? [Click Me](https://nbviewer.org/github/ChandrashekharRobbi/GFG-DSA/blob/main/Hashing.ipynb?flush_cache=true)\n",
    "\n",
    "1. [Frequencies of Array Elements](#Frequencies-of-Array-Elements)\n",
    "2. [Implementation of Chaining](#Implementation-of-Chaining)\n",
    "3. [Hashing for pair - 1](#Hashing-for-pair---1)\n",
    "4. [Hashing for pair - 2](#Hashing-for-pair---2)\n",
    "5. [Linear Probing in Hashing](#Linear-Probing-in-Hashing)\n",
    "6. [Implementation of Linear Probing](#Implementation-of-Linear-Probing)\n",
    "7. [Quadratic Probing in Hashing](#Quadratic-Probing-in-Hashing) \n",
    "8. [Separate chaining in Hashing](#Separate-chaining-in-Hashing)\n",
    "9. [Count Non-Repeated Elements](#Count-Non-Repeated-Elements)\n",
    "10. [Print Non-Repeated Elements](#Print-Non-Repeated-Elements)\n",
    "11. [Non Repeating Character](#Non-Repeating-Character)\n",
    "12. [Winner of an election](#Winner-of-an-election)\n",
    "13. [First Repeating Element](#First-Repeating-Element)\n",
    "1. [Intersection of Two Arrays](#Intersection-of-Two-Arrays)\n",
    "1. [count of dictinct elements ](#count-of-dictinct-elements-)\n",
    "1. [Number Containing 1,2,3](#Number-Containing-1,2,3)\n",
    "1. [Subarray with 0 sum](#Subarray-with-0-sum)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "5e09f375",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Note that after executing new function your next cell will automatically converted to markdown cell :)\n"
     ]
    }
   ],
   "source": [
    "%run imp_personal.py\n",
    "z = MyFunction()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e3379061",
   "metadata": {},
   "source": [
    "# Collision Handling"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a383257",
   "metadata": {},
   "source": [
    "## Chaining\n",
    "\n",
    "\n",
    "* It creates a link in the same index of an array"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "81a603d8",
   "metadata": {},
   "source": [
    "## Implementation of Chaining"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "e4eafc43",
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyHash:\n",
    "    def __init__(self,b):\n",
    "        self.BUCKET = b\n",
    "        self.table = [[] for x in range(b)]\n",
    "        \n",
    "    def hashFunction(self,x):\n",
    "        i = x % self.BUCKET\n",
    "        return i\n",
    "    \n",
    "    def insert(self, x):\n",
    "        i = self.hashFunction(x)\n",
    "        self.table[i].append(x)\n",
    "        print(self.table)\n",
    "        \n",
    "    def remove(self,x):\n",
    "        i = self.hashFunction(x)\n",
    "        \n",
    "        if x in self.table[i]:\n",
    "            self.table[i].remove(x)\n",
    "            print(self.table)\n",
    "        else:\n",
    "            print(\"Item is not present in Hash Table\")\n",
    "            \n",
    "    def search(self,x):\n",
    "        i = self.hashFunction(x)\n",
    "        return x in self.table[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "fa8db77a",
   "metadata": {},
   "outputs": [],
   "source": [
    "h = MyHash(7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "266218a5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[70], [], [], [], [], [], []]\n"
     ]
    }
   ],
   "source": [
    "h.insert(70)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "8136bc4c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[70], [71], [], [], [], [], []]\n"
     ]
    }
   ],
   "source": [
    "h.insert(71)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "02580bb5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[70], [71], [9], [], [], [], []]\n"
     ]
    }
   ],
   "source": [
    "h.insert(9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "3fec2397",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[70, 56], [71], [9], [], [], [], []]\n"
     ]
    }
   ],
   "source": [
    "h.insert(56)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "d6733360",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[70, 56], [71], [9, 72], [], [], [], []]\n"
     ]
    }
   ],
   "source": [
    "h.insert(72)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "cb3c4f1d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Item is not present in Hash Table\n"
     ]
    }
   ],
   "source": [
    "h.remove(23)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "f0da0a89",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[70], [71], [9, 72], [], [], [], []]\n"
     ]
    }
   ],
   "source": [
    "h.remove(56)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "583d3fe5",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "h.search(72)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "6a55e8e6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Item is not present in Hash Table\n"
     ]
    }
   ],
   "source": [
    "h.remove(56)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "ad83c8f7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[], [71], [9, 72], [], [], [], []]\n"
     ]
    }
   ],
   "source": [
    "h.remove(70)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "74c099f5",
   "metadata": {},
   "source": [
    "## Open Addressing\n",
    "\n",
    "* No. of slots in Hash Table >= No of values to be inserted in Hash Table\n",
    "* Cache Friendly"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "767f0c4d",
   "metadata": {},
   "source": [
    "### Linear Probing\n",
    "\n",
    "* Linearly search for next empty slots when there is a collision.\n",
    "```python\n",
    "hash(key) = key % 7\n",
    "hash(key,i) = ((hash(key) + i) % 7)\n",
    "```\n",
    "* Insert Operation:\n",
    "```bash\n",
    "if !collisionOccur:\n",
    "    append the number/item\n",
    "else:\n",
    "    linearly iterate index and append to next empty slot\n",
    "```\n",
    "* In search function we stop searching when one of the three cases occur\n",
    "    1. Empty SLots\n",
    "    2. Key Found\n",
    "    3. Once we have completed traversing the entire hash table.\n",
    "* In delete Operation\n",
    "    * After Deletion:\n",
    "        1. Simply making Slot Empty => which results to empty slots and when searching it will stop in empty slot and does not iterate further\n",
    "        \n",
    "        To reduce this problem we should mark deleted slots as `deleted`\n",
    "        \n",
    "**Problem With Linear Probing**\n",
    "\n",
    "\n",
    "    1. Clustering\n",
    "    \n",
    "To handle **Clustering problem with linear probing** we use \n",
    "\n",
    "\n",
    "1.  Quadratic Probing\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f674040f",
   "metadata": {},
   "source": [
    "## Implementation of Linear Probing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "74e5829c",
   "metadata": {},
   "outputs": [],
   "source": [
    "class MyHashLinearProbig:\n",
    "    def __init__(self, c):\n",
    "        self.cap = c\n",
    "        self.table = [-1]*c\n",
    "        self.size = 0\n",
    "        \n",
    "    def hash(self, x):\n",
    "        return x % self.cap\n",
    "    \n",
    "    def insert(self,key):\n",
    "        if self.size == self.cap:\n",
    "            return False           # when table is full\n",
    "        if self.search(key) == True:\n",
    "            return False    # when key is already present\n",
    "        t = self.table\n",
    "        i = self.hash(key)\n",
    "        while t[i] not in (-1,-2):\n",
    "            i = (i + 1) % self.cap\n",
    "        t[i] = key\n",
    "        self.size += 1\n",
    "        return True\n",
    "                \n",
    "    def search(self, key):\n",
    "        h = self.hash(key)\n",
    "        t = self.table\n",
    "        i = h\n",
    "        while t[i] != -1:\n",
    "            if t[i] == key:\n",
    "                return True     # key found\n",
    "            i = (i + 1) % self.cap\n",
    "            if i == h:\n",
    "                return False    # Traversed entire table\n",
    "        return False  # Empty Slot\n",
    "    \n",
    "    def remove(self,key):\n",
    "        h = self.hash(key)\n",
    "        t = self.table\n",
    "        i = h\n",
    "        while t[i] != 1:\n",
    "            if t[i] == key:\n",
    "                t[i] = -2        # we mark as deleted by inserting -2\n",
    "                return True\n",
    "            i = (i + 1) % self.cap\n",
    "            if i == h:\n",
    "                return False     # Traversed entire table\n",
    "        return False             # Key not found"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bef40a98",
   "metadata": {},
   "source": [
    "> Note : we can handle `-1` and `-2` numbers by replacing `None` and `dummy reference` respectively"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "95f7a397",
   "metadata": {},
   "outputs": [],
   "source": [
    "a = MyHashLinearProbig(7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "1944d0bd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.insert(49)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "103389f1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.insert(50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "07fa7eff",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.insert(51)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "3895cf5a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.search(50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "dbb5ec93",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.search(69)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "10fbdd1e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.remove(69)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "2449aa26",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.remove(50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "e237670c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.insert(123)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ad39dd6a",
   "metadata": {},
   "source": [
    "### Quadratic Probing\n",
    "\n",
    "*The function of quadratic probing will be* :  \n",
    "```python\n",
    "hash(key,i) = ((hash(key) + i**2) % m)\n",
    "```\n",
    "\n",
    "*Condition for quadratic probing to give best results*\n",
    "\n",
    "```python\n",
    "if loadFactor < 0.5 and m is prime:\n",
    "    then only quadratic probing will give good result\n",
    "else:\n",
    "    it can form Secondary Clustering\n",
    "```\n",
    "**Problems with Quadratic Probing**:\n",
    "1. Secondary Clustering\n",
    "\n",
    "To handle **Secondary Clustering problem with quadratic probing** we use \n",
    "\n",
    "\n",
    "Double Hashing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "7386be22",
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "class MyHashQuadraticProbing:\n",
    "    def __init__(self, c):\n",
    "        self.cap = c\n",
    "        self.table = [-1]*c\n",
    "        self.size = 0\n",
    "\n",
    "    def hash(self, x):\n",
    "        return x % self.cap\n",
    "\n",
    "    def insert(self,key):\n",
    "        if self.size == self.cap:\n",
    "            return False           # when table is full\n",
    "        if self.search(key) == True:\n",
    "            return False    # when key is already present\n",
    "        t = self.table\n",
    "        i = self.hash(key)\n",
    "        while t[i] not in (-1,-2):\n",
    "            i = (key + power**2) % self.cap\n",
    "            power += 1\n",
    "        t[i] = key\n",
    "        self.size += 1\n",
    "        return True\n",
    "\n",
    "    def search(self, key):\n",
    "        h = self.hash(key)\n",
    "        t = self.table\n",
    "        i = h\n",
    "        while t[i] != -1:\n",
    "            if t[i] == key:\n",
    "                return True     # key found\n",
    "            i = (key + power**2) % self.cap\n",
    "            power += 1\n",
    "            if i == h:\n",
    "                return False    # Traversed entire table\n",
    "        return False  # Empty Slot\n",
    "\n",
    "    def remove(self,key):\n",
    "        h = self.hash(key)\n",
    "        t = self.table\n",
    "        i = h\n",
    "        while t[i] != 1:\n",
    "            if t[i] == key:\n",
    "                t[i] = -2        # we mark as deleted by inserting -2\n",
    "                return True\n",
    "            i = (key + i**2) % self.cap\n",
    "            if i == h:\n",
    "                return False     # Traversed entire table\n",
    "        return False             # Key not found"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3f15960a",
   "metadata": {},
   "source": [
    "### Double Hashing\n",
    "\n",
    "1. Double Hashing is generalized version of Linear Probing\n",
    "\n",
    "2. *The function of double hashing will be* :  \n",
    "```python\n",
    "hash1(key) = key % m\n",
    "hash2(key) = (m-1) - (key % (m-1))\n",
    "hash(key,i) = ((hash1(key) + i*hash2(key)) % m)\n",
    "```\n",
    "3. If hash2(key) is relatively prime to m , then it always find a free slot if there is one.\n",
    "4. Distributes keys more uniformly than linear probing and quadratic probing\n",
    "5. It creates **No clustering**\n",
    "\n",
    "6. Agorithm for double hashing\n",
    "\n",
    "```python\n",
    "def DoubleHashing(table,key):\n",
    "    if table is full:\n",
    "        return error\n",
    "    probe = hash1(key)\n",
    "    offset = hash2(key) #in linear probing offset = 1\n",
    "    while (table[probe] is occupied):\n",
    "        probe = (probe + offset ) % m\n",
    "    table[probe] = key\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "873f45e4",
   "metadata": {},
   "source": [
    "# Problems"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "06921c20",
   "metadata": {},
   "source": [
    "## Frequencies of Array Elements"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "437ee997",
   "metadata": {},
   "outputs": [],
   "source": [
    "def FreqArrElementUsingHash(arr):\n",
    "    hash = {}\n",
    "    for i in arr:\n",
    "        if i not in hash.keys():\n",
    "            hash[i] = 1\n",
    "        else:\n",
    "            hash[i] += 1\n",
    "    for i in hash.keys():\n",
    "        print(i,hash[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "029e3df6",
   "metadata": {},
   "outputs": [],
   "source": [
    "arr1 = [10,12,10,15,10,20,12,12]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "6a646d3a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 3\n",
      "12 3\n",
      "15 1\n",
      "20 1\n"
     ]
    }
   ],
   "source": [
    "FreqArrElementUsingHash(arr1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "28cd070c",
   "metadata": {},
   "outputs": [],
   "source": [
    "arr2 = [10,10,10,10]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "27261f36",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 4\n"
     ]
    }
   ],
   "source": [
    "FreqArrElementUsingHash(arr2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "8c6c14c7",
   "metadata": {},
   "outputs": [],
   "source": [
    "arr3 = [10,20]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "817b9b87",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 1\n",
      "20 1\n"
     ]
    }
   ],
   "source": [
    "FreqArrElementUsingHash(arr3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7325ac38",
   "metadata": {},
   "source": [
    "## Hashing for pair - 1\n",
    "\n",
    "You are given an array of distinct integers and a sum. Check if there's a pair with the given sum in the array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "bb75db3d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sumExists(arr, N, sum):\n",
    "    #Your code here\n",
    "    for i in arr:\n",
    "        d = sum - i\n",
    "        if (d in arr) and (d != i):\n",
    "            return 1\n",
    "        \n",
    "    return 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2396f5e1",
   "metadata": {},
   "source": [
    "## Hashing for pair - 2\n",
    "\n",
    "You are given an array of integers and an integer sum. You need to find if two numbers in the array exists that have sum equal to the given sum."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "0b2699b6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sumExists(arr, N, sum):\n",
    "    #Your code here\n",
    "    hash = {}\n",
    "    for i in arr:\n",
    "        hash[i] = 1\n",
    "    for x in hash.keys():\n",
    "        d = sum - i\n",
    "        if (d in hash) and (d != x):\n",
    "            return 1\n",
    "    return 0"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e87cd718",
   "metadata": {},
   "source": [
    "## Linear Probing in Hashing\n",
    "\n",
    "Given an array of integers and a hash table size. Fill the array elements into a hash table using Linear Probing to handle collisions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "71034fd9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def linearProbing(self,hashSize, arr, sizeOfArray):\n",
    "        #Your code here\n",
    "        class MyHashLinearProing:\n",
    "            def __init__(self,c):\n",
    "                self.cap = c\n",
    "                self.table = [-1]*c\n",
    "                self.size = 0\n",
    "            def hash(self,key):\n",
    "                return key % self.cap\n",
    "            def search(self,key):\n",
    "                h = self.hash(key)\n",
    "                t = self.table\n",
    "                i = h\n",
    "                while t[i] != -1:\n",
    "                    if t[i] == key:\n",
    "                        return True\n",
    "                    i = (i + 1) % self.cap\n",
    "                    if i == h:\n",
    "                        return False\n",
    "                return False\n",
    "            def insert(self, key):\n",
    "                if self.size == self.cap:\n",
    "                    return False\n",
    "                if self.search(key) == True:\n",
    "                    return False\n",
    "                t = self.table\n",
    "                i = self.hash(key)\n",
    "                while t[i] not in (-1,-2):\n",
    "                    i = (i + 1) % self.cap\n",
    "                t[i] = key\n",
    "                self.size += 1\n",
    "                return True\n",
    "        m = MyHashLinearProing(hashSize)\n",
    "        for i in arr:\n",
    "            m.insert(i)\n",
    "        return m.table"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c1aa137a",
   "metadata": {},
   "source": [
    "## Quadratic Probing in Hashing\n",
    "\n",
    "Given an array of integers and a Hash table. Fill the elements of the array into the hash table by using Quadratic Probing in case of collisions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "b1bfce94",
   "metadata": {},
   "outputs": [],
   "source": [
    "def QuadraticProbing(self,hash, hashSize, arr, N):\n",
    "        #Your code here\n",
    "        class MyHashQuadraticProbing:\n",
    "            def __init__(self, c,hash):\n",
    "                self.cap = c\n",
    "                self.table = hash\n",
    "                self.size = 0\n",
    "                \n",
    "            def hash(self, x):\n",
    "                return x % self.cap\n",
    "            \n",
    "            def insert(self,key):\n",
    "                if self.size == self.cap:\n",
    "                    return False           # when table is full\n",
    "                if self.search(key) == True:\n",
    "                    return False    # when key is already present\n",
    "                t = self.table\n",
    "                i = self.hash(key)\n",
    "                power = 0\n",
    "                while t[i] not in (-1,-2):\n",
    "                    i = (key + power**2) % self.cap\n",
    "                    power += 1\n",
    "                t[i] = key\n",
    "                self.size += 1\n",
    "                return True\n",
    "                        \n",
    "            def search(self, key):\n",
    "                h = self.hash(key)\n",
    "                t = self.table\n",
    "                i = h\n",
    "                power = 0\n",
    "                while t[i] != -1:\n",
    "                    if t[i] == key:\n",
    "                        return True     # key found\n",
    "                    i = (key + power**2) % self.cap\n",
    "                    power += 1\n",
    "                    if i == h:\n",
    "                        return False    # Traversed entire table\n",
    "                return False  # Empty Slo\n",
    "            def final():\n",
    "                return self.table\n",
    "                   # Key not found\n",
    "        b = MyHashQuadraticProbing(hashSize, hash)\n",
    "        for i in arr:\n",
    "            b.insert(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "0a725c06",
   "metadata": {},
   "outputs": [],
   "source": [
    "def QuadraticProbing(self,hash, hashSize, arr, N):\n",
    "        #Your code here\n",
    "        for value in arr:\n",
    "            i = 0 \n",
    "            p = lambda x: (value + x**2) % hashSize\n",
    "            while hash[p(i)] not in [-1, value]: \n",
    "                i += 1\n",
    "            hash[p(i)] = value \n",
    "            \n",
    "        return hash"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3b5b749e",
   "metadata": {},
   "source": [
    "## Separate chaining in Hashing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "af47226e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def separateChaining(self, hashSize, arr, sizeOfArray):\n",
    "    #Your code here\n",
    "    #return hashtable\n",
    "    hash = [[] for x in range(hashSize)]\n",
    "    for value in arr:\n",
    "        i = value % hashSize\n",
    "        hash[i].append(value)\n",
    "    return hash"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "406405a7",
   "metadata": {},
   "source": [
    "## Count Non-Repeated Elements\n",
    "\n",
    "You are given an array of integers. You need to print the count of non-repeated elements in the array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "6964a9e3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def countNonRepeated(self,arr,n):\n",
    "    #Your code here\n",
    "    count = 0\n",
    "    hash = {}\n",
    "    for i in arr:\n",
    "        if i not in hash:\n",
    "            hash[i] = 1\n",
    "        else:\n",
    "            hash[i] += 1\n",
    "    for i in hash.keys():\n",
    "        if hash[i] == 1:\n",
    "            count += 1\n",
    "    return count"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3a04558a",
   "metadata": {},
   "source": [
    "## Print Non-Repeated Elements\n",
    "\n",
    "You are given an array of integers. You need to print the non-repeated elements as they appear in the array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "61419d6d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def printNonRepeated(self,arr,n):\n",
    "    #Your code here\n",
    "    hash = {}\n",
    "    lst = []\n",
    "    for i in arr:\n",
    "        if i not in hash:\n",
    "            hash[i] = 1\n",
    "        else:\n",
    "            hash[i] += 1\n",
    "\n",
    "    for x in arr:\n",
    "        if hash[x] == 1:\n",
    "            lst.append(x)\n",
    "    return lst"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a0247b78",
   "metadata": {},
   "source": [
    "## Non Repeating Character\n",
    "\n",
    "Given a string S consisting of lowercase Latin Letters. Return the first non-repeating character in S. If there is no non-repeating character, return '$'."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "4ac3656b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def nonrepeatingCharacter(self,s):\n",
    "    #code here\n",
    "    hash = {}\n",
    "    for i in s:\n",
    "        if i not in hash:\n",
    "            hash[i] = 1\n",
    "        else:\n",
    "            hash[i] += 1\n",
    "    for i in s:\n",
    "        if hash[i] == 1:\n",
    "            return i\n",
    "\n",
    "    return '$'"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bd329c49",
   "metadata": {},
   "source": [
    "## Winner of an election\n",
    "\n",
    "Given an array of names (consisting of lowercase characters) of candidates in an election. A candidate name in array represents a vote casted to the candidate. Print the name of candidate that received Max votes. If there is tie, print lexicographically smaller name."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "44a8dfc2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def winner(self,arr,n):\n",
    "    # Your code here\n",
    "    # return the name of the winning candidate and the votes he recieved\n",
    "    hash = {}\n",
    "    for i in arr:\n",
    "        if i not in hash:\n",
    "            hash[i] = 1\n",
    "        else:\n",
    "            hash[i] += 1\n",
    "    max_votes = max(hash.values())\n",
    "    max_arr = []\n",
    "    for x in hash.keys():\n",
    "        if hash[x] == max_votes:\n",
    "            max_arr.append(x)\n",
    "    max_arr.sort()\n",
    "    return max_arr[0], max_votes"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e632df0",
   "metadata": {},
   "source": [
    "## First Repeating Element\n",
    "\n",
    "Given an array arr[] of size n, find the first repeating element. The element should occur more than once and the index of its first occurrence should be the smallest."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "0f3b18e1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def firstRepeated(self,arr, n):\n",
    "\n",
    "    #arr : given array\n",
    "    #n : size of the array\n",
    "    hash = {}\n",
    "    repeat = -1\n",
    "    for i in arr:\n",
    "        if i not in hash:\n",
    "            hash[i] = 1\n",
    "        else:\n",
    "            hash[i] += 1\n",
    "\n",
    "    for i in range(n):\n",
    "        if hash[arr[i]] > 1:\n",
    "            repeat = i + 1\n",
    "            break\n",
    "    return repeat"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "71fa38b9",
   "metadata": {},
   "outputs": [],
   "source": [
    "def firstRepeated(self,arr,n):\n",
    "    repeat = -1\n",
    "    for i in range(n):\n",
    "        if arr.count(arr[i]) > 1:\n",
    "            repeat = i + 1\n",
    "            break\n",
    "    return repeat"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9e9ace28",
   "metadata": {},
   "source": [
    "## Intersection of Two Arrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "e539f705",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def NumberofElementsInIntersection(self,a, b, n, m):\n",
    "        #return: expected length of the intersection array.\n",
    "        values = set()\n",
    "        for i in a:\n",
    "            values.add(i)\n",
    "        count = 0\n",
    "        for i in b:\n",
    "            if i in values:\n",
    "                values.remove(i)\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cc83ce18",
   "metadata": {},
   "source": [
    "## count of dictinct elements "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "48603a6a",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:    \n",
    "    #Function to return the count of number of elements in union of two arrays.\n",
    "    def doUnion(self,a,n,b,m):\n",
    "        values = set()\n",
    "        for i in a:\n",
    "            values.add(i)\n",
    "        for j in b:\n",
    "            values.add(j)\n",
    "        return len(values)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7bba8fb0",
   "metadata": {},
   "source": [
    "## Number Containing 1,2,3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "4eb60bea",
   "metadata": {},
   "outputs": [],
   "source": [
    "#Function to find all the numbers with only 1,2 and 3 in their digits.\n",
    "def findAll():\n",
    "    #code here\n",
    "    set_num = {'1','2','3'}\n",
    "    for i in range(1,1000001):\n",
    "        s = set(str(i))\n",
    "        if s.issubset(set_num):\n",
    "            mp[i] = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f8b4c714",
   "metadata": {},
   "source": [
    "## Subarray with 0 sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "0d0578d0",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Naive Solution as it takes O(n^2) time complexity\n",
    "def subArrayExists(self,arr,n):\n",
    "    for i in range(n):\n",
    "        for j in range(i+1, n+1):\n",
    "            if sum(arr[i:j]) == 0:\n",
    "                return True\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "6322545c",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    \n",
    "    #Function to check whether there is a subarray present with 0-sum or not.\n",
    "    # we have used hashing to calculate prefix_sum as anything addition of zero is anything only.\n",
    "    def subArrayExists(self,arr,n):\n",
    "        h1 = set()\n",
    "        prefix_sum = 0\n",
    "        for i in range(n):\n",
    "            prefix_sum += arr[i]\n",
    "            if prefix_sum == 0 or prefix_sum in h1:\n",
    "                return True\n",
    "            h1.add(prefix_sum)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "64581f6b",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "990953f6",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}