Stack_Queue_and_Heap_Implimentations.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Some well-known Stacks and Queues Questions and Answers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Check if the expression in parenthesis is balanced\n",
    "# Ex: “[()]{}{[()()]()}” True,   “[(])” False\n",
    "\n",
    "# create a function that takes the string as input\n",
    "def paranthesis_balancing(string):\n",
    "    # create a dictionary\n",
    "    check_dict = {}\n",
    "    for i in range(len(string)):\n",
    "        # if [, {, ( are seen, append them to the dictionary for how many times they are seen. \n",
    "        if string[i] == '[' or string[i] == '(' or string[i] == '{':\n",
    "            if string[i] in check_dict.keys():\n",
    "                check_dict[string[i]] += 1\n",
    "            else:\n",
    "                check_dict[string[i]] = 1\n",
    "        elif string[i] == ']':\n",
    "            check_if_in = check_dict.get('[')\n",
    "            if check_if_in == None:\n",
    "                return False\n",
    "            else:\n",
    "                check_dict['['] -= 1\n",
    "        elif string[i] == ')':\n",
    "            check_if_in = check_dict.get('(')\n",
    "            if check_if_in == None:\n",
    "                return False\n",
    "            else:\n",
    "                check_dict['('] -= 1\n",
    "        elif string[i] == '}':\n",
    "            check_if_in = check_dict.get('{')\n",
    "            if check_if_in == None:\n",
    "                return False\n",
    "            else:\n",
    "                check_dict['{'] -= 1\n",
    "    for k, v in check_dict.items():\n",
    "        if v != 0:\n",
    "            return False\n",
    "    # print(check_dict) to view the dict.\n",
    "    return True\n",
    "\n",
    "string = \"[()]{}{[()()]}()\"\n",
    "paranthesis_balancing(string)        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Find the Minimum Number of Platforms Required for a Railway / Bus Station\n",
    "# Inbound = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}    \n",
    "# Outbound = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}\n",
    "\n",
    "\n",
    "def min_platforms_needed(array_in, array_out):\n",
    "    assert (len(array_in) == len(array_out))\n",
    "    max_platform = 0\n",
    "    curr_platform = 0\n",
    "    i = 0\n",
    "    j = 0\n",
    "    while i < len(array_in) and j < len(array_out):\n",
    "        if array_in[i] < array_out[j]:\n",
    "            curr_platform += 1\n",
    "            if curr_platform > max_platform:\n",
    "                max_platform = curr_platform\n",
    "            i += 1\n",
    "        elif array_in[i] > array_out[j]:\n",
    "            curr_platform -= 1\n",
    "            j += 1\n",
    "        else: # if they come and go in the same time\n",
    "            i += 1\n",
    "            j += 1\n",
    "        \n",
    "    return max_platform\n",
    "\n",
    "inbound = [900, 940, 950, 1100, 1500, 1800]\n",
    "outbound = [910, 1200, 1120, 1130, 1900, 2000]\n",
    "min_platforms_needed(inbound, outbound)\n",
    "        \n",
    "            \n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[900, 940, 1100, 1800, 1500, 950]\n"
     ]
    }
   ],
   "source": [
    "# if it is needed to convert the type of the input in the above example:\n",
    "\n",
    "a = {'9:00', '9:40', '9:50', '11:00', '15:00', '18:00'}\n",
    "all_times = []\n",
    "b = []\n",
    "for i in a:\n",
    "    b = []\n",
    "    joined = \"\"\n",
    "    for j in i:\n",
    "        if j != ':':\n",
    "            b.append(j)\n",
    "    joined = \"\".join(b)\n",
    "    all_times.append(int(joined))\n",
    "print(all_times) # inbound times\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 8, 3, 27, 8, 6, 5245, 245, 78, 26, 725, 24, 9]\n",
      "[[0.0, 'hello'], [10.02, 'first'], [10.32, '0'], [224.09, 'dog'], [186.76, 'oink'], [97.87, 'bear']]\n",
      "0.0 <class 'float'> hello <class 'str'>\n"
     ]
    }
   ],
   "source": [
    "# create a heapq (min heap) and impliment its basic methods\n",
    "\n",
    "class Heapq():\n",
    "    def __init__(self):\n",
    "        self.heap = []\n",
    "    \n",
    "            \n",
    "    def push(self,k): # append k to the array and percolate up with the last index\n",
    "        self.heap.append(k)\n",
    "        index_of_last_item = len(self.heap)-1 \n",
    "        self.percUp(index_of_last_item) # last item's index\n",
    "\n",
    "             \n",
    "    def percUp(self,i): # commonly known as \"siftdown method\"\n",
    "        while i > 0: # smallest index need to be 1 since first index is 0\n",
    "            if self.heap[i] < self.heap[(i-1) // 2]: # if child is smaller than its parent, swap\n",
    "                tmp = self.heap[(i-1) // 2]\n",
    "                self.heap[(i-1) // 2] = self.heap[i]\n",
    "                self.heap[i] = tmp\n",
    "            i = (i-1) // 2\n",
    "\n",
    "            \n",
    "    def pop(self): # pop last element and put it in the head, return head\n",
    "        if len(self.heap) == 0: return None\n",
    "        if len(self.heap) == 1: \n",
    "            tmp = self.heap.pop()\n",
    "            return tmp\n",
    "        retval = self.heap[0] # first item\n",
    "        last_item = self.heap.pop() # delete last item and assign it to a variable\n",
    "        self.heap[0] = last_item  # swap first item with last item\n",
    "        self.percDown(0)\n",
    "        return retval\n",
    "\n",
    "\n",
    "    def percDown(self,i): # commonly known as \"siftup method\"\n",
    "        # leftchild index is 2*i + 1, rightchild index is 2*i + 2, \n",
    "        # rightchild might not exist\n",
    "        while i < (len(self.heap) // 2):\n",
    "            mc = self.minChild(i)\n",
    "            if self.heap[i] > self.heap[mc]:\n",
    "                tmp = self.heap[i]\n",
    "                self.heap[i] = self.heap[mc]\n",
    "                self.heap[mc] = tmp\n",
    "            i = mc   \n",
    "            \n",
    "            \n",
    "    def minChild(self,i):\n",
    "        left_child_index = (i*2) + 1\n",
    "        right_child_index = left_child_index + 1\n",
    "        # if there is no right child, return the left child's index\n",
    "        if (left_child_index + 1) == len(self.heap): return left_child_index\n",
    "        elif self.heap[left_child_index] < self.heap[right_child_index]: # choose the smaller child \n",
    "            return left_child_index\n",
    "        else:\n",
    "            return right_child_index\n",
    "\n",
    "\n",
    "    def heapify(self,alist): \n",
    "        self.heap = alist[:]\n",
    "        n = len(self.heap)\n",
    "        for i in reversed(range(n//2)): # 4, 3, 2, 1, 0 and 0 is also included.\n",
    "            self.percDown(i)\n",
    "        return self.heap\n",
    "    \n",
    "    \n",
    "         \n",
    "if __name__== \"__main__\":\n",
    "            \n",
    "    bh_test = Heapq()\n",
    "    test_set2 = [24,26,6,27,725,3,5245,245,78,8,8,0,9] \n",
    "    bh_test.heapify(test_set2)\n",
    "    print(bh_test.heap)\n",
    "    test_set3 = [[0.0, 'hello'], [10.02, 'first'], [97.87, 'bear'], [224.09, 'dog'], [186.76, 'oink'], [10.32, '0']]\n",
    "    bh_test.heapify(test_set3)\n",
    "    print(bh_test.heap)\n",
    "    value, text = bh_test.pop()\n",
    "    print(value, type(value), text, type(text))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Yes\n"
     ]
    }
   ],
   "source": [
    "# Rearrange characters in a string such that no two adjacent are same\n",
    "# Input: aaabc  Output: abaca ,   Input: aaabb  Output: ababa ,   Input: aa  Output: Not Possible\n",
    "\n",
    "def isPossible(Str): \n",
    "  \n",
    "    # To store the frequency of \n",
    "    # each of the character \n",
    "    freq = dict() \n",
    "  \n",
    "    # To store the maximum frequency so far \n",
    "    max_freq = 0\n",
    "    for j in range(len(Str)): \n",
    "        freq[Str[j]] = freq.get(Str[j], 0) + 1\n",
    "        if (freq[Str[j]] > max_freq): \n",
    "            max_freq = freq[Str[j]] \n",
    "  \n",
    "    # If possible \n",
    "    if (max_freq <= (len(Str) - max_freq + 1)): \n",
    "        return True\n",
    "    return False\n",
    "  \n",
    "# Driver code \n",
    "Str = \"geeksforgeeks\"\n",
    "  \n",
    "if (isPossible(Str)): \n",
    "    print(\"Yes\") \n",
    "else: \n",
    "    print(\"No\") "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def if_possible_with_no_adj_replicas(string):\n",
    "    \n",
    "    a_dict = {}\n",
    "    for i in string:\n",
    "        if i in a_dict.keys():\n",
    "            a_dict[i] += 1\n",
    "        else:\n",
    "            a_dict[i] = 1\n",
    "    for k,v in a_dict.items():\n",
    "        if v > (len(string)+1) //2:\n",
    "            return False\n",
    "    return True\n",
    "    \n",
    "test_text = 'aaabb'\n",
    "if_possible_with_no_adj_replicas(test_text)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "source": [
    "# Kth smallest element in a stream \n",
    "test_stream = [2,36,17,34,44,12,6,9,0,30] # find the 3rd smallest element, answer 6\n",
    "\n",
    "test_heap = Heapq()\n",
    "test_heap.heapify(test_stream)\n",
    "k = 3\n",
    "for i in range(k-1): # take out the previous elements and return the head\n",
    "    test_heap.pop()\n",
    "\n",
    "print(test_heap.heap[0])"
   ]
  },
  {
   "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}