array_based.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem 1\n",
    "Anagram Check\n",
    "Problem\n",
    "Given two strings, check to see if they are anagrams. An anagram is when the two strings can be written using the exact same letters (so you can just rearrange the letters to get a different phrase or word).\n",
    "\n",
    "For example:\n",
    "\n",
    "\"public relations\" is an anagram of \"crap built on lies.\"\n",
    "\n",
    "\"clint eastwood\" is an anagram of \"old west action\"\n",
    "\n",
    "Note: Ignore spaces and capitalization. So \"d go\" is an anagram of \"God\" and \"dog\" and \"o d g\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def anagram(s1,s2):\n",
    "    s1=s1.replace(\" \",\"\").lower()\n",
    "    s2=s2.replace(\" \",\"\").lower()\n",
    "    lowercase=\"abcdefghijklmnopqsrtuvwxyz\"\n",
    "    dict1=dict.fromkeys(list(s1),0)\n",
    "    dict2=dict.fromkeys(list(s1),0)\n",
    "    \n",
    "    if len(s1) == len(s2):\n",
    "        for i in range(0,len(s1)):\n",
    "            dict1[s1[i]] += 1\n",
    "            dict2[s2[i]] += 1\n",
    "        if dict1 == dict2:\n",
    "            return True\n",
    "        else:\n",
    "             return False\n",
    "    else:\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "#not optimal\n",
    "def anagram(s1,s2):\n",
    "    s1=sorted(s1.replace(\" \",\"\"))\n",
    "    s2=sorted(s2.replace(\" \",\"\"))\n",
    "    return s1==s2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "def anagram(s1,s2):\n",
    "    s1=s1.replace(\" \",\"\")\n",
    "    s2=s2.replace(\" \",\"\")\n",
    "    \n",
    "    if len(s1) != len(s2):\n",
    "        return False\n",
    "    \n",
    "    count={}\n",
    "    for letter in s1:\n",
    "        if letter in count:\n",
    "            count[letter] += 1\n",
    "        else:\n",
    "            count[letter] = 1\n",
    "    \n",
    "    for letter in s2:\n",
    "        if letter in count:\n",
    "            count[letter] -= 1\n",
    "        else:\n",
    "            count[letter] = 1\n",
    "    \n",
    "    for k in count:\n",
    "        if count[k] !=0:\n",
    "            return False\n",
    "    return True\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ALL TEST CASES PASSED\n"
     ]
    }
   ],
   "source": [
    "from nose.tools import assert_equal\n",
    "\n",
    "class AnagramTest(object):\n",
    "    \n",
    "    def test(self,sol):\n",
    "        assert_equal(sol('go go go','gggooo'),True)\n",
    "        assert_equal(sol('abc','cba'),True)\n",
    "        assert_equal(sol('hi man','hi     man'),True)\n",
    "        assert_equal(sol('aabbcc','aabbc'),False)\n",
    "        assert_equal(sol('123','1 2'),False)\n",
    "        print \"ALL TEST CASES PASSED\"\n",
    "\n",
    "# Run Tests\n",
    "t = AnagramTest()\n",
    "t.test(anagram)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 2\n",
    "\n",
    "Array Pair Sum\n",
    "\n",
    "Given an integer array, output all the unique pairs that sum up to a specific value k.\n",
    "\n",
    "So the input:\n",
    "\n",
    "pair_sum([1,3,2,2],4)\n",
    "\n",
    "would return 2 pairs:\n",
    "\n",
    " (1,3)\n",
    " (2,2)\n",
    "\n",
    "NOTE: FOR TESTING PURPOSES CHANGE YOUR FUNCTION SO IT OUTPUTS THE NUMBER OF PAIRS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pair_sum(arr,k):\n",
    "    #edgecase check\n",
    "    if len(arr)<2:\n",
    "        return\n",
    "    #sets for tracking\n",
    "    seen = set()\n",
    "    output = set()\n",
    "    \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",
    "    return len(output)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ALL TEST CASES PASSED\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "RUN THIS CELL TO TEST YOUR SOLUTION\n",
    "\"\"\"\n",
    "from nose.tools import assert_equal\n",
    "\n",
    "class TestPair(object):\n",
    "    \n",
    "    def test(self,sol):\n",
    "        assert_equal(sol([1,9,2,8,3,7,4,6,5,5,13,14,11,13,-1],10),6)\n",
    "        assert_equal(sol([1,2,3,1],3),1)\n",
    "        assert_equal(sol([1,3,2,2],4),2)\n",
    "        print 'ALL TEST CASES PASSED'\n",
    "        \n",
    "#Run tests\n",
    "t = TestPair()\n",
    "t.test(pair_sum)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# problem 3\n",
    "\n",
    "Find the Missing Element\n",
    "Problem\n",
    "Consider an array of non-negative integers. A second array is formed by shuffling the elements of the first array and deleting a random element. Given these two arrays, find which element is missing in the second array.\n",
    "\n",
    "Here is an example input, the first array is shuffled and the number 5 is removed to construct the second array.\n",
    "\n",
    "Input:\n",
    "\n",
    "finder([1,2,3,4,5,6,7],[3,7,2,1,4,6])\n",
    "\n",
    "Output:\n",
    "\n",
    "5 is the missing number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution type 1 : sorting \n",
    "A more efficient solution is to sort the first array, so while checking whether an element in the first array appears in the second, we can do binary search (we'll learn about binary search in more detail in a future section). But we should still be careful about duplicate elements. The complexity is O(NlogN).\n",
    "\n",
    "If we don’t want to deal with the special case of duplicate numbers, we can sort both arrays and iterate over them simultaneously. Once two iterators have different values we can stop. The value of the first iterator is the missing element. This solution is also O(NlogN). Here is the solution for this approach:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "def finder(arr1,arr2):\n",
    "    #sorting arrays\n",
    "    arr1.sort()\n",
    "    arr2.sort()\n",
    "    \n",
    "    for num1,num2 in zip(arr1,arr2):\n",
    "        if num1 !=num2:\n",
    "            return num1\n",
    "    return arr1[-1]\n",
    "\n",
    "#Expectation in interview  linear time "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions2: Hashtable \n",
    "In most interviews, you would be expected to come up with a linear time solution. We can use a hashtable and store the number of times each element appears in the second array. Then for each element in the first array we decrement its counter. Once hit an element with zero count that’s the missing element. Here is this solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "import collections \n",
    "def finder(arr1,arr2):\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"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution3: linear time & constant space\n",
    "    \n",
    "One possible solution is computing the sum of all the numbers in arr1 and arr2, and subtracting arr2’s sum from array1’s sum. The difference is the missing number in arr2. However, this approach could be problematic if the arrays are too long, or the numbers are very large. Then overflow will occur while summing up the numbers.\n",
    "\n",
    "By performing a very clever trick, we can achieve linear time and constant space complexity without any problems. Here it is: initialize a variable to 0, then XOR every element in the first and second arrays with that variable. In the end, the value of the variable is the result, missing element in array2.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "def finder(arr1,arr2):\n",
    "    result=0\n",
    "    # Perform an XOR between the numbers in the arrays\n",
    "    for num in arr1+arr2: \n",
    "        result^=num \n",
    "    return result \n",
    "#XOR approach    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ALL TEST CASES PASSED\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "RUN THIS CELL TO TEST YOUR SOLUTION\n",
    "\"\"\"\n",
    "from nose.tools import assert_equal\n",
    "\n",
    "class TestFinder(object):\n",
    "    \n",
    "    def test(self,sol):\n",
    "        assert_equal(sol([5,5,7,7],[5,7,7]),5)\n",
    "        assert_equal(sol([1,2,3,4,5,6,7],[3,7,2,1,4,6]),5)\n",
    "        assert_equal(sol([9,8,7,6,5,4,3,2,1],[9,8,7,5,4,3,2,1]),6)\n",
    "        print 'ALL TEST CASES PASSED'\n",
    "\n",
    "# Run test\n",
    "t = TestFinder()\n",
    "t.test(finder)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 4\n",
    "\n",
    "Given an array of integers (positive and negative) find the largest continuous sum."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "SOLUTION:\n",
    "If the array is all positive, then the result is simply the sum of all numbers. The negative numbers in the array will cause us to need to begin checking sequences.\n",
    "\n",
    "The algorithm is, we start summing up the numbers and store in a current sum variable. After adding each element, we check whether the current sum is larger than maximum sum encountered so far. If it is, we update the maximum sum. As long as the current sum is positive, we keep adding the numbers. When the current sum becomes negative, we start with a new current sum. Because a negative current sum will only decrease the sum of a future sequence. Note that we don’t reset the current sum to 0 because the array can contain all negative integers. Then the result would be the largest negative number."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [],
   "source": [
    "def large_cont_sum(arr): \n",
    "    \n",
    "    # Check to see if array is length 0\n",
    "    if len(arr)==0: \n",
    "        return 0\n",
    "    \n",
    "    # Start the max and current sum at the first element\n",
    "    max_sum=current_sum=arr[0] \n",
    "    \n",
    "    # For every element in array\n",
    "    for num in arr[1:]: \n",
    "        \n",
    "        # Set current sum as the higher of the two\n",
    "        current_sum=max(current_sum+num, num)\n",
    "        \n",
    "        # Set max as the higher between the currentSum and the current max\n",
    "        max_sum=max(current_sum, max_sum) \n",
    "        \n",
    "    return max_sum "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ALL TEST CASES PASSED\n"
     ]
    }
   ],
   "source": [
    "from nose.tools import assert_equal\n",
    "\n",
    "class LargeContTest(object):\n",
    "    def test(self,sol):\n",
    "        assert_equal(sol([1,2,-1,3,4,-1]),9)\n",
    "        assert_equal(sol([1,2,-1,3,4,10,10,-10,-1]),29)\n",
    "        assert_equal(sol([-1,1]),1)\n",
    "        print 'ALL TEST CASES PASSED'\n",
    "        \n",
    "#Run Test\n",
    "t = LargeContTest()\n",
    "t.test(large_cont_sum)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Poblem 5\n",
    "Given a string of words, reverse all the words. For example:\n",
    "\n",
    "Given:\n",
    "\n",
    "'This is the best'\n",
    "\n",
    "Return:\n",
    "\n",
    "'best the is This'\n",
    "\n",
    "As part of this exercise you should remove all leading and trailing whitespace. So that inputs such as:\n",
    "\n",
    "'  space here'  and 'space here      '\n",
    "\n",
    "both become:\n",
    "\n",
    "'here space'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rev_word(s):\n",
    "    return \" \".join(reversed(s.split()))\n",
    "    # return \" \".join(s.split()[::-1])\n",
    "#Not what interviwer is looking for sort of cheating with using python "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rev_word(s):\n",
    "    \"\"\"\n",
    "    Manually doing the splits on the spaces.\n",
    "    \"\"\"\n",
    "    \n",
    "    words = []\n",
    "    length = len(s)\n",
    "    spaces = [' ']\n",
    "    \n",
    "    # Index Tracker\n",
    "    i = 0\n",
    "    \n",
    "    # While index is less than length of string\n",
    "    while i < length:\n",
    "        \n",
    "        # If element isn't a space\n",
    "        if s[i] not in spaces:\n",
    "            \n",
    "            # The word starts at this index\n",
    "            word_start = i\n",
    "            \n",
    "            while i < length and s[i] not in spaces:\n",
    "                \n",
    "                # Get index where word ends\n",
    "                i += 1\n",
    "            # Append that word to the list\n",
    "            words.append(s[word_start:i])\n",
    "        # Add to index\n",
    "        i += 1\n",
    "        \n",
    "    # Join the reversed words\n",
    "    return \" \".join(reversed(words))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ALL TEST CASES PASSED\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "RUN THIS CELL TO TEST YOUR SOLUTION\n",
    "\"\"\"\n",
    "\n",
    "from nose.tools import assert_equal\n",
    "\n",
    "class ReversalTest(object):\n",
    "    \n",
    "    def test(self,sol):\n",
    "        assert_equal(sol('    space before'),'before space')\n",
    "        assert_equal(sol('space after     '),'after space')\n",
    "        assert_equal(sol('   Hello John    how are you   '),'you are how John Hello')\n",
    "        assert_equal(sol('1'),'1')\n",
    "        print \"ALL TEST CASES PASSED\"\n",
    "        \n",
    "# Run and test\n",
    "t = ReversalTest()\n",
    "t.test(rev_word)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 6 - String Compression\n",
    "\n",
    "Given a string in the form 'AAAABBBBCCCCCDDEEEE' compress it to become 'A4B4C5D2E4'. For this problem, you can falsely \"compress\" strings of single or double letters. For instance, it is okay for 'AAB' to return 'A2B1' even though this technically takes more space.\n",
    "\n",
    "The function should also be case sensitive, so that a string 'AAAaaa' returns 'A3a3'.\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution\n",
    "Since Python strings are immutable, we'll need to work off of a list of characters, and at the end convert that list back into a string with a join statement.\n",
    "\n",
    "The solution below should yield us with a Time and Space complexity of O(n). Let's take a look with careful attention to the explanatory comments:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [],
   "source": [
    "def compress(s):\n",
    "    \"\"\"\n",
    "    This solution compresses without checking. Known as the RunLength Compression algorithm.\n",
    "    \"\"\"\n",
    "    \n",
    "    # Begin Run as empty string\n",
    "    r = \"\"\n",
    "    l = len(s)\n",
    "    \n",
    "    # Check for length 0\n",
    "    if l == 0:\n",
    "        return \"\"\n",
    "    \n",
    "    # Check for length 1\n",
    "    if l == 1:\n",
    "        return s + \"1\"\n",
    "    \n",
    "    #Intialize Values\n",
    "    last = s[0]\n",
    "    cnt = 1\n",
    "    i = 1\n",
    "    \n",
    "    while i < l:\n",
    "        \n",
    "        # Check to see if it is the same letter\n",
    "        if s[i] == s[i - 1]: \n",
    "            # Add a count if same as previous\n",
    "            cnt += 1\n",
    "        else:\n",
    "            # Otherwise store the previous data\n",
    "            r = r + s[i - 1] + str(cnt)\n",
    "            cnt = 1\n",
    "            \n",
    "        # Add to index count to terminate while loop\n",
    "        i += 1\n",
    "    \n",
    "    # Put everything back into run\n",
    "    r = r + s[i - 1] + str(cnt)\n",
    "    \n",
    "    return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ALL TEST CASES PASSED\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "RUN THIS CELL TO TEST YOUR SOLUTION\n",
    "\"\"\"\n",
    "from nose.tools import assert_equal\n",
    "\n",
    "class TestCompress(object):\n",
    "\n",
    "    def test(self, sol):\n",
    "        assert_equal(sol(''), '')\n",
    "        assert_equal(sol('AABBCC'), 'A2B2C2')\n",
    "        assert_equal(sol('AAABCCDDDDD'), 'A3B1C2D5')\n",
    "        print 'ALL TEST CASES PASSED'\n",
    "\n",
    "# Run Tests\n",
    "t = TestCompress()\n",
    "t.test(compress)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem 7\n",
    "Unique Characters in String\n",
    "Given a string,determine if it is compreised of all unique characters. For example, the string 'abcde' has all unique characters and should return True. The string 'aabcde' contains duplicate characters and should return false."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [],
   "source": [
    "def uni_char(s):\n",
    "    return len(set(s)) == len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [],
   "source": [
    "def uni_char(s):\n",
    "    chars = set()\n",
    "    for let in s:\n",
    "        # Check if in set\n",
    "        if let in chars:\n",
    "            return False\n",
    "        else:\n",
    "            #Add it to the set\n",
    "            chars.add(let)\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "ALL TEST CASES PASSED\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "RUN THIS CELL TO TEST YOUR CODE>\n",
    "\"\"\"\n",
    "from nose.tools import assert_equal\n",
    "\n",
    "\n",
    "class TestUnique(object):\n",
    "\n",
    "    def test(self, sol):\n",
    "        assert_equal(sol(''), True)\n",
    "        assert_equal(sol('goo'), False)\n",
    "        assert_equal(sol('abcdefg'), True)\n",
    "        print 'ALL TEST CASES PASSED'\n",
    "        \n",
    "# Run Tests\n",
    "t = TestUnique()\n",
    "t.test(uni_char)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}