Hash.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\"\n",
    "217. Contains Duplicate\n",
    "Given an array of integers, find if the array contains any duplicates.\n",
    "Your function should return true if any value appears at least twice in the array, \n",
    "and it should return false if every element is distinct.\n",
    "\n",
    "Input: [1,2,3,1]\n",
    "Output: true\n",
    "\"\"\"\n",
    "from typing import List\n",
    "def containsDuplicate(nums: List[int]) -> bool:\n",
    "    Hash = dict();\n",
    "    for val in nums:\n",
    "        if val in Hash:\n",
    "            Hash[val] = Hash[val] + 1\n",
    "            if Hash[val] > 1:\n",
    "                return True\n",
    "        else:\n",
    "            Hash[val] = 1\n",
    "    return False  \n",
    "\n",
    "containsDuplicate([1,2,3,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\"\n",
    "961. N-Repeated Element in Size 2N Array\n",
    "In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.\n",
    "Return the element repeated N times.\n",
    "\n",
    "Input: [1,2,3,3]\n",
    "Output: 3\n",
    "\"\"\"\n",
    "def repeatedNTimes(A: List[int]) -> int:\n",
    "    Hash = dict()\n",
    "    size = len(A)//2\n",
    "    for i in range(len(A)):\n",
    "        if A[i] in Hash:\n",
    "            Hash[A[i]] = Hash[A[i]] + 1\n",
    "        else :\n",
    "            Hash[A[i]]=1\n",
    "        if(Hash[A[i]] == size):\n",
    "            return A[i]\n",
    "repeatedNTimes([1,2,3,3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "242. Valid Anagram\n",
    "Given two strings s and t , write a function to determine if t is an anagram of s.\n",
    "\n",
    "Input: s = \"anagram\", t = \"nagaram\"\n",
    "Output: true\n",
    "\"\"\"\n",
    "def isAnagram(s: str, t: str) -> bool:\n",
    "    strs = [s,t] \n",
    "    AnaList  = []\n",
    "    for x in strs:\n",
    "        freq = [0]*26\n",
    "        for y in x:\n",
    "            freq[ord(y)-ord('a')] +=1\n",
    "        key = tuple(freq)\n",
    "        AnaList.append(key)\n",
    "    if(AnaList[0] == AnaList[1]):\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "print(isAnagram(\"anagram\",\"nagaram\"))\n",
    "print(isAnagram(\"rat\",\"car\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "http://tinyurl.com/01234\n",
      "https://leetcode.com/problems/design-tinyurl\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "535. Encode and Decode TinyURL\n",
    "\n",
    "Note: This is a companion problem to the System Design problem: Design TinyURL.\n",
    "\n",
    "TinyURL is a URL shortening service where you enter a URL such as \n",
    "https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk.\n",
    "\n",
    "Design the encode and decode methods for the TinyURL service. \n",
    "There is no restriction on how your encode/decode algorithm should work.\n",
    "You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.\n",
    "\"\"\"\n",
    "\n",
    "class Codec:\n",
    "\n",
    "    Hash = dict()\n",
    "\n",
    "    def encode(self, longUrl: str) -> str:\n",
    "        arr = longUrl.split(\"/\")\n",
    "#         print(arr)\n",
    "        url = \"\"\n",
    "        for x in range(0,len(arr)):\n",
    "#             print(x)\n",
    "            self.Hash[x] = arr[x]\n",
    "            url += str(x)\n",
    "        \n",
    "        return \"http://tinyurl.com/\"+url\n",
    "\n",
    "    def decode(self, shortUrl: str) -> str:\n",
    "        \"\"\"Decodes a shortened URL to its original URL.\n",
    "        \"\"\"\n",
    "#         print(shortUrl,self.Hash)\n",
    "        short = shortUrl.split('http://tinyurl.com/')\n",
    "        url = \"\"\n",
    "        for x in short[1]:\n",
    "            url += self.Hash[int(x)]\n",
    "            if(x!=short[1][-1]):\n",
    "                url+=\"/\"\n",
    "        \n",
    "        print(url)\n",
    "        return url\n",
    "        \n",
    "        \n",
    "\n",
    "codec = Codec()\n",
    "# codec.decode(codec.encode(\"https://leetcode.com/problems/design-tinyurl\"))\n",
    "encodedUrl = codec.encode(\"https://leetcode.com/problems/design-tinyurl\")\n",
    "print(encodedUrl)\n",
    "decodedUrl = codec.decode(encodedUrl)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}