Interview Question: find the first character that occurs only once in a string.

First singleton character in string.ipynb

{
 "metadata": {
  "name": "First singleton character in string"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Easy interview coding question:\n",
      "\n",
      "Given a string, find the first character that appears only once.\n",
      "\n",
      "The input is this string, and the correct result is 'z'"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "letters = \"asdzfasdfrasfy\""
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 16
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###First method\n",
      "* Count all the letters, then find the first singleton (2 passes)\n",
      "* This method shows knowledge of python but is not optimal in terms of runtime"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import collections\n",
      "letter_counts = collections.Counter(letters)\n",
      "print letter_counts"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "Counter({'a': 3, 'f': 3, 's': 3, 'd': 2, 'r': 1, 'y': 1, 'z': 1})\n"
       ]
      }
     ],
     "prompt_number": 17
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Now that we have the count of each letter, we will select those letters which appear only once.\n",
      "single_letters = [k for k, v in letter_counts.iteritems() if v == 1]\n",
      "print single_letters"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "['r', 'y', 'z']\n"
       ]
      }
     ],
     "prompt_number": 18
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Finally, we select the first letter from the input letters that appears once\n",
      "for letter in letters:\n",
      "    if letter in single_letters:\n",
      "        print letter\n",
      "        break"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "z\n"
       ]
      }
     ],
     "prompt_number": 19
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "###Second method\n",
      "* Use a list to store singletons and move them to a set if encountered again (1 pass)\n",
      "* This method is simple and fast "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# Second method -- Using a list to store singletons and moving them to a set if encountered again (1 pass)\n",
      "single_letters = []\n",
      "multi_letters = set([])\n",
      "for letter in letters:\n",
      "    if letter not in single_letters + list(multi_letters):\n",
      "        single_letters.append(letter)\n",
      "    elif letter in single_letters:\n",
      "        single_letters.remove(letter)\n",
      "        multi_letters.add(letter)\n",
      "print single_letters[0]\n",
      "        "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "z\n"
       ]
      }
     ],
     "prompt_number": 20
    }
   ],
   "metadata": {}
  }
 ]
}

Viewable at: http://nbviewer.ipython.org/5768547