Data_Structure_Stacks.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Minimum Element"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "N = input()\n",
    "arr = [0]\n",
    "\n",
    "for i in range(N):\n",
    "    ty = sys.stdin.readline()\n",
    "    if int(ty[0]) == 1:\n",
    "        [x,y] = map(int, ty.strip().split(\" \"))\n",
    "        arr.append(max(y, arr[-1]))\n",
    "        \n",
    "    elif int(ty[0]) == 2:\n",
    "        if(len(arr)!= 0):\n",
    "            arr.pop()\n",
    "    else:\n",
    "        # print(max(arr)) #max function can get really slow when the list is really large\n",
    "        print(arr[-1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ballanced Bracket"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "\n",
    "dict = {'(':')', '[':']', '{':'}'}\n",
    "\n",
    "def ballance(ss):\n",
    "    arr = []\n",
    "    # count = 0\n",
    "    for i in ss:\n",
    "        if i in dict:\n",
    "            arr.append(dict[i])\n",
    "        else:\n",
    "            if not arr or i != arr.pop():\n",
    "                return False\n",
    "    \n",
    "    if len(arr) == 0:   \n",
    "        return True\n",
    "\n",
    "t = int(raw_input().strip())\n",
    "\n",
    "for a0 in xrange(t):\n",
    "    s = raw_input().strip()\n",
    "    if ballance(s):\n",
    "        print('YES')\n",
    "    else:\n",
    "        print('NO')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Equal Stacks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "\n",
    "n1,n2,n3 = raw_input().strip().split(' ')\n",
    "n1,n2,n3 = [int(n1),int(n2),int(n3)]\n",
    "\n",
    "# h1, h2, h3 are three lists\n",
    "h1 = map(int,raw_input().strip().split(' '))\n",
    "h2 = map(int,raw_input().strip().split(' '))\n",
    "h3 = map(int,raw_input().strip().split(' '))\n",
    "\n",
    "count1 = sum(h1)\n",
    "count2 = sum(h2)\n",
    "count3 = sum(h3)\n",
    "# count = [count1, count2, count3]\n",
    "\n",
    "while not (count1 == count2 == count3):\n",
    "    if count1 == max(count1, count2, count3):\n",
    "        count1 -= h1.pop(0)\n",
    "    elif count2 == max(count1, count2, count3):\n",
    "        count2 -= h2.pop(0)\n",
    "    elif count3 == max(count1, count2, count3):\n",
    "        count3 -= h3.pop(0)\n",
    "\n",
    "print(count1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Game of Two Stacks"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "g = int(raw_input().strip())\n",
    "for a0 in xrange(g):\n",
    "    n,m,x = raw_input().strip().split(' ')\n",
    "    n,m,x = [int(n),int(m),int(x)]\n",
    "    a = map(int, raw_input().strip().split(' '))\n",
    "    b = map(int, raw_input().strip().split(' '))\n",
    "    # your code goes here\n",
    "    count = 0 #record the number of integers removed from two stacks\n",
    "    # total = 0 #record the sum of the integers removed from the two stacks\n",
    "    i,j,temp_sum = 0,0,0\n",
    "    while(i<n and temp_sum + a[i] <= x):\n",
    "        temp_sum += a[i]\n",
    "        i += 1\n",
    "    count = i\n",
    "    while(j<m and i>=0):\n",
    "        temp_sum += b[j]\n",
    "        j += 1\n",
    "        while (temp_sum > x and i>0):\n",
    "            i -= 1\n",
    "            temp_sum -= a[i]\n",
    "            \n",
    "        if(temp_sum <= x and i+j > count):\n",
    "            count = i + j\n",
    "    print(count)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Largest Rectangle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# this method is more like a binary search\n",
    "\n",
    "import sys \n",
    "\n",
    "N = int(raw_input().strip()) #number of buildings\n",
    "H = map(int, raw_input().strip().split(\" \")) #list of the height of each building\n",
    "\n",
    "def find_Max(h):\n",
    "    if h:\n",
    "        k = len(h)\n",
    "        temp_max = k*min(h)\n",
    "        i = h.index(min(h))\n",
    "        h_left = h[:i]\n",
    "        left_max = find_Max(h_left)\n",
    "        if temp_max < left_max:\n",
    "            temp_max = left_max\n",
    "        if i+1 < k:\n",
    "            h_right = h[i+1:]\n",
    "            right_max = find_Max(h_right)\n",
    "            if temp_max < right_max:\n",
    "                temp_max = right_max\n",
    "        return temp_max\n",
    "    else:\n",
    "        return 0\n",
    "    \n",
    "print(find_Max(H))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Simple Text Editor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "S = str()\n",
    "Q = int(raw_input()) # number of operations\n",
    "\n",
    "last = [] #record last operation 1 or 2\n",
    "# slast = [] #record second last operation 1 or 2\n",
    "lstr = [] #record the last string\n",
    "# slstr = [] #record the second last string\n",
    "\n",
    "def add_str(s1, s2):\n",
    "    s1 += s2\n",
    "    lstr.append(s2)\n",
    "    last.append(1)\n",
    "    return s1\n",
    "    \n",
    "def delete_str(s1, s2):\n",
    "    k = int(s2)\n",
    "    lstr.append(s1[-k:])  \n",
    "    s1 = s1[:-k]\n",
    "    last.append(2)\n",
    "    return s1\n",
    "\n",
    "def print_k(s1, s2):\n",
    "    print(s1[int(s2)-1])\n",
    "\n",
    "def undo_prev(s):\n",
    "    if last[-1] == 1: #delete the str added to S\n",
    "        temp = len(lstr[-1])\n",
    "        s = s[:-temp]\n",
    "        last.pop()\n",
    "        lstr.pop()\n",
    "        return s\n",
    "    \n",
    "    elif last[-1] == 2: #add the deleted str back to S\n",
    "        s += lstr[-1]\n",
    "        last.pop()\n",
    "        lstr.pop()\n",
    "        return s\n",
    "\n",
    "for _ in xrange(Q):\n",
    "    \n",
    "    ss = raw_input().strip().split()\n",
    "    # print(ss)\n",
    "    if ss[0] == '1': #add string to S\n",
    "        S = add_str(S, ss[1])\n",
    "        # print(S, last[-1], lstr[-1])\n",
    "    elif ss[0] == '2': #delete string from S\n",
    "        S = delete_str(S, ss[1])\n",
    "    elif ss[0] == '3': #print kth character in S\n",
    "        print_k(S, ss[1])\n",
    "        # print(S)\n",
    "    else: #undo the last operation 1 or 2\n",
    "        S = undo_prev(S)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Poisonous Plants"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "\n",
    "N = int(raw_input()) #number of plants at initial state\n",
    "p = map(int, raw_input().strip().split()) #list of the pesticide for each plant\n",
    "\n",
    "days = [0] * N\n",
    "s = [0]\n",
    "mi = p[0]\n",
    "ma = 0\n",
    "\n",
    "for i in range(1, N):\n",
    "    if p[i] > p[i - 1]:\n",
    "        days[i] = 1\n",
    "    mi = min(mi, p[i])\n",
    "    while s and p[s[-1]] >= p[i]:\n",
    "        if p[i] > mi:\n",
    "            days[i] = max(days[i], days[s[-1]] + 1)\n",
    "        s.pop()\n",
    "    ma = max(ma, days[i])\n",
    "    s += [i]\n",
    "    print(s)\n",
    "\n",
    "print(ma)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "AND xor OR"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = 9\n",
    "b = 6\n",
    "((a & b)^(a | b)) & (a ^ b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Waiter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "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
}