[Data Type] Dictionary Part One.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Python Dictionary Characteristics\n",
    "## 1. unordered\n",
    "## 2. changeable\n",
    "## 3. no duplicate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'brand': 'BMW', 'model': 'Model 3', 'year': 2000}\n"
     ]
    }
   ],
   "source": [
    "dictionary_1 = {\n",
    "    \"brand\":\"BMW\",\n",
    "    \"model\": \"Model 3\",\n",
    "    \"year\": 2000}\n",
    "\n",
    "print(dictionary_1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_keys(['brand', 'model', 'year'])"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 1. keys()\n",
    "dictionary_1.keys()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_values(['BMW', 'Model 3', 2000])"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#2. values()\n",
    "dictionary_1.values()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_items([('brand', 'BMW'), ('model', 'Model 3'), ('year', 2000)])"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#3. items()\n",
    "dictionary_1.items()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Question 1: Two Sum, by every tech company\n",
    "- Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.\n",
    "- You may assume that each input would have exactly one solution, and you may not use the same element twice.\n",
    "- You can return the answer in any order.\n",
    "- https://leetcode.com/problems/two-sum/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1]"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# solution 1: double for loops \n",
    "\n",
    "def two_sum(nums,target):\n",
    "    result = []\n",
    "    for i in range(len(nums)):\n",
    "        for j in range(i+1, len(nums)):\n",
    "            if i != j and nums[i]+nums[j]==target: \n",
    "                result.append(i)\n",
    "                result.append(j)\n",
    "    return result\n",
    "\n",
    "# test case \n",
    "nums = [2,7,11,15]\n",
    "target = 9\n",
    "two_sum(nums,target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 0]"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# solution 2: dictionary \n",
    "\n",
    "def two_sum (nums,target): \n",
    "    \n",
    "    dictionary = {}\n",
    "    \n",
    "    for index,value in enumerate(nums): \n",
    "        \n",
    "        diff = target - value \n",
    "        \n",
    "        if diff in dictionary:\n",
    "            return [index, dictionary[diff]]\n",
    "        else: \n",
    "            dictionary[value] = index\n",
    "\n",
    "    return \n",
    "\n",
    "# test case \n",
    "nums = [2,7,11,15]\n",
    "target = 9\n",
    "two_sum(nums,target)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Question 2: Unique Number of Occurrences, by Google\n",
    "- Given an array of integers arr, write a function that returns true if and only if the number of occurrences of each value in the array is unique.\n",
    "- https://leetcode.com/problems/unique-number-of-occurrences/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# dictionary and set()\n",
    "# dictionary: key-value pair \n",
    "# set: store unique values\n",
    "\n",
    "def uniqueOccurrences(arr):\n",
    "    \n",
    "    dictionary = {}             \n",
    "        \n",
    "    for i in arr: \n",
    "        if i in dictionary: \n",
    "            dictionary[i]+=1\n",
    "                \n",
    "        else:\n",
    "            dictionary[i]=1\n",
    "                \n",
    "    return len(dictionary.values()) == len(set(dictionary.values()))\n",
    "\n",
    "# test case \n",
    "arr = [1,2,2,1,1,3]\n",
    "uniqueOccurrences(arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Question 3: N-Repeated Element in Size 2N Array, by Apple\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",
    "- https://leetcode.com/problems/n-repeated-element-in-size-2n-array/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# solution 1: built-in Counter()\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "def repeatedNTimes(A):\n",
    "    count = Counter(A)\n",
    "    for i in count:\n",
    "        if count[i]>1:\n",
    "            return i\n",
    "    \n",
    "# test case\n",
    "A = [1,2,3,3]\n",
    "repeatedNTimes(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# solution 2: items()\n",
    "\n",
    "def repeatedNTimes(A):\n",
    "    \n",
    "    N = len(A)//2\n",
    "    \n",
    "    dictionary = {}\n",
    "    \n",
    "    for i in A: \n",
    "        if i in dictionary:\n",
    "            dictionary[i] +=1\n",
    "            \n",
    "        else:\n",
    "            dictionary[i] = 1\n",
    "            \n",
    "    for key, value in dictionary.items():\n",
    "        \n",
    "        if value==N:\n",
    "            \n",
    "            return key\n",
    "        \n",
    "        \n",
    "# test case\n",
    "A = [1,2,3,3]\n",
    "repeatedNTimes(A)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Question 4: Single-Row Keyboard, by Google\n",
    "- There is a special keyboard with all keys in a single row.\n",
    "- Given a string keyboard of length 26 indicating the layout of the keyboard (indexed from 0 to 25), initially your finger is at index 0. To type a character, you have to move your finger to the index of the desired character. \n",
    "- The time taken to move your finger from index i to index j is |i - j|.\n",
    "- You want to type a string word. Write a function to calculate how much time it takes to type it with one finger.\n",
    "- https://leetcode.com/problems/single-row-keyboard/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def single_row_keyboard(keyboard, word):\n",
    "    \n",
    "    dictionary = {}\n",
    "    \n",
    "    for i in range(len(keyboard)):     # construct a new dict to store keyboard's position and letter\n",
    "        dictionary[keyboard[i]] = i\n",
    "    \n",
    "    temp = 0\n",
    "    \n",
    "    result = 0 \n",
    "    \n",
    "    for w in word: \n",
    "        result += abs(dictionary[w] - temp) # to calculate the differences between the current and the previous letters\n",
    "        temp = dictionary[w]\n",
    "        \n",
    "    return result\n",
    "\n",
    "# test case \n",
    "keyboard = \"abcdefghijklmnopqrstuvwxyz\"\n",
    "word = \"cba\"\n",
    "single_row_keyboard(keyboard,word)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "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": 2
}