2nd Track Arrays.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Elements of Programming Interviews\n",
    "## Arrays\n",
    "### Track 2: 6.1, 6.2, *6.3*, 6.6, 6,7, 6.9, *6.10*, 6.12, *6.15*, 6.17, 6.18 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.1 - The Dutch National Flag Problem\n",
    ">\"*The Dutch national flag problem (DNF) is a computer science programming problem proposed by Edsger Dijkstra.[2] The flag of the Netherlands consists of three colours: red, white and blue. Given balls of these three colours arranged randomly in a line (the actual number of balls does not matter), the task is to arrange them such that all balls of the same colour are together and their collective colour groups are in the correct order.*\"\n",
    "\n",
    ">Write a program that takes an array A and an index *i* into A, and rearranges the elements such that all elements less than A[i] (the pivot) appear first, followed by elements equal to the pivot, followed by elements greater than the pivot.\n",
    "\n",
    ">>My inital brute force solution would be to make three lists, and insert into them accordingly, then merge them back."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 4, 5, 3, 4, 1, 2, 4, 6, 10, 8, 9]"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def DNF_merge_bf(arr, i):\n",
    "    pivot = arr[i]\n",
    "    lt_partition = []\n",
    "    eq_partition = []\n",
    "    gt_partition = []\n",
    "    for elem in arr:\n",
    "        if elem < pivot:\n",
    "            lt_partition.append(elem)\n",
    "        elif elem == pivot:\n",
    "            eq_partition.append(elem)\n",
    "        else:\n",
    "            gt_partition.append(elem)\n",
    "    return lt_partition + eq_partition + gt_partition\n",
    "A = [10, 1, 2, 8, 4, 6, 5, 3, 4, 9, 1, 2, 4] \n",
    "DNF_merge_bf(A, 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Time Complexity: O(n), time and space complexity. This is not efficient enough, too much space needed.\n",
    ">>Second approach is to go through the list initially and move all elements less than pivot to the front, then go thorugh list again and group all pivots, then lastly go through and group all items greater than pivot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 1, 2, 4, 4, 4, 6, 5, 10, 9, 8]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def DNF_group(arr, i):\n",
    "    pivot = arr[i]\n",
    "    #loop from front, find elements smaller than pivot and fill them in \n",
    "    for i, elem in enumerate(arr):\n",
    "        for j in range(i+1, len(arr)):\n",
    "            if arr[j] < pivot:\n",
    "                arr[i], arr[j] = arr[j], arr[i]\n",
    "                break;\n",
    "    #loop from back, find elements bigger than pivot and fill them in\n",
    "    for i in range(len(arr)-1, -1, -1):\n",
    "        for j in range(i, -1, -1):\n",
    "            if arr[j] > pivot:\n",
    "                arr[i], arr[j] = arr[j], arr[i]\n",
    "                break;\n",
    "    return arr\n",
    "A = [10, 1, 2, 8, 4, 6, 5, 3, 4, 9, 1, 2, 4] \n",
    "DNF_group(A, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">Notes for this next method to improve time complexity to O(n)\n",
    ">>The smaller variable start at 0, and is only incremented once a small elements is swapped into it. By doing this, we avoid having to have a second loop. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 1, 2, 4, 4, 4, 6, 5, 10, 9, 8]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def DNF_faster(arr, i):\n",
    "    insert_index = 0\n",
    "    pivot = arr[i]\n",
    "    for i, elem in enumerate(arr):\n",
    "        if elem < pivot:\n",
    "            arr[insert_index], arr[i] = arr[i], arr[insert_index]\n",
    "            insert_index += 1\n",
    "    insert_index = len(arr) - 1\n",
    "    for i in range(len(arr)-1, -1, -1):\n",
    "        if arr[i] > pivot:\n",
    "            arr[insert_index], arr[i] = arr[i], arr[insert_index]\n",
    "            insert_index -= 1\n",
    "    return arr\n",
    "\n",
    "A = [10, 1, 2, 8, 4, 6, 5, 3, 4, 9, 1, 2, 4]             \n",
    "DNF_faster(A, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def DNF_classes(arr, i):\n",
    "    low = 0\n",
    "    high = len(arr) - 1\n",
    "    eq = 0 # corresponds to the unclassified elem\n",
    "    pivot = arr[i]\n",
    "    i = 0\n",
    "    while eq <= high:\n",
    "        elem = arr[i]\n",
    "        if elem < pivot:\n",
    "            arr[low], arr[i] = arr[i], arr[low]\n",
    "            low += 1\n",
    "            eq += 1\n",
    "        elif elem == pivot:\n",
    "            eq += 1\n",
    "        else:\n",
    "            arr[high], arr[i] = arr[i], arr[high]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Time complexity: O(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.2 - Increment Arbitrary Precision Number\n",
    ">Write a program that takes as input an array of digits encoding a decimal number D and updates the array to represent the number D+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 0, 0, 0]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def increment_num(narr):\n",
    "    carry = 0\n",
    "    for i in range(len(narr)-1,-1, -1):\n",
    "        narr[i] += 1\n",
    "        if narr[i] == 10:\n",
    "            carry = 1\n",
    "            narr[i] = 0\n",
    "        if carry == 0:\n",
    "            break\n",
    "    if narr[0] == 0:\n",
    "        narr.insert(0, 1)\n",
    "    return narr\n",
    "increment_num([1,2,3])\n",
    "increment_num([9,9,9])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.6 - Delete Duplicates From a Sorted Array\n",
    ">Write a program which takes as an input, a sorted array, and updates it so that all duplicates have been removed and the remaining elements have been shifted left to fill the emptied indices."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 5, 7, 11, 13, 0, 0, 0]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Initial brute force approach\n",
    "# this algorithm has bad space complexity of O(n), can be done in O(1)\n",
    "def remove_duplicates_bf(arr):\n",
    "    unique_arr = []\n",
    "    for elem in arr:\n",
    "        if elem not in unique_arr:\n",
    "            unique_arr.append(elem)\n",
    "    return unique_arr + ([0] * (len(arr) - len(unique_arr)))\n",
    "remove_duplicates_bf([2,3,5,5,7,11,11,11,13])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 5, 7, 11, 13, 11, 11, 13]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def remove_duplicates(arr):\n",
    "    insert_ix = 1 \n",
    "    curr_val = arr[0]\n",
    "    for elem in arr[1:]:\n",
    "        if elem != curr_val:\n",
    "            arr[insert_ix] = elem\n",
    "            curr_val = elem\n",
    "            insert_ix += 1\n",
    "    return arr\n",
    "remove_duplicates([2,3,5,5,7,11,11,11,13])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Time complexity: O(n)\n",
    "#### Space Complexity: O(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.7 Buy and Sell a stock once\n",
    ">Write a program that takes an array denoting the daily stock price, and returns the maximum profit that could be made by buying and then selling one share of that stock."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Initial brute force approach, bad time complexity O(n^2)\n",
    "#will try to implement in O(n)\n",
    "def buy_and_sell_bf(stocks):\n",
    "    max_profit = 0\n",
    "    buy_ix = 0\n",
    "    sell_ix = 1\n",
    "    for b_ix, b_p in enumerate(stocks):\n",
    "        for s_ix in range(b_ix, len(stocks)):\n",
    "            s_p = stocks[s_ix]\n",
    "            profit = s_p - b_p\n",
    "            if profit > max_profit:\n",
    "                buy_ix = b_ix\n",
    "                sell_ix = s_ix\n",
    "                max_profit = profit\n",
    "    return buy_ix, sell_ix, max_profit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(4, 6, 30)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "stocks = [310, 315, 275, 295, 260, 270, 290, 230, 255, 250]\n",
    "buy_and_sell_bf(stocks)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0, 4, 9)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# buy and sell, returns the max profit along with buy and sell ix's\n",
    "def buy_and_sell_with_ix(stocks):\n",
    "    buy_ix = 0\n",
    "    sell_ix = 1\n",
    "    curr_min_buy_ix = 0\n",
    "    max_profit = stocks[sell_ix] - stocks[buy_ix]\n",
    "    for i, price in enumerate(stocks):\n",
    "        if price - stocks[curr_min_buy_ix] > max_profit:\n",
    "            buy_ix = curr_min_buy_ix\n",
    "            sell_ix = i\n",
    "            max_profit = stocks[sell_ix] - stocks[buy_ix]\n",
    "        if price < stocks[curr_min_buy_ix]:\n",
    "            curr_min_buy_ix = i\n",
    "    return buy_ix, sell_ix, max_profit\n",
    "buy_and_sell_with_ix([1,5,2,4,10])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "30"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#the insight is that the maximum profit will be generated by the minimum price seen so far\n",
    "#and todays current price\n",
    "def buy_and_sell(stocks):\n",
    "    min_price = stocks[0]\n",
    "    max_profit = stocks[1] - stocks[0]\n",
    "    for price_today in stocks[1:]:\n",
    "        max_profit_today = price_today - min_price\n",
    "        max_profit = max(max_profit, max_profit_today)\n",
    "        min_price = min(min_price, price_today)\n",
    "    return max_profit\n",
    "buy_and_sell(stocks)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Generator Practice\n",
    ">Generate a list of primes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "3\n",
      "5\n",
      "7\n",
      "11\n",
      "13\n",
      "17\n",
      "19\n",
      "23\n",
      "29\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "def is_prime(number):\n",
    "    if number == 1:\n",
    "        return False\n",
    "    elif number == 2:\n",
    "        return True\n",
    "    elif number % 2 == 0:\n",
    "        return False\n",
    "    for i in range(3, int(math.sqrt(number)) + 1, 2):\n",
    "        if number % i == 0:\n",
    "            return False\n",
    "    return True\n",
    "def get_primes(number):\n",
    "    while True:\n",
    "        if is_prime(number):\n",
    "            yield number\n",
    "        number += 1\n",
    "def list_primes(n):\n",
    "    for prime in get_primes(1):\n",
    "        print prime\n",
    "        if prime > n:\n",
    "            break\n",
    "list_primes(25)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.9 - Enumerate all prime from 1 to N\n",
    ">Write a program that takes an integer argument and returns all the primes between 1 and that number."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[2, 3, 5, 7]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "def enum_primes(n):\n",
    "    primes = []\n",
    "    candidates = np.ones(n, dtype='int')\n",
    "    for num in range(0, len(candidates)):\n",
    "        if candidates[num] == 0:\n",
    "            print num\n",
    "            continue\n",
    "        elif is_prime(num):\n",
    "            print num\n",
    "            primes.append(num)\n",
    "            for multiple in range(num, n, num):\n",
    "                candidates[multiple] = 0\n",
    "        else:\n",
    "            candidates[num] = 0\n",
    "    return primes\n",
    "            \n",
    "enum_primes(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.10 - Permute the Elements of an Array\n",
    ">Given an array A of n elements and a permutation P, apply P to A. For example, {2, 0, 1, 3} maps the elements at P[0] would map the element at location 0 to the 2 index of the permutation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['b', 'c', 'a', 'd']"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def permute_array_bf(arr, permutation):\n",
    "    result = [None] * len(arr)\n",
    "    for location, i in enumerate(permutation):\n",
    "        result[i] = arr[location]\n",
    "    return result\n",
    "permute_array_bf(['a','b','c','d'], [2,0,1,3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Time Complexity: O(n) on both space and time, can be improved\n",
    ">>This next approach uses cyclic permutations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['d', 'c', 'b', 'a']"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def permute_array(arr, permutation):\n",
    "    for i in range(len(permutation)):\n",
    "        if permutation[i] > 0:\n",
    "            find_cyclic_permutation(arr, permutation, i )\n",
    "    return arr\n",
    "\n",
    "def find_cyclic_permutation(arr, permutation, start):\n",
    "    ix = start\n",
    "    next_pos = permutation[start]\n",
    "    val_to_swap = arr[ix]\n",
    "    while True:\n",
    "        tmp = arr[next_pos]\n",
    "        arr[next_pos] = val_to_swap\n",
    "        permutation[ix] -= len(permutation)\n",
    "        ix = next_pos\n",
    "        next_pos = permutation[next_pos]\n",
    "        val_to_swap = tmp\n",
    "        if ix == start:\n",
    "            break\n",
    "permute_array(['a', 'b', 'c', 'd'], [2,0,1,3])\n",
    "permute_array(['a', 'b', 'c', 'd'], [3,2,1,0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Time complexity: O(n), constant space complexity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.12 - Sample Offline Data\n",
    ">Implement an algorithm that takes as input an array of distinct elements and a size, and returns a subset of the given size of the array elements. All subsets should be equally likely. Return the result in input array itself."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[7, 4, 0, 3, 1, 5, 6, 2, 8, 9]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from random import randint\n",
    "def random_sampling(arr, size):\n",
    "    k = 0\n",
    "    while k < size:\n",
    "        r_ix = randint(k, len(arr) - 1)\n",
    "        arr[k], arr[r_ix] = arr[r_ix], arr[k]\n",
    "        k += 1\n",
    "    return arr\n",
    "random_sampling(range(10), 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.15 - Compute a Random Subset\n",
    ">Write a program that takes in two numbers $n,k$ such that $k \\le n$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[14, 34, 52, 26]"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def random_subset(n, k):\n",
    "    ht = {}\n",
    "    for i in range(k):\n",
    "        r_ix = randint(i,n-1)\n",
    "        if i not in ht.keys() and r_ix not in ht.keys():\n",
    "            ht[i], ht[r_ix] = r_ix, i\n",
    "        elif i in ht.keys() and r_ix not in ht.keys():\n",
    "            ht[r_ix], ht[i] = ht[i], r_ix\n",
    "        elif i not in ht.keys() and r_ix in ht.keys():\n",
    "            ht[i], ht[r_ix] = ht[r_ix], i\n",
    "        else: #i,r_ix both in ht.keys()\n",
    "            ht[i], ht[r_ix] = ht[r_ix], ht[i]\n",
    "    subset = []\n",
    "    for i in range(k):\n",
    "        subset.append(ht[i])\n",
    "    return subset\n",
    "random_subset(100, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.17 - Sudoku Checker"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_region(board, start_row, start_col):\n",
    "    region = []\n",
    "    for row in range(start_row, start_row+3):\n",
    "        for col in range(start_col, start_col+3):\n",
    "            region.append(board[row][col])\n",
    "    return region\n",
    "\n",
    "def has_duplicates(arr):\n",
    "    seen_numbers = {}\n",
    "    for num in arr:\n",
    "        if num in seen_numbers.keys():\n",
    "            return True\n",
    "        else:\n",
    "            if num != 0:\n",
    "                seen_numbers[num] = None\n",
    "                \n",
    "def sudoku_checker(board):\n",
    "    for row in range(9):\n",
    "        if has_duplicates(board[row]):\n",
    "            return False\n",
    "    for col in range(9):\n",
    "        if has_duplicates([row[col] for row in board[0:9]]):\n",
    "            return False\n",
    "    for row in [0, 3, 6]:\n",
    "        for col in [0, 3, 6]:\n",
    "            if has_duplicates(get_region(board, row, col)):\n",
    "                return False\n",
    "    return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "board = [[randint(1,10000) for i in range(9)] for i in range(9)]\n",
    "sudoku_checker(board)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[6376, 3230, 1043, 7989, 5234, 6934, 5994, 1654, 6730]"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_region(board, 3, 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.18 Compute the spiral ordering of a 2D array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import math\n",
    "def spiral_order(arr):\n",
    "    top_row = 0\n",
    "    bot_row = len(arr) - 1\n",
    "    left_col = 0\n",
    "    right_col = len(arr) - 1\n",
    "    loop = 0\n",
    "    while loop < math.floor(len(arr) / 2):\n",
    "        #print top row\n",
    "        for col in xrange(left_col, right_col+1):\n",
    "            print arr[top_row][col]\n",
    "        #print right col\n",
    "        for row in xrange(top_row+1, bot_row):\n",
    "            print arr[row][right_col]\n",
    "        #print bottom row\n",
    "        for col in xrange(right_col, left_col-1, -1):\n",
    "            print arr[bot_row][col]\n",
    "        #print left col\n",
    "        for row in xrange(bot_row-1, top_row, -1):\n",
    "            print arr[row][left_col]\n",
    "        top_row += 1\n",
    "        bot_row -= 1\n",
    "        left_col += 1\n",
    "        right_col -= 1\n",
    "        loop += 1\n",
    "    if len(arr) % 2 == 1:\n",
    "        center = int(math.floor(len(arr) / 2))\n",
    "        print arr[center][center]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "6\n",
      "8\n",
      "7\n",
      "6\n",
      "4\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "A = [\n",
    "    [1, 2, 3],\n",
    "    [4, 5, 6],\n",
    "    [6, 7, 8]\n",
    "]\n",
    "spiral_order(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "8\n",
      "12\n",
      "16\n",
      "15\n",
      "14\n",
      "13\n",
      "9\n",
      "5\n",
      "6\n",
      "7\n",
      "11\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "B = [\n",
    "    [1, 2, 3, 4],\n",
    "    [5, 6, 7, 8],\n",
    "    [9, 10, 11, 12],\n",
    "    [13, 14, 15, 16]\n",
    "]\n",
    "spiral_order(B)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [Root]",
   "language": "python",
   "name": "Python [Root]"
  },
  "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}