02_activities/assignments/assignment_1.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Coding Problems\n",
    "\n",
    "## Objective\n",
    "\n",
    "This assignment aims to demonstrate how to study a data structures or algorithms question in depth to prepare for an industry coding interview. Leetcode is a popular coding practice site that many use to practice for technical interviews. Like behavioral interviews, it's important to practice and keep your skills sharp.\n",
    "\n",
    "## Group Size\n",
    "\n",
    "Please complete this individually.\n",
    "\n",
    "## Part 1:\n",
    "\n",
    "_*You will be assigned one of three problems based of your first name. Enter your first name, in all lower case, execute the code below, and that will tell you your assigned problem. Include the output as part of your submission (do not clear the output). The problems are based-off problems from Leetcode.*_\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import hashlib\n",
    "\n",
    "def hash_to_range(input_string: str) -> int:\n",
    "     hash_object = hashlib.sha256(input_string.encode())\n",
    "     hash_int = int(hash_object.hexdigest(), 16)\n",
    "     return (hash_int % 3) + 1\n",
    "input_string = \"your_first_name_here\"\n",
    "result = hash_to_range(input_string)\n",
    "print(result)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "  <summary>Question 1</summary>\n",
    "\n",
    "  # Question One: Check Duplicates in Tree\n",
    "\n",
    "  Given the `root` of a binary tree, check whether it is contains a duplicate value. If a duplicate exists, return the duplicate value. If there are multiple duplicates, return the one with the closest distance to the root. If no duplicate exists, return -1.\n",
    "\n",
    "  ## Examples\n",
    "\n",
    "  ### Example 1\n",
    "\n",
    "  ![](./images/q1_ex1.png)\n",
    "\n",
    "  Input: `root = [1, 2, 2, 3, 5, 6, 7]` *What traversal method is this?*\n",
    "\n",
    "  Output: 2\n",
    "\n",
    "  ### Example 2\n",
    "\n",
    "  ![](./images/q1_ex2.png)\n",
    "\n",
    "  Input: `root = [1, 10, 2, 3, 10, 12, 12]`\n",
    "\n",
    "  Output: 10\n",
    "\n",
    "  ### Example 3\n",
    "\n",
    "  ![](./images/q1_ex3.png)\n",
    "\n",
    "  Input: `root = [10, 9, 8, 7]`\n",
    "\n",
    "  Output: -1\n",
    "\n",
    "</details>\n",
    "\n",
    "#### Starter Code for Question 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, val = 0, left = None, right = None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "def is_duplicate(root: TreeNode) -> int:\n",
    "  # TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "  <summary>Question 2</summary>\n",
    "\n",
    "  # Question Two: Path to Leaves\n",
    "\n",
    "  Given the `root` of a binary tree, return all root to leaf paths in any order.\n",
    "\n",
    "  ## Examples\n",
    "\n",
    "  ### Example 1\n",
    "\n",
    "  ![](./images/q1_ex1.png)\n",
    "\n",
    "  Input: `root = [1, 2, 2, 3, 5, 6, 7]` *What traversal method is this?*\n",
    "\n",
    "  Output: [[1, 2, 3], [1, 2, 5], [1, 2, 6], [1, 2, 7]]\n",
    "\n",
    "  ### Example 2\n",
    "\n",
    "  ![](./images/q1_ex3.png)\n",
    "\n",
    "  Input: `root = [10, 9, 7, 8]`\n",
    "\n",
    "  Output: [[10, 7], [10, 9, 8]]\n",
    "\n",
    "</details>\n",
    "\n",
    "#### Starter Code for Question 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, val = 0, left = None, right = None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "def bt_path(root: TreeNode) -> List[List[int]]:\n",
    "  # TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "  <summary>Question 3</summary>\n",
    "\n",
    "  # Question Three: Missing Number in Range\n",
    " \n",
    "  You are given a list containing `n` integers in the range `[0, n]`. Return a list of numbers that are missing from the range `[0, n]` of the array. If there is no missing number, return -1. Note, all the integers in the list may not be unique.\n",
    "  \n",
    "  ## Examples\n",
    "\n",
    "  ### Example 1\n",
    "\n",
    "  Input: `lst = [0, 2]`\n",
    "\n",
    "  Output: [1]\n",
    "\n",
    "  ### Example 2\n",
    "\n",
    "  Input: `lst = [5, 0, 1]`\n",
    "\n",
    "  Output: [2, 3, 4]\n",
    "\n",
    "  ### Example 3\n",
    "\n",
    "  Input: `lst = [6, 8, 2, 3, 5, 7, 0, 1, 10]`\n",
    "\n",
    "  Output: [4, 9]\n",
    "\n",
    "</details>\n",
    "\n",
    "#### Starter Code for Question 3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def missing_num(nums: List) -> int:\n",
    "  # TODO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "## Part 2:\n",
    "\n",
    "-   Paraphrase the problem in your own words\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your answer here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- In this .ipynb file, there are examples that illustrate how the code should work (the examples provided above). Create 2 new examples for the question you have been assigned, that demonstrate you understand the problem. For question 1 and 2, you don't need to create the tree demonstration, just the input and output.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your answer here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "-   Code the solution to your assigned problem in Python (code chunk). Try to find the best time and space complexity solution!\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your answer here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "-   Explain why your solution works\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your answer here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "-   Explain the problem’s time and space complexity\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your answer here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "-   Explain the thinking to an alternative solution (no coding required, but a classmate reading this should be able to code it up based off your text)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Your answer here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Evaluation Criteria\n",
    "\n",
    "-   Problem is accurately stated\n",
    "\n",
    "-   Two examples are correct and easily understandable\n",
    "\n",
    "-   Correctness, time, and space complexity of the coding solution\n",
    "\n",
    "-   Clarity in explaining why the solution works, its time and space complexity\n",
    "\n",
    "-   Clarity in the proposal to the alternative solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Submission Information\n",
    "\n",
    "🚨 **Please review our [Assignment Submission Guide](https://github.com/UofT-DSI/onboarding/blob/main/onboarding_documents/submissions.md)** 🚨 for detailed instructions on how to format, branch, and submit your work. Following these guidelines is crucial for your submissions to be evaluated correctly.\n",
    "\n",
    "### Submission Parameters:\n",
    "* Submission Due Date: `HH:MM AM/PM - DD/MM/YYYY`\n",
    "* The branch name for your repo should be: `assignment-1`\n",
    "* What to submit for this assignment:\n",
    "    * This Jupyter Notebook (assignment_1.ipynb) should be populated and should be the only change in your pull request.\n",
    "* What the pull request link should look like for this assignment: `https://github.com/<your_github_username>/algorithms_and_data_structures/pull/<pr_id>`\n",
    "    * Open a private window in your browser. Copy and paste the link to your pull request into the address bar. Make sure you can see your pull request properly. This helps the technical facilitator and learning support staff review your submission easily.\n",
    "\n",
    "Checklist:\n",
    "- [ ] Create a branch called `assignment-1`.\n",
    "- [ ] Ensure that the repository is public.\n",
    "- [ ] Review [the PR description guidelines](https://github.com/UofT-DSI/onboarding/blob/main/onboarding_documents/submissions.md#guidelines-for-pull-request-descriptions) and adhere to them.\n",
    "- [ ] Verify that the link is accessible in a private browser window.\n",
    "\n",
    "If you encounter any difficulties or have questions, please don't hesitate to reach out to our team via our Slack at `#cohort-3-help`. Our Technical Facilitators and Learning Support staff are here to help you navigate any challenges."
   ]
  }
 ],
 "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.11.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}