Practice_algorithms-Copy1.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#quickSort\n",
    "\n",
    "def partition(A,p,r):\n",
    "    i=p-1\n",
    "    x=A[r]\n",
    "    for j in range(p,r):\n",
    "        if A[j]<=x:\n",
    "            i=i+1\n",
    "            tmp=A[i]\n",
    "            A[i]=A[j]\n",
    "            A[j]=tmp\n",
    "    tmp=A[i+1]\n",
    "    A[i+1]=A[r]\n",
    "    A[r]=tmp\n",
    "    return i+1\n",
    "        \n",
    "def quicksort(A,p,r):\n",
    "    if p<r:\n",
    "        q=partition(A,p,r)\n",
    "        quicksort(A,p,q-1)\n",
    "        quicksort(A,q+1,r)\n",
    "\n",
    "a=[2,8,7,3,5,6,4]\n",
    "quicksort(a,0,len(a)-1)\n",
    "print(a)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3, 4, 5, 6, 7, 8]\n"
     ]
    }
   ],
   "source": [
    "#mergesort\n",
    "def mergesort(A):\n",
    "    if len(A)<=1:\n",
    "        return A\n",
    "    mid=len(A)//2\n",
    "    l=mergesort(A[0:mid])\n",
    "    r=mergesort(A[mid:])\n",
    "    return merge(l,r)\n",
    "\n",
    "def merge(l,r):\n",
    "    s=[None]*(len(l)+len(r))\n",
    "    i=0\n",
    "    j=0\n",
    "    k=0\n",
    "    while(i<len(l) and j<len(r)):\n",
    "        if l[i]<=r[j]:\n",
    "            s[k]=l[i]\n",
    "            i+=1\n",
    "        else:\n",
    "            s[k]=r[j]\n",
    "            j+=1\n",
    "        k+=1\n",
    "    while(i<len(l)):\n",
    "        s[k]=l[i]\n",
    "        i+=1\n",
    "        k+=1\n",
    "    while(j<len(r)):\n",
    "        s[k]=r[j]\n",
    "        j+=1\n",
    "        k+=1\n",
    "    return s\n",
    "\n",
    "a=[2,8,7,3,5,6,4]\n",
    "a1=[1,3,7,9]\n",
    "a2=[2,5,8,20,30]\n",
    "print(mergesort(a))\n",
    "#print(merge(a1,a2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-3, 2, 5, 8, 20, 30, 100, 500]\n"
     ]
    }
   ],
   "source": [
    "#bublesort\n",
    "\n",
    "def bublesort(a):\n",
    "    for i in range(len(a)):\n",
    "        for j in range(i+1, len(a)):\n",
    "            if a[i]> a[j]:\n",
    "                t=a[i]\n",
    "                a[i]=a[j]\n",
    "                a[j]=t\n",
    "    return a\n",
    "                \n",
    "a2=[500,2,100,5,-3,8,20,30]                \n",
    "print(bublesort(a2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "n=[2,3,6,7]\n",
    "result=[[]]\n",
    "def comb(s):\n",
    "    global result\n",
    "    if len(s)==0: return\n",
    "    result.append(s)\n",
    "    print(s)\n",
    "    for i in range(0, len(s)):\n",
    "        t = s[0:i] + s[i + 1:]\n",
    "        comb(t)\n",
    "\n",
    "res = [[]]\n",
    "comb(n)\n",
    "result=np.unique(result)\n",
    "#print(result)\n",
    "print(len(result))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[]\n",
      "2\n",
      "1\n",
      "(True, 1)\n"
     ]
    }
   ],
   "source": [
    "#Trie Implementation\n",
    "#print (ord('a'))\n",
    "#print (chr(97))\n",
    "class Trie:\n",
    "    def __init__(self,val=''):\n",
    "        self.isEnd=0\n",
    "        self.cnt=0\n",
    "        self.children={}\n",
    "        self.val=val\n",
    "    def add(self,ch,isEnd):\n",
    "        if ch not in self.children.keys():\n",
    "            self.children[ch]=Trie(ch)\n",
    "        self.cnt=self.cnt+1\n",
    "        self.isEnd=isEnd\n",
    "        return self.children[ch]\n",
    "\n",
    "def insert(strs, root):\n",
    "    isEnd=0\n",
    "    if len(strs)==1:\n",
    "        isEnd=1\n",
    "    chld=root.add(strs[0],isEnd)\n",
    "    isEnd=0\n",
    "    for i in range(1,len(strs)):\n",
    "        if (i==len(strs)-1):\n",
    "            isEnd=1\n",
    "        chld=chld.add(strs[i],isEnd)\n",
    "\n",
    "def traverse(root,path,L):\n",
    "    if root is None:\n",
    "        return\n",
    "    chld=root.children\n",
    "    path.append(root.val)\n",
    "    if chld is None or len(chld.keys())==0:\n",
    "        L.append(path)\n",
    "        return\n",
    "\n",
    "    for k in chld.keys():\n",
    "        #print(k)\n",
    "        traverse(chld[k],path+[],L)\n",
    "def search(root,strs):\n",
    "    for i in range(len(strs)):\n",
    "        chld=root.children\n",
    "        if strs[i] not in chld.keys():\n",
    "            return False\n",
    "        root=chld[strs[i]]\n",
    "        print(root.cnt)\n",
    "    return True, root.cnt\n",
    "    \n",
    "\n",
    "p=[]\n",
    "root=Trie()\n",
    "insert(\"bear\", root)\n",
    "insert(\"bell\",root)\n",
    "insert(\"sport\",root)\n",
    "insert(\"stop\",root)\n",
    "L=[]\n",
    "#traverse(root,[],L)\n",
    "print(L)\n",
    "print(search(root,\"sp\"))\n",
    "\n",
    "    \n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "et\n",
      "tx\n",
      "tt\n",
      "ex\n",
      "xt\n",
      "xe\n",
      "te\n"
     ]
    }
   ],
   "source": [
    "from itertools import permutations \n",
    "#print(list(permutations(\"text\",2)))\n",
    "d=set(list(permutations(\"text\",2)))\n",
    "for p in d:\n",
    "    print(\"\".join(p))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sorting Object Using Priority Queue\n",
    "========"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "khaled 300\n",
      "bh 150\n",
      "Shahinur 120\n",
      "jeff 110\n"
     ]
    }
   ],
   "source": [
    "import queue\n",
    "class Employee:\n",
    "    def __init__(self, name=None,salary=0, age=0):\n",
    "        self.name=name\n",
    "        self.salary=salary\n",
    "        self.age=age\n",
    "\n",
    "emp1=Employee(\"Shahinur\", -120, 35)\n",
    "emp2=Employee(\"jeff\", -110, 45)\n",
    "emp3=Employee(\"khaled\", -300, 45)\n",
    "emp4=Employee(\"bh\", -150, 40)\n",
    "pq=queue.PriorityQueue()\n",
    "pq.put((emp1.salary,emp1))\n",
    "pq.put((emp2.salary,emp2))\n",
    "pq.put((emp3.salary,emp3))\n",
    "pq.put((emp4.salary,emp4))\n",
    "\n",
    "while(pq.empty()==False):\n",
    "    salary, emp=pq.get()\n",
    "    print(emp.name,-1*salary)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n"
     ]
    }
   ],
   "source": [
    "a=10\n",
    "b=12\n",
    "print (b & a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9\n",
      "<class 'ZeroDivisionError'>\n",
      "5.0\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "import sys\n",
    "\n",
    "arr=np.random.randint(10)\n",
    "print(arr)\n",
    "try:\n",
    "    for i in range(10):\n",
    "        tx=10/0\n",
    "except:\n",
    "    print (sys.exc_info()[0])\n",
    "finally:\n",
    "    print(tx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "queue is full\n",
      "10\n",
      "11\n"
     ]
    }
   ],
   "source": [
    "a=[[]]*10\n",
    "\n",
    "size=5\n",
    "queue=[]*5\n",
    "\n",
    "def enqueue(e):\n",
    "    if len(queue)<size:\n",
    "        queue.append(e)\n",
    "    else:\n",
    "        print(\"queue is full\")\n",
    "def deq():\n",
    "    if len(queue)>0:\n",
    "        return queue.pop(0)\n",
    "    else:\n",
    "        print(\"Queue is empty\")\n",
    "        return None\n",
    "\n",
    "enqueue(10)\n",
    "enqueue(11)\n",
    "enqueue(12)\n",
    "enqueue(13)\n",
    "enqueue(14)\n",
    "enqueue(17)\n",
    "print(deq())\n",
    "enqueue(18)\n",
    "print(deq())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "300\n"
     ]
    }
   ],
   "source": [
    "class staticvar:\n",
    "    val=0\n",
    "    def __init__(self, name, salary):\n",
    "        self.name=name\n",
    "        self.salary=salary\n",
    "        \n",
    "staticvar.val=100\n",
    "o1=staticvar(\"Sh\", 120)\n",
    "o1.val=500\n",
    "o2=staticvar(\"jJ\", 130)\n",
    "o2.val=300\n",
    "print(o2.val)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Child.. name 100 3.4\n"
     ]
    }
   ],
   "source": [
    "#polymorphism and inheritance\n",
    "class person:\n",
    "    def __init__(self, name, salary):\n",
    "        self.name=name\n",
    "        self.salary=salary\n",
    "    def printf(self):\n",
    "        print(\"base class\",self.name,self.salary)\n",
    "class student(person):\n",
    "    def __init__(self, name,salary, cgpa):\n",
    "        super().__init__( name, salary)\n",
    "        self.cgpa=cgpa\n",
    "    def printf(self):\n",
    "        print(\"Child..\",self.name,self.salary,self.cgpa)\n",
    "\n",
    "obj=student(\"name\",100,3.4)\n",
    "obj.printf()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "ename": "Exception",
     "evalue": "Dont even think it. Its Singleton",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mException\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-44-ea847e5ea7a9>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m     16\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     17\u001b[0m \u001b[0mo1\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0msingleton\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 18\u001b[0;31m \u001b[0mo2\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0msingleton\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-44-ea847e5ea7a9>\u001b[0m in \u001b[0;36m__init__\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m     10\u001b[0m     \u001b[0;32mdef\u001b[0m \u001b[0m__init__\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     11\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0msingleton\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0minstance\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m             \u001b[0;32mraise\u001b[0m \u001b[0mException\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Dont even think it. Its Singleton\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     13\u001b[0m         \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     14\u001b[0m              \u001b[0msingleton\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0minstance\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mException\u001b[0m: Dont even think it. Its Singleton"
     ]
    }
   ],
   "source": [
    "#Singleton\n",
    "\n",
    "class singleton:\n",
    "    instance=None\n",
    "    @staticmethod\n",
    "    def getinstance():\n",
    "        if singleton.instance is None:\n",
    "            singleton.instance=singleton()\n",
    "        return singleton.instance\n",
    "    def __init__(self):\n",
    "        if singleton.instance is not None:\n",
    "            raise Exception(\"Dont even think it. Its Singleton\")\n",
    "        else:\n",
    "             singleton.instance=self\n",
    "        \n",
    "\n",
    "o1=singleton()\n",
    "o2=singleton()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n",
      "8\n",
      "9\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "def testgen():\n",
    "    num=0\n",
    "    while True:\n",
    "        yield num\n",
    "        num=num+1\n",
    "\n",
    "gen=testgen()\n",
    "for i,val in enumerate (gen):\n",
    "    if i >10:\n",
    "        break\n",
    "    print(val)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "sun mon tue wed thu fri sat\n"
     ]
    }
   ],
   "source": [
    "weekdays = ['sun','mon','tue','wed','thu','fri','sat']\n",
    "listAsString = ' '.join(weekdays)\n",
    "\n",
    "print(listAsString)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "45\n",
      "453\n",
      "4531\n",
      "4531\n"
     ]
    }
   ],
   "source": [
    "num=1354\n",
    "rev=0\n",
    "while num>0:\n",
    "    rev=rev*10+num%10\n",
    "    print(rev)\n",
    "    num=int(num/10)\n",
    "print(rev)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 165,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[2, 6, 3, 4, 8], [2, 6, 3, 7, 4, 8], [2, 6, 3, 7, 8], [2, 6, 7, 4, 8], [2, 6, 7, 8]]\n",
      "1-->2-->6-->7-->4-->\n",
      "{1, 2, 3, 4, 5, 6, 7, 8}\n"
     ]
    }
   ],
   "source": [
    "import sys\n",
    "import queue\n",
    "graph={}\n",
    "num_vert=8\n",
    "class node:\n",
    "    def __init__(self, val=0,dist=sys.maxsize,isvisied=False,parent=None,edge_length=1):\n",
    "        self.val=val\n",
    "        self.dist=dist\n",
    "        self.isvisied=isvisied\n",
    "        self.parent=parent\n",
    "        self.neighbor=[]\n",
    "        self.edge_length=1\n",
    "def add_edges(source,dest):\n",
    "    if source in graph.keys():\n",
    "        sn=graph[source]\n",
    "    else:\n",
    "        sn=node(val=source)\n",
    "        graph[source]=sn\n",
    "    if dest in graph.keys():\n",
    "        dt=graph[dest]\n",
    "    else:\n",
    "        dt=node(val=dest)\n",
    "        graph[dest]=dt\n",
    "    sn.neighbor.append(dt)\n",
    "    #dt.neighbor.append(sn)\n",
    "    \n",
    "add_edges(1,2)\n",
    "add_edges(1,5)\n",
    "add_edges(2,6)\n",
    "add_edges(6,3)\n",
    "add_edges(6,7)\n",
    "add_edges(3,4)\n",
    "add_edges(3,7)\n",
    "add_edges(7,4)\n",
    "add_edges(7,8)\n",
    "add_edges(4,8)\n",
    "#print(len(graph[7].neighbor))\n",
    "\n",
    "def BFS(source):\n",
    "    node=graph[source]\n",
    "    node.parent=None\n",
    "    node.dist=0\n",
    "    node.isvisied=True\n",
    "    q=[]\n",
    "    q.append(node)\n",
    "    while(len(q)>0):\n",
    "        nd=q.pop(0)\n",
    "        for child in nd.neighbor:\n",
    "            if child.isvisied==False:\n",
    "                q.append(child)\n",
    "                child.isvisied=True\n",
    "                child.parent=nd\n",
    "                child.dist=nd.dist+1\n",
    "\n",
    "                \n",
    "def shortest_path(source,dest):\n",
    "    pq=queue.PriorityQueue()\n",
    "    sn=graph[source]\n",
    "    sn.dist=0\n",
    "    sn.parent=None\n",
    "    dn=graph[dest]\n",
    "    S=set()\n",
    "    for nd in graph.keys():\n",
    "        pq.put((nd,graph[nd]))\n",
    "    while(pq.empty()==False):\n",
    "        dist,node=pq.get()\n",
    "        S.add(node.val)\n",
    "        for chld in node.neighbor:\n",
    "            if chld.dist>node.dist+node.edge_length:\n",
    "                chld.dist=node.dist+node.edge_length\n",
    "                chld.parent=node\n",
    "    \n",
    "    path=\"\"\n",
    "    while(dn.parent is not None or dn.parent==sn):\n",
    "        path= str(dn.val)+\"-->\"+path\n",
    "        dn=dn.parent\n",
    "    print(str(source)+\"-->\"+path)\n",
    "    print(S)\n",
    "    \n",
    "        \n",
    "    \n",
    "#BFS(2)   \n",
    "def find_path(s, d, L, C) :\n",
    "    if s.val==d.val or s is None:\n",
    "        C.append(d.val)\n",
    "        L.append(C)\n",
    "        return L\n",
    "    s.isvisied=True\n",
    "    C.append(s.val)\n",
    "    for chld in s.neighbor:\n",
    "        find_path(chld,d,L,C+[])\n",
    "    return \n",
    "\n",
    "def allpaths(source, dest):\n",
    "    if source not in graph.keys() or dest not in graph.keys():\n",
    "        print(\"no path\")\n",
    "        return\n",
    "    else:\n",
    "        sn=graph[source]\n",
    "        dn=graph[dest]\n",
    "        L=[]\n",
    "        find_path(sn,dn,L,[])\n",
    "        print(L)\n",
    "\n",
    "allpaths(2,8)  \n",
    "shortest_path(1,4)\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[2 2 1 2 2 2 1 1 2 1]\n",
      " [2 2 2 2 1 1 2 1 1 2]\n",
      " [1 2 2 1 2 2 1 1 1 2]\n",
      " [2 1 2 2 2 1 1 1 2 1]\n",
      " [2 1 1 1 1 1 2 2 1 1]\n",
      " [1 2 2 1 1 1 1 1 1 2]\n",
      " [2 1 2 2 2 1 1 2 1 2]\n",
      " [2 2 2 1 2 1 1 2 1 2]\n",
      " [2 2 2 2 2 2 2 2 2 1]\n",
      " [1 1 2 1 2 1 1 2 1 2]]\n"
     ]
    }
   ],
   "source": [
    "import pickle\n",
    "import numpy as np\n",
    "dicts={}\n",
    "ss=np.random.randint(1,3,(10,10))\n",
    "tt=np.random.randint(1,3,(10,10))\n",
    "dicts[\"salam\"]=ss\n",
    "dicts[\"john\"]=tt\n",
    "\n",
    "with open(\"test.pickle\",\"wb\") as f:\n",
    "    pickle.dump(dicts,f)\n",
    "\n",
    "with open(\"test.pickle\",\"rb\") as f:\n",
    "    test=pickle.load(f)   \n",
    "print(test[\"salam\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 179,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 9 10 12]\n"
     ]
    }
   ],
   "source": [
    "a = np.array([[12, 15], [10, 1],[9, 20]])\n",
    "arr1 = np.sort(a, axis = 0)\n",
    "print(arr1[:,0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 189,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 30, 4, 4, 3, 6, 0, 3, 0, 6]\n",
      "[0, 0, 0, 0, 1, 30, 4, 4, 3, 6]\n"
     ]
    }
   ],
   "source": [
    "arr=[1,30,4,0,4,0,0,3,0,6]\n",
    "pos=0\n",
    "for i in range(len(arr)):\n",
    "    if arr[i]!=0:\n",
    "        arr[pos]=arr[i]\n",
    "        pos+=1\n",
    "\n",
    "print(arr)\n",
    "\n",
    "arr=[1,30,4,0,4,0,0,3,0,6]\n",
    "pos=len(arr)-1\n",
    "for i in range(len(arr)-1,-1,-1):\n",
    "    if arr[i]!=0:\n",
    "        arr[pos]=arr[i]\n",
    "        pos-=1\n",
    "while(pos>=0):\n",
    "    arr[pos]=0\n",
    "    pos-=1\n",
    "print(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 197,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 8], [10, 20]]\n"
     ]
    }
   ],
   "source": [
    "l=[[1, 5],[1,6], [3, 7], [4, 6], [6, 8], [10,15],[12,20]]\n",
    "i=1\n",
    "\n",
    "while i<len(l):\n",
    "    if l[i-1][0]==l[i][0]:\n",
    "        l[i-1][1]=max(l[i-1][1],l[i][1])\n",
    "        l.pop(i)\n",
    "        continue\n",
    "    if l[i-1][1]>l[i][0] and l[i-1][1]<l[i][1]:\n",
    "        l[i-1][1]=l[i][1]\n",
    "        l.pop(i)\n",
    "        continue\n",
    "    if l[i-1][1]>l[i][1]:\n",
    "        l.pop(i)\n",
    "        continue\n",
    "    i+=1\n",
    "print(l)\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}