CTCI-Python-ch3.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#3.1 Describe how you could use a single array to implement three stacks\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class signleArrayStack(object):\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.arr=[]\n",
    "        \n",
    "    def push(self,i):\n",
    "        return self.arr.append(i)\n",
    "    \n",
    "    def pop(self,index):\n",
    "        return self.arr.pop(index)\n",
    "    \n",
    "    def peek(self,index):\n",
    "        return self.arr[index]\n",
    "    \n",
    "    def size(self):\n",
    "        return len(self.arr)\n",
    "    \n",
    "    def show(self):\n",
    "        return self.arr\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s=signleArrayStack()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s.push(1)\n",
    "s.push(2)\n",
    "s.push(3)\n",
    "s.push(4)\n",
    "s.push(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s.size()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s.peek(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#3.2 How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class signleArrayStack(object):\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.arr=[]\n",
    "        \n",
    "    def push(self,i):\n",
    "        return self.arr.append(i)\n",
    "    \n",
    "    def pop(self,index):\n",
    "        return self.arr.pop(index)\n",
    "    \n",
    "    def peek(self,index):\n",
    "        return self.arr[index]\n",
    "    \n",
    "    def size(self):\n",
    "        return len(self.arr)\n",
    "    \n",
    "    def show(self):\n",
    "        return self.arr\n",
    "    \n",
    "    def minimum(self):\n",
    "        return min(self.arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s.minimum()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#3.3 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stack(object):\n",
    "    def __init__(self, capacity):\n",
    "        self.capacity = capacity\n",
    "        self.size = 0\n",
    "        self.top = None\n",
    "        self.bottom = None\n",
    "\n",
    "    def is_full(self):\n",
    "        return self.size == self.capacity\n",
    "\n",
    "    def is_empty(self):\n",
    "        return self.size == 0\n",
    "\n",
    "    def join(self, above, below):\n",
    "        if below:\n",
    "            below.above = above\n",
    "        if above:\n",
    "            above.below = below\n",
    "\n",
    "    def push(self, v):\n",
    "        if self.size >= self.capacity:\n",
    "            return False\n",
    "        self.size += 1\n",
    "        n = Node(v)\n",
    "        if self.size == 1:\n",
    "            self.bottom = n\n",
    "        self.join(n, self.top)\n",
    "        self.top = n\n",
    "        return True\n",
    "\n",
    "    def pop(self):\n",
    "        if not self.top:\n",
    "            return None\n",
    "        t = self.top\n",
    "        self.top = self.top.below\n",
    "        self.size -= 1\n",
    "        return t.value\n",
    "\n",
    "    def remove_bottom(self):\n",
    "        b = self.bottom\n",
    "        self.bottom = self.bottom.above\n",
    "        if self.bottom:\n",
    "            self.bottom.below = None\n",
    "        self.size -= 1\n",
    "        return b.value\n",
    "\n",
    "class SetOfStacks(object):\n",
    "    def __init__(self, capacity):\n",
    "        self.capacity = capacity\n",
    "        self.stacks = []\n",
    "\n",
    "    def get_last_stack(self):\n",
    "        if not self.stacks:\n",
    "            return None\n",
    "        return self.stacks[-1]\n",
    "\n",
    "    def is_empty(self):\n",
    "        last = self.get_last_stack()\n",
    "        return not last or last.is_empty()\n",
    "\n",
    "    def push(self, v):\n",
    "        last = self.get_last_stack()\n",
    "        if last and not last.is_full():\n",
    "            last.push(v)\n",
    "        else:\n",
    "            stack = Stack(self.capacity)\n",
    "            stack.push(v)\n",
    "            self.stacks.append(stack)\n",
    "\n",
    "    def pop(self):\n",
    "        last = self.get_last_stack()\n",
    "        if not last:\n",
    "            return None\n",
    "        v = last.pop()\n",
    "        if last.size == 0:\n",
    "            del self.stacks[-1]\n",
    "        return v\n",
    "\n",
    "    def pop_at(self, index):\n",
    "        return self.left_shift(index, True)\n",
    "\n",
    "    def left_shift(self, index, remove_top):\n",
    "        stack = self.stacks[index]\n",
    "        removed_item = stack.pop() if remove_top else stack.remove_bottom()\n",
    "        if stack.is_empty():\n",
    "            del self.stacks[index]\n",
    "        elif len(self.stacks) > index + 1:\n",
    "            v = self.left_shift(index + 1, False)\n",
    "            stack.push(v)\n",
    "        return removed_item\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#3.4\n",
    "class Hanoi:\n",
    "    \n",
    "    def __init__(self, size):\n",
    "        self.towers = [[], [], []]\n",
    "        self.size = size\n",
    "        self.towers[0] = [x for x in range(size, 0, -1)]\n",
    "\n",
    "    def playHanoi(self):\n",
    "        self.printTowers()\n",
    "        self.moveDisk(self.size, 1, 2, 3)\n",
    "        self.printTowers()\n",
    "\n",
    "    def moveDisk(self, size, fr, helper, to):\n",
    "        if size == 1:\n",
    "            data = self.towers[fr-1].pop()\n",
    "            self.towers[to-1].append(data)\n",
    "            print (\"Disk\", data, \": Tower\", fr, \"->\", to)      \n",
    "        else:\n",
    "            self.moveDisk(size - 1, fr, to, helper)\n",
    "            self.moveDisk(1, fr, helper, to)\n",
    "            self.moveDisk(size - 1, helper, fr, to)\n",
    "\n",
    "    def printTowers(self):\n",
    "        for i in self.towers:\n",
    "            print (i)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#----------------test---------------\n",
    "hanoi = Hanoi(4)\n",
    "hanoi.playHanoi()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#3.5\n",
    "class Queue(object):\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.q=[]\n",
    "    \n",
    "    def isEmpty(self):\n",
    "        return self.q.size()==0\n",
    "    def size(self):\n",
    "        return len(self.q)\n",
    "    \n",
    "    def enqueue(self,i):\n",
    "        return self.q.insert(0,i)\n",
    "    def dequeue(self):\n",
    "        return "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "1 2 3 4 10 11\n",
      "31\n"
     ]
    }
   ],
   "source": [
    "import sys\n",
    "\n",
    "def simpleArraySum(n, ar):\n",
    "    # Complete this function\n",
    "    sum=0\n",
    "    for i in ar:\n",
    "        sum+=i\n",
    "    return sum\n",
    "\n",
    "\n",
    "\n",
    "n = int(input().strip())\n",
    "ar = list(map(int, input().strip().split(' ')))\n",
    "result = simpleArraySum(n, ar)\n",
    "print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "def solve(a0, a1, a2, b0, b1, b2):\n",
    "    # Complete this function\n",
    "    scores={'Alice':0, 'Bob':0}\n",
    "    \n",
    "    if a0>b0:\n",
    "        scores['Alice']+=1\n",
    "    elif a0<b0:\n",
    "        scores['Bob']+=1\n",
    "\n",
    "    if a1>b1:\n",
    "        scores['Alice']+=1\n",
    "    elif a1<b1:\n",
    "        scores['Bob']+=1\n",
    "        \n",
    "    if a2>b2:\n",
    "        scores['Alice']+=1\n",
    "    elif a2<b2:\n",
    "        scores['Bob']+=1\n",
    "        \n",
    "    return list(scores.values())\n",
    "\n",
    "\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1]"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solve(20,20,30,20,20,50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2]"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def twoSum(nums, target):\n",
    "    \"\"\"\n",
    "    :type nums: List[int]\n",
    "    :type target: int\n",
    "    :rtype: List[int]\n",
    "    \"\"\"\n",
    "    if len(nums)==0:\n",
    "        return False\n",
    "    \n",
    "    for i in range(len(nums)+1):\n",
    "        for j in range(i+1,len(nums)):\n",
    "            if nums[i]+nums[j]==target:\n",
    "                return [i,j]\n",
    "     \n",
    "            \n",
    "twoSum([3,2,4],6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "for i in range(3):\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a=[3,2,4]\n",
    "len(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "False\n",
      "1 2\n"
     ]
    }
   ],
   "source": [
    "\n",
    "for i in range(len(a)+1):\n",
    "    for j in range(i+1,len(a)):\n",
    "        if a[i]+a[j]==6:\n",
    "            print (i,j)\n",
    "        else:\n",
    "            print (False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [],
   "source": [
    "B=[12,28,46,32,50]\n",
    "A=[50,12,32,46,28]\n",
    "\n",
    "[1,4,3,2,0]\n",
    "d={x: i for i , x in enumerate(B)}\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{12: 0, 28: 1, 32: 3, 46: 2, 50: 4}"
      ]
     },
     "execution_count": 103,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "d\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, 4, 3, 2, 0)"
      ]
     },
     "execution_count": 99,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 0, 3, 2, 1]"
      ]
     },
     "execution_count": 106,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[d[x] for x in A]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 142,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def nums(n):\n",
    "\n",
    "    for i in str(n):\n",
    "        if i==0 or int(n)%int(i)>0:\n",
    "            return False\n",
    "        \n",
    "    return True\n",
    "        \n",
    "nums('14')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 145,
   "metadata": {},
   "outputs": [
    {
     "ename": "ZeroDivisionError",
     "evalue": "integer division or modulo by zero",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mZeroDivisionError\u001b[0m                         Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-145-429d918af76c>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m     16\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     17\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 18\u001b[1;33m \u001b[0mselfDividingNumbers\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m22\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m<ipython-input-145-429d918af76c>\u001b[0m in \u001b[0;36mselfDividingNumbers\u001b[1;34m(left, right)\u001b[0m\n\u001b[0;32m     11\u001b[0m         \u001b[0mls\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     12\u001b[0m         \u001b[1;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mrange\u001b[0m \u001b[1;33m(\u001b[0m\u001b[0mleft\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mright\u001b[0m\u001b[1;33m+\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 13\u001b[1;33m             \u001b[1;32mif\u001b[0m \u001b[0mnums\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     14\u001b[0m                 \u001b[0mls\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     15\u001b[0m         \u001b[1;32mreturn\u001b[0m \u001b[0mls\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-145-429d918af76c>\u001b[0m in \u001b[0;36mnums\u001b[1;34m(n)\u001b[0m\n\u001b[0;32m      2\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      3\u001b[0m     \u001b[1;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mstr\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mn\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 4\u001b[1;33m         \u001b[1;32mif\u001b[0m \u001b[0mi\u001b[0m\u001b[1;33m==\u001b[0m\u001b[1;36m0\u001b[0m \u001b[1;32mor\u001b[0m \u001b[0mint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mn\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m%\u001b[0m\u001b[0mint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m>\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      5\u001b[0m             \u001b[1;32mreturn\u001b[0m \u001b[1;32mFalse\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      6\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mZeroDivisionError\u001b[0m: integer division or modulo by zero"
     ]
    }
   ],
   "source": [
    "def nums(n):\n",
    "\n",
    "    for i in str(n):\n",
    "        if i==0 or int(n)%int(i)>0:\n",
    "            return False\n",
    "        \n",
    "    return True\n",
    "\n",
    "def selfDividingNumbers(left, right):\n",
    "\n",
    "        ls=[]\n",
    "        for i in range (left,right+1):\n",
    "            if nums(i):\n",
    "                ls.append(i)\n",
    "        return ls\n",
    "    \n",
    "\n",
    "selfDividingNumbers(2,22)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "metadata": {},
   "outputs": [],
   "source": [
    "def arrayPairSum(nums):\n",
    "    \"\"\"\n",
    "    :type nums: List[int]\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    nums=sorted(nums)\n",
    "    return sum(nums[::2])\n",
    "    return sum(sorted(nums[::2]))\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 177,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 177,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arrayPairSum([1,2,3,2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 223,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findComplement( num):\n",
    "        i = 1\n",
    "        while i <= num:\n",
    "            i = i << 1\n",
    "            print (i, (i - 1) ^ num)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 224,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 4\n",
      "4 6\n",
      "8 2\n"
     ]
    }
   ],
   "source": [
    "findComplement(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 303,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverseWords( s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        '''if len(s) == 0:\n",
    "            return s\n",
    "        else:\n",
    "            return reverseWords(s[1:]) + s[0]\n",
    "        return ([list(reversed(i)) for i in s.split(' ')])'''\n",
    "        return ' '.join([i[::-1] for i in s.split(' ')])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 304,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"s'teL ekat edoCteeL tsetnoc\""
      ]
     },
     "execution_count": 304,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "reverseWords(\"Let's take LeetCode contest\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 385,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findWords( words):\n",
    "    \"\"\"\n",
    "    :type words: List[str]\n",
    "    :rtype: List[str]\n",
    "    \"\"\"\n",
    "    import re\n",
    "    pat = re.compile(r'(?i)([qwertyuiop]*|[asdfghjkl]*|[zxcvbnm]*)').match\n",
    "    return list(filter(pat,words))\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 386,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Hello', 'Alaska', 'Dad', 'Peace']"
      ]
     },
     "execution_count": 386,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "findWords([\"Hello\", \"Alaska\", \"Dad\", \"Peace\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 376,
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name 're' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-376-4189729d8551>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mfilter\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mre\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mcompile\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m'(?i)([qwertyuiop]*|[asdfghjkl]*|[zxcvbnm]*)$'\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mmatch\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mwords\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mNameError\u001b[0m: name 're' is not defined"
     ]
    }
   ],
   "source": [
    "filter(re.compile('(?i)([qwertyuiop]*|[asdfghjkl]*|[zxcvbnm]*)$').match, words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 404,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random,string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 457,
   "metadata": {},
   "outputs": [],
   "source": [
    "class codec:\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.url2code={}\n",
    "        self.code2url={}\n",
    "    \n",
    "    def encode(self,longUrl):\n",
    "        \"\"\"Encodes a URL to a shortened URL.\n",
    "\n",
    "        :type longUrl: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        while longUrl not in self.url2code:\n",
    "\n",
    "            code = ''.join(random.choice(string.ascii_uppercase + string.digits) for _ in range(8))\n",
    "            if code not in self.code2url:\n",
    "                self.code2url[code]=longUrl\n",
    "                self.url2code[longUrl]=code\n",
    "\n",
    "        return 'http://tinyurl.com/'+ self.url2code[longUrl]\n",
    "    \n",
    "    def decode(self,shortUrl):\n",
    "        \n",
    "        return self.code2url[shortUrl[-8:]]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 458,
   "metadata": {},
   "outputs": [],
   "source": [
    "c=codec()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 459,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'http://tinyurl.com/PHANQKDE'"
      ]
     },
     "execution_count": 459,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c.encode('www.google.com')\n",
    "#c.decode('http://tinyurl.com/9ATNN5FV')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 461,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'www.google.com'"
      ]
     },
     "execution_count": 461,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c.decode('http://tinyurl.com/PHANQKDE')    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 483,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sol(s):\n",
    "\n",
    "    sizes=[]\n",
    "    while s:\n",
    "        i=1\n",
    "        while set(s[:i]) & set(s[i:]):\n",
    "            i+=1\n",
    "            print (set(s[:i]))\n",
    "            print (set(s[i:]))\n",
    "        sizes.append(i)\n",
    "        s=s[i:]\n",
    "        \n",
    "    \n",
    "    return sizes\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 484,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'a', 'b'}\n",
      "{'a', 'g', 'f', 'k', 'l', 'h', 'b', 'e', 'j', 'c', 'i', 'd'}\n",
      "{'a', 'b'}\n",
      "{'a', 'g', 'f', 'k', 'l', 'h', 'b', 'e', 'j', 'c', 'i', 'd'}\n",
      "{'a', 'b'}\n",
      "{'a', 'g', 'f', 'k', 'l', 'h', 'b', 'e', 'j', 'c', 'i', 'd'}\n",
      "{'a', 'c', 'b'}\n",
      "{'a', 'g', 'f', 'k', 'l', 'h', 'b', 'e', 'j', 'c', 'i', 'd'}\n",
      "{'a', 'c', 'b'}\n",
      "{'a', 'g', 'f', 'k', 'l', 'h', 'e', 'j', 'c', 'i', 'd'}\n",
      "{'a', 'c', 'b'}\n",
      "{'a', 'g', 'f', 'k', 'l', 'h', 'e', 'j', 'c', 'i', 'd'}\n",
      "{'a', 'c', 'b'}\n",
      "{'a', 'g', 'f', 'k', 'l', 'h', 'e', 'j', 'i', 'd'}\n",
      "{'a', 'c', 'b'}\n",
      "{'g', 'f', 'k', 'l', 'h', 'e', 'j', 'i', 'd'}\n",
      "{'e', 'd'}\n",
      "{'g', 'f', 'k', 'l', 'h', 'e', 'j', 'i', 'd'}\n",
      "{'e', 'f', 'd'}\n",
      "{'g', 'k', 'l', 'h', 'e', 'j', 'i', 'd'}\n",
      "{'e', 'f', 'd'}\n",
      "{'g', 'k', 'l', 'h', 'e', 'j', 'i', 'd'}\n",
      "{'e', 'f', 'g', 'd'}\n",
      "{'k', 'l', 'h', 'e', 'j', 'i', 'd'}\n",
      "{'e', 'f', 'g', 'd'}\n",
      "{'k', 'l', 'h', 'e', 'j', 'i'}\n",
      "{'e', 'f', 'g', 'd'}\n",
      "{'k', 'h', 'l', 'j', 'i'}\n",
      "{'i', 'h'}\n",
      "{'k', 'h', 'l', 'j', 'i'}\n",
      "{'j', 'i', 'h'}\n",
      "{'k', 'h', 'l', 'j', 'i'}\n",
      "{'j', 'i', 'h'}\n",
      "{'l', 'k', 'j', 'i'}\n",
      "{'k', 'j', 'i', 'h'}\n",
      "{'l', 'j', 'i'}\n",
      "{'k', 'h', 'l', 'j', 'i'}\n",
      "{'j', 'i'}\n",
      "{'k', 'h', 'l', 'j', 'i'}\n",
      "{'j'}\n",
      "{'k', 'h', 'l', 'j', 'i'}\n",
      "set()\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[9, 7, 8]"
      ]
     },
     "execution_count": 484,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sol('ababcbacadefegdehijhklij')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def countBattleships(board):\n",
    "    \"\"\"\n",
    "    :type board: List[List[str]]\n",
    "    :rtype: int\n",
    "    \"\"\"\n",
    "    row, col = len(board), len(board[0])\n",
    "    count=0\n",
    "    for i in range(row):\n",
    "        for j in range(col):\n",
    "            if board[i][j]=='X' and (i==0 or board[i-1][j]=='.') and (j==0 or board[i][j-1]=='.'):\n",
    "\n",
    "                count+=1\n",
    "\n",
    "    return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "countBattleships([[\"X\",\".\",\".\",\"X\"],[\".\",\".\",\".\",\"X\"],[\".\",\".\",\".\",\"X\"]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "def countBits( num):\n",
    "    \"\"\"\n",
    "    :type num: int\n",
    "    :rtype: List[int]\n",
    "    \"\"\"\n",
    "    ls=[]\n",
    "    for i in  range(num+1):\n",
    "        \n",
    "        ls.append(bin(i)[2:].count('1'))\n",
    "        \n",
    "    return ls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 1, 2, 1, 2]"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "countBits(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "people=[[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[7, 1], [7, 0], [6, 1], [5, 2], [5, 0], [4, 4]]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "insertion_order = sorted(people, reverse=True)\n",
    "insertion_order"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "insertion_order = sorted(people, key=lambda (h,k): (-h,k))\n",
    "insertion_order\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[5, 0], [7, 0], [6, 1], [5, 2], [4, 4], [7, 1]]"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ordered_line = []\n",
    "for person in insertion_order:\n",
    "    ordered_line.insert(person[1], person)\n",
    "ordered_line"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "ordered_line = []\n",
    "for person in insertion_order:\n",
    "    ordered_line.insert(person[1], person)\n",
    "ordered_line"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reconstructQueue(self, people):\n",
    "\n",
    "    if not people:\n",
    "        return []\n",
    "    ordered_line = []\n",
    "\n",
    "    insertion_order = sorted(people, key = lambda (h,k): (-h,k))\n",
    "\n",
    "    for person in insertion_order:\n",
    "        ordered_line.insert(person[1], person)\n",
    "\n",
    "    return ordered_line\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "metadata": {},
   "outputs": [],
   "source": [
    "def countSmaller( nums):\n",
    "    \n",
    "    dic=dict()\n",
    "    ls=[]\n",
    "    \n",
    "    '''    for i in range(len(nums)):\n",
    "        dic[nums[i]]=0'''\n",
    "    \n",
    "    for i in nums:\n",
    "        dic[i]=0\n",
    "        \n",
    "    for i in range(len(nums)+1):\n",
    "        for j in range(i+1,(len(nums))):\n",
    "            \n",
    "            if nums[i]>nums[j]:\n",
    "                dic[nums[i]]+=1\n",
    "                ls.append(dic[nums[i]])\n",
    "    #for k, v in dic.items():\n",
    "        \n",
    "    \n",
    "    return dic,dic.values(),dic.keys()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "({1: 0, 2: 1, 5: 2, 6: 1}, [0, 1, 2, 1], [1, 2, 5, 6])"
      ]
     },
     "execution_count": 138,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "countSmaller([5, 2, 6, 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 242,
   "metadata": {},
   "outputs": [],
   "source": [
    "import operator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 251,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findDuplicates(nums):\n",
    "    \n",
    "    if set(nums)==nums:\n",
    "        return False\n",
    "    dic=dict()\n",
    "    for i in nums:\n",
    "        dic[i]=0\n",
    "    for i in nums:\n",
    "        dic[i]+=1\n",
    "  \n",
    "    sorted_x = sorted(dic.items(), key=operator.itemgetter(1))\n",
    "        \n",
    "    \n",
    "    return sorted_x[0][0]\n",
    "#sorted(dic.keys(),reverse=True)[0] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 252,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 252,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "findDuplicates([1,1,2,3,3,4,4,8,8])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 256,
   "metadata": {},
   "outputs": [],
   "source": [
    "def countSubstrings(s):\n",
    "    \n",
    "    ls=[]\n",
    "    for i in range(len(s)):\n",
    "        ls= s[:i]\n",
    "        for j in ls:\n",
    "            if ls==ls[::-1]:\n",
    "                print ls\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 257,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a\n"
     ]
    }
   ],
   "source": [
    "countSubstrings(\"abc\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 267,
   "metadata": {},
   "outputs": [],
   "source": [
    "def optimalDivision(nums):\n",
    "    \n",
    "    a=map(str,nums)\n",
    "    \n",
    "    return '({}/({}))'.format(a[0],'/'.join(a[1:]))\n",
    "    \n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 268,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'(1000/(100/10/2))'"
      ]
     },
     "execution_count": 268,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "optimalDivision([1000,100,10,2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 352,
   "metadata": {},
   "outputs": [],
   "source": [
    "import string, collections, re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 366,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 384,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "''"
      ]
     },
     "execution_count": 384,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "shortestCompletingWord(\"1s3 456\",[\"looks\", \"pest\", \"stew\", \"show\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 379,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 379,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "contains(\"1s3 456\",\"pest\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 376,
   "metadata": {},
   "outputs": [],
   "source": [
    "def shortestCompletingWord( licensePlate, words):\n",
    "        regex = re.compile('[^a-zA-Z]')\n",
    "        licensePlate = regex.sub('', licensePlate)\n",
    "        counter = collections.Counter(licensePlate.lower())\n",
    "        res = ''\n",
    "        for word in words:\n",
    "            if contains(counter, word):\n",
    "                if res == '' or len(word) < len(res):\n",
    "                    res = word\n",
    "        return res\n",
    "\n",
    "\n",
    "def contains( counter1, w2):\n",
    "    c2 = collections.Counter(w2)\n",
    "    c2.subtract(counter1)\n",
    "    return all(map(lambda x: x >= 0,c2.values()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 383,
   "metadata": {},
   "outputs": [],
   "source": [
    "def shortestCompletingWord(licensePlate, words):\n",
    "    \n",
    "    import string, collections, re\n",
    "    regex = re.compile('[^a-zA-Z]')\n",
    "    licensePlate = regex.sub('',licensePlate)\n",
    "    counter = collections.Counter(licensePlate.lower())\n",
    "    res=''\n",
    "    \n",
    "    for word in words:\n",
    "        if contains(counter,word):\n",
    "            if res=='' or len(word)< len(res):\n",
    "                re=word\n",
    "    return res\n",
    "\n",
    "\n",
    "def contains(counter1,w2):\n",
    "    \n",
    "    c2=collections.Counter(w2)\n",
    "    #print c2\n",
    "    c2.subtract(counter1)\n",
    "    #print c2\n",
    "    \n",
    "    return all(map(lambda x: x>=0, c2.values()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 425,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dailyTemperatures(temperatures):\n",
    "    \n",
    "    temp={}\n",
    "    temp2={}\n",
    "    for i , t in enumerate(temperatures):\n",
    "        temp[i]= t\n",
    "    print temp\n",
    "    results = [0]*len(temperatures)\n",
    "    for i in range(len(temperatures)-1,-1,-1):\n",
    "        temp = temperatures[i]\n",
    "        day = str('inf')\n",
    "        \n",
    "        for j in range(temp+1,101):\n",
    "            if j in temp2:\n",
    "                day = min(day, temp2[j]-i)\n",
    "                print day\n",
    "        if day!=str('inf'):\n",
    "            results[i]=day\n",
    "            \n",
    "        temp2[temp]=i\n",
    "    return results\n",
    "        \n",
    "    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 426,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{0: 73, 1: 74, 2: 75, 3: 71, 4: 69, 5: 72, 6: 76, 7: 73}\n",
      "2\n",
      "1\n",
      "1\n",
      "1\n",
      "1\n",
      "2\n",
      "2\n",
      "2\n",
      "4\n",
      "1\n",
      "1\n",
      "1\n",
      "1\n",
      "1\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[1, 1, 4, 2, 1, 1, 0, 0]"
      ]
     },
     "execution_count": 426,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 465,
   "metadata": {},
   "outputs": [],
   "source": [
    "import collections\n",
    "def singleNumber(nums):\n",
    "    \n",
    "    dic= collections.Counter(nums)\n",
    "    #print dic\n",
    "    sorted_dic = sorted(dic.items(),reverse=False, key=operator.itemgetter(1))\n",
    "    #print list(sorted_dic[:2])\n",
    "    print [x[0] for x in list(sorted_dic[:2])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 466,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Counter({1: 2, 2: 2, 3: 1, 5: 1})\n",
      "[(3, 1), (5, 1)]\n",
      "[3, 5]\n"
     ]
    }
   ],
   "source": [
    "singleNumber([1, 2, 1, 3, 2, 5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 504,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os, sys, collections, operator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 520,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findDuplicate(paths):\n",
    "    \n",
    "    dic={}\n",
    "    ls=[]\n",
    "    for lines in paths:\n",
    "        data = lines.split()\n",
    "        root=data[0]\n",
    "        ls.append(data[-1])\n",
    "    print ls\n",
    "    counter=collections.Counter(ls)\n",
    "    print counter\n",
    "    return sorted(counter.items(), reverse=True)[0][0]\n",
    "    \n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 521,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['2.txt(efgh)', '3.txt(abcd)', '4.txt(efgh)', '4.txt(efgh)']\n",
      "Counter({'4.txt(efgh)': 2, '2.txt(efgh)': 1, '3.txt(abcd)': 1})\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'4.txt(efgh)'"
      ]
     },
     "execution_count": 521,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "findDuplicate([\"root/a 1.txt(abcd) 2.txt(efgh)\", \"root/c 3.txt(abcd)\", \"root/c/d 4.txt(efgh)\", \"root 4.txt(efgh)\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 482,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'C:\\\\Users\\\\User\\\\Downloads\\\\Compressed\\\\ctci-master\\\\python'"
      ]
     },
     "execution_count": 482,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "os.getcwd()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 473,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['.ipynb_checkpoints',\n",
       " 'Chapter 1',\n",
       " 'Chapter 2',\n",
       " 'Chapter 3',\n",
       " 'Chapter 4',\n",
       " 'Chapter 9',\n",
       " 'CTCI-Python-ch1.ipynb',\n",
       " 'CTCI-Python-ch2.ipynb',\n",
       " 'CTCI-Python-ch3.ipynb']"
      ]
     },
     "execution_count": 473,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "os.listdir('.')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]\n",
    "d =collections.defaultdict(list)\n",
    "for k,v in s:\n",
    "    d[v]=k\n",
    "d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 530,
   "metadata": {},
   "outputs": [],
   "source": [
    "def findDuplicate(paths):\n",
    "    \n",
    "    M = collections.defaultdict(list)\n",
    "    ls=[]\n",
    "    for lines in paths:\n",
    "        data = lines.split()\n",
    "        root=data[0]\n",
    "        for file in data[1:]:\n",
    "            name, _, content = file.partition('(')\n",
    "            print name,_,content\n",
    "            M[content[:-1]].append(root + '/' + name)\n",
    "    print M\n",
    "\n",
    "        #return [x for x in M.values() if len(x) > 1]\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 531,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.txt ( abcd)\n",
      "2.txt ( efgh)\n",
      "3.txt ( abcd)\n",
      "4.txt ( efgh)\n",
      "4.txt ( efgh)\n",
      "defaultdict(<type 'list'>, {'abcd': ['root/a/1.txt', 'root/c/3.txt'], 'efgh': ['root/a/2.txt', 'root/c/d/4.txt', 'root/4.txt']})\n"
     ]
    }
   ],
   "source": [
    "findDuplicate([\"root/a 1.txt(abcd) 2.txt(efgh)\", \"root/c 3.txt(abcd)\", \"root/c/d 4.txt(efgh)\", \"root 4.txt(efgh)\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 548,
   "metadata": {},
   "outputs": [],
   "source": [
    "def minMoves2( nums):\n",
    "    median = sorted(nums)[len(nums) / 2]\n",
    "    print median\n",
    "    return list(abs(num - median) for num in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 547,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "'int' object is not iterable",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-547-9f7909964a6d>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mminMoves2\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m3\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m<ipython-input-546-aba3a94ec0ea>\u001b[0m in \u001b[0;36mminMoves2\u001b[1;34m(nums)\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[1;32mdef\u001b[0m \u001b[0mminMoves2\u001b[0m\u001b[1;33m(\u001b[0m \u001b[0mnums\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 2\u001b[1;33m     \u001b[0mmedian\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0msorted\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mnums\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mlen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mnums\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m/\u001b[0m \u001b[1;36m2\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      3\u001b[0m     \u001b[1;32mprint\u001b[0m \u001b[0mmedian\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      4\u001b[0m     \u001b[1;32mreturn\u001b[0m \u001b[0mlist\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mabs\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mnum\u001b[0m \u001b[1;33m-\u001b[0m \u001b[0mmedian\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mnum\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mnums\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mTypeError\u001b[0m: 'int' object is not iterable"
     ]
    }
   ],
   "source": [
    "minMoves2([1,2,3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "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.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}