Table of Contents

Algorithms

  1. Array Duplicates:
    Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times. Find these repeating numbers in O(n) and using only constant memory space.

    1. Mathematical Solution: \(O(n), O(1)\)
      • Traverse the given array from i= 0 to n-1 elements
        • Go to index arr[i]%n and increment its value by n.
      • Now traverse the array again and print all those
        • indexes i for which arr[i]/n is greater than 1.
    2. Indexes Solution: \(O(n), O(1)\) 
       traverse the list for i= 0 to n-1 elements
 {
   check for sign of A[abs(A[i])] ;
   if positive then
      make it negative by   A[abs(A[i])]=-A[abs(A[i])];
   else  // i.e., A[abs(A[i])] is negative
      this   element (ith element of list) is a repetition
 }
  2. Re-Arranging Array Indexes:
    Rearrange an array so that arr[i] becomes arr[arr[i]] with O(1) extra space
    1. Mathematical Solution: \(O(n), O(1)\)
      • Increase every array element arr[i] by \((\text{arr}[\text{arr}[i]] % n) * n\).
      • Divide every element by \(n\).

    The idea is to store both numbers as the quotient and the remainder inside the array element

  3. Two Sum Problem:
    Given an array of integers, return indices of the two numbers such that they add up to a specific target.
    1. HashTable: \(O(n), O(1)\)
      Iterate and inserting elements into the table, we also look back to check if current element’s complement already exists in the table. If it exists, we have found a solution and return immediately.

  4. Permutations of an Array:
    Key Idea:

     def _permute(a, l, r, results): 
     if l==r: 
         results.append(a.copy())
     else: 
         for i in range(l,r+1): 
             a[l], a[i] = a[i], a[l] 
             _permute(a, l+1, r, results) 
             a[l], a[i] = a[i], a[l]
            
 def permute(arr: List[int]) -> List[List[int]]:
     results = []
     _permute(arr, 0, len(arr)-1, results)
     return results

    For strings:

     def _permute(s, chosen, results): 
 if len(s) < 1: 
     # results.append(a.copy())
     print(chosen)
 else: 
     for i in range(len(s)):
         # Choose
         c = s[i]
         chosen += c
         s = s.replace(c, "")
         # Explore
         _permute(s, chosen, results) 
         # UnChoose
         chosen = chosen[:-1]
         s = s[:i] + c + s[i:]
            
 def permute(s):
     results = []
     _permute(s, "", results)
     return results

 permute('abc')

    Generate permutation at index \(k\):

     def getPermutation(self, n, k):
     """
     :type n: int
     :type k: int
     :rtype: str 
     """
     k-=1
     nl = list(range(1,n+1))
     out = ''
     while n>0:
         temp = math.factorial(n-1)
         out+=str(nl.pop(k//temp))
         k %= temp
         n -= 1
     return out
  5. Hight/Depth of Tree:
    Use DFS: 
     def dfs(self, root, visited = [], depth=1):
     if not root.children:
         return depth
     # visited.append(root)
     max_depth = depth
     for node in root.children:
         # 2 Lines below: only needed if graph is not a tree
         # if node not in visited:
             # max_depth = max(self.dfs(node, visited, depth+1), max_depth)
         max_depth = max(self.dfs(node, depth+1), max_depth)
     return max_depth
        
    
 def maxDepth(self, root: 'Node') -> int:
     if not root:
         return 0
     return self.dfs(root)
  6. Pre-Order Traversal: 
     def preorderTraversal_iterative(self, root: TreeNode) -> List[int]:
     arr = []
     stack = []
     while 1:
         while root:
             stack.append(root)
             arr.append(root.val)
             root = root.left
         if not stack:
             break
         root = stack[-1].right
         stack.pop()
     return arr
    
    
 def preorderTraversal_recursive(self, root: TreeNode) -> List[int]:
     self.arr = []
     def helper(root):
         if not root:
             return
         self.arr.append(root.val)
         helper(root.left)
         helper(root.right)
     helper(root)
     return self.arr

    In-order:

     def inOrderT(root):    
     self.ans = []
     def helper(root):
         if not root:
             return
         helper(root.left)
         self.ans.append(root.val)
         helper(root.right)
     helper(root)
     return self.ans

Strings

  1. Uniqueness of characters:
    1. Array of indices / Hashmap: O(n=len(string)), O(256)
  2. Permutations (str a is perm of str b):
    1. Sort both -> equality: O(n log n)
    2. (fixed) array of character counts
  3. Replace a char in str w/ more than one char (e.g. all ‘a’ in str -> ‘bb’):
    1. count number of ‘a’ in str -> multiply by (len(‘bb’) - 1) -> start modifying from back of string (backwards)
  4. Palindrome:
    To check for if a string is a Palindrome, count the number of characters:
    • even len(s): all char-counts must be even
    • odd len(s): only one char-count can be odd

    Best sol (Still O(N)):

    1. Use a bit vector -> map chars to 26 bit-vector -> toggle everytime you see char -> check bit vector == 0 (has at most 1 “on” bit)

  5. Q1.5:

  6. Rotate Matrix (implement it):

  7. Check str a is ROTATION of str b:
    By making one call to isSubstring:
    • Note: str b always substring of str a+a (e.g. “waterbottle”, “erbottlewat”: “erbottlewat” isSubstr of “waterbottle”+”waterbottle”=”wat_erbottlewat_erbottle”)
  8. Notes:
    • Ask ASCII or UTF8

NOTES

  1. Listen Carefully
  2. Draw an example
  3. Find Bruteforce
  4. Optimize:
    • look for unused info - more examples - start with “incorrect” sol - timeVSspace - precompute - BCR
  5. Walk through the algorithm
  6. Implement
  7. Test

Face-up/Face-down Cards:
Video

  1. A card deck of 52 cards, 13 face-up.
  2. The Face-up cards are distributed randomly throughout the deck.
  3. You are blindfolded and you don’t know anything about the cards.
  4. How can you create two piles with the same amount of face-up cards?

Let \(x\) be the number of face-up cards in pile #1

  \(\uparrow\) \(\downarrow\)
pile #1 \(= 13\) \(x\) \(13 - x\)
pile #2 \(= 39\) \(13 - x\) \(26 + x\)

Face-up/Face-down Cards Generic Version:

  1. A card deck of 52 cards, \(k\) face-up.

Let \(x\) be the number of face-up cards in pile #1

  \(\uparrow\) \(\downarrow\)
pile #1 \(= k\) \(x\) \(k - x\)
pile #2 \(= 52-k\) \(k - x\) \((52-k) - (k-x)\)

Face-up/Face-down Cards Generic Version (flipped):

  1. A card deck of 52 cards, \(k\) face-down.
  2. How can you create two piles with the same amount of face-down cards?

Let \(x\) be the number of face-down cards in pile #1

  \(\uparrow\) \(\downarrow\)
pile #1 \(= k\) \(k-x\) \(x\)
pile #2 \(= 52-k\) \((52-k)-(k-x)\) \(k - x\)