Programming Questions A

ProgrammingQuestionsA.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": null
   },
   "source": [
    "# nth Fibonacci Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": null
   },
   "source": [
    "The $n$th Fibonacci number is recursively defined as:\n",
    "\n",
    "$$\n",
    "\\begin{equation*}\n",
    "    f(n) = \\begin{cases}\n",
    "               0               & n = 0\\\\\n",
    "               1               & n = 1\\\\\n",
    "               f(n-1) + f(n-2) & \\text{otherwise}\n",
    "           \\end{cases}\n",
    "\\end{equation*}\n",
    "$$\n",
    "  \n",
    "Write an $O(n)$ time recursive function that returns the nth Fibonacci number. Hint: $O(n)$ space as well.\n",
    "\n",
    "## Solution\n",
    "Basically, implement the definition, but with a global table at which we store the $n$th Fibonacci number.  This lookup table makes the algorithm run in time $O(n)$, as we fill in a missing value in the table once, and otherwise look it up when it's required.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": null
   },
   "outputs": [],
   "source": [
    "fib_table = {}\n",
    "def fib(n):\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    elif n in fib_table:\n",
    "        return fib_table[n]\n",
    "\n",
    "    fib_n = fib(n-2) + fib(n-1)\n",
    "    fib_table[n] = fib_n\n",
    "    return fib_n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": null
   },
   "outputs": [],
   "source": [
    "assert fib(0) == 0\n",
    "assert fib(1) == 1\n",
    "assert fib(5) == 5\n",
    "assert fib(10) == 55\n",
    "assert fib(20) == 6765"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": null
   },
   "source": [
    "You can also get this down to $O(\\log n)$ time using matrix operations and/or other identities involving the Fibonacci numbers. (See [here](http://www.nayuki.io/page/fast-fibonacci-algorithms).)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": null
   },
   "source": [
    "# Longest Palindromic Substring\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": null
   },
   "source": [
    "Given a string, find the longest substring which is a palindrome. For example, if the given string is `\"forgeeksskeegfor\"`, the output should be `\"geeksskeeg\"`.\n",
    "\n",
    "## Solutions\n",
    "\n",
    "### Simple approach\n",
    "Examine all substrings of all possible lengths $O(n^3)$.\n",
    "\n",
    "### More clever approach\n",
    "Go through `for i in range(len(s))` to find the longest palindrome centered at `i` (and `[i, i + 1`]).  Take the max of these.  This is $O(n^2)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": null
   },
   "outputs": [],
   "source": [
    "def longest_palindrome(s):\n",
    "    longest = \"\"\n",
    "    for i in range(len(s)):\n",
    "        j = 0       # get longest string centered on i\n",
    "        while 0 <= i - j and i + j < len(s) and s[i - j] == s[i + j]:\n",
    "            j += 1\n",
    "        j -= 1      # went one step too far\n",
    "        if 2 * j + 1 > len(longest):\n",
    "            longest = s[i - j: i + j + 1]\n",
    "\n",
    "        j = 0 # get longest string centered on (i, i + 1)\n",
    "        while 0 <= i - j and i + j + 1 < len(s) and s[i - j] == s[i + j + 1]:\n",
    "            j += 1\n",
    "        j -= 1       # went one step too far \n",
    "        if 2 * j + 2 > len(longest):\n",
    "            longest = s[i - j: i + j + 2]\n",
    "    return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": null
   },
   "outputs": [],
   "source": [
    "assert longest_palindrome(\"forgeeksskeegfor\") == \"geeksskeeg\"\n",
    "assert longest_palindrome(\"madam\") == \"madam\"\n",
    "assert longest_palindrome(\"abcdefghijklmnopqrstuvwxyz\") == \"a\"  #  Takes the first palindrome of the longest length.\n",
    "assert longest_palindrome(\"banana\") == \"anana\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": null
   },
   "source": [
    "### Really clever approach\n",
    "If you really want to impress someone, [this](http://www.geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-1/) will find palindromes in $O(n)$ time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": null
   },
   "source": [
    "# Letter Combinations of a Phone Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": null
   },
   "source": [
    "Given a digit string, return all possible letter combinations that the number could represent.\n",
    "\n",
    "Input: Digit string \"23\"\n",
    "\n",
    "Output: `[\"ad\", \"ae\", \"af\", \"bd\", \"be\", \"bf\", \"cd\", \"ce\", \"cf\"]`.\n",
    "\n",
    "## Solution\n",
    "\n",
    "http://stackoverflow.com/questions/2344496/how-can-i-print-out-all-possible-letter-combinations-a-given-phone-number-can-re\n",
    "\n",
    "Here's a recursive solution.  You could improve performance with memoization, if this would be called many times."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": null
   },
   "outputs": [],
   "source": [
    "def letterCombinations(digits):\n",
    "    # Mapping table for translating number to letters\n",
    "    num2letter = {\"2\":\"abc\", \"3\":\"def\", \"4\":\"ghi\", \"5\":\"jkl\",\"6\":\"mno\", \"7\":\"pqrs\", \"8\":\"tuv\", \"9\":\"wxyz\"}\n",
    " \n",
    "    # The result for an empty string is an empty string.\n",
    "    if len(digits) == 0:    \n",
    "        return [\"\"]\n",
    "\n",
    "    # We are only handling numbers from 2 to 9.\n",
    "    if not digits[0] in num2letter:\n",
    "        raise LookupError(\"Unacceptable input.\")\n",
    "        \n",
    "    # Terminate case for recursion\n",
    "    if len(digits) == 1: \n",
    "        return list(num2letter[digits])\n",
    " \n",
    "    # The strings for the current digit.\n",
    "    temp = list(num2letter[digits[0]])\n",
    "    result = []\n",
    "    # Recursion case. Append the recursion result to each string for current digit.\n",
    "    for tail in letterCombinations(digits[1:]):\n",
    "        result.extend([i+tail for i in temp])\n",
    " \n",
    "    return sorted(result)   #  \"Sorted\" called to make the output consistent with the above example and \n",
    "                            #  to make testing easier.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": null
   },
   "outputs": [],
   "source": [
    "assert letterCombinations(\"23\") == ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']\n",
    "assert letterCombinations(\"238\") == ['adt','adu','adv','aet','aeu','aev','aft','afu','afv','bdt','bdu','bdv',\n",
    "                                     'bet','beu','bev','bft','bfu','bfv','cdt','cdu','cdv','cet','ceu','cev',\n",
    "                                     'cft','cfu','cfv']\n",
    "assert letterCombinations(\"7\") == ['p', 'q', 'r', 's']"
   ]
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}