Arrays in Python.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Array sequences in Python\n",
    "Array sequences in Python include: lists, tuples and strings. All the three support indexing.\n",
    "\n",
    "Each byte has a unique address. Consecutive bytes have consecutive numbers as address. Each byte can be accessed, read or written to in O(1), i.e. in constant time.\n",
    "\n",
    "A group of related variables can be stored one after another in contiguous portion of memory. This is an **array**.\n",
    "Each unicode character is represented in 2 bytes by Python. For example, the string \"SAMPLE\" will take 12 bytes.\n",
    "The two byte location alloted to a character is called **cell**. Now, each cell must be of same size, not necessarily of 2 bytes.\n",
    "\n",
    "## Referential Arrays\n",
    "Consider an array of strings. All strings will have different length. Hence they cannot be stored in consecutive locations (as discussed earlier). Hence in an array of strings, a reference of each string is stored. All references take up equal space, i.e. each cell has a reference to a string that is stored in another location.\n",
    "In python, list and tuples are referential in nature. \n",
    "\n",
    "In slices, it looks like a new list is formed. In reality, it holds the reference to the same objects as the original list. Changes made to slice do not change the original list. The new list element now points to a new object that is different from the old list.\n",
    "\n",
    "## Coping Arrays\n",
    "```backup = list(array)``` This creates a shallow copy of the list, each elements reference the same object as the first list. To create a new list, with elements pointing to new objects, **deepcopy** function from **copy** module can be used.\n",
    "\n",
    "```counter = [0] * 8``` all elements refer to the same location that holds value 0. ```counter[1] = 2``` This creates a new reference and saves it to index 1. \n",
    "\n",
    "```counter.extend(lst)``` Here, extend function add cells to the old list where each element is referring to the same object as the list *lst*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Time Complexities of functions called on Python lists\n",
    "**Operation**|**Big-O Efficiency**\n",
    ":-----:|:-----:\n",
    "index [] |O(1)\n",
    "index assignment |O(1)\n",
    "append |O(1)\n",
    "pop() |O(1)\n",
    "pop(i) |O(n)\n",
    "insert(i,item) |O(n)\n",
    "del operator |O(n)\n",
    "iteration |O(n)\n",
    "contains (in) |O(n)\n",
    "get slice [x:y] |O(k)\n",
    "del slice |O(n)\n",
    "set slice |O(n+k)\n",
    "reverse |O(n)\n",
    "concatenate |O(k)\n",
    "sort |O(n log n)\n",
    "multiply |O(nk)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A list instance often has greater capacity than specified. The following examples illustrates that size of array is increased in chunks."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "length 0 size in bytes 64\n",
      "length 1 size in bytes 96\n",
      "length 2 size in bytes 96\n",
      "length 3 size in bytes 96\n",
      "length 4 size in bytes 96\n",
      "length 5 size in bytes 128\n",
      "length 6 size in bytes 128\n",
      "length 7 size in bytes 128\n",
      "length 8 size in bytes 128\n",
      "length 9 size in bytes 192\n"
     ]
    }
   ],
   "source": [
    "import sys\n",
    "\n",
    "n=10\n",
    "data = []\n",
    "for i in range(n):\n",
    "    a = len(data)\n",
    "    b = sys.getsizeof(data)\n",
    "    print(\"length\", a, \"size in bytes\", b)\n",
    "    data.append(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Change the value of n to 50 and run the program again. This is to understand how increase of capacity occurs. This is called dynamic array. List class in Python are dynamic arrays.\n",
    "\n",
    "In following example, a custom dynamic array is written."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import ctypes\n",
    "\n",
    "class DynamicArray(object):\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.n = 0\n",
    "        self.capacity = 1\n",
    "        self.A = self.make_array(self.capacity)\n",
    "        \n",
    "    def __len__(self):\n",
    "        return self.n\n",
    "    \n",
    "    def __getitem__(self, k):\n",
    "        if not 0 <= k < self.n:\n",
    "            return IndexError('K is out of bound!')\n",
    "        return self.A[k]\n",
    "    \n",
    "    def append(self, ele):\n",
    "        if self.n == self.capacity:\n",
    "            self._resize(2*self.capacity) #2x if capacity isn't enough\n",
    "        self.A[self.n] = ele\n",
    "        self.n += 1\n",
    "        \n",
    "    def _resize(self, new_cap):\n",
    "        B = self.make_array(new_cap)\n",
    "        for k in range(self.n):\n",
    "            B[k] = self.A[k]\n",
    "        self.A = B\n",
    "        self.capacity = new_cap\n",
    "        \n",
    "    def make_array(self, new_cap):\n",
    "        return (new_cap * ctypes.py_object)()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "length: 1\n",
      "length: 2\n",
      "second element 2\n"
     ]
    }
   ],
   "source": [
    "arr = DynamicArray()\n",
    "arr.append(1)\n",
    "print(\"length:\", len(arr))\n",
    "arr.append(2)\n",
    "print(\"length:\", len(arr))\n",
    "print(\"second element\", arr[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Amotized Analysis of Array\n",
    "This is to study how capacity is increased for dynamic arrays.\n",
    "\n",
    "## Interview Questions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Results of first implementation\n",
      "True\n",
      "False\n",
      "Results of second implementation\n",
      "True\n",
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "Anagram Check: Given two strings if they are anagrams\n",
    "Ignore white spaces and capitalizations\n",
    "\"\"\"\n",
    "\n",
    "def anagram_check(a, b): # preferred solution\n",
    "    a = a.lower().replace(' ','')\n",
    "    b = b.lower().replace(' ','')\n",
    "    return sorted(a) == sorted(b)\n",
    "\n",
    "print(\"Results of first implementation\")\n",
    "print(anagram_check(\"God\", \"Dog\"))\n",
    "print(anagram_check(\"clint eastwood\", \"olsd west action\"))\n",
    "\n",
    "def anagram_check2(a, b):\n",
    "    \n",
    "    a = a.lower().replace(' ','')\n",
    "    b = b.lower().replace(' ','')\n",
    "    if len(a) != len(b):\n",
    "        return False\n",
    "    count = {}\n",
    "    for letter in a:\n",
    "        if letter in count:\n",
    "            count[letter] += 1\n",
    "        else:\n",
    "            count[letter] = 1\n",
    "    for letter in b:\n",
    "        if letter in count:\n",
    "            count[letter] -= 1\n",
    "        else:\n",
    "            return False\n",
    "    \n",
    "    for k in count:\n",
    "        if count[k] != 0:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "print(\"Results of second implementation\")\n",
    "print(anagram_check2(\"God\", \"Dog\"))\n",
    "print(anagram_check2(\"clint eastwood\", \"olsd west action\"))\n",
    "print(anagram_check2(\"clint eastwood\", \"old west action\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 3)\n",
      "(2, 2)\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "Array Pair Sum:  given an integer array, output all unique pairs that sum up to a specific value k\n",
    "\"\"\"\n",
    "\n",
    "def array_pair_sum(arr,k):\n",
    "    if len(arr) < 2: # no pairs can be formed\n",
    "        print(\"Length of array less than 2\")\n",
    "    seen = set()\n",
    "    output = set()\n",
    "    for num in arr:\n",
    "        target = k-num\n",
    "        if target not in seen:\n",
    "            seen.add(num)\n",
    "        else:\n",
    "            output.add(((min(num, target)), max(num, target)))\n",
    "    print('\\n'.join(map(str, list(output))))\n",
    "array_pair_sum([1,3,2,2], 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "First Implementation\n",
      "5\n",
      "2\n",
      "Second Implementation\n",
      "5\n",
      "2\n",
      "Third Implementation\n",
      "5\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "Find missing element: two arrays of non-negative elements\n",
    "First array has only one element which is not there in the second array\n",
    "Find it\n",
    "\"\"\"\n",
    "\n",
    "def find_missing_element(arr1, arr2): # O(nlogn)\n",
    "    arr1.sort()\n",
    "    arr2.sort()\n",
    "    for num1, num2 in zip(arr1, arr2):\n",
    "        if num1!= num2:\n",
    "            return num1\n",
    "    return arr1[-1]\n",
    "\n",
    "print(\"First Implementation\")\n",
    "print(find_missing_element([1,2,3,4,5], [1,2,3,4]))\n",
    "print(find_missing_element([1,2,3,4,5], [1,5,3,4]))\n",
    "\n",
    "import collections\n",
    "\n",
    "# defaultdict allows you to access a key that does not exist in the dictionary\n",
    "def find_missing_element2(arr1, arr2): #o(n)\n",
    "    d = collections.defaultdict(int)\n",
    "    for num in arr2:\n",
    "        d[num]+=1\n",
    "    for num in arr1:\n",
    "        if d[num] == 0:\n",
    "            return num\n",
    "        else:\n",
    "            d[num] -= 1\n",
    "\n",
    "print(\"Second Implementation\")\n",
    "print(find_missing_element2([1,2,3,4,5], [1,2,3,4]))\n",
    "print(find_missing_element2([1,2,3,4,5], [1,5,3,4]))\n",
    "\n",
    "def find_missing_element3(arr1, arr2): # clever trick O(n)\n",
    "    result = 0\n",
    "    for num in arr1+arr2:\n",
    "        result ^= num\n",
    "    return result\n",
    "\n",
    "print(\"Third Implementation\")\n",
    "print(find_missing_element3([1,2,3,4,5], [1,2,3,4]))\n",
    "print(find_missing_element3([1,2,3,4,5], [1,5,3,4]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another approach is to sum all elements of array1 and subtract it with sum of array2 elements. This approach is not good when the numbers are very precise with decimal points or the numbers are very large. In the former you may loose data and in the latter you may encounter overflow exceptions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "29"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\"\n",
    "Largest Continuous Sum: given an array of integers, find largest continuous sum sub array\n",
    "\"\"\"\n",
    "\n",
    "def largest_sum(arr):\n",
    "    if len(arr) == 0:\n",
    "        return 0\n",
    "    max_sum = current_sum = arr[0]\n",
    "    for num in arr[1:]:\n",
    "        current_sum = max(current_sum+num, num)\n",
    "        max_sum = max(current_sum, max_sum)\n",
    "        \n",
    "    return max_sum\n",
    "\n",
    "largest_sum([1,2,-1,3,4,10,10,-10,-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "Sentence Reversal:  given a string reverse the word order in the string\n",
    "\"\"\"\n",
    "\n",
    "def reverse_string1(s):\n",
    "    return \" \".join(reversed(s.split()))\n",
    "\n",
    "def reverse_string2(s):\n",
    "    return \" \".join(s.split()[::-1])\n",
    "\n",
    "# The above solutions are usinf python basic functions. Not acceptable in interview. \n",
    "# Hence more algorithmic approach is required.\n",
    "\n",
    "def reverse_string3(s):\n",
    "    words = []\n",
    "    length = len(s)\n",
    "    space = [' ']\n",
    "    \n",
    "    i=0\n",
    "    \n",
    "    while i<length:\n",
    "        if s[i] not in space:\n",
    "            word_start = i\n",
    "            while i < length and s[i] not in space:\n",
    "                i+=1\n",
    "            words.append(s[word_start:i])\n",
    "        i+=1\n",
    "        \n",
    "    return \" \".join(reversed(words))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "you are how John Hello\n",
      "before space\n"
     ]
    }
   ],
   "source": [
    "print(reverse_string3('     Hello   John    how are   you   '))\n",
    "print(reverse_string3('     space before   '))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "String compression: 'AAAABBBBCCCCCCCCDDEEE' -> 'A4B4C8D2E3'\n",
    "Function should be case sensitive 'AAAaaa' -> 'A3a3'\n",
    "\"\"\"\n",
    "\n",
    "def string_compression(s): #O(n)\n",
    "    r = \"\"\n",
    "    if len(s) == 0:\n",
    "        return \"\"\n",
    "    if len(s) == 1:\n",
    "        return s+\"1\"\n",
    "    last = s[0]\n",
    "    count = 1\n",
    "    i = 1\n",
    "    \n",
    "    while i < len(s):\n",
    "        if s[i] == s[i-1]:\n",
    "            count += 1\n",
    "        else:\n",
    "            r += s[i-1] + str(count)\n",
    "            count = 1\n",
    "        i+=1\n",
    "    r += s[i-1]+str(count)\n",
    "    return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "A4B4C8D2E3\n",
      "A3a3\n"
     ]
    }
   ],
   "source": [
    "print(string_compression('AAAABBBBCCCCCCCCDDEEE'))\n",
    "print(string_compression('AAAaaa'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "First implementation\n",
      "True\n",
      "False\n",
      "Second implementation\n",
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "Unique characters in string: given a string, check if it has all unique characters\n",
    "\"\"\"\n",
    "def unique_char_check(s):\n",
    "    return len(set(s)) == len(list(s))\n",
    "\n",
    "print(\"First implementation\")\n",
    "print(unique_char_check(\"abcde\"))\n",
    "print(unique_char_check(\"abcdde\"))\n",
    "\n",
    "# above solution is okay, but another approach should also be mentioned\n",
    "\n",
    "def unique_char_check2(s):\n",
    "    chars  = set()\n",
    "    for l in s:\n",
    "        if l in chars:\n",
    "            return False\n",
    "        else:\n",
    "            char.add(l)\n",
    "    return True\n",
    "\n",
    "print(\"Second implementation\")\n",
    "print(unique_char_check(\"abcde\"))\n",
    "print(unique_char_check(\"abcdde\"))"
   ]
  }
 ],
 "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
}