{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Homework 5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name: [Your name]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Data Structures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 1 (3 + 5 + 2 points)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a string $s$ consisting of multiple words, implement an algorithm to reverse the order of the words using a stack data structure. You are not allowed to use built-in string reverse functions or slicing. Your algorithm should run in $O(n)$ time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "a. Describe the logic of your algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "b. Implement your algorithm in Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def reverseString(s):\n",
    "    # implement me\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "c. Analyze the time-complexity of your algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 2 (7 + 3 points)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Implement your own `Queue` (FIFO) class in Python using two stacks (LIFO). Note that the `list` data-type implements a stack in Python. Your `Queue` class must implement the following methods:\n",
    "\n",
    "- `enQueue(x)`: appends `x` into the queue. \n",
    "\n",
    "- `deQueue()`: pops the head of the queue.\n",
    "\n",
    "- `peek()`: returns the head of the queue (without deleting).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "a. Implement your algorithm in Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "b. For each of the above methods, describe its time and (extra)-space complexities in big $O$-notation. You may *optionally* add the amortized costs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 3 (3 + 5 + 2 points)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an integer array $A$ and two integers $minK$ and $maxK$. A fixed-bound subarray is a contiguous subarray of $A$ that satisfies the following conditions:\n",
    "\n",
    "- The minimum value in the subarray is equal to $minK$.\n",
    "- The maximum value in the subarray is equal to $maxK$.\n",
    "\n",
    "Write an algorithm using Queue to return the total number of fixed-bound subarrays.\n",
    "\n",
    "Example:\n",
    "\n",
    "Input:  \n",
    "A=[1, 3, 5, 2, 7, 5], minK=1, maxK=5\n",
    "\n",
    "Output: 2\n",
    "\n",
    "Explanation:\n",
    "The fixed-bound subarrays are [1, 3, 5] and [1, 3, 5, 2].\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "a. Describe the logic of your algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "b. Implement your algorithm in Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def countSubarrays(A, minK, maxK):\n",
    "    # implement me\n",
    "    pass\n",
    "\n",
    "countSubarrays([1, 3, 5, 2, 7, 5], 1, 5) # 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "c. Analyze the time-complexity of your algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.12.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}