2023-2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "5e83ab56-18b3-4d87-ad22-3d2e5cde9fe7",
   "metadata": {},
   "source": [
    "### 1339. Maximum Product of Splitted Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a8d0aae0-df6c-475d-af63-84f8f70cefc7",
   "metadata": {},
   "source": [
    "### 692. Top K Frequent Words"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "86d6c7ff-782c-4f94-b230-2a2e69679ad4",
   "metadata": {},
   "outputs": [],
   "source": [
    "bucket sort + trie solution needs review"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4c5bdcc2-ec0b-4875-956d-85710b929f6a",
   "metadata": {},
   "source": [
    "### 43. Multiply Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "371bd307-ec56-43dd-9b2c-76b959f953cc",
   "metadata": {},
   "source": [
    "### 4. median of sorted array"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1ff3419-735c-4abb-a363-42b7acdc2c6a",
   "metadata": {},
   "source": [
    "### 9. palindrome number"
   ]
  },
  {
   "cell_type": "raw",
   "id": "24a6dd8d-709a-4d55-b9da-b253b6c576a6",
   "metadata": {},
   "source": [
    "reverse half"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "71d6d2fb-006b-4d4f-87f2-b02c4067112e",
   "metadata": {},
   "source": [
    "## 29. divide"
   ]
  },
  {
   "cell_type": "raw",
   "id": "03ad0102-e16a-4a4f-b1ea-f8b11c8c1cd2",
   "metadata": {},
   "source": [
    "pretty complicated"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5a4c010c-3d97-43b2-b420-e95acdb391a4",
   "metadata": {},
   "outputs": [],
   "source": [
    "44. WildCard Matching"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "367ffc66-4b6c-4189-9f19-dcdb41238392",
   "metadata": {},
   "outputs": [],
   "source": [
    "similar to Edit distance"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0c4cdaab-fe06-434b-bad0-cb663c48a022",
   "metadata": {},
   "source": [
    "### 53. Maxium subarray"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4a83ad64-7362-4b09-afb0-c5beff56676b",
   "metadata": {},
   "outputs": [],
   "source": [
    "56. merge interval"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ab8e7cae-eb42-49ed-9a15-4ef2ef6f74ae",
   "metadata": {},
   "outputs": [],
   "source": [
    "123. best time to buy/sell stock"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "141d1312-7409-41e7-b72b-89e7007d2876",
   "metadata": {},
   "outputs": [],
   "source": [
    "need to review other similar questions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "81ec9fa8-9c57-4d7c-90fb-5d44a3234f6f",
   "metadata": {},
   "outputs": [],
   "source": [
    "146. LRU Cache"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1b99236e-9e3c-4c97-b5d1-367de1f5862a",
   "metadata": {},
   "outputs": [],
   "source": [
    "200. Num of islands"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8be5181a-3de0-4a24-840f-8a285a73c916",
   "metadata": {},
   "outputs": [],
   "source": [
    "207. course schedule"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fa6f9c8d-d178-4512-8e07-f7029de1cb13",
   "metadata": {},
   "outputs": [],
   "source": [
    "289. gameoflife"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a0daa98c-3dab-4b3e-835f-a492dcea5c49",
   "metadata": {},
   "outputs": [],
   "source": [
    "380. Insert delete GetRandom"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "02c2089d-2a17-4908-9c57-2c984e618ad3",
   "metadata": {},
   "outputs": [],
   "source": [
    "415. addstring"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9cc43e08-c3e3-409d-8636-ee12181ab1be",
   "metadata": {},
   "outputs": [],
   "source": [
    "443. compress string"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c05be573-c083-42a1-84b0-fb0e5ddff608",
   "metadata": {},
   "outputs": [],
   "source": [
    "little tricky"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "722a4fd5-fdd6-4dae-9d75-1b8f650b7595",
   "metadata": {},
   "outputs": [],
   "source": [
    "528. Random Pick with weight"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9e6470f9-66aa-4486-9e7f-7040dae4f15c",
   "metadata": {},
   "outputs": [],
   "source": [
    "547. friendCircNum"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "08146910-29e3-47d7-8e26-e2aa2262f596",
   "metadata": {},
   "source": [
    "# 564. nearest palindrome"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d8c3b5ca-70c1-4331-bf10-527022eb6bc4",
   "metadata": {},
   "outputs": [],
   "source": [
    "very tough (TODO)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "055738d4-313e-4324-82d4-0ff56aa6667c",
   "metadata": {},
   "outputs": [],
   "source": [
    "606. tree2str"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1f1ac184-dafb-4b37-9db0-5888c1986005",
   "metadata": {},
   "source": [
    "# 698. canPartitionKsubsets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4a07a57e-32df-44ed-be7a-596dabbdf91e",
   "metadata": {},
   "outputs": [],
   "source": [
    "918. MaxCirArray"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "55718069-ba3b-4ee3-b721-173501e520f9",
   "metadata": {},
   "outputs": [],
   "source": [
    "1048. longestStrChain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "300d53b9-bdb9-416e-984d-4d109e43bf1e",
   "metadata": {},
   "outputs": [],
   "source": [
    "1779. nearestValidPoint"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b0251683-6e2d-4c99-b91e-1d16763f3a79",
   "metadata": {},
   "outputs": [],
   "source": [
    "KNN implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f4af2a56-d920-4a07-b57e-c011d2ba9191",
   "metadata": {},
   "outputs": [],
   "source": [
    "design text editor\n",
    "https://leetcode.com/discuss/interview-question/304048/Google-onsite-question-Design-Text-Editor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "67f0e956-240f-471f-a3bd-b112e29e5980",
   "metadata": {},
   "outputs": [],
   "source": [
    "https://leetcode.com/discuss/interview-question/algorithms/1968209/Two-sigma-hacker-rank-code-assessment"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a378f302-8c10-41f1-8665-cbe4a549c727",
   "metadata": {},
   "source": [
    "# Sorting Review: #912. Sort an Array\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a7af6a7-ee21-4090-9241-0d2aa78bc8a9",
   "metadata": {},
   "source": [
    "Given an array of integers nums, sort the array in ascending order and return it.\n",
    "\n",
    "You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "494f23e0-ff8b-438e-820d-d15eaa7f1252",
   "metadata": {},
   "source": [
    "This question contains most details about all the sorting algos."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d07a0730-5c68-47c2-83d6-649e8c8a2fd1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sortArray(self, nums: List[int]) -> List[int]:\n",
    "    temp_arr = [0] * len(nums)\n",
    "\n",
    "    # Function to merge two sub-arrays in sorted order.\n",
    "    def merge(left: int, mid: int, right: int):\n",
    "        # Calculate the start and sizes of two halves.\n",
    "        start1 = left\n",
    "        start2 = mid + 1\n",
    "        n1 = mid - left + 1\n",
    "        n2 = right - mid\n",
    "\n",
    "        # Copy elements of both halves into a temporary array.\n",
    "        for i in range(n1):\n",
    "            temp_arr[start1 + i] = nums[start1 + i]\n",
    "        for i in range(n2):\n",
    "            temp_arr[start2 + i] = nums[start2 + i]\n",
    "\n",
    "        # Merge the sub-arrays 'in tempArray' back into the original array 'arr' in sorted order.\n",
    "        i, j, k = 0, 0, left\n",
    "        while i < n1 and j < n2:\n",
    "            if temp_arr[start1 + i] <= temp_arr[start2 + j]:\n",
    "                nums[k] = temp_arr[start1 + i]\n",
    "                i += 1\n",
    "            else:\n",
    "                nums[k] = temp_arr[start2 + j]\n",
    "                j += 1\n",
    "            k += 1\n",
    "\n",
    "        # Copy remaining elements\n",
    "        while i < n1:\n",
    "            nums[k] = temp_arr[start1 + i]\n",
    "            i += 1\n",
    "            k += 1\n",
    "        while j < n2:\n",
    "            nums[k] = temp_arr[start2 + j]\n",
    "            j += 1\n",
    "            k += 1\n",
    "\n",
    "    # Recursive function to sort an array using merge sort\n",
    "    def merge_sort(left: int, right: int):\n",
    "        if left >= right:\n",
    "            return\n",
    "        mid = (left + right) // 2\n",
    "        # Sort first and second halves recursively.\n",
    "        merge_sort(left, mid)\n",
    "        merge_sort(mid + 1, right)\n",
    "        # Merge the sorted halves.\n",
    "        merge(left, mid, right)\n",
    "\n",
    "    merge_sort(0, len(nums) - 1)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}