9_facebook_final.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "24775fd7",
   "metadata": {},
   "source": [
    "# Facebook Internal questions\n",
    "\n",
    "# 1. Reverse to Make Equal\n",
    "\n",
    "Given two arrays A and B of length N, determine if there is a way to make A equal to B by reversing any subarrays from array B any number of times.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "33f57f2f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def are_they_equal(array_a, array_b):\n",
    "    quicksort(array_a, 0, len(array_a) - 1)\n",
    "    quicksort(array_b, 0, len(array_b) - 1)\n",
    "    return array_a == array_b\n",
    "\n",
    "def partition(nums, left, right):\n",
    "    partitionIndex = left\n",
    "    pivotElement = nums[right]\n",
    "    \n",
    "    for j in range(left, right):\n",
    "        if nums[j] <= pivotElement:\n",
    "            nums[partitionIndex], nums[j] = nums[j], nums[partitionIndex]\n",
    "            partitionIndex += 1\n",
    "    nums[partitionIndex], nums[right] = nums[right], nums[partitionIndex]\n",
    "    return partitionIndex\n",
    "\n",
    "\n",
    "def quicksort(nums, left, right):\n",
    "    \n",
    "    if left < right:\n",
    "        partitionIndex = partition(nums, left, right)\n",
    "\n",
    "        quicksort(nums, left, partitionIndex - 1)\n",
    "        quicksort(nums, partitionIndex + 1, right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "48532027",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = [1, 2, 3, 4]\n",
    "B = [1, 4, 3, 2]\n",
    "\n",
    "are_they_equal(A, B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "b0a3a8eb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A = [1, 2, 3, 4]\n",
    "B = [1, 2, 3, 5]  \n",
    "\n",
    "are_they_equal(A, B)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fba1c9fa",
   "metadata": {},
   "source": [
    "# 2. Passing Yearbooks\n",
    "\n",
    "arr = [3, 2, 4, 1]\n",
    "\n",
    "* Student 1 passes their yearbook to Student 3\n",
    "* Student 2 passes their yearbook to Student 2\n",
    "* Student 3 passes their yearbook to Student 4\n",
    "* Student 4 passes their yearbook to Student 1\n",
    "\n",
    "\n",
    "* Student 1 signs Student 4 yearbook and pass it to Student 3\n",
    "* Student 2 passes to themselves.\n",
    "* Student 3 signs Student 4 yearbook and passes to Student 4\n",
    "* Student 3 signs Student 1 yearbook and passes to Student 4\n",
    "* Student 4 signs Student 3 yearbook and passes to Student 1\n",
    "* Student 4 signs Student 1 yearbook and passes to Student 1\n",
    "\n",
    "\n",
    "* Student 1 signs Student 3 yearbook and passes to Student 3\n",
    "\n",
    "The sign is complete.\n",
    "\n",
    "So 1, 3 and 4 have 3 signatures (including their own). 2 has one signature."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "aa65b406",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Brute force --> O(N^2)\n",
    "def findSignatureCounts(arr):\n",
    "    output = [1 for i in range(len(arr))]\n",
    "    \n",
    "    for i in range(len(arr)):\n",
    "        next_s = i\n",
    "        while arr[next_s] != i + 1:\n",
    "            output[i] += 1\n",
    "            next_s = arr[next_s]-1\n",
    "    return output  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "1eef3f56",
   "metadata": {},
   "outputs": [],
   "source": [
    "# O(N)\n",
    "\n",
    "def findSignatureCounts(arr):\n",
    "    visited_students = set()\n",
    "    root_indexes = [-1] * len(arr)\n",
    "    signatures = [0] * len(arr)\n",
    "    \n",
    "    for i in range(len(arr)):\n",
    "        student = arr[i]\n",
    "        \n",
    "        if student in visited_students:\n",
    "            continue\n",
    "            \n",
    "        visited_students.add(student)\n",
    "        \n",
    "        signatures[i] = 1\n",
    "        next_i = student - 1\n",
    "        \n",
    "        while next_i != i:\n",
    "            signatures[i] += 1\n",
    "            root_indexes[next_i] = i\n",
    "            visited_students.add(arr[next_i])\n",
    "            next_i = arr[next_i] - 1\n",
    "    \n",
    "    print(root_indexes)\n",
    "    print(signatures)\n",
    "    for i in range(len(arr)):\n",
    "        if root_indexes[i] != -1:\n",
    "            signatures[i] = signatures[root_indexes[i]]\n",
    "            \n",
    "    return signatures"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "0b4e0cc7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 2]"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [2, 1]\n",
    "findSignatureCounts(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "520a069e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1]"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [1, 2]\n",
    "findSignatureCounts(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "f5a7f179",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3, 1, 3, 3]"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [3, 2, 4, 1]\n",
    "findSignatureCounts(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "9b2d1c40",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [1,4,3,2]\n",
    "arr[-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a6a47187",
   "metadata": {},
   "source": [
    "# 3. Contiguous subarrays"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "id": "63ddbc59",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Brute force --> O(N^2)\n",
    "def count_subarrays(arr): #O(N^2)\n",
    "    # Starts from each index,\n",
    "    # expand towards both directions looking for a larger element.\n",
    "    n = len(arr)\n",
    "    result = [1] * n\n",
    "    for i, x in enumerate(arr):\n",
    "        for direction in [1, -1]:\n",
    "            step = 1\n",
    "            while 0 <= i+ direction*step < n and  arr[i+ direction*step] < x:\n",
    "                result[i] += 1\n",
    "                step += 1\n",
    "\n",
    "    return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "id": "14ea6343",
   "metadata": {},
   "outputs": [],
   "source": [
    "def count_subarrays(arr): #O(N)\n",
    "    # this solution uses Stacks. Every index starts with n possibilities.\n",
    "    # Using stack, going from left to right, we remove the subarrays that\n",
    "    # doesn't satisify the problem condition at this line:\n",
    "    # 'result[st.pop()] -= n-i'\n",
    "    # Then we do it again from right to left.\n",
    "    n = len(arr)\n",
    "    result = [n] * n\n",
    "    st = []\n",
    "    for i, x in enumerate(arr):\n",
    "        while st and x >= arr[st[-1]]:\n",
    "            result[st.pop()] -= n-i\n",
    "        st.append(i)\n",
    "    st.clear()\n",
    "    for i, x in reversed(list(enumerate(arr))):\n",
    "        while st and x >= arr[st[-1]]:\n",
    "            result[st.pop()] -= i+1\n",
    "        st.append(i)\n",
    "    return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "id": "7ad8e449",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 1, 5, 1]"
      ]
     },
     "execution_count": 89,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [3, 4, 1, 6, 2]\n",
    "\n",
    "count_subarrays(arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fd5e2a6c",
   "metadata": {},
   "source": [
    "# 4. Rotational Cipher"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "b5cee464",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rotationalCipher(input_str, rotation_factor):\n",
    "    \n",
    "    cap_alpha = [chr(c) for c in range(ord('A'), ord('Z') + 1)]\n",
    "    alpha = [chr(c) for c in range(ord('a'), ord('z') + 1)]\n",
    "    \n",
    "    result = []\n",
    "    \n",
    "    for c in input_str:\n",
    "        if not c.isalnum():\n",
    "            result.append(c)\n",
    "        elif c.isdigit():\n",
    "            result.append(str(int(c) + rotation_factor)[-1])\n",
    "        else:\n",
    "            if c.isupper():\n",
    "                idx = cap_alpha.index(c) + rotation_factor\n",
    "                if idx > 25:\n",
    "                    idx %= 26\n",
    "                result.append(cap_alpha[idx])\n",
    "            else:\n",
    "                idx = alpha.index(c) + rotation_factor\n",
    "                if idx > 25:\n",
    "                    idx %= 26\n",
    "                result.append(alpha[idx])\n",
    "    return \"\".join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "d1959ed6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Cheud-726?'"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "inputs = 'Zebra-493?'\n",
    "rotationFactor = 3\n",
    "\n",
    "rotationalCipher(inputs, rotationFactor)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "593c7835",
   "metadata": {},
   "source": [
    "# 5. Matching pairs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "id": "bc7aa5bb",
   "metadata": {},
   "outputs": [],
   "source": [
    "s = \"abcd\"\n",
    "t = \"adcb\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "id": "43d37c95",
   "metadata": {},
   "outputs": [],
   "source": [
    "def matching_pairs(s, t):\n",
    "    # CHECK FOR VALID INPUT\n",
    "    if len(s) != len(t):\n",
    "        raise ValueError(f\"Strings have different lengths.\")\n",
    "    if len(s) < 2:\n",
    "        raise ValueError(f\"Length of strings {len(s)} precludes a swap being possible.\")\n",
    "\n",
    "    # CHECK FOR MATCHING STRINGS\n",
    "    if s == t:\n",
    "        if contains_repeat_char(s):\n",
    "            # any repeated characters can be swapped with impunity\n",
    "            return len(s)\n",
    "        else:\n",
    "            # must impose a swap, which reduces matches\n",
    "            return len(s) - 2\n",
    "\n",
    "    # TRAVERSE THE STRINGS\n",
    "    # Count the matching pairs while saving data about the pairs for a potential swap later\n",
    "    misses = set()  # non-matching pairs\n",
    "    pairs = set()  # the swap pool\n",
    "    base = 0 # pre-swap count of matching pairs\n",
    "\n",
    "    for si, ti in zip(s, t):\n",
    "        pairs.add((si, ti))\n",
    "        if si == ti:\n",
    "            base += 1\n",
    "            pairs.add((si, True))  # matched pair swap candidate\n",
    "        else:\n",
    "            misses.add((si, ti))\n",
    "            pairs.add((si, False))   # unmatched pair swap candidate\n",
    "\n",
    "    # CHECK FOR SPECIFIC MISSES THAT CAN BE SWAPPED\n",
    "    # CHECK THEM IN SERIAL ORDER BECAUSE EACH SWAP TYPES IMPACT THE MATCH COUNT DIFFERENTLY\n",
    "    \n",
    "    # Check for a swap that creates two new matches: eg. pre-swap s='ab', t='ba'; after swap s='ba'\n",
    "    for m in misses:\n",
    "        if (m[1], m[0]) in pairs: return base + 2\n",
    "    # Check for a swap that creates one new match: eg. pre-swap s='at', t='xa'; after swap s='ta'\n",
    "    for m in misses:\n",
    "        if (m[1], False) in pairs: return base + 1\n",
    "    # Check for a swap that breaks an existing match while creating a new one: eg. pre-swap s='ab', t='aa'; after swap s='ba'\n",
    "    for m in misses:\n",
    "        if (m[1], True) in pairs: return base\n",
    "\n",
    "    # CHECK FOR REPEATED CHARACTERS IN 's', which can be swapped with impunity\n",
    "    if contains_repeat_char(s):\n",
    "        return base\n",
    "\n",
    "    # IMPOSE A SWAP\n",
    "    # 2 indices that both contain misses can be swapped with impunity\n",
    "    if len(misses) >= 2:\n",
    "        return base\n",
    "\n",
    "    # swapping an index that has a miss with an index that has a match removes a match\n",
    "    if len(misses) == 1 and base >= 1:\n",
    "        return base - 1\n",
    "\n",
    "    # else, swap indexes of two matching pairs, which removes both matches\n",
    "    return base - 2\n",
    "\n",
    "def contains_repeat_char(str):\n",
    "    used = set()\n",
    "    for c in str:\n",
    "        if c in used:\n",
    "            return True\n",
    "        else:\n",
    "            used.add(c)\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "id": "2f8244f9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 113,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = \"abcd\"\n",
    "t = \"adcb\"\n",
    "\n",
    "matching_pairs(s,t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "id": "4fb4b25c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 114,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = 'pabc'\n",
    "t = 'apcb'\n",
    "matching_pairs(s,t)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9caa8905",
   "metadata": {},
   "source": [
    "# 6. Revenue Milestone"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "de0f0d7a",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def accumulate(revenues):\n",
    "    total = 0\n",
    "    prefix_sums = []\n",
    "    \n",
    "    for i in revenues:\n",
    "        total += i\n",
    "        prefix_sums.append(total)\n",
    "    \n",
    "    return prefix_sums\n",
    "\n",
    "def getMilestoneDays(revenues, milestones):\n",
    "    prefix_sums = accumulate(revenues)\n",
    "    \n",
    "    def search(target):\n",
    "        left = 0\n",
    "        right = len(prefix_sums)\n",
    "        \n",
    "        while left < right:\n",
    "            mid = (left + right)//2\n",
    "            if prefix_sums[mid] < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        # left + 1 because 0th index corresponds to 1st day\n",
    "        return left + 1 if left < len(prefix_sums) else -1\n",
    "    \n",
    "    result = []\n",
    "    \n",
    "    for milestone in milestones:\n",
    "        result.append(search(milestone))\n",
    "    \n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "95f3dcbd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 6, 10]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "revenues = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]\n",
    "milestones = [100, 200, 500]\n",
    "\n",
    "getMilestoneDays(revenues, milestones)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9e695fff",
   "metadata": {},
   "source": [
    "# 7. 1 Billion Users\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "95628624",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def sumDay(arr, t):\n",
    "    running = 0 \n",
    "    for i in arr:\n",
    "        running += (i ** t)\n",
    "    return running\n",
    "\n",
    "def binary_search(arr, low, high):\n",
    "    while low < high:\n",
    "        mid = math.floor((low + high)/2)\n",
    "        if sumDay(arr, mid) < 1000000000:\n",
    "            low = mid + 1\n",
    "        else:\n",
    "            high = mid\n",
    "    return low\n",
    "\n",
    "\n",
    "def getBillionUsersDay(growthRates):\n",
    "    i = 1\n",
    "    users = sumDay(growthRates, i)\n",
    "    if users >= 1000000000:\n",
    "        return 1\n",
    "\n",
    "    # find the upper boundry\n",
    "    while users < 1000000000:\n",
    "        i *= 2\n",
    "        users = sumDay(growthRates, i)\n",
    "    \n",
    "    print(users, growthRates)\n",
    "    # find the exact boundry\n",
    "    return binary_search(growthRates, i // 2, i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "07a58661",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "186140372879.47342 [1.5]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "52"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "growthRates = [1.5]\n",
    "getBillionUsersDay(growthRates)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "67996867",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "384383308505649.2 [1.1, 1.2, 1.3]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "79"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "growthRates = [1.1, 1.2, 1.3]\n",
    "getBillionUsersDay(growthRates)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cd32f747",
   "metadata": {},
   "source": [
    "# 8. Counting Triangles"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "c9aba3b4",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "from collections import defaultdict\n",
    "\n",
    "def countDistinctTriangles(arr):\n",
    "    hash_map = defaultdict(list)\n",
    "    \n",
    "    for i in arr:\n",
    "        hash_map[tuple(sorted(i))].append(i)\n",
    "    \n",
    "    return len(hash_map.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "f6b24041",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [[2, 2, 3], [3, 2, 2], [2, 5, 6]]\n",
    "countDistinctTriangles(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "893c1d44",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [[8, 4, 6], [100, 101, 102], [84, 93, 173]]\n",
    "countDistinctTriangles(arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d1db52ba",
   "metadata": {},
   "source": [
    "# 9. Balanced Split"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "51900800",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[7]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [1,1,5,7]\n",
    "\n",
    "#[1,1,5] and [7]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "9def4d13",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(arr[0:3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "7087f33f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "math.floor((len(arr))/2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "a969b810",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sum(arr[0:4]) == sum(arr[4:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "8823c033",
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = [1,2,3,4,5,5]\n",
    "\n",
    "#[1,2,3,4] and [5,5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "id": "7282a3d4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def binary_search(arr, target):\n",
    "    low = 0\n",
    "    high = len(arr) - 1\n",
    "    \n",
    "    while low <= high:\n",
    "        mid = math.floor((low+high)/2)\n",
    "        if arr[mid] == target:\n",
    "            return mid\n",
    "        elif arr[mid] < target:\n",
    "            low = mid + 1\n",
    "        else:\n",
    "            high = mid - 1\n",
    "    return -1\n",
    "\n",
    "def balancedSplitExists(arr):\n",
    "    \n",
    "    arr.sort()\n",
    "    \n",
    "    running_sum = 0\n",
    "    prefix_sums = []\n",
    "    \n",
    "    for i in arr:\n",
    "        running_sum += i\n",
    "        prefix_sums.append(running_sum)\n",
    "    \n",
    "    max_sum = prefix_sums[-1]\n",
    "    \n",
    "    if max_sum % 2 != 0:\n",
    "        return False\n",
    "    \n",
    "    target = max_sum // 2\n",
    "    \n",
    "    \n",
    "    index_to_find = binary_search(prefix_sums, target)\n",
    "    \n",
    "    if index_to_find == -1:\n",
    "        return False\n",
    "    \n",
    "    return arr[index_to_find] < arr[index_to_find + 1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "id": "756ec1c9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 116,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [1, 5, 7, 1]\n",
    "balancedSplitExists(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "id": "979c25a7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 117,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [12, 7, 6, 7, 6]\n",
    "balancedSplitExists(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "id": "57f393a0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 118,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [1,2,3,4,10]\n",
    "balancedSplitExists(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "id": "14e6a639",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 119,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [2, 1, 2, 5]\n",
    "balancedSplitExists(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "id": "eaa31928",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 120,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [3, 6, 3, 4, 4]\n",
    "balancedSplitExists(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "id": "2e7dbed4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 121,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "balancedSplitExists([3,3,4,5,5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "id": "2670fca6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'ab'"
      ]
     },
     "execution_count": 124,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "aa = ['a', 'b']\n",
    "\n",
    "\"\".join(aa)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "95f8e03f",
   "metadata": {},
   "source": [
    "# 10. Encrypted Words\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "id": "125b742b",
   "metadata": {},
   "outputs": [],
   "source": [
    "def findEncryptedWord(s):\n",
    "    \n",
    "    if not s:\n",
    "        return \"\"\n",
    "    \n",
    "    cur_length = len(s)\n",
    "    \n",
    "    if cur_length == 1 or cur_length == 2:\n",
    "        return s\n",
    "    if cur_length % 2 == 0:\n",
    "        mid = cur_length // 2 - 1\n",
    "    else:\n",
    "        mid = cur_length // 2\n",
    "        \n",
    "    return s[mid] + findEncryptedWord(s[:mid]) + findEncryptedWord(s[mid+1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 126,
   "id": "52000cdf",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'eafcobok'"
      ]
     },
     "execution_count": 126,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S = \"facebook\"\n",
    "findEncryptedWord(S)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9983e1d5",
   "metadata": {},
   "source": [
    "# 11. Change in a Foreign Currency\n",
    "\n",
    "Come back to this for optimization\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 136,
   "id": "426769d8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def canGetExactChange(targetMoney, denominations):\n",
    "    if targetMoney < 0:\n",
    "        return False\n",
    "    if targetMoney == 0:\n",
    "        return True\n",
    "    \n",
    "    for i in range(len(denominations)):\n",
    "        if canGetExactChange(targetMoney - denominations[i], denominations):\n",
    "            return True\n",
    "    return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "id": "32f781e8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 142,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "targetMoney = 75\n",
    "denominations = [4, 17, 29]\n",
    "\n",
    "canGetExactChange(targetMoney, denominations)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "id": "d5e1e74c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 143,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "targetMoney = 94\n",
    "denominations =  [5, 10, 25, 100, 200]\n",
    "\n",
    "canGetExactChange(targetMoney, denominations)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ba17689",
   "metadata": {},
   "source": [
    "# 12. Balance Brackets\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "id": "bf153829",
   "metadata": {},
   "outputs": [],
   "source": [
    "def isBalanced(s):\n",
    "    \n",
    "    if len(s) == 0:\n",
    "        return True\n",
    "    \n",
    "    parens = {\n",
    "        '(':')',\n",
    "        '{':'}',\n",
    "        '[':']'\n",
    "    }\n",
    "    \n",
    "    stack = []\n",
    "    \n",
    "    for i in range(len(s)):\n",
    "        if s[i] in parens.keys():\n",
    "            stack.append(s[i])\n",
    "        else:\n",
    "            if len(stack) > 0:\n",
    "                leftBracket = stack.pop()\n",
    "            else:\n",
    "                return False\n",
    "            correctBracket = parens[leftBracket]\n",
    "            if s[i] != correctBracket:\n",
    "                return False\n",
    "    return len(stack) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "id": "dcfbdd38",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 147,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = '{[()]}'\n",
    "isBalanced(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "id": "c6845727",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 148,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = '{}()'\n",
    "isBalanced(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "id": "21b05b09",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 149,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = '{(})'\n",
    "isBalanced(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "id": "a1e416de",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 150,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = ')'\n",
    "isBalanced(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "id": "23bcae44",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(3, 1), (4, 2), (2, 3), (1, 4)]"
      ]
     },
     "execution_count": 151,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [3,4,2,1]\n",
    "[(v, i) for i, v in enumerate(arr, start = 1)]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "42bc89c2",
   "metadata": {},
   "source": [
    "# 13. Queue removals"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 156,
   "id": "07d08314",
   "metadata": {},
   "outputs": [],
   "source": [
    "from operator import itemgetter\n",
    "\n",
    "def findPositions(arr, x):\n",
    "    queue = [(v, i) for i, v in enumerate(arr, start=1)]\n",
    "    \n",
    "    output = []\n",
    "    \n",
    "    for _ in range(x):\n",
    "        tmp = queue[:x]\n",
    "        max_value = max(tmp, key=itemgetter(0))\n",
    "        output.append(max_value[1])\n",
    "        tmp.remove(max_value)\n",
    "        tmp = [(v-1, i) if v > 0 else (v, i) for v, i in tmp]\n",
    "        queue = queue[x:] + tmp\n",
    "    \n",
    "    return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "id": "003ac421",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 6, 4, 1, 2]"
      ]
     },
     "execution_count": 157,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [1, 2, 2, 3, 4, 5]\n",
    "x = 5\n",
    "findPositions(arr, x)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9670a673",
   "metadata": {},
   "source": [
    "# 14. Number of visible nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 160,
   "id": "2634654c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def visible_nodes(root):\n",
    "    result = []\n",
    "    node = root\n",
    "    level = 0\n",
    "    return traversePreOrder(node, level, result)\n",
    "\n",
    "def traversePreOrder(node, level, result):\n",
    "    if node is None:\n",
    "        return\n",
    "    \n",
    "    if level >= len(result):\n",
    "        result.append(node.val)\n",
    "        \n",
    "    if node.left is not None:\n",
    "        traversePreOrder(node.left, level + 1, result)\n",
    "    \n",
    "    if node.right is not None:\n",
    "        traversePreOrder(node.right, level + 1, result)\n",
    "    \n",
    "    return len(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 161,
   "id": "ce0bf7e3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "✓Test #1\n",
      "✓Test #2\n"
     ]
    }
   ],
   "source": [
    "class TreeNode: \n",
    "  def __init__(self,key): \n",
    "    self.left = None\n",
    "    self.right = None\n",
    "    self.val = key \n",
    "\n",
    "def printInteger(n):\n",
    "  print('[', n, ']', sep='', end='')\n",
    "\n",
    "test_case_number = 1\n",
    "\n",
    "def check(expected, output):\n",
    "  global test_case_number\n",
    "  result = False\n",
    "  if expected == output:\n",
    "    result = True\n",
    "  rightTick = '\\u2713'\n",
    "  wrongTick = '\\u2717'\n",
    "  if result:\n",
    "    print(rightTick, 'Test #', test_case_number, sep='')\n",
    "  else:\n",
    "    print(wrongTick, 'Test #', test_case_number, ': Expected ', sep='', end='')\n",
    "    printInteger(expected)\n",
    "    print(' Your output: ', end='')\n",
    "    printInteger(output)\n",
    "    print()\n",
    "  test_case_number += 1\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "  root_1 = TreeNode(8)\n",
    "  root_1.left = TreeNode(3)\n",
    "  root_1.right = TreeNode(10)\n",
    "  root_1.left.left = TreeNode(1)\n",
    "  root_1.left.right = TreeNode(6)\n",
    "  root_1.left.right.left = TreeNode(4)\n",
    "  root_1.left.right.right = TreeNode(7)\n",
    "  root_1.right.right = TreeNode(14)\n",
    "  root_1.right.right.left = TreeNode(13)\n",
    "  expected_1 = 4\n",
    "  output_1 = visible_nodes(root_1)\n",
    "  check(expected_1, output_1)\n",
    "\n",
    "  root_2 = TreeNode(10)\n",
    "  root_2.left = TreeNode(8)\n",
    "  root_2.right = TreeNode(15)\n",
    "  root_2.left.left = TreeNode(4)\n",
    "  root_2.left.left.right = TreeNode(5)\n",
    "  root_2.left.left.right.right = TreeNode(6)\n",
    "  root_2.right.left =TreeNode(14)\n",
    "  root_2.right.right = TreeNode(16)\n",
    "\n",
    "  expected_2 = 5\n",
    "  output_2 = visible_nodes(root_2)\n",
    "  check(expected_2, output_2)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "044eef02",
   "metadata": {},
   "source": [
    "# 15. Nodes in a Subtree\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 166,
   "id": "a9f51aa5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def count_of_nodes(root, queries, s):\n",
    "    #it's global, no need to use it in recursive arguments\n",
    "    dictionary = {}\n",
    "\n",
    "    def dfs(root):\n",
    "        # end of tree, base case        \n",
    "        if not root: \n",
    "            return\n",
    "        # what char is for every node\n",
    "        # e.g. node 2 in the example has 'b'\n",
    "        dictionary[root.val] = s[root.val - 1]\n",
    "        \n",
    "        # no children, base case 2\n",
    "        if not root.children:\n",
    "            return\n",
    "\n",
    "        # in the example, nodes 2 and 3 are the children\n",
    "        for c in root.children:\n",
    "            # recursively run dfs for the children subtrees\n",
    "            dfs(c)\n",
    "            # add to for every root, all the chars you found at the children\n",
    "            # so you can count them for the queries\n",
    "            dictionary[root.val] += dictionary[c.val]\n",
    "\n",
    "    dfs(root)\n",
    "    res = []\n",
    "    \n",
    "    for q in queries:\n",
    "        res.append(dictionary[q[0]].count(q[1]))\n",
    "\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 164,
   "id": "a5fc7378",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node: \n",
    "  def __init__(self, data): \n",
    "    self.val = data \n",
    "    self.children = []\n",
    "    \n",
    "n_1 ,q_1 = 3, 1 \n",
    "s_1 = \"aba\"\n",
    "root_1 = Node(1) \n",
    "root_1.children.append(Node(2)) \n",
    "root_1.children.append(Node(3)) \n",
    "queries_1 = [(1, 'a')]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 165,
   "id": "e506deda",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2]"
      ]
     },
     "execution_count": 165,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "count_of_nodes(root_1, queries_1, s_1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "410d5010",
   "metadata": {},
   "source": [
    "# 16. Largest Triple Products\n",
    "arr = [2, 1, 2, 1, 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 195,
   "id": "e4b92e44",
   "metadata": {},
   "outputs": [],
   "source": [
    "from queue import PriorityQueue\n",
    "\n",
    "def findMaxProduct(arr):\n",
    "    \n",
    "    q = PriorityQueue()\n",
    "    \n",
    "    result = []\n",
    "    \n",
    "    for i in range(len(arr)):\n",
    "        q.put(-arr[i])\n",
    "        \n",
    "        if q.qsize() < 3:\n",
    "            result.append(-1)\n",
    "        else:\n",
    "            x = q.get()\n",
    "            y = q.get()\n",
    "            z = q.get()\n",
    "            print(x,y,z)\n",
    "            ans = x * y * z\n",
    "            \n",
    "            result.append(-ans)\n",
    "            \n",
    "            q.put(x)\n",
    "            q.put(y)\n",
    "            q.put(z)\n",
    "    return result\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 196,
   "id": "ded6f182",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-2 -2 -1\n",
      "-2 -2 -1\n",
      "-2 -2 -2\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[-1, -1, 4, 4, 8]"
      ]
     },
     "execution_count": 196,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [2, 1, 2, 1, 2]\n",
    "findMaxProduct(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 197,
   "id": "e62e58ff",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-3 -2 -1\n",
      "-4 -3 -2\n",
      "-5 -4 -3\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[-1, -1, 6, 24, 60]"
      ]
     },
     "execution_count": 197,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [1, 2, 3, 4, 5]\n",
    "findMaxProduct(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 178,
   "id": "b7979863",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-1, -1, 56, 56, 140, 140]"
      ]
     },
     "execution_count": 178,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [2, 4, 7, 1, 5, 3]\n",
    "findMaxProduct(arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "304b8d94",
   "metadata": {},
   "source": [
    "# 17. Magical Candy Bags\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 215,
   "id": "e4ec843e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Priority queue gets lowest first. So -\n",
    "# O(n+klogn)\n",
    "\n",
    "def maxCandies(arr, k):\n",
    "    \n",
    "    q = PriorityQueue()\n",
    "    \n",
    "    count = 0\n",
    "    \n",
    "    for i in range(len(arr)):\n",
    "        q.put(-arr[i])\n",
    "        \n",
    "    for i in range(k):\n",
    "        max_candy = -q.get()\n",
    "        count += max_candy\n",
    "        max_candy = math.floor(max_candy/2)\n",
    "        q.put(-max_candy)\n",
    "    \n",
    "    return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 213,
   "id": "2201618e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "14"
      ]
     },
     "execution_count": 213,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [2, 1, 7, 4, 2]\n",
    "k = 3\n",
    "\n",
    "maxCandies(arr, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 214,
   "id": "cc050e36",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "228"
      ]
     },
     "execution_count": 214,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [19, 78, 76, 72, 48, 8, 24, 74, 29]\n",
    "k = 3\n",
    "\n",
    "maxCandies(arr, k)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "374e4170",
   "metadata": {},
   "source": [
    "# 18. Median Stream\n",
    "\n",
    "[5, 15, 1, 3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 221,
   "id": "f8a33388",
   "metadata": {},
   "outputs": [],
   "source": [
    "# O(n^2logn)\n",
    "\n",
    "def findMedian(arr):\n",
    "    \n",
    "    result = []\n",
    "    \n",
    "    for i in range(len(arr)):\n",
    "        if i == 0:\n",
    "            result.append(arr[i])\n",
    "        elif i % 2 == 1:\n",
    "            tmp = sorted(arr[:i+1])\n",
    "            mid = math.floor(len(tmp)/2)\n",
    "            median = int((tmp[mid] + tmp[mid-1])/2)\n",
    "            result.append(median)\n",
    "        else:\n",
    "            tmp = sorted(arr[:i+1])\n",
    "            mid = math.floor(len(tmp)/2)\n",
    "            median = int(tmp[mid])\n",
    "            result.append(median)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 222,
   "id": "0de35088",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 10, 5, 4]"
      ]
     },
     "execution_count": 222,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [5, 15, 1, 3]\n",
    "findMedian(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 223,
   "id": "d167da99",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1]"
      ]
     },
     "execution_count": 223,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [1, 2]\n",
    "findMedian(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 224,
   "id": "e2559ca1",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 4, 3, 4, 3]"
      ]
     },
     "execution_count": 224,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [2, 4, 7, 1, 5, 3]\n",
    "findMedian(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 225,
   "id": "b8a34dee",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 10, 5, 4, 3, 4, 5, 6, 7, 6, 7, 6]"
      ]
     },
     "execution_count": 225,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [5, 15, 1, 3, 2, 8, 7, 9, 10, 6, 11, 4]\n",
    "findMedian(arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "34bbbb44",
   "metadata": {},
   "source": [
    "We can use a max heap on the left side to represent elements that are less than effective median, and a min-heap on the right side to represent elements that are greater than effective median.\n",
    "\n",
    "After processing an incoming element, the number of elements in heaps differs utmost by 1 element. When both heaps contain the same number of elements, we pick the average of heaps root data as effective median. When the heaps are not balanced, we select effective median from the root of the heap containing more elements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 236,
   "id": "e3807aa9",
   "metadata": {},
   "outputs": [],
   "source": [
    "# T --> O(NlogN)\n",
    "# S --> O(N)\n",
    "from heapq import heappush, heappop, heapify\n",
    "\n",
    "def findMedian(arr):\n",
    "    heap1 = []\n",
    "    heap2 = []\n",
    "    result = []\n",
    "    \n",
    "    for i in range(len(arr)):\n",
    "        heappush(heap1, -arr[i])\n",
    "        heappush(heap2, -heappop(heap1))\n",
    "        \n",
    "        if len(heap2) > len(heap1):\n",
    "            heappush(heap1, -heappop(heap2))\n",
    "        \n",
    "        if len(heap2) != len(heap1):\n",
    "            result.append(int(-heap1[0]))\n",
    "        else:\n",
    "            result.append(int((heap2[0] - heap1[0])/2))\n",
    "    \n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 237,
   "id": "b779a54a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 10, 5, 4]"
      ]
     },
     "execution_count": 237,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [5, 15, 1, 3]\n",
    "findMedian(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 232,
   "id": "2fafa198",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1]"
      ]
     },
     "execution_count": 232,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [1, 2]\n",
    "findMedian(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 233,
   "id": "d9ea34b9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 4, 3, 4, 3]"
      ]
     },
     "execution_count": 233,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr = [2, 4, 7, 1, 5, 3]\n",
    "findMedian(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "6b653a1b",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}