Practice DSA

min_stack.md

MinStack

Design a Stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.

• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Example:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Solution

To solve this problem, we'll use two stacks. The first stack, which is the main stack, will store all elements. The other stack will keep track of the minimum elements.

When pushing an element, we'll add it to the main stack. If it's smaller than or equal to the current minimum, we'll also add it to the minimum stack.

For pop operations, we'll remove from both stacks if the popped element is the current minimum.

The top operation will return the top of the main stack, while getMin will return the top of the minimum stack.

This approach ensures all operations have O(1) time complexity because each operation only involves adding or removing elements from the top of the stacks, which are constant-time operations.

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def getMin(self):
        if self.min_stack:
            return self.min_stack[-1]

    def push(self, val):
        if not self.min_stack or self.min_stack[-1] >= val:
            self.min_stack.append(val)
        self.stack.append(val)

    def pop(self):
        if self.stack:
            if self.min_stack and self.stack[-1] == self.min_stack[-1]:
                self.min_stack.pop()
            self.stack.pop()

    def top(self):
        if self.stack:
            return self.stack[-1]


minStack = MinStack()

print(minStack.getMin())
minStack.push(3)
minStack.push(5)
minStack.push(2)
minStack.push(6)
minStack.push(1)

print(minStack.getMin())

minStack.pop()
print(minStack.getMin())
minStack.pop()
print(minStack.getMin())
minStack.pop()
print(minStack.getMin())
minStack.pop()
print(minStack.getMin())

n_queens.py

class Solution:
  def __init__(self):
    self.solve_count = 0

  def solveNQueens(self, n: int) -> list[list[str]]:
    # Check if queen at row and columns is safe from other queens
    def issafe(r,c):
      n = len(board)
      for i in range(n):
        # Check Queen present at upper direction (same column)
        if board[i][c] == 'Q':
          return False
        # Check Queen is present at left upper diagonal direction
        if r - i >= 0 and c - i >= 0 and board[r-i][c-i] == 'Q':
          return False
        # Check Queen is present at right upper diagonal direction
        if r - i >= 0 and c + i < n and board[r-i][c+i] == 'Q':
          return False
      return True

    # Recursive method
    # Starts from row 0 and iterates all the columns
    #
    def solve(r):
      n = len(board)
      self.solve_count += 1
      # If row is at max, then add the solution to ANS and print current board
      if r == n:
        print(board)
        ans.append(["".join(i) for i in board])
        return

      # Iterate column by colum
      for c in range(0,n):
        # print(r,c)
        # If queen is not safe, then move back to previous row and change queen's column. Then check for safety
        if issafe(r,c):
          # If Queen is safe, then place the queen. Now, move to next row
          board[r][c] = 'Q'
          solve(r+1)
          # Remove the queen
          board[r][c] = '.'

    # Create Empty board
    board = [['.']*n for i in range(n)]
    # Collect all possible answerws
    ans =[]
    # start with 0th row
    solve(0)
    # At the very end, the board will be clear
    print(board)

    print(self.solve_count)
    return ans

s = Solution()
s.solveNQueens(8)

Practice DSA Plan.md

System Design repo list

https://github.com/stars/valarpirai/lists/system-design

Object oriented system design - LLD

https://github.com/tssovi/grokking-the-object-oriented-design-interview

My Courses

https://www.udemy.com/home/my-courses/learning/

DSA

Interview Questions - https://github.com/mission-peace/interview/wiki

Array

https://www.techinterviewhandbook.org/algorithms/array/ Sliding window - https://leetcode.com/problems/minimum-window-substring/solutions/26808/here-is-a-10-line-template-that-can-solve-most-substring-problems/

practice.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "762f4f2b-379b-47a6-9074-eb8771b9f9bc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1], [2, 3, 4], [0, 5]]\n",
      "[[0, 1, 2], [5], [3, 4, 6]]\n"
     ]
    }
   ],
   "source": [
    "def find_groups(groupSizes):\n",
    "    groups = {}\n",
    "    result = []\n",
    "    for i in range(0, len(groupSizes)):\n",
    "        group_size = groupSizes[i]\n",
    "        \n",
    "        if group_size not in groups:\n",
    "            groups[group_size] = []\n",
    "\n",
    "        groups[group_size].append(i)\n",
    "        \n",
    "    \n",
    "        if len(groups[group_size]) == group_size:\n",
    "            result.append(groups[group_size])\n",
    "            groups[group_size] = []\n",
    "\n",
    "    return result\n",
    "\n",
    "print(find_groups([2,1,3,3,3,2]))\n",
    "print(find_groups([3,3,3,3,3,1,3]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "ed769bc1-5996-4e04-9e29-02dce7a9fa37",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "-----\n",
      "4\n",
      "3\n",
      "2\n",
      "1\n",
      "0\n",
      "[0, 0, 9, 0, 0]\n",
      "1\n",
      "2\n",
      "3\n",
      "-----\n",
      "3\n",
      "2\n",
      "1\n",
      "0\n",
      "[24, 12, 8, 6]\n"
     ]
    }
   ],
   "source": [
    "def productExceptSelf(nums):\n",
    "    l = len(nums)\n",
    "    left_product = [1] * l\n",
    "\n",
    "    for i in range(1, l):\n",
    "        print(i)\n",
    "        left_product[i] = nums[i - 1] * left_product[i - 1]\n",
    "\n",
    "    print('-----')\n",
    "    right_product = 1\n",
    "    for i in range(l - 1, -1, -1):\n",
    "        print(i)\n",
    "        left_product[i] *= right_product\n",
    "        right_product *= nums[i]\n",
    "\n",
    "    return left_product\n",
    "\n",
    "print(productExceptSelf([-1,1,0,-3,3]))\n",
    "print(productExceptSelf([1,2,3,4]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "4592cf5b-e6d5-47ea-acdd-e82095d0fe9b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 2\n",
      "1 7\n",
      "2 11\n",
      "3 15\n",
      "-1\n",
      "0 3\n",
      "1 2\n",
      "2 4\n",
      "[1, 2]\n",
      "0 3\n",
      "1 2\n",
      "2 3\n",
      "[0, 2]\n",
      "0 3\n",
      "1 1\n",
      "2 5\n",
      "[1, 2]\n",
      "0 3\n",
      "1 2\n",
      "2 3\n",
      "3 3\n",
      "-1\n"
     ]
    }
   ],
   "source": [
    "def two_sum(list, target):\n",
    "    dic = {}\n",
    "    for i, num in enumerate(list):\n",
    "        print(i, num)\n",
    "        temp = target - num\n",
    "        if temp in dic:\n",
    "            return [dic[temp], i]\n",
    "        dic[num] = i\n",
    "    return -1\n",
    "\n",
    "\n",
    "print(two_sum([2, 7, 11, 15], 10))\n",
    "print(two_sum([3, 2, 4], 6))\n",
    "print(two_sum([3, 2, 3], 6))\n",
    "print(two_sum([3, 1, 5, 3], 6))\n",
    "print(two_sum([3, 2, 3, 3], 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "31aa3552-4d24-4661-b264-3a5163447475",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n",
      "1\n",
      "2\n",
      "2\n",
      "3\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "class MinStack:\n",
    "    def __init__(self):\n",
    "        self.stack = []\n",
    "        self.min_stack = []\n",
    "\n",
    "    def getMin(self):\n",
    "        if self.min_stack:\n",
    "            return self.min_stack[-1]\n",
    "\n",
    "    def push(self, val):\n",
    "        if not self.min_stack or self.min_stack[-1] >= val:\n",
    "            self.min_stack.append(val)\n",
    "        self.stack.append(val)\n",
    "\n",
    "    def pop(self):\n",
    "        if self.stack:\n",
    "            if self.min_stack and self.stack[-1] == self.min_stack[-1]:\n",
    "                self.min_stack.pop()\n",
    "            self.stack.pop()\n",
    "\n",
    "    def top(self):\n",
    "        if self.stack:\n",
    "            return self.stack[-1]\n",
    "\n",
    "\n",
    "minStack = MinStack()\n",
    "\n",
    "print(minStack.getMin())\n",
    "minStack.push(3)\n",
    "minStack.push(5)\n",
    "minStack.push(2)\n",
    "minStack.push(6)\n",
    "minStack.push(1)\n",
    "\n",
    "print(minStack.getMin())\n",
    "\n",
    "minStack.pop()\n",
    "print(minStack.getMin())\n",
    "minStack.pop()\n",
    "print(minStack.getMin())\n",
    "minStack.pop()\n",
    "print(minStack.getMin())\n",
    "minStack.pop()\n",
    "print(minStack.getMin())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "80964b11-725d-4a7a-a9ff-6dea03f107ba",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-3\n",
      "0\n",
      "-2\n"
     ]
    }
   ],
   "source": [
    "minStack = MinStack()\n",
    "minStack.push(-2)\n",
    "minStack.push(0)\n",
    "minStack.push(-3)\n",
    "print(minStack.getMin()) # return -3\n",
    "minStack.pop()\n",
    "print(minStack.top())    #/ return 0\n",
    "print(minStack.getMin()) # return -2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "c4770e22-c940-47ae-96e2-d8ca0b2b1375",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 1 ['()']\n",
      "2 2 ['(())', '()()']\n",
      "3 5 ['((()))', '(()())', '(())()', '()(())', '()()()']\n",
      "4 14 ['(((())))', '((()()))', '((())())', '((()))()', '(()(()))', '(()()())', '(()())()', '(())(())', '(())()()', '()((()))', '()(()())', '()(())()', '()()(())', '()()()()']\n",
      "5 42 ['((((()))))', '(((()())))', '(((())()))', '(((()))())', '(((())))()', '((()(())))', '((()()()))', '((()())())', '((()()))()', '((())(()))', '((())()())', '((())())()', '((()))(())', '((()))()()', '(()((())))', '(()(()()))', '(()(())())', '(()(()))()', '(()()(()))', '(()()()())', '(()()())()', '(()())(())', '(()())()()', '(())((()))', '(())(()())', '(())(())()', '(())()(())', '(())()()()', '()(((())))', '()((()()))', '()((())())', '()((()))()', '()(()(()))', '()(()()())', '()(()())()', '()(())(())', '()(())()()', '()()((()))', '()()(()())', '()()(())()', '()()()(())', '()()()()()']\n"
     ]
    }
   ],
   "source": [
    "# Generate Paranthesis\n",
    "def generateParenthesis(n):\n",
    "    result = []\n",
    "    backtrack(result, n, '', 0, 0)\n",
    "    print(n, len(result), result)\n",
    "\n",
    "def backtrack(result, n, s, open, close):\n",
    "    if len(s) == 2 * n:\n",
    "        result.append(s)\n",
    "        return\n",
    "\n",
    "    if open < n:\n",
    "        backtrack(result, n, s + '(', open + 1, close)\n",
    "\n",
    "    if close < open:\n",
    "        backtrack(result, n, s + ')', open, close + 1)\n",
    "\n",
    "\n",
    "generateParenthesis(1)\n",
    "generateParenthesis(2)\n",
    "generateParenthesis(3)\n",
    "generateParenthesis(4)\n",
    "generateParenthesis(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "3905af0a-5f9b-46b9-b5d2-dc65f8835d62",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 0, 1], [0, 0, 0], [1, 0, 1]]\n",
      "[[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]\n",
      "[[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]\n"
     ]
    }
   ],
   "source": [
    "# Matrix set zero for full row and column if a cell has 0 in it\n",
    "\n",
    "def setZeroes(matrix):\n",
    "    \"\"\"\n",
    "    Do not return anything, modify matrix in-place instead.\n",
    "    \"\"\"\n",
    "    m, n = len(matrix), len(matrix[0])\n",
    "    # print(matrix, m, n)\n",
    "    zero_rows = []\n",
    "    zero_cols = []\n",
    "\n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            if matrix[i][j] == 0:\n",
    "                zero_rows.append(i)\n",
    "                zero_cols.append(j)\n",
    "\n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            if i in zero_rows or j in zero_cols:\n",
    "                matrix[i][j] = 0\n",
    "\n",
    "    print(matrix)\n",
    "\n",
    "def setZeroes_v2(matrix):\n",
    "    m, n = len(matrix), len(matrix[0])\n",
    "    zero_rows = [False] * m\n",
    "    zero_cols = [False] * n\n",
    "\n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            if matrix[i][j] == 0:\n",
    "                zero_rows[i] = True\n",
    "                zero_cols[j] = True\n",
    "\n",
    "    for i in range(m):\n",
    "        for j in range(n):\n",
    "            if zero_rows[i] or zero_cols[j]:\n",
    "                matrix[i][j] = 0\n",
    "    print(matrix)\n",
    "\n",
    "\n",
    "setZeroes([[1,1,1],[1,0,1],[1,1,1]])\n",
    "setZeroes([[0,1,2,0],[3,4,5,2],[1,3,1,5]])\n",
    "setZeroes_v2([[0,1,2,0],[3,4,5,2],[1,3,1,5]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "05b2a2de-a337-4e4d-a571-fdfac706b25d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 6, 9, 8, 7, 4, 5]\n",
      "[1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "''"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Spiral Matrix\n",
    "# Given an m x n matrix, return all matrix elements in spiral order.\n",
    "\n",
    "def spiral_matrix(matrix):\n",
    "    if not matrix:\n",
    "        return []\n",
    "\n",
    "    rows, cols = len(matrix), len(matrix[0])\n",
    "\n",
    "    top, bottom, left, right = 0, rows - 1, 0, cols - 1\n",
    "\n",
    "    result = []\n",
    "    while len(result) < rows * cols:\n",
    "        for i in range(left, right + 1):\n",
    "            result.append(matrix[top][i])\n",
    "        top += 1\n",
    "\n",
    "        for i in range(top, bottom + 1):\n",
    "            result.append(matrix[i][right])\n",
    "        right -= 1\n",
    "\n",
    "        if top <= bottom:\n",
    "            for i in range(right, left - 1, -1):\n",
    "                result.append(matrix[bottom][i])\n",
    "            bottom -= 1\n",
    "\n",
    "        if left <= right:\n",
    "            for i in range(bottom, top - 1, -1):\n",
    "                result.append(matrix[i][left])\n",
    "            left += 1\n",
    "\n",
    "    return result\n",
    "\n",
    "\n",
    "spiral_matrix([[1,2,3],[4,5,6],[7,8,9]])\n",
    "spiral_matrix([[1,2,3,4],[5,6,7,8],[9,10,11,12]])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "4e8b60db-3842-4509-98ac-9e5d647cf431",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 1], [2], [3], [4, 4], [5], [6], [], [], [], [10]]\n",
      "1\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "4\n",
      "5\n",
      "6\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "# Merge K Sorted lists\n",
    "# 1. Find Min and Max value from the List. Collect all values\n",
    "# 2. Bucket them\n",
    "# 3. Create new list from the bucket\n",
    "import sys\n",
    "\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "def mergeKSortedLists(lists):\n",
    "    min_val = sys.maxsize # Set Max value\n",
    "    max_val = -sys.maxsize # Set negative Max value\n",
    "\n",
    "    values = []\n",
    "    for l_list in lists:\n",
    "        for item in l_list:\n",
    "            min_val = min(min_val, item)\n",
    "            max_val = max(max_val, item)\n",
    "            values.append(item)\n",
    "\n",
    "    bucket = [[] for _ in range(max_val - min_val + 1)]\n",
    "\n",
    "    for item in values:\n",
    "        bucket[item - min_val].append(item)\n",
    "\n",
    "    # print(bucket)\n",
    "\n",
    "    head = ListNode()\n",
    "    curr = head\n",
    "    for i in range(len(bucket)):\n",
    "        for val in bucket[i]:\n",
    "            curr.next = ListNode(val)\n",
    "            curr = curr.next\n",
    "\n",
    "    return head.next\n",
    "\n",
    "def print_list(head):\n",
    "    while head:\n",
    "        print(head.val)\n",
    "        head = head.next\n",
    "\n",
    "head = mergeKSortedLists([[1,4,5],[1,3,4],[2,6, 10]])\n",
    "print_list(head)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "9fe28b26-c140-4c0a-bf6a-01d43603b1e9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[], [], [], [], [], [], [], [], [], []]\n"
     ]
    }
   ],
   "source": [
    "bucket = [[] for _ in range(10)]\n",
    "print(bucket)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "64c27c09-99f6-4dfc-9940-f70b706c014f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[], [], [], [], [], [], [], [], [], []]\n"
     ]
    }
   ],
   "source": [
    "bucket = [[]] * 10\n",
    "print(bucket)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "7b59eb1b-0320-4a53-b13f-d5d236fef57e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "def is_valid_sudoku(board):\n",
    "    if not board:\n",
    "        return False\n",
    "    duplicates = {}\n",
    "\n",
    "    for row in range(9):\n",
    "        for col in range(9):\n",
    "            val = board[row][col]\n",
    "\n",
    "            if val != '.':\n",
    "                # Row Key\n",
    "                key = val + 'R' + str(row)\n",
    "                if key in duplicates:\n",
    "                    return False\n",
    "                duplicates[key] = True\n",
    "    \n",
    "                # Column Key\n",
    "                key = val + 'C' + str(col)\n",
    "                if key in duplicates:\n",
    "                    return False\n",
    "                duplicates[key] = True\n",
    "    \n",
    "                #  3*3 Block\n",
    "                key = val + 'DLOCK' + str(row//3) + str(col//3)\n",
    "                if key in duplicates:\n",
    "                    return False\n",
    "                duplicates[key] = True\n",
    "\n",
    "    return True\n",
    "\n",
    "\n",
    "board = [[\"5\",\"3\",\".\",\".\",\"7\",\".\",\".\",\".\",\".\"]\n",
    ",[\"6\",\".\",\".\",\"1\",\"9\",\"5\",\".\",\".\",\".\"]\n",
    ",[\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\"6\",\".\"]\n",
    ",[\"8\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"3\"]\n",
    ",[\"4\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"1\"]\n",
    ",[\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"]\n",
    ",[\".\",\"6\",\".\",\".\",\".\",\".\",\"2\",\"8\",\".\"]\n",
    ",[\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"5\"]\n",
    ",[\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]]\n",
    "\n",
    "print(is_valid_sudoku(board))\n",
    "\n",
    "board = [[\"5\",\"3\",\".\",\".\",\"7\",\".\",\".\",\".\",\".\"]\n",
    ",[\"6\",\"5\",\".\",\"1\",\"9\",\"5\",\".\",\".\",\".\"]\n",
    ",[\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\"6\",\".\"]\n",
    ",[\"8\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"3\"]\n",
    ",[\"4\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"1\"]\n",
    ",[\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"]\n",
    ",[\".\",\"6\",\".\",\".\",\".\",\".\",\"2\",\"8\",\".\"]\n",
    ",[\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"5\"]\n",
    ",[\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]]\n",
    "\n",
    "print(is_valid_sudoku(board))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "7043818f-1ec5-4e63-b70a-577965b703a0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5]\n",
      "[1]\n",
      "[2, 3, 4]\n",
      "[4, 0, 2, 5, 3, 1]\n",
      "[1]\n",
      "[4, 2, 3]\n",
      "[0, 1, 2, 3, 4, 5, '_', '_', '_', '_', '_', '_', '_', '_', '_']\n",
      "[1, '_', '_', '_']\n",
      "[2, 3, 4, '_', '_', '_', '_', '_']\n"
     ]
    }
   ],
   "source": [
    "# Return unique elements\n",
    "def find_duplicates(arr):\n",
    "    arr.sort()\n",
    "    unique = []\n",
    "    for i in range(1, len(arr)):\n",
    "        if arr[i - 1] != arr[i]:\n",
    "            unique.append(arr[i - 1])\n",
    "\n",
    "    unique.append(arr[-1])\n",
    "\n",
    "    return unique\n",
    "\n",
    "# Find Unique elements using Hashmap\n",
    "def find_duplicates_v2(arr):\n",
    "    visited = {}\n",
    "    for i in range(len(arr)):\n",
    "        if arr[i] not in visited:\n",
    "            visited[arr[i]] = True\n",
    "\n",
    "    return list(visited.keys())\n",
    "\n",
    "# Find unique values. Replace duplicate with _\n",
    "def find_duplicates_v3(arr):\n",
    "    arr.sort()\n",
    "    idx = 0\n",
    "    for i in range(1, len(arr)):\n",
    "        if arr[i - 1] != arr[i]:\n",
    "            arr[idx] = arr[i - 1]\n",
    "            idx += 1\n",
    "\n",
    "    arr[idx] = arr[-1]\n",
    "    idx += 1\n",
    "\n",
    "    for i in range(idx, len(arr)):\n",
    "        arr[i] = '_' # 0\n",
    "\n",
    "\n",
    "    return arr\n",
    "\n",
    "print(find_duplicates([4, 2, 5, 3, 3, 1, 2, 4, 1, 5, 5, 5, 3, 1]))\n",
    "print(find_duplicates([1, 1, 1, 1]))\n",
    "print(find_duplicates([4, 4, 2, 3, 2, 2, 4, 3]))\n",
    "\n",
    "print(find_duplicates_v2([4, 0, 2, 5, 3, 3, 1, 2, 4, 1, 5, 5, 5, 3, 1]))\n",
    "print(find_duplicates_v2([1, 1, 1, 1]))\n",
    "print(find_duplicates_v2([4, 4, 2, 3, 2, 2, 4, 3]))\n",
    "\n",
    "print(find_duplicates_v3([4, 0, 2, 5, 3, 3, 1, 2, 4, 1, 5, 5, 5, 3, 1]))\n",
    "print(find_duplicates_v3([1, 1, 1, 1]))\n",
    "print(find_duplicates_v3([4, 4, 2, 3, 2, 2, 4, 3]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "a2a0c8ac-40b0-4ba7-bdda-71632ba76b1c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Tree Node\n",
    "class TreeNode(object):\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.left  = None\n",
    "        self.right = None\n",
    "\n",
    "def build_tree(arr, i, n):\n",
    "    root = None\n",
    "    if i < n and arr[i] is not None:\n",
    "        root = TreeNode(arr[i])\n",
    "        root.left = build_tree(arr, 2 * i + 1, n)\n",
    "        root.right = build_tree(arr, 2 * i + 2, n)\n",
    "    return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "49a70275-086f-445a-8312-56e1dcb4316e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 \n",
      "9 20 \n",
      "15 7 \n",
      "\n",
      "\n",
      "1 \n",
      "2 3 \n",
      "4 5 6 \n"
     ]
    }
   ],
   "source": [
    "def level_order(root):\n",
    "    if not root:\n",
    "        return\n",
    "\n",
    "    queue = [root]\n",
    "\n",
    "    while queue:\n",
    "        level_size = len(queue)\n",
    "        for i in range(level_size):\n",
    "            item = queue.pop(0)\n",
    "            print(item.value, end=\" \")\n",
    "            if item.left:\n",
    "                queue.append(item.left)\n",
    "            if item.right:\n",
    "                queue.append(item.right)\n",
    "        print(\"\")\n",
    "\n",
    "arr = [3, 9, 20, None, None, 15, 7]\n",
    "root = build_tree(arr, 0 , len(arr))\n",
    "\n",
    "level_order(root)\n",
    "\n",
    "print(\"\\n\")\n",
    "arr = [1, 2, 3, 4, None, 5, 6]\n",
    "root = build_tree(arr, 0 , len(arr))\n",
    "\n",
    "level_order(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3012ffcc-181a-4b1c-9712-6ae13308f3a0",
   "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.12.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}

practice_old.ipynb

RateLimitter.ipynb

N Queens - Total iterations 2057
Total answers - 92 (from wiki)