KTH LARGEST ELEMENT IN AN ARRAY

# KTH LARGEST ELEMENT IN AN ARRAY
"""
You are given an unsorted array of integers and an integer k, return kth largest 
element in the array. 

Largest in the sorted order. 

nums = [2,3,1,5,4] , k = 2 
output : 4 

"""
import heapq
def kth_largest_array(nums, k):
    heap = []
    for num in nums:
      heapq.heappush(heap, num)
      if len(heap) > k:
          heapq.heappop(heap)
    return heap[0]

'''
heap order - it guarantees is parent < children 
Smallest element will always be at the top the rest can be in any order 
nums = [2,3,1,5,4] k = 2 
heap = [1,2,3] if > k yes so we pop 
heap = [2,3]
add 4 heap = [2,3,4]  is > k yes hence we pop 
heap = [3,4]
add 5 heap = [3,4,5] > k yes hence we pop 
heap = [4,5] 
Then we return the top of heap[0]
= 4 
'''
# sorted 
def kth_largest_array(nums, k):
    nums.sort()
    return nums[len(nums) - k]

KTH LARGEST ELEMENT IN A STREAM

# KTH LARGEST ELEMENT IN A STREAM

"""
Design a class to find the kth largest integer in a stream of values that 
include dupicates.

Implement the following methods. 
Constructor (int k , int [] nums) 
Int add (int val)

Input: ["KthLargest", [3, [1, 2, 3, 3]], 
"add", [3], "add", [5], "add", [6], "add", [7], "add", [8]]
k = 3 
stream = [1,2,3,3]
So we first push the first ones and then we will pop the extra ones
init 
push 1 - [1]
push 2 - [2]
push 3 - [3]
push 3 - [3] size > k hence we pop the smallest and add it 
stream = [2,3,3]

add (3) - size > k, hence we pop smallest [3,3,3] - return 3 
add (5) - size > k, hence we pop smallest [3,3,5] - return 3 
add (6) - size > k, hence we pop smallest [3,5,6] - return 3 
add (7) - size > k, hence we pop smallest [5,6,7] - return 5 
add (8) - size > k, hence we pop smallest [6,7,8] - return 6 
Hence our output is [null,3,3,3, 5,6]

Assumptions
- Can nums be empty 
- Can k be larger than nums length 
- Are duplicates counted by position or uniqueness
- -ve numbers possible?
- Will there be atleast k elements before add ()

"""
# SORTING 
k = k 
arr = nums 

def add(val):
    arr.append(val)
    arr.sort()
    return arr[len(arr) - k] 

class KthLargest:
    def __init__(self, k, nums):
        self.k = k
        self.arr = nums

    def add(self, val):
        self.arr.append(val)
        self.arr.sort()
        return self.arr[len(self.arr) - self.k]

# HEAP APPROACH

import heapq 
class Kth Largest:
    def __init__(self, k, nums):
        self.k = k
        self.heap = []
        
        for num in nums:
            heapq.heappush(self.heap, num)
            if len(self.heap)> k:
                heap.heappop(self.heap)
        def add (self, val):
            heapq.heappush(self.heap, val)
            if len(self.heap) > self.k:
                heapq.heappop(self.heap)
            if len(self.heap)< k:
                return -1 

        return self.heap[0]

    

# FIND MEDIAN FROM DATA STREAM 
# SORTING APPROACH 
data = []

def addNum(num):
    data.append(num)
  
def findMedian():
    data.sort()
    mid = len(data)//2  # it will give me the index not the actual value 
    if len(data) % 2 != 0:
        return float(data[mid]  # odd 
    else:
        return (data[mid-1] + data[mid])/2  # even 
'''
data = []
addNum(1) - data = [1]
addNum(2) - data = [1,2]
addNum(3) - data = [1,2,3] 

findMedian():
sorted = [1,2,3]
mid = 3//2 = 1 
odd - return data[1] = 2 

addNum(4) - data = [1,2,3,4] 
findMedian():
sort = [1,2,3,4]
mid = 4//2 = 2 
even - return data[1] +data[2]/2 = 2 +3/2 = 2.5 
'''
class MedianFinder:
    def __init__(self):
        self.data = []
    
    def addNum(self, num):
        self.data.append(num)               # O(1) - just append
    
    def findMedian(self):
        self.data.sort()                    # O(n log n) - sort only when needed
        mid = len(self.data) // 2
        if len(self.data) % 2 != 0:
            return float(self.data[mid])            # odd - middle element
        return (self.data[mid-1] + self.data[mid]) / 2  # even - average

# HEAPS APPROACH 
import heapq
class MedianFinder:
    def __init__(self):
        self.left = []
        self.right = []

    def add(self, num):
        # always push to left first
        heapq.heappush(self.left, -num)
        
        # fix order: left top must <= right top
        if self.left and self.right and (-self.left[0] > self.right[0]):
            heapq.heappush(self.right, -heapq.heappop(self.left))
        
        # fix sizes
        if len(self.left) > len(self.right) + 1:   # left too big
            heapq.heappush(self.right, -heapq.heappop(self.left))
        if len(self.right) > len(self.left):        # right too big
            heapq.heappush(self.left, -heapq.heappop(self.right))
        
        return self.get_median()
    
    def get_median(self):
        if len(self.left) > len(self.right):
            return float(-self.left[0])             # odd — left top
        return (-self.left[0] + self.right[0]) / 2 # even — average


# MK AVERAGE IN A STREAM  
class MKAverage:
    def __init__(self, m, k):
        self.m = m
        self.k = k
        self.stream = []
    
    def addElement(self, num):
        self.stream.append(num)             # just append, sort later
    
    def calculateMKAverage(self):
        if len(self.stream) < self.m:
            return -1                       # not enough elements yet
        
        last_m = self.stream[-self.m:]      # take last m elements
        last_m.sort()                       # sort them
        trimmed = last_m[self.k:-self.k]    # remove k from each end
        
        return sum(trimmed) // len(trimmed) # average of middle
'''
m=6, k=2
obj = MKAverage(6, 2)

addElement(3)  → stream=[3]
addElement(1)  → stream=[3,1]
addElement(4)  → stream=[3,1,4]
addElement(1)  → stream=[3,1,4,1]
addElement(5)  → stream=[3,1,4,1,5]
addElement(9)  → stream=[3,1,4,1,5,9]

calculateMKAverage():
len=6 == m continue

last_m   = [3,1,4,1,5,9]
sorted   = [1,1,3,4,5,9]
trimmed  = [1,1,3,4,5,9][2:-2]
         = [3,4]
average  = (3+4)//2 = 3 

addElement(2) → stream=[3,1,4,1,5,9,2]

calculateMKAverage():
last_m   = [1,4,1,5,9,2]    - last 6 only, 3 dropped off
sorted   = [1,1,2,4,5,9]
trimmed  = [1,1,2,4,5,9][2:-2]
         = [2,4]
average  = (2+4)//2 = 3 
'''

LAST STONE WEIGHT

"""
      Intuition:
      - Iterate through the array of stones
      - At each step pick the two heaviest stones (maxHeap)
          - if x == y:
              destroy both stones
          - if x < y:
              destroy x
              y = y -x
      
      stones = [2,3,6,2,4]

      => [2, 3, 2, 2]
      => [1, 2, 2]
      => [1]

"""
import heapq
 def lastStoneWeight(self, stones: List[int]) -> int:
      # Create max heap from stones
      heapq.heapify_max(stones)
      # Run simulation
      while len(stones) > 1:
          x = heapq.heappop_max(stones)
          y = heapq.heappop_max(stones)
          if x == y:
              continue 
          z = x - y
          heapq.heappush_max(stones, z)
      if not stones:
          return 0 
      return stones[0]

K CLOSEST POINTS TO ORIGIN

import heapq
from math import sqrt
"""
    Assumptions:
    - Return in any order

    Intuition:
    - Find all the euclidean distances of the points
    - Keep the points in minheap
    - Return the k closest points to the origin

    points = [[0,2],[2,2]], k = 1
    minHeap = [ [8, 2, 2]]
    res = [[0, 2]]

    Time: O(n)
    Space: O(n)

    """

def kClosest(points, k):
    minHeap = []
    res = []

    for (x, y) in points:
        z = sqrt((x ** 2) + (y ** 2))
        heapq.heappush(minHeap, [z, x, y])
    
    while len(res) < k:
        (_, x, y) = heapq.heappop(minHeap)
        res.append([x, y])
    
    return res

TASK SCHEDULER

from collections import Counter, deque
import heapq

def leastInterval(tasks, n):
    # step 1 — count frequencies
    count = Counter(tasks)
    
    # step 2 — max heap using negation
    maxHeap = [-cnt for cnt in count.values()]
    heapq.heapify(maxHeap)
    
    time = 0
    q = deque()     # [count, readyTime]
    
    while maxHeap or q:
        time += 1
        
        if not maxHeap:
            # heap empty — jump straight to next ready task
            time = q[0][1]
        else:
            # run most frequent task
            cnt = 1 + heapq.heappop(maxHeap)   # decrement (remember negated)
            if cnt:                             # still has remaining count
                q.append([cnt, time + n])       # push to cooldown queue
        
        # check if front of queue is ready
        if q and q[0][1] == time:
            heapq.heappush(maxHeap, q.popleft()[0])
    
    return time

DESIGN TWITTER

class Twitter:

    def __init__(self):
        self.time = 0
        self.followMap = defaultdict(set)
        self.tweetMap = defaultdict(list)

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweetMap[userId].append((self.time, tweetId))
        self.time += 1

    def getNewsFeed(self, userId: int) -> List[int]:
        feed = self.tweetMap[userId][:]
        for followeeId in self.followMap[userId]:
            feed.extend(self.tweetMap[followeeId])

        feed.sort(key=lambda x: -x[0])
        return [tweetId for _, tweetId in feed[:10]]

    def follow(self, followerId: int, followeeId: int) -> None:
        if followerId != followeeId:
            self.followMap[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.followMap[followerId].discard(followeeId)

Decode Ways

A string consisting of uppercase english characters can be encoded
to a number using the following mapping:
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"

s= '12'
output = 2 
'12' could be decoded as 'AB' (1 2) or 'L' (12)

s = '01'
output = 0 
it cannot be decoded because '01' cannot be mapped into a letter.

Assumptions 
- What happens when the string is empty we return 0 
- What happens if the string starts with 0? we return 0 since its invalid 
- What if string has consecutive zeros? return 0 since its invalid as well 
- Are we working with strings or them as values
- They are valid range is 1-26 only 

Define the states 
ways(i) = number of wats to decode s starting at index i 
s = '126'
     012

Define the recurrence 
At each index i we have 2 choices 
- decode single digit - s[i] 
- decode two digits - s[i + i +2] 

ways(i) = ways(i+1) + ways(i+2)

Time : O(n) 
Space : O(n)

def decode_ways(s):
  memo = {}
  def ways(i):
    # base cases 
    if i == len(s): # decode entire string 
      return 1 
    if s[i] == '0': # invalid 
      return 0 
    
    # memo check 
    if i in memo:
      return memo[i]
    #decode single digit 
    memo[i] = ways[i+1] 

    # decode 2 digits if valid 
    if i+1 < len(s) and 10 <= int(s[i+i+2]) <= 26 
      memo[i] += ways(i +2)
    return memo[i]
  
  return ways(0)

'''
ways(0) is called
    is 0 == len(s)? no
    is s[0] == '0'? no, s[0] = '1'
    is 0 in memo? no

    choice 1: single digit
      memo[0] = ways(1)

        ways(1) is called
          is 1 == len(s)? no
          is s[1] == '0'? no, s[1] = '2'
          is 1 in memo? no

          choice 1: single digit
            memo[1] = ways(2)

              ways(2) is called
                is 2 == len(s)? YES - base case
                return 1 

            memo[1] = 1

          choice 2: two digits
            is i+1 < len(s)? 2 < 2? NO skip

          return memo[1] = 1 

    memo[0] = 1

    choice 2: two digits
      is i+1 < len(s)? 1 < 2? YES 
      is 10 <= int("12") <= 26? YES 
      memo[0] += ways(2)
              =  1 + 1 = 2 

    return memo[0] = 2 
'''

Word Break

Given a string s and a dictonary of strings wordDict , return true if s
can be segemented into a space - separated sequence of dictonary words. 

You are allowed to reuse words in the dict an unlimited times. 
Assume all words are unique. 

s= 'neetcode' , wordDict = ['neet', 'code']
output = true 

s = "catsincars", wordDict = ["cats","cat","sin","in","car"]
Output: false

Assumptions
- What happens when s in empty? return True 
- What if wordDict is empty we return false 
- Case sensitive? upper and lower case 
- Can we reuse words - yes we can 
- Will all the words be unique? yes 

Define the states 
segment(i) = can we segment s[i:] into valid dictonary words? 
s = 'neetcode'
     01234567
i tracks current position in s 

Define the recurrence 
At each index i we try every word in wordDict:
  if s[i + i + len(word)] == word : # word matches at position i 
    segement(i) = segement(i + len(word)) # skip past the word 

 segment(i) = any(segment(i + len(word))
               for word in wordDict
               if s[i: i + len(word)] == word
               
Base cases 
if i == len(s):
  return True 


Time : O(n)
Space : O(n)

def word_break(s, wordDict):
    memo = {}
    def segment(i):
    # Base case 
    if i == len(s):
      return True 
    # memo check 
    if i in memo:
      return memo[i]
    memo[i] = False  # no match found 
    for word in wordDict:
        end = i + len(word) # where the word would end 
        if s[i:end] == word: # word matches at position i 
            if segment(end): # can we segment the rest 
                memo[i] = True # found a valid path 
                break   # no need to check further 
        return memo[i]

    return segment(0)

Unique paths

There is an m x n grid where you are allowed to move either down or
to the right at any point in time. 

Return the number of possible unique paths that can be taken from the 
top-left corner of the grid (grid[0][0]) to the bottom right corner 
(grid[m-1][n-1] 

input : m = 3 , n = 6 
output : 21 

input: m = 3 , n = 3 
output : 6 

Assumptions 
- What if m or n is 1? only one path , go straight 
- What if m or n is 0? return 0 
- Can we only move right or down ?
- What if m == n == 1 ? already at destination hence return 1 

Define the states
paths(row, col) = no of unique paths from (row, col)
                  to bottom right corner (m-1, n-1)
grid :
0    1    2    3    4    5
0  [start  →   →   →   →   →  ]
1  [  ↓                       ]
2  [  ↓    →   →   →   →  end ]

Define the recurrence 
At each cell we have 2 choices:
  - Choice 1 : move right - paths(r, col +1)
  - Choice 2 : move down - paths(row+1, c)
paths(row,col) = paths(row, col+1) + paths(row+1, col)

Base cases 
if row == m or col == n: # out of bounds 
  return 0 
if row == m-1 and col == n -1: # reached destination
  return 1 

Time: 
Space:

def unique_paths(m,n):
    memo = {}
    def paths(row, cols):
        # Base case 
        if row == m or col == n:
          return 0 
        if row == m-1 and col == n-1:
          return 1
        # Memo check 
        if (row, col) in memo:
           return memo[(row,col)]
        memo[(row, col)] = paths(row,col+1) + paths(row+1, col)
        return memo[(row,col)]
     return paths(0,0)

Longest Increasing Path In a Matrix

You are given a 2D grid of integers matrix, where each integer is >= 0 
return the length of longest strictly increasing path within matrix. 
You can either move horizontally or vertically. (right, left, up , down)
No diagonal move. 
row+1 , col (right)
row -1, col (left)
row, col +1 (down)
row, col -1 (up)

matrix 
[5,5,3],
[2,3,6],
[1,1,1]
output = 4 
The longest increasing path is [1, 2, 3, 6] or [1, 2, 3, 5].

def increasing_path(matrix):
    memo = {}
    ROWS, COLS = len(matrix), len(matrix[0])
    def path(r,c, prevVal):
    # base cases 
        if r <0 or r >= ROWS or c<0 or c>= COLS or matrix[r][c] <= prevVal:
          return 0 
      # memo check 
        if (r,c) in memo:
          return memo[(r,c)]
      # move in all directions 
        memo[(r,c)] = 1 
        for dr, dc in directions:
            neighbor = path(r+ dr, c+ dc, matrix[r][c])
            memo[(r,c)] = max(memo[(r,c)], 1 + neighbor)
        return memo[(r,c)]
        
    longest = 0 
    for r in range(ROWS):
      for c in range(COLS):
        dfs(longest, path(r,c,-1))
    return longest
    

Partition Equal Subset Sum

You are given an array of +ve integers nums.

Return true if you can partition the array into 2 subsets, subset1 and subset2 
where sum(subset1) == sum(subset2). Otherwise return false 

Input: nums = [1,2,3,4]
Output: true

Input: nums = [1,2,3,4,5]
Output: false

2 choices 
- Take the current number into the subset 
- Skip the current number 

We need to keep reducing the target until :
  - target becomes 0 
  - we have run out of numbers or target becomes -ve 

Define the states 
I need to output a boolean if we can partition the array into 2 subsets.

Define the recurrence relation


Base cases 
if sum(nums) % 2 : return False # if its odd we return False 

Time: O(n)
Space: O(n)

# Brute force 
'''
Time: O (2^n)
Space: O (n)

'''
def canPartition(nums):
    if sum(nums) % 2:
      return False 
    def dfs(i, target):
      if i >= len(nums):
        return target == 0 
      if target < 0:
        return False 
      return dfs(i+1, target) or dfs(i+1, target - nums[i])
    return dfs(0, sum(nums)//2)

# MEMOIZATION 
def canPartition(self, nums: List[int]) -> bool:
    if sum(nums) % 2:
        return False

    target = sum(nums) // 2
    memo = {}
    
    def partition(i, remaining):
        # base cases
        if remaining == 0:                 
            return True
        if i == len(nums):                    
            return False
        if remaining < 0:                    
            return False
        
        # memo check 
        if (i, remaining) in memo:
            return memo[(i, remaining)]
        
        memo[(i, remaining)] = partition(i+1, remaining - nums[i])  or partition(i+1, remaining)            
        return memo[(i, remaining)]
    
    return partition(0, target)

Target Sum

You are given an array of integers nums and an integer target. 

For each number in the array, you can choose to either add or substract it to 
a total sum. 

Return the different ways that you can build the expression such that the total
sum equals target. 

nums = [2,2,2] , target = 2 
output : 3 

There are 3 different ways to sum the input numbers to get a sum of 2.
+2 +2 -2 = 2
+2 -2 +2 = 2
-2 +2 +2 = 2

def target_sum(nums, target):
    memo = {}
    
    def ways(i, remaining):
        # base cases
        if i == len(nums) and remaining == 0:   # hit target
            return 1
        if i == len(nums):                      # missed target
            return 0
        
        # memo check
        if (i, remaining) in memo:
            return memo[(i, remaining)]
        
        # two choices: add or subtract
        memo[(i, remaining)] = (
            ways(i+1, remaining - nums[i])      # add nums[i]
            +
            ways(i+1, remaining + nums[i])      # subtract nums[i]
        )
        
        return memo[(i, remaining)]
    
    return ways(0, target)

Interleaving String

You are given 3 strings. s1, s2 and s3. Return true if s3 is formed by
interleaving s1 and s2 together or false otherwise. 

Assume s1,s2 and s3 consists of lowercase letters. 

Input: s1 = "aaaa", s2 = "bbbb", s3 = "aabbbbaa"
Output: true

We can split s1 into ["aa", "aa"], s2 can remain as "bbbb" and 
s3 is formed by interleaving ["aa", "aa"] and "bbbb".

Input: s1 = "", s2 = "", s3 = ""
Output: true

Input: s1 = "abc", s2 = "xyz", s3 = "abxzcy"
Output: false

Time : O(nxm) n - len(s1) and m - len(s2)
Space: O(n ) - memo store and call stack

def isInterleaving_string(s1,s2,s3):
    if len(s1) + len(s2) != len(s3):
        return False 
    memo = {}
    def interleave(i,j):
      if i == len(s1) and j == len(s2):
        return True 
      # memo check 
      if (i,j) in memo:
        return memo[(i,j)]  
      # make the choices 
      memo[(i,j)] = False  #Asssume no match 
      if i < len(s1) and s1[i] == s3[i+j]: # match s1
        if interleave(i+1, j)
          memo[(i,j)] = True 
          return True 

      if j < len(s2) and s2[j] == s3[i+j]: # match s2 
          if interleave(i, j+1):
              memo[(i,j)] = True 
              return True 
      return memo[(i,j)] 

    return interleave(0,0)

'''
length check = 4+4 == 8 
interleave(0,0) 
interleave (0,0) is 
  i =0 == len(s1) and j=0==len(s2) - no 
  (0,0) in memo? no 
  s3[0+0] = s3[0] = 'a' 

choice 1: s1[0] ='a' == s3[0] = 'a'? yes 
    interleave (1,0) is called 
      s3[1+0] = s3[1] = 'a' 
   choice 1: s1[1] = 'a' == s3[1] = 'a' ? yes 
    interleave (2,0) is called 
      s3[2+0] = s3[2] = 'b' 
    choice 1 : s1[2] = 'a' == s3[2] = 'b' ? no 
    choice 2 : s2[0] = 'b' == s3[2] = 'b' ? yes 
        interleave (2,1) is called 
        s3[2+1] = s3[3] = 'b' 
      choice 1 : s1[2] = 'a' == s3[4] = 'b' ? no 
      choice 2 : s2[2] = 'b' == s3[4] = 'b' ? yes 
        interleave(2,3) is called 
        s3[2+3] = s3[5] = 'b' 
     choice 1 : s1[2]= 'a' == s3[5] = 'b' ? yes 
       interleave (2,4) is called 
       s3[2+4] = s3[6] = 'a'
       j = 4 == len(s2) so skip choice 2 

    choice 1 : s1[2] = 'a' == s3[6] = 'a' ? yes 
      interleave (3,4) is called 
      s3[3+4] = s3[7] = 'a'
      j = 4 == len(s2) so skip choice 2 
     
    choice 1: s1[3]= 'a' == s3[7] = 'a'? yes 
      interleave (4,4) is called 
      i == len(s1) and j==len(s2) ? yes 
      return True 
    
      memo[(3,4)] = True : return True 
      memo[(2,4)] = True  : return True 
    
    memo[(2,3)] = True 
    memo[(2,2)] = True 
    memo[(2,1)] = True 
    memo[(2,0)] = True 
    memo[(1,0)] = True 

memo[(0,0)] = True 
True 
'aa' +'bbbb' + 'aa'
'''

def interleaving_string(s1, s2, s3):
    if len(s1) + len(s2) != len(s3):
        return False
    
    memo = {}
    
    def interleave(s1_idx, s2_idx, s3_idx):
        # base case: used all of s3
        if s3_idx == len(s3):
            return s1_idx == len(s1) and s2_idx == len(s2)
        
        # memo check
        if (s1_idx, s2_idx) in memo:
            return memo[(s1_idx, s2_idx)]
        
        result = False
        
        # choice 1: match s1
        if s1_idx < len(s1) and s1[s1_idx] == s3[s3_idx]:
            result = interleave(s1_idx+1, s2_idx, s3_idx+1)
        
        # choice 2: match s2 only if s1 failed
        if not result and s2_idx < len(s2) and s2[s2_idx] == s3[s3_idx]:
            result = interleave(s1_idx, s2_idx+1, s3_idx+1)
        
        memo[(s1_idx, s2_idx)] = result
        return result
    
    return interleave(0, 0, 0)

Edit Distance

You are given 2 strings word1 and word2, each consisting of lowercase 
english letters. 
You are allowed to perform 3 operations on word1 an unlimited number of
times.   
  - Insert a character at any position 
  - Delete a character at any position
  - Replace a character at any position
Return the min number of operations to make word1 equal word2

Input: word1 = "monkeys", word2 = "money"
Output: 2
monkeys -> monkey (remove s)
monkey -> money (remove k)

Input: word1 = "neatcdee", word2 = "neetcode"
Output: 3
neatcdee -> neetcdee (replace a with e)
neetcdee -> neetcde (remove last e)
neetcde -> neetcode (insert o)

Time : O(m x n) 
Space: O(m x n)

# Brute force approach 
def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    def edit(i, j):
      if i == m:
          return n-j
      if j == n:
          return m-i 
      if word1[i] == word2[j]:
          return edit(i+1, j +1)
      res = min(edit(i+1, j) , edit(i, j+1))
      res = min(res, edit(i+1, j+1))
      return res +1 
    return edit(0,0)


# Memoization
def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    memo = {}
    def edit(i, j):
      if i == m:
          return n-j
      if j == n:
          return m-i
      if (i,j) in memo:
          return memo[(i,j)] 
      if word1[i] == word2[j]:
          memo[(i,j)] = memo(i+1, j+1)
      else:
        res = min(edit(i+1, j) , edit(i, j+1))
        res = min(res, edit(i+1, j+1))
        memo[(i,j)] = res + 1
        return memo[(i,j)] 
    return edit(0,0)

Burst Balloons

You are given an array of integers nums of size n. The ith element represents
a balloon with an integer value of nums[i]. You must burst all of the balloons. 

If you burst the ith balloon, you will receive nums[i-1] * nums[i] * nums[i+1] coins
If i-1 or i+1 goes out of bounds of the array, then assume the out of bounds value is 1.

Return the maximum no of coins you can receive by busrting all balloons. 

nums = [4,2,3,7]
output = 143 
Explanation:
nums = [4,2,3,7] --> [4,3,7] --> [4,7] --> [7] --> []
coins =  4*2*3    +   4*3*7   +  1*4*7  + 1*7*1 = 143

def max_coins(nums):
    ballons = [1] + nums +[1]
    memo = {}
    def burst(left, right):
        if left > right:
          return 0 
        if (left, right) in memo:
          return memo[(left, right)]
        memo[(left, right)] = 0 
        
        for last in range(left, right +1):
            coins = ballons[left-1] * ballons[last] * ballons[right+1]
            coins += burst(left, last-1) + burst(last+1, right)
            memo[(left, right)] = max(memo[(left, right)], coins)

        return memo[(left, right)]

    return burst(1, len(ballons)-2)

Regular Expression Matching

You are given an input string s consisting of lowercases english letters, and 
a pattern p consisting of lowercase english letters, as well as '.' and '*' characters.

Return true if the pattern matches the entire input string, otherwise return Flse

'.' matches any single character 
'*' matches 0 or more of the preceding element
s = 'aa' p = '.b' 
output = false 

Regardless of which character we choose for the '.' in the pattern, 
we cannot match the second character in the input string.

s= 'nnn' p = 'n*' 
output = true 
'*' means zero or more of the preceding element, 'n'. We choose 'n' to 
repeat three times.

s = "xyz", p = ".*z"
Output: true
The pattern ".*" means zero or more of any character, so we choose ".." 
to match "xy" and "z" to match "z".

Time: O (n)
Space: O(n)

# Brute Force approach 
def isMatch(s,p):
    m, n = len(s), len(p)

        def dfs(i, j):
            if j == n:
                return i == m

            match = i < m and (s[i] == p[j] or p[j] == ".")
            if (j + 1) < n and p[j + 1] == "*":
                return (dfs(i, j + 2) or          # don't use *
                       (match and dfs(i + 1, j))) # use *
            if match:
                return dfs(i + 1, j + 1)
            return False

        return dfs(0, 0)
    


# Memoization
def isMatch(s,p):
        m, n = len(s), len(p)
        cache = {}

        def dfs(i, j):
            if j == n:
                return i == m
            if (i, j) in cache:
                return cache[(i, j)]

            match = i < m and (s[i] == p[j] or p[j] == ".")
            if (j + 1) < n and p[j + 1] == "*":
                cache[(i, j)] = (dfs(i, j + 2) or
                                (match and dfs(i + 1, j)))
                return cache[(i, j)]

            if match:
                cache[(i, j)] = dfs(i + 1, j + 1)
                return cache[(i, j)]

            cache[(i, j)] = False
            return False

        return dfs(0, 0)

Best Time to Buy And Sell Stock With Cooldown

You are given an integer array prices where prices[i] is the price of 
NeetCoin on the ith day.

You may buy and sell one NeetCoin multiple times with the following 
restrictions:

    After you sell your NeetCoin, you cannot buy another one on the 
    next day (i.e., there is a cooldown period of one day).
    You may only own at most one NeetCoin at a time.

You may complete as many transactions as you like.

Return max profit you can achieve. 
Input: prices = [1,3,4,0,4]
Output: 6

Buy on day 0 (price = 1) and sell on day 1 (price = 3), profit = 3-1 = 2. 
Then buy on day 3 (price = 0) and sell on day 4 (price = 4), 
profit = 4-0 = 4. Total profit is 2 + 4 = 6.

# Brute Force approach
def maxProfit(prices):
        def dfs(i, buying):
            if i >= len(prices):
                return 0

            cooldown = dfs(i + 1, buying)
            if buying:
                buy = dfs(i + 1, not buying) - prices[i]
                return max(buy, cooldown)
            else:
                sell = dfs(i + 2, not buying) + prices[i]
                return max(sell, cooldown)

        return dfs(0, True)

# Memoization
def maxProfit(prices):
        dp = {}  # key=(i, buying) val=max_profit

        def dfs(i, buying):
            if i >= len(prices):
                return 0
            if (i, buying) in dp:
                return dp[(i, buying)]

            cooldown = dfs(i + 1, buying)
            if buying:
                buy = dfs(i + 1, not buying) - prices[i]
                dp[(i, buying)] = max(buy, cooldown)
            else:
                sell = dfs(i + 2, not buying) + prices[i]
                dp[(i, buying)] = max(sell, cooldown)
            return dp[(i, buying)]

        return dfs(0, True)

Lets solve the neetcode 150 dynamic programming list.

So when the interviewer start with number of ways just know thats a DP problem.

Basics first.

So dynamic programming you can solve the problem with a brute force approach (recursion), memoization or using tabulation.

My focus will be mostly memoization so I can cement the recursion approach. In this approach, we try to solve the bigger problem by recursively finding the solution to smaller sub-problems. Whenever we solve a sub-problem, we cache its result so that we don’t end up solving it repeatedly if it’s called multiple times. Instead, we can just return the saved result.

When you thinking of solving using dynamic programming you need to first think of a few things.

1. Define the states. It is what uniquely identifies a subproblem. What does each DP entry represent? Think what am I trying to compute at each step? Like of the pattern that you need to use.

Example am I solving using fibonnaci, knapsack, LIS or LCS.

1. Define the recurrence. How do I build the solution for a state using smaller states. Like what is the algorithm that will help me achieve what I need to solve what I am being asked.
2. Choose the correct implementation style. How do I actually code it. Do I use brute force, memoization or tabulation.

So something I have noticed is you can choose to solve the problem using dictionary memoization or array memoization.

My focus will be mainly dictionary (hashmap) technique to enforce mastery.

So that you can understand how memoization works

memo = empty map {}
# helper function 
f(sub_problem_id):
  # basecases
  if sub_problem is basecase:
    return result directly
  if subproblem in memo_map:
    return cached result 
  memo[subproblem_id] = recurrence relation formula
  return memo[subproblem_id]
return f(initial subproblem)

Climbing stairs

You are climbing stairs.
It takes n steps to reach the top. 
Each time you can either climb 1 or 2 steps. 
(This forms the basecases)

the 3 ways are:
  1+1+1
  1+2
  2+1

Define the states
- How many ways can I reach step i (current step)

Define the recurrence 
- You have 2 choices : 1 or 2 steps
- Climb 1 step 
- Climb 2 steps 
dfs(i) = dfs(i-1) + dfs(i-2)
Hence it resembles fibonnaci sequence 

Basecases
if i == n:
    return 1 - valid path 
if i > n:
    return 0 - invalid path 


We will implement using memoization 

Time : O(n) - memoization ensures each subproblem is solved exactly once.
Space: O(n) - for the memo table and O(n) for the recursive call stack

# FORWARD APPROACH 
def climbing_stairs(n):
  memo= {}
  def dfs(i):
    if i == n:
      return 1 
    if i > n:
      return 0 
    if i in memo:
      return memo[i]
    memo[i] = dfs( i + 1) + dfs(i +2)
    return memo[i]
  return dfs(0) 

'''
dfs(0) = 0 
dfs(1) = 1 
dfs(2) = 2 
dfs(3) = 3 
dfs(4) = 5 
dfs(5) = 8 



n = 3
define the function
initialize the cache = {}- its empty nothing to store 
We define the helper function dfs(i)
Kick it off with return dfs(0) hence we start ground up 

dfs(0) is called 
  is 0 == n? no
  is 0 > n? no 
  is 0 in cache ? no 
  so we compute cache[i] = dfs(1) + dfs(2) - 2 + 1 (both already 
in memo hence we dont need to recompute them)  = 3 - so we store 
memo[0] 

  dfs(1) is called
    is 1 == n?    no
    is 1 > n?     no
    is 1 in memo? no
    memo[1] = dfs(2) + dfs(3) - 1 + 1 (memo[2] is 
already stored and dfs(3) hit the base case = 2 - so we store 
memo[1] then we bubble back to dfs(0)

  dfs(2) is called
    is 2 == n?    no
    is 2 > n?     no
    is 2 in memo? no
    memo[2] = dfs(3) + dfs(4) = 1+0 = 1 - so we store
we store memo[2] - we bubble back to dfs(1)

  dfs(3) is called 
    is 3 == n ? yes hence we return 1 
  dfs(4) is called 
    is 4 > n? yes hence we return 0 (out of bound)

  memo[2] = 1 + 0 = 1 
  dfs(3) is called 
    is 3 == n yes we already have this hence we return 1 
  memo[1] = 1+1 = 2 
  dfs(2) is called 
    is 2 in memo - yes hence we dont recompute it 
  memo[0] = 2 + 1 = 3 
Hence our final answer is 3 
'''

# BACKWARD APPROACH 
def climbing_stairs(n)
  memo = {}
  def climb(step):
    if step <= 2:
      return step 
    if step in memo:
      return memo[step]
    memo[step] = climb(step -1) + climb(step-2)
    return memo[step]
  return climb(n)

# BRUTE FORCE 
def climbing_stairs(n):
    def dfs(i):
        if i == n:      # reached top
            return 1
        if i > n:       # out of bound
            return 0
        return dfs(i+1) + dfs(i+2)  # recompute everything
    return dfs(0)

Fibonnaci number

Given n , calculate f(n). 
n = 2 
output = 1 

n = 3 
output = 2 

Define the states 
- f(i) = the fibonnaci number at position i 

Define the recurrence 
f(i) = f(i -1) + f(i -2) - each number is the sume of the 2 numbers 
before it. 

0, 1,1,2,3,5,8 

Basecases
- 0 and 1 

We will implement using memoization 

Time: O(n) - each subproblem solved exactly once
Space: O(n) - for the memo table and O(n) for the recursive call stack 

# BACKWARD APPROACH
def fib(n):
  memo = {}
  def dfs(i):
    if i == 0:
      return 0 
    if i == 1:
      return 1
    if i in memo:
      return memo[i]
    memo[i] = dfs(i -1) + dfs(i -2)
      return memo[i]
  return dfs(n)

'''
Define the function 
Initialize the memo = empty since we have nothing to store 
Define the helper function dfs(i)
Kick it off with return dfs(n) hence we backwards 
n = 4
dfs(4) is called:
  is 4 == 0 ? no 
  is 4 == 1 ? no 
  is 4 in memo ? no 
  memo[4] = dfs(3) + dfs(2) - 2 + 1 = 3 - hence we return it as final 
answer. 

dfs(3) is called:
  is 3 == 0 ? no 
  is 3 == 1 ? no 
  is 3 in memo ? no 
  memo[3] = dfs(1) + dfs(2) - 1 + 1 = 2 - we bubble back up 

dfs(2) is called:
  is 2 == 0 ? no 
  is 2 == 1 ? no 
  is 2 in memo ? no 
  memo[2] = dfs(1) + dfs(0) - 1 + 0 = 1 - bubble back up 

dfs(1) is called:
  is 1 == 0 ? no 
  is 1 == 1 ? yes - we have hit a basecase

dfs(0) is called:
  is 0 == 0 ? yes - we have hit a base case 
'''

# BRUTE FORCE 
def fib(n):
    def dfs(i):
        if i == 0:      # base case
            return 0
        if i == 1:      # base case
            return 1
        return dfs(i-1) + dfs(i-2)  # recompute everything
    return dfs(n)

Min Cost Climbing Stairs

You are given an array of integers cost where cost[i] is cost of taking a step
from ith floor of a staircase. 
You can step either (i + 1)th floor or (i + 2)th floor. 
You can choose to start at index 0 or the index 1 floor. 
Return the minimum cost to reach top of the staircase. 

Example :
Input : cost = [1,2,3]

Output : 2 

Define the states
Minimum cost to reach the top from step i 

At each step we have 2 choices to make to either take 1 or 2 steps

Define the states
We trying to find the minimum cost to reach the top from step i 

Define the recurrence 
At each step step i you have 2 choices: 
  - climb 1 step or climb 2 steps 
dfs(i)  = cost[i] + min(dfs(i +1), dfs(i + 2))
cost[i] - pay current step cost, then take the cheaper path.


Basecases 
if i >= len(cost): - reached or passed the top
  return 0 



I will implement using memoization 

Time: O(n) - each subproblem solved exactly once
Space: O(n) - for the memo table and O(n) for the recursive call stack

def min_cost_climbing_stairs(cost):
  memo = {}
  def dfs(i):
    if i >= len(cost): # base case , reached the top
      return 0 
    if i in memo:
      return memo[i]
    memo[i] = cost[i] + min(dfs(i+1), dfs(i +2)) # pay and take cheaper path
    return memo
  return min(dfs(0), dfs(1)) # you can start here

'''
dfs(3)
- is 3 >= len(cost) yes - hence return 0 
dfs(2) 
- is 2 in memo ? no 
memo[2] = cost[2] + min(dfs(3) + dfs(4)
         = 3 + min(0, 0) = 3 
dfs(1)
- is 1 in memo? no 
memo[1] = cost[1] + min(dfs(2), dfs(3))
        = 2 + min(3,0) = 2 
dfs(0) 
- is 0 in memo? no 
memo[0] = cost[0] + min(dfs(1), dfs(2))
        = 1  + min(2,3) = 3 
return 3
'''

# BRUTE FORCE 
def min_cost_climbing(cost):
  def dfs(i):
    if i >= len(cost):
      return 0 
    return cost[i] + min(dfs(i + 1), dfs(1 + 2))
  return min(dfs(0), dfs(1))

Longest Increasing Subsequence

Given an integer array nums , return the length of longest increasing 
subsequence.
A subsequence - Delete characters while maintaing characters in the sequence. 
It doesnt have to be contiguous. (They dont have to follow each other).

Input : nums = [9,1,4,2,3,3,7]
output = 4 
Values = [1,2,3,7]

Assumptions to think about and ask your interviewer  
- What happens when you have duplicates?
- Think about the input size 
- What happens when you have negative values
- What if they need you to return the actual values compared to the total of it
- What if you need to return the indexes as well
- Think of the edgecases: when its empty, null, happy and unhappy path 

Visual this as a tree 
nums = [9,1,4,2,3,3,7]
        BRUTE FORCE
        at 9 you have 2 choices - to either include it or not include it
        when we get to the other value 1 we also have 2 choices
        So we do that for each single character and realise it 2 ^ n - exponential
        Can we do better?
  O (n^2)
DFS with cache 
[1,2,4,3]
0  1 2 3

So we take 1 decision at each index and add their values. Hence this will be the 
subsequences we have so far. 

I have shared a diagram above to show how it looks like.

So we know when we start at index 0 we have 3 values that
come afterwards. So we can try the 3 possible decisions. 

So they are possible since all the values are greater than
1. 

Something to not is that if the values are not greater we can
continue there hence we stop. 

LIS[0] = 3 
LIS[1] = 2 
LIS[2] = 1 
LIS[3] = 1 


Define the states - we trying to understand the problem
Length of longest increasing subsequence starting at index i 

Define the recurrence 
At each index i, we look at every j after i 
If nums[j]> nums[i]: only include if its greater 
  - we can extend the subsequence 
dfs(i) = 1 + max(dfs(j)) for all j > i where nums[j] > nums[i] 
1 represent count of our current element 

Basecases 
If i == len(nums): return 0 (we out of bound)

dfs(0) - we can go to indices 1,2,3 (2 > 1 - [1,2], 4 > 1 - [1,4], 3 > 1 - [1,3]
dfs(1) - we can go to indices 2,3  (4 > 2 - [1,2,4], 3 > 2 - [1,2,3])
dfs(2) - we can go nowhere (nothing after 4 is greater)
dfs(3) - we can go nowhere (nothing after 3)

LIS[3] - 1 
LIS[2] - 1 
LIS[1] = 1 + max(LIS[2], LIS[3] = 1 + max(1,1) = 2 
LIS[0] = 1 + max(LIS[1], LIS[2], LIS[3]) = 1 + max(2,1,1) = 3 


We will implement with memoization

Time : O (n^2) - Running through i and j 
Space: O (n) - memoziation and calling the stack each level 

# DICTIONARY MEMOIZATION 
def longest_increasing_subsequence(nums):
    memo = {}
    def lis(current):
        if current == len(nums):
            return 0
        if current in memo:
            return memo[current]
        
        memo[current] = 1
        for next_idx in range(current + 1, len(nums)):
            if nums[next_idx] > nums[current]:
                memo[current] = max(memo[current], 1 + lis(next_idx))
        return memo[current]
    return max(lis(current) for current in range(len(nums)))

'''
dfs(3) 
- is 3 in memo? no 
- memo[3] = 1 
- Its out of bound
- return 1 

dfs(2) 
- is 2 in memo? no 
- memo[2] = 1 
- j = 3 : is num[3] > nums[2] ? is 3 > 4 ? no 
- return 1 

dfs(1)
- Is 1 in memo ? no 
- memo[1] = 1 
- j = 2 : is nums[2] > nums[1]? is 4 > 2? yes 
memo[1] = max(1, 1 + dfs(2)) = max(1, 1+1) = 2
- j = 3 : is nums[3] > nums[1]? is 3 > 2? yes
memo[1] = max(2, 1 + dfs(3)) = max(2, 1+1) = 2 
return 2 

dfs(3) 
- Is 0 in memo? no 
- j = 1: is nums[1] > nums[0]? is 2 > 1? yes
memo[0] = max(1, 1 + dfs(1)) = max(1, 1+2) = 3
- j = 2 : already in memo 
- j = 3 : already in memo 
- return 3 

max(3,2,1,1) = 3 
values = [1,2,3] or [1,2,4]
'''

# ARRAY MEMOIZATION 
def longest_increasing_subsequence(n):
  memo = [-1] * n 
  def dfs(i):
    if memo[i] != -1:
      return memo[i]
    LIS = 1 
    for j in range(i + 1, n):
      if nums[j] > numsi]:
        LIS = max(LIS, 1 + dfs(j))
    memo[i] = LIS 
    return LIS 
  return max(dfs(i) for i in range(len(nums))

Longest Common Subsequence

Given 2 strings text1 and text2, return the length of their 
longest common subsequence. If there is no common subsequence
return 0. 

Assumptions 
- What if either string is empty?
- What if both strings are identicial ?
- What happens if there is no common subsequence?
- Is it case sensitive?
- What if they want the actual subsequence not just the length?
- What if they want indices?

Example:
text1 : 'cat' text2: 'crabt'
output : 3

Define the states 
We need to find the longest common subsequence. Starting at index i in s1 and 
index j in s2 

Define the recurrence relation
We have 2 choices at each i and j 
Choice 1 : characters match 
take it and move both pointers forward 
dfs(i,j) = 1 + dfs(i+1, j+1)
Choice 2 : characters dont match 
try skipping one character from either string 
dfs(i, j) = max(dfs(1+1, j) , dfs(i, j+1)

Basecases 
if i == len(text1): return 0 
if j == len(text2) : return 0 


We will implement using memoization

Visualization of the problem 

     a  c  e
     0  1  2
a 0 [3, 2, 1]
b 1 [2, 2, 1]
c 2 [2, 2, 1]
d 3 [1, 1, 1]
e 4 [1, 1, 1]

Each cell (i,j) = LCS from i in text1 and j in text2 
we fill from bottom right to top left 

def longestCommonSubsequence(text1, text2):
  memo = {}
  def count(i,j):
    if i == len(text1) or j == len(text2):
        return 0 
    if (i, j) in memo:
        return memo[(i,j)]
    if text1[i] == text2[j]:
        memo[(i,j)] = 1 + count(i + 1, j + 1)
    else:
        memo[(i,j)] = max(count(i + 1, j), count(i, j + 1 ))
        return memo[(i,j)]
  return count(0,0)

'''
text1 = 'abcde'
text2 = 'ace'
we kick it off at dfs(0,0)
dfs(0,0)
- 0 == len(text1) ? no
- 0 == len(text2) ? no
- (0,0) in memo? no
  text1[0] == text2[0]? a == a yes 
  memo[(0,0)] = 1 + dfs(1,1) = 1 + 2 = 3 

dfs(1,1)
- (1,1) in memo? no
  text1[1] == text2[1]? b == c - no 
  memo[(1,1)] = max(dfs(2,1), dfs(1,2)) = max(2,1) = 2

  dfs(1,2) 
  is (1,2) in memo? no 
  text1[1] == text2[2] ? b == e ? no 
  memo[(1,2)] = max(dfs(2,2), dfs(1,3)) = max(1,0) = 1
  
  dfs(2,2)
  is (2,2) in memo? no 
  text1[2] == text2[2] ? c == e ? no
  memo[(2,2)] = max(dfs(3,2), dfs(2,3))
            = max(1,0) - dfs(3,2) - already in memo = 1 
  
  dfs(1,3) 
  is 3 == len(text2) - yes hence basecase 
  return 0 
 


dfs(2,1)
- (2,1) in memo? nope
  text1[2] == text2[1]? c == c - yes
  memo[(2,1)] = 1+ max(dfs(3,2) - 1 +1 = 2 

dfs(3,2)
- (3,2) in memo? nope
  text1[3] == text2[2]? d == e - no
  memo[(3,2)] = max(dfs(4,2), dfs(3,3)) - max(1,0) = 1 
dfs(3,3) == len(text2) hence basecase return 0 

dfs(4,2)
- (4,2) in memo? nope
  text1[4] == text2[1]? e == e - yes
  memo[(4,2)] = 1+ max(dfs(5,3) - 1 + 0 = 1 

dfs(5,3) 
- if 5 == len(text1) = yes hence base case reached return 0 


Final answer = 3 
common subsequence = 'ace'
'''

Distinct subsequence

You are given 2 strings s and t , both consisting of english letters. 
Return the number of distinct subsequences of s which are equal
to t. 

Input : s = 'caaat' t = 'cat'
output : 3 

Input : s = 'xxyxy' , t = 'xy' 
output: 5 

Assumptions
- We are only working with strings or numbers as well?
- Duplicates count as distinct if at different indexes 
- What is the input size?
- Is it case sensitive? focus on lower case letters 
- Empty string s - return 0 
- Empty string t - return 1 
- s is shorter than t - return 0 since its impossible 


Define the states 
We need to find the number of distinct subsequences of s which 
are equal to t. 
 
count (i,j) = number of distinct subsequences of s[i:]
              that equal t[j:]
s = 'caaat' t = 'cat'
     01234       012
i tracks position in s 
j tracks position in t 

Define the recurrence relation 
At each position i in s and j in t we have 2 choices 
Choice 1 : characters match s[i] == t[i] 
    - use s[i] to match t[j] - move both forward 
      - count (i+1, j +1)
    - skip s[i] - move only i forward 
      - count (i + 1, j)
    count(i,j) = count (i +1, j +1) + count (i +1, j )

Choice 2 : characters dont match s[i] != t[j]
      must skip s[i] - move only i forward 
      count(i,j) = count (i +1, j)

s = 'caaat' t = 'cat'
at i = 1 (a) and j = 1 (a) - they match 
but we have 3 a's in s - each one can be used to match t[1]
So we need to count all possibilities 
  - use first a : 'c[a]at' matches 'cat' 
  - use second a : 'ca[a]t' matches 'cat'
  - use third a : 'caa[a]t' wait, no 't' after
so we count each valid path
    

Basecases
if j == len(t):
      return 1 
    if i == len(s):  
      return 0

We will use the memoization approach 


Time : O (n)
Space :O (n)

def distinct_subsequences(s,t):
  memo = {}
  def count (i,j):
    # base cases
    if j == len(t):
      return 1 
    if i == len(s):  
      return 0 

    # memo check 
    if (i,j) in memo:
      return memo[(i,j)]

    # recurrence 
    if s[i] == s[j]:
      memo[(i,j)] = count (i+1, j+1 + count (i +1, j)
    else:
      memo[(i,j)] = count (i +1 , j ) 
      return memo[(i,j)]

  return count (0,0)

Coin Change

You are given an integer array coins rep coins of different
denominations (1 dollar, 5 dollar, etc) and an integer amount
that represents a target amount of money. 

Return the minimum number of coins to make up the target and if 
impossible return -1 

Assume you have an unlimited number of coins. 

Example : coins = [1,5,10] , amount = 12 
output : 3 

For this you have 2 choices for each until we get the min
number of coins we can use up until we get the target. 

Assumptions 
- What if amount is 0 ?
- What if coins array is empty 
- What if amount is impossible to make? 
- Can we reuse coins? yes 
- What if we have a negative amount?

Define the state
Find the minimum number of coins that can make up the exact target.

Define the recurrence 
At each amount i we try every coin. 
Change = 1 + min(change(remaining-coin) - for every coin
1 - count current coin and take the cheapest path 
Only try coin if remaining - coin >= 0 

Base cases
if remaining == 0 : return 0 - exact amount made 
if remaining < 0 : return 1e9 - invalid path 

We will use memoization 

Time : O(n) * m - amount and number of coins 
Space : O (n) - memo table and call stack 

def coin_change(coins, amount):
    memo = {}
    def change(remaining):
      # base cases 
      if remaining == 0: # exact amount 
          return 0 

      # memo check 
      if remaining in memo:
          return memo[remaining]
      fewest = 1e9 
      for coin in coins:
        if remaining - coin >= 0:
          fewest = min(fewest, 1 + change(remaining- coin))

      memo[remaining] = fewest 
        return memo[remaining]

    minimum_coins = change(amount)
    return -1 of minimum_coins >= 1e9 else minimum_coins 

Coin change 2

Its the same coins and amount but now we need to return the 
number of combinations that make up the amount. 
Order doesnt not matter. 
coins = [1,2,5]
amount = 5 
output = 4 
combinations 
5 
2+2+1 
2+1+1+1
1+1+1+1+1

coins = [1,2,5]
         0,1,2 
At each step i we have 2 choices 
We can either use the coin again - change(i, remaining - coin[i])
skip to the next coin - change(i + 1, remaining)

Define the states
We need to find the number of combinations using coins from 
index i onwards to make up remaining amount. 

Define the recurrence 
change(i, remaining) = change(i, remaining-coins[i]) + change (i+1, remaining)

Base cases 
if remaining == 0 : return 1 - exact amount made 
if remaining < 0: return 0 - overshot 
if i == len(coins): return 0 - no more coins to try 

We will implement with memoization 

def coin_change_2(coins, amount):
    memo = {}
    def change(i, remaining):
      # base cases
      if remaining == 0:
        return 1 
      if remaining <0: 
         return 0 
      if i == len(coins): 
         return 0 
      # Memo check
      if (i,remaining) in memo:  
         return memo[(i,remaining)] 
      # Compute the memo 
      memo(i, remaining) = change(i, remaining-coins[i]) + change (i+1, remaining)
        return memo[(i,remaining)]

    return change(0, amount)

House Robber

You are given an interger array nums where nums[i] rep the amount of 
money the ith house has. 

So for this you have 2 choices. You can either rob the house or not 
rob it. And you cannot rob houses next to each other since they will
alert the police hence you have to skip the house next to each other.

You need to return the maximum amount of money you can rob without
alerting the police. 

Example:
nums = [1,1,3,3]
Output = 4 

You can either pick num[0] and num[2] or num[1] and num[3] since
they are similar 

Assumptions
- what if array is empty
- What happens if the array has only 1 house 
- What happens when it has 2 houses 
- Think of negative values 

Define the states
- We need to find the maximum amount money you can rob from houses that
are not adjacent to each other without alerting the police. 

Define the recurrence relation
At each house we have 2 choices 
- rob it : take nums[i] and skip next house 
- dont rob it : skip it and move to the next house 
dfs(i) = max(nums[i] + dfs(i+2), dfs(i + 1))

Basecases 
if i >= len(nums):
   return 0  # we are out of bound 

Will use the memoization approach 

def house_robber(nums):
  memo = {}
  def rob(house):
    # Base case: No more houses to rob
    if house >= len(nums):
        return 0

    if house in memo:
        return memo[house]

    memo[house] = max(nums[house] + rob(house + 2), rob(house + 1))

    return memo[house]

  return rob(0)
  

House Robber 2

Similar to house robber 1 but now the houses are arranged in a circle 
meaning the first and last house are now adjacent to each other. 

nums = [1,2,3,1]
output = 4 (rob house 0 and house 2 )

Circle means house 0 and house n -1 are neighbors 
How can we handle this? 
- case 1: rob house 0 to n-2 - exclude the last house 
- case 2 : rob house 1 to n-1 - exclude first house 

ans = max(case1, case2)

Define the states 
- Maximum money from house i up to end index 

Define the recurrence relation
same as house robber 1:
dfs(i) = max(nums[i] + dfs(i+2), dfs(i+1))

just with a different end point for each case

Base case 
if i >=end:
    return 0 

def house_robber_two(nums):
    memo = {}
    n = len(nums)

    if len(nums) == 1:
        return nums[0]

    def rob(house, last):
        # Base case: No more houses to rob
        if house >= last:
            return 0

        if (house, last) in memo:
            return memo[(house, last)]

        memo[(house, last)] = max(
            nums[house] + rob(house + 2, last), rob(house + 1, last)
        )

        return memo[(house, last)]

    return max(rob(0, n - 1), rob(1, n))

"""
        Intuition:
        - Two choices:
            - Rob a house
            - Or not rob a house
        - If you decide to rob a house you must skip the adjacent house.
        - However robber must ensure maximum amount
        - Recurrence: rob(i) + rob(i + 2)
        - Maximum of current house robbed
        - If out of boundes: -> 0

        Input: nums = [2,9,8,3,6]
                       0,1,2,3,4

        Output: 15

        memo = {
        (0, 3): 8,
        (2, 3): 8,
        (0, 4): 11
        (1, 4): 12
        (2, 4): 9
        (3, 4): 3

        }
        n = 5

        - rob(0, 3) -> 8:
            - 2 + rob(3, 3), 0 -> 2
                -
            - rob(2, 3) -> 8:
                - 8 + rob(4, 3), 0: -> 8
                    - rob(4, 3) -> 0
                - rob(3, 3) -> 0

        - rob(0, 4): -> 12
            - 2 + rob(2, 4): -> 11
                - rob(2, 4): -> 9

            - rob(1, 4): -> 12
                - 9 + rob(3, 4): -> 3
                    - rob(3, 4): -> 3
                        - 3 + rob(5, 4), 0: -> 3
                        - rob(4, 4) -> 0

                - rob(2, 4) -> 9:
                    - 9 + rob(4, 4), 0: -> 9
                    - rob(3, 4): -> 3
        """

Longest Palindromic Substring

Given a string s , return the longest substring of s that is 
a palindrome. 

s= 'babad'
output = 'bab' or 'aba' both valid 

Assumptions 
- What happens if the string is empty 
- Do we care if its case sensitive 
- What is we have multiple longest palindromes of same length
- What happens if the string has only 1 character - palindrome

Every palindrome has a center 
odd length : single character center 'bab' - a 
even length : 2 characters center 'bb' - center in bb 
So we try every possible center and then expand outwards while 
characters match 

Define the states
Palindrome (left, right) = is s[left:right+1] a palindrome 
s = 'babad'
     01234
expand from each center outwards 

Define the recurrence 
expand(left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
      expand outward
        left -= 1 
        right += 1 

Basecases 

if left < 0 : stop 
if right >= len(s): stop 
if s[left] != s[right] : stop - characters dont match 

Time : O(n)
Space : O(n)

def longest_palindromic_substring(input_string):
    result = ""
    def expand(left, right):
        while left >= 0 and right < len(input_string) and input_string[left] == input_string[right]:
            left  -= 1
            right += 1
        return input_string[left+1:right]
    
    for i in range(len(input_string)):
        odd  = expand(i, i)      # odd length palindrome
        even = expand(i, i+1)    # even length palindrome
        
        if len(odd) > len(result):
            result = odd
        if len(even) > len(result):
            result = even
    
    return result

Palindromic Substring

Given a string s , return the number of substrings within s that 
are palindromes. 

s= 'abc'
output = 3 
a, b, c

s= 'aaa'
output = 6 
a , a ,a , aa, aa, aaa

Longest palindromic substring - return the longest palindrome
Palindromic substrings - count all palindromes 

Assumptions 
- What if string is empty - return 0 
- Single characters count as palindromes - yes 
- Case sensitive ? lower and upper case 
- What if all characters are the same ? 

Define the states 
Count = total number of palindromic substrings 
expand (left, right) = count all palindromes (expanding from center- left, right)

Define the recurrence relation
expand (left, right):
  while characters match and in bounds:
    count += 1 
    expand outward 

Basecases 
if left < 0: stop 
if right >= len(s): stop 
if s[left] != s[right] : stop # not a palindrome

Time: O (n ^2)
Space : O (1)

def palindromic_substrings(input_string):
  count = 0 
  def expand (left, right):
    nonlocal count 
    while left >= 0 and right < len(input_string) and input_string[left] == input_string[right]:
      count += 1 
      left -= 1 
      right += 1 
    for i in range (len(input_string)):
      expand(i, i)
      expand (i,i +1)

    return count 

Maximum subarray

Given an array of integers nums, find the subarray with the largest 
sum and return the sum. 
nums = [2,-3,4,-2,-2,1,-1,4]
output = 8 

Assumptions
- What if array is empty? return 0 
- What if all numbers are -ve ? return the least -ve
- What if array has one element ? return that element
- Can the subarray be empty - yes 

2 choices :
- extend previous subarray 
- start a fresh 

current_sum = maximum subarray sum ending at current index
max_sum     = maximum subarray sum seen so far

current_sum = max(nums[i], current_cum + nums[i])
max_sum = max(max_sum, current_sum)


We will use Kadane's algorithm. 


Time : O(n) - pass through the array
Space : O(1) 

def maxSubarray (nums):
  current_sum = max_sum = nums[0]
  for num in nums[1:]:
    current_sum = max(num, current_sum + num)
    max_sum = max(max_sum , current_sum)
  return max_sum 

Maximum product subarray

Given an integer array nums, find a subarray that has the 
largest product within the array and return it. 

nums = [1,2,-3,4]
output = 4 

def max_product_subarray(nums):
  max_curr = nums[0]
  min_curr = nums[0]
  result = nums[0]

  for num in nums[1:]:
    candidates = (num, max_curr * num, min_curr * num)
    max_curr = max(candidates)
    min_curr = min(candidates)
       res = max(res, max_curr)
  return result 

I will do a 2nd article to do the remaining problems.

Happy coding.

Topics

• Security and access control
• Firewalls
• Proxies
• VPNs (Virtual Private Network)
• Load balancers
• Network optimization

So the whole concept is we want to control who gets in (security) and make sure once they’re in, things move fast (load balancing/optimization).

Security and access control

1. ACL (Access Control List)

They are used to filter traffic in a network. (The “bouncer” at the door).

Types of Access Control List

• Standard : Filters based ONLY on the source IP address.
• Extended : Filters based on source/destination IP , protocol and port numbers.

ACLs are stateless (they look at each packet alone) hence firewalls evolved to fix this.

2. FIREWALLS

Monitor and controls traffic based on rules.

It established a barrier between a trusted internet network and an untrusted external network.

The main functions :-

• Packet filtering
• Stateful inspection
• Proxying
• Network Address Translation (NAT)

In firewalls we have zones for them.

• DMZ (Demilitarized Zone): Semi-isolated segment between internal and external networks. (Hosts public servers like web/mail).
• Internal Zone: The trusted, secure core of the network.
• External Zone: The untrusted portion (the public internet).

Types of firewalls

• Packet Filtering Firewalls (Stateless):

How: Examines packets individually against rules (IP, port, protocol).

Characteristics: Simple, fast, but vulnerable to IP spoofing (because it doesn’t remember previous packets).

Rule Example: Allow TCP traffic from Any source to Destination 192.168.1.100 on Port 80 (HTTP).

• Stateful Inspection Firewalls:

How: Keeps track of active connections (a “state table”).

Characteristics: Context-aware. If you request a website, it allows the response back in automatically. Better security than stateless.

• Proxy Firewalls (Application-Level Gateway):

How: Acts as an intermediary (middleman). The client talks to the proxy, the proxy talks to the internet.
Characteristics:
Content inspection (looks inside the data).
Forward Proxy: Represents clients (hides internal users).
Reverse Proxy: Represents servers (hides backend servers (often a Load Balancer)

• Next-Generation Firewalls (NGFW):

How: Traditional firewall + advanced features.
Characteristics:
Deep Packet Inspection (DPI): Looks at the payload of the packet (not just the header).
Intrusion Prevention Systems (IPS): Actively blocks malicious activity.
Application Awareness: Can identify “Facebook” traffic regardless of port.

3. PROXIES

An intermediary server acting as a gateway between a client and a server.

Why use a proxy? Privacy, Security, Content Filtering, Caching, Load Balancing, Access Control, Anonymity.

Types of proxies

• Forward Proxy (Client-side): Sits in front of clients. Used to bypass geo-restrictions or filter employee traffic.
• Reverse Proxy (Server-side): Sits in front of servers. Used for load balancing, caching, and SSL termination.
• Transparent Proxy: Intercepts traffic without the user knowing (caching/content filtering).
• Explicit Proxy (HTTP/HTTPS/SOCKS): Client must configure to use it. SOCKS works at a lower level (TCP/UDP) and is more versatile.

4. VPNs(Virtual Private Network)

Creates a secure, encrypted tunnel over a public network between a device and a VPN server. Masks your IP and encrypts data.

It takes your original packet (with your real IP), encrypts it, and wraps it inside a new packet with the VPN server’s IP.

Key protocols

• PPTP: Old, insecure. (Don’t use).
• L2TP/IPsec: More secure, but often slow.
• IKEv2/IPsec: Good for mobile devices (handles network changes well).
• OpenVPN: Open source, very secure, gold standard.
• WireGuard: Newer, lighter, faster than OpenVPN.

Simple cryptography concepts:-

• Symmetric Encryption: Same key to encrypt and decrypt (Fast, used for the actual data).
• Asymmetric Encryption: Public/Private key pair (Slow, used to securely exchange the symmetric key).

VPN Modes

• Transport Mode: Encrypts only the payload (used between servers).
• Tunnel Mode: Encrypts the entire packet (used for VPNs).

IPsec Components:

• AH (Authentication Header): Integrity & authentication (no encryption).
• ESP (Encapsulating Security Payload): Encryption, integrity, authentication (The workhorse).
• IKE (Internet Key Exchange): Manages keys and negotiates Security Associations (SAs).
• Diffie-Hellman (DH): The algorithm to securely exchange keys over a public network. (DH Group = strength of the key).

Insight :

• IPsec: Network-layer (Layer 3). Requires client software. Better for full network access (Site-to-Site).
• SSL VPN: Application-layer (Layer 7). Often uses a web browser. Better for client-to-site (remote employee accessing email).

5. LOAD BALANCER

It distributes incoming network traffic across multiple servers.

Features

• Health Checks (stops sending traffic to dead servers).
• Session Persistence (Sticky sessions: keeps a user on the same server).
• SSL Termination (decrypts HTTPS once, sends HTTP to backend servers).
• Content-based Routing (send /video to server A, /images to server B).

Algorithms

• Round Robin: Rotates through the list (Server 1, 2, 3, 1). Best when servers are identical.
• Least Connections: Sends to the server with the fewest active connections. Best for long-lived connections (streaming, databases).
• IP Hash (or Consistent Hashing): Uses client IP to pick a server. Ensures the same client always hits the same server (good for caching).
• Weighted Round Robin / Least Connections: Same as above, but you assign “weights” (Server A is 3x faster than Server B, so it gets 3x the traffic).

NETWORK OPTIMIZATION

It is created on 4 pillars.

• Speed (low latency, high throughput)
• Reliability (no downtime)
• Capacity (handles growth)
• Security (protected while fast)

Metrics

Speed: Bandwidth (max), Latency (time), Throughput (actual), Packet loss.

Reliability: Uptime (%), MTBF (time between failures), MTTR (time to fix).

Capacity: Utilization (%), Connection count, Growth trends.

1. SPEED

Its how fast data moves across the network.

Speed metrics are : — bandwidth utilization, latency , throughput and packet loss.

Bandwidth — maximum data transfer rate of a network or internet connection measured in bits per second. It indicates the amount of data that can be transmitted over a network connection in a given amount of time.

The higher the bandwidth the more the data can be sent or received at once.

Bandwidth utilization is when we measure the percentage of the total available bandwidth.

Latency is the time it takes for data to travel from the source to the destination. Hence lower latency indicates better network performance.

Throughput it is the actual amount of data successfully transmitted over a network in a given period (bits per second). Video streaming needs high throughput.

To optimize throughput you can use load balancing, increase bandwidth and minimize network congestion.

Packet loss is the percentage of packets that are lost during transmission.

Lower packet loss rates indicates a more reliable and faster network while high packet loss can severely degrade the network performance.

You need to upgrade hardware (routers, switches, NICs), optimize network protocols (TCP tuning, QUIC) , minimize latency (CDNs and Edge computing) and minimize packet loss (congestion control and traffic shaping).

Low latency + low packet loss = real speed

2. RELIABILITY

This is about keeping the network working consistently over time.

We need to add redundancy, load balancing and regular maintenance.

Key metrics

Uptime (%)

• Example: 99.99% uptime (“four nines”)
• Measures availability

MTBF (Mean Time Between Failures)

• Average time system runs before failure

MTTR (Mean Time To Repair)

• How quickly issues are fixed

How to improve reliability

• Redundancy : having multiple servers, links and data centers.
• Failover systems : automatic switching when failure occurs
• Load balancing : Distribute traffic across systems.
• Monitoring and altering : detect failures early

Example platforms such as Netflix rely heavily on redundancy across regions

3. CAPACITY (SCALABILITY)

This is about handling growth without degrading performance.

Capacity metrics

• Network utilization, connection count , data volume and growth trends

This is a question you need to ask yourself can your network handle 10x more users tomorrow or in a few years?

Utilization (%)

• How much of resources are being used
• High utilization → risk of congestion

Connection count

• Number of active users/connections

Growth trends

• Traffic increase over time

How to improve capacity

• Horizontal scaling : ading more servers instead of upgrading one
• Auto-scaling systems
• Efficient resource allocation
• Traffic distribution

4. SECURITY

Think of this as protecting the network while maintaining performance.

Key considerations

• Encryption (TLS)
• Firewalls
• Intrusion dection systems (IDS/IPS)
• DDoS protection

Example : HTTPS adds encryption overhead, but modern protocols (like HTTP/3) reduce the performance impact.

REAL WORLD SYSTEM EXAMPLE: Youtube

• Speed : smooth video playback
• Reliability : no buffering / crashes
• Capacity : millions of user simultaneously
• Security : protected stream and user data

• HTTP (Hypertext Transfer Protocol)
• HTTP methods
• HTTP status codes
• HTTP/2 vs HTTP/3
• Differences between HTTP/2 AND HTTP/3
• DNS
• DHCP
• Remote Shell Access — Telnet , SSH
• Interview scenarios

It is responsible for providing network services and protocols that enable applications to communicate with each other over a network.

HTTP (Hypertext Transfer Protocol)

Its a stateless protocol , meaning that each request-reponse cycle is independent and doesn't retain any information from previous interactions.

It is used for transmitting and receiving web pages and other resources on the WWW.

The browser initiates a HTTP request, the server processes the request and sends back a HTTP response to the browser.

A client sends a HTTP request to a server, the server responds with a HTTP response.

The request consists of: a method (GET, POST, PUT, DELETE), a target resource (URL or URI), headers and an optionally a message body.

The response includes: a status code, headers and an optional response body.

HTTP Methods

• GET : Retrieve a resource
• POST : Submit data to be processed by the server
• PUT : Store or update a resource
• DELETE : Remove a resource
• HEAD : Retrieve only the headers of a resource
• OPTIONS : Retrieve the supported methods and capabilities of a server
• PATCH : Partially update a resource

To maintain state or session information, mechanisms like cookies or session tokens are commonly used.

HTTP cookies — are small pieces of data stored on the client-side by websites to track user activity and store user-specific information. They are stored as key-value pairs in the user’s browser.

Cookie attributes

• Name and value : The key value pair that stores the data.
• Domain : specifies the domain(s) to which the cookie applies.
• Path : Defines the URL path(s) within the domain for which the cookie is valid.
• Expiration : Specifies when the cookie should expire.
• Secure and HTTP only : Flags that control whether the cookie should be sent only over HTTPS and if it can be accessed by client-side scripts respectively.

HTTP Headers

HTTP requests and responses include headers that provide additional information and instructions.

Common headers include:-

• Content type (specifies the MIME type of the data)
• Content length (Indicates the size of the message body)
• User agent (provides information about the client)
• Server (Identifies the server software)

HTTP Status Codes

It includes status codes that indicate the outcome of the request.

Common status code range: —

• 1xx : Informational
• 2xx : Success
• 3xx : Redirection
• 4xx : Client errors
• 5xx : Server errors

HTTP/2 and HTTP/3

Newer version of the HTTP protocol designed to improve performance and efficiency.

HTTP/3 is based on QUIC protocol which is built on top of UDP (User Datagram Protocol).

HTTP/2 introduces multiplexing which allows multiple streams of data to be transferred simultaneously over a single TCP connection.

A limitation that might occur in TCP is head of line blocking. This means when a single packet is lost during transmission. TCP has to wait for that specific packet to be retransmitted before the rest of the steam can proceed which causes delays for all stream sharing that connection.

HTTP/3 leverages QUIC hence it eliminates the issue of head-of-line blocking since it uses UDP and introduces multiplexed streams directly at the protocol level. If a stream experiences a packet loss the other streams are unaffected and can continue transmitting data without delays.

Head of line blocking its a performance bottleneck that occurs when a packet at the front of the queue prevents other packets behind it from being processed even though these packets might be ready to move forward.

HTTP/2 head of line blocking happens at 2 levels :- TCP level and HPACK header compression. (If header frames are lost or delayed , the dependency between header for different streams can cause the entire connection to stall).

Differences between HTTP/2 and HTTP/3

DNS (Domain Name System)

It translates the domain name to an IP address.

The client first checks its local cache to see if the IP address for the domain is already stored.

If not found, the client sends a DNS query to a DNS resolver.

The resolver recursively traverses the DNS hierarchy, starting from the root servers, then moves to the TLD servers and finally to the authoritative servers until it obtains the IP address associated with the domain.

The resolver caches the obtained IP address for future use and returns its to the client.

Various types of records:-

- A (Address) : Maps a domain name to an IPv4 address.

- AAAA (IPv6 Address) : Maps a domain name to an IPv6 address.

- CNAME (Canonical Name) : Provides an alias or canonical name for a domain.

- MX (Mail Exchanger) : Specifies the mail server responsible for accepting incoming emails.
- TXT (Text) : Stores arbitrary text info associated with a domain
- NS (Name Server) : Indicates the authoritative DNS servers for a domain

They implement caching to improve perfomance and reduce the load on the network.

Caching helps store recently accessed domain records and IP addresses allowing subsequent queries for the same domain to be resolved more quickly.

DHCP (Dynamic Host Configuration Protocol)

It automatically assigns IP addresses to devices on a network.

It simplifies the process of configuring IP addresses and network settings by providing a centralized mechanism for dynamic IP address allocation.

It allows devices to obtain IP addresses, subnet masks, default gateways, DNS servers and other configuration parameters automatically.

It operates in a client-server model.

DHCP clients request IP address assignment and network configuration parameters from DHCP servers.

The servers are responsible for managing and assigning IP addresses and network settings to DHCP clients.

When a client requests an IP address, the DHCP servers leases an IP address to the client for a specific lease time.

DHCP Relay

- Typically a router or switch, forwards DHCP messages between clients and servers.

- The relay agent listens for DHCP broadcasts from clients, encapsulates the messages and sends them to the DHCP server.

- The DHCP server responds through the relay agent which forwards the response to the client.

DHCPv6 — it provides functionality to DHCP for IPv4 but uses different message formats and protocols for IPv6 address assignment and configuration.

Remote Shell Access — Telnet , SSH

1. Telnet

Its a network protocol used for remote access to servers and network devices.

It does not provide encryption or secure authentication mechanisms. Data transmitted over Telnet is sent in plaintext, making it vulnerable to interception and unauthorised access.

It typically uses port 23 for communication.

Features:-

• Remote shell access: Telnet allows users to log in remotely to a server and execute commands.
• Device configuration: Telnet is commonly used to remotely configure network devices, such as routers and switches.
• Simplicity: Telnet is relatively straightforward and easy to use compared to SSH but lacks the security features provided by SSH.

2. SSH (Secure shell)

It is a secure network protocol that provides secure remote login, command execution, and secure file transfer between two computers.

Encrypts the data exchanged between the client and server, providing confidentiality and integrity of the communication.

It supports multiple authentication methods, including password-based authentication, public key authentication, and host-based authentication.

It typically uses port 22 for communication.

Features

• Secure remote shell access: SSH allows users to log in remotely to a server and execute commands securely.
• Secure file transfer: SSH includes SFTP (SSH File Transfer Protocol) and SCP (Secure Copy) for secure file transfer between client and server.
• Port forwarding: SSH allows creating secure tunnels for forwarding network connections, enabling secure access to remote services.
• X11 forwarding: SSH supports X11 forwarding, allowing the forwarding of graphical applications over the encrypted SSH connection.

Differences in telnet and ssh

Putting it all together

Data is encapsulated from application layer then keeps adding headers as well as one moves down the layers.

The decapsulation happens by removing the headers as well as one goes down the layers.

PING happens at the ICMP protocol. It servers as a messaging system for IP networks, facilitating error reporting, network diagnostics and control functions.

Interview scenarios

What happens when you type meta.com into a browser and hit Enter?

Why wouldn't you want a root DNS server to answer queries for you, 
instead of delegating you to an authoritative server?

Describe how you would identify and resolve an issue with a service 
that is no longer responding to requests.

What options do you have, nefarious or otherwise, to stop people on 
a wireless network you are also on (but have no admin rights to) from 
hogging bandwidth by streaming videos?

How does DNS resolution work?

Differences of TLS1.2 vs TLS 1.3

TLS TERMINATION

TLS termination is the process of decrypting encrypted TLS/SSL traffic at a specific point in the network, so it can be processed in plain text.

Where it happens: It’s most commonly performed on a load balancer or a reverse proxy

How it works

• Client connects: The client (e.g., a user’s browser) initiates a secure TLS handshake with the load balancer.
• Load Balancer holds certificate: The load balancer presents its SSL/TLS certificate to the client and completes the handshake. The client sees the load balancer as the “server.”
• Encrypted — Decrypted: All traffic between the client and the load balancer remains encrypted.
• Termination Point: The load balancer decrypts the incoming traffic (this is the “termination” of the TLS connection).
• Internal Forwarding: The load balancer then forwards the now unencrypted HTTP request to the backend application servers based on its load-balancing rules.
• Return Path: The backend server sends a plain text response back to the load balancer, which re-encrypts it before sending it back to the client.

Happy networking.

The transport layer facilitates communication between applications running on different computers.

Topics

• TCP
• UDP
• QUIC
• Port numbers
• Maximum Segment Size (MSS)
• MTU vs MSS
• Interview scenarios

It breaks data into segments, assigns and destination port numbers to identify applications and utilizes protocols such as TCP and UDP.

Port numbers are unique identifiers used by the transport layer to identify specific applications or services running on a host.

The posts range from 0 to 65535 and are divided into 3 ranges:-

• Well known ports (0–1023) — ports assigned to specific services or applications universally recognized across different systems.
• Registered ports (1024–49151) — ports assigned by the Internet Assigned Numbers Authority (IANA) to specific services or applications upon request.
• Dynamic or private ports (49152–65535) — ports are available for temporary or private use.

When data is sent from an application, the transport layer assigns a source port number to identify the application on the sender’s side. On the receiving end, the transport layer used the destination port number to deliver the received data to the appropriate application.

TCP (Transmission Control Protocol)

Its a reliable , connection-oriented transport layer protocol that ensures the ordered and error-free delivery of data packets over IP packets.

Characteristics

• Reliability
• Connection-oriented
• Ordered delivery
• Flow control
• Congestion control
• Connection termination
• Error detection and correction
• TCP header has 20–60 bytes

TCP provides reliable data transmission by using acknowledgments, retransmissions and error detection mechanism to ensure that data arrives at the destination accurately and in the correct order.

TCP guarantees the ordered delivery of data packets. Each packet is assigned a sequence number and receiver reassembles the packets in the correct order based on these sequence numbers.

TCP FLOW CONTROL

TCP flow control is a mechanism that allows the receiver to control the amount of data sent by the sender at one time.

It ensures that the receiver’s buffer does not overflow by advertising a “window” size, which represents the amount of data it can receive before sending an acknowledgment.

Its ensures that the receiver can handle the incoming data at a rate it can process, preventing the receiver from being overwhelmed by a faster sender.

How it works: —

• Window Size Advertisement: The receiver includes a window size in its ACK packets, indicating how much data it can receive.
• Sender’s Adjustment: The sender uses this window size to determine how much data it can send before waiting for an acknowledgment.
• Sliding Window Mechanism: The sender maintains a sliding window of data that it can send. As the receiver acknowledges data, the sender slides the window forward, allowing it to send more data.

CONGESTION CONTROL

TCP congestion control prevents network congestion on routers

The sender adjusts the congestion window (cwnd) based on network capacity, using ACKs and packet loss as signals.

Its responsible for preventing network congestion, which occurs when network resources are overloaded with more data than they can handle.

Congestion can lead to packet loss, increased latency, and degraded performance.

How it works:-

TCP congestion control algorithms dynamically adjust the sending rate of data based on the perceived network conditions. They aim to find an optimal sending rate that utilizes the available network capacity without causing congestion.

Congestion control algorithms monitor network congestion signals such as packet loss and delay and adjust the sending rate by reducing or increasing the number of packets sent.

How TCP handles network congestion

1. Slow Start Begins with a small congestion window (e.g., 1–10 MSS). The congestion window increases by 1 MSS per ACK received, which causes it to double every Round Trip Time (exponential growth), rapidly probing network capacity. Slow Start ends when the congestion window reaches the slow start threshold (ssthresh), or congestion is detected.

2. Congestion Avoidance After Slow Start, the congestion window increases linearly (by 1 MSS per Round Trip Time). This is a slower, more cautious growth phase. Together with the reductions that follow packet loss, this linear growth forms the Additive Increase part of AIMD (Additive Increase/Multiplicative Decrease).

3. Congestion Detection & Recovery Packet loss (signalled by either a Timeout or Triple Duplicate ACK ) indicates congestion. The slow start threshold (ssthresh) is halved in both cases (Multiplicative Decrease), but the congestion window reduction differs depending on the TCP variant and the type of loss event:

• TCP Tahoe: Both Timeout and Triple Duplicate ACK reset the congestion window to 1 MSS and re-enter Slow Start.
• TCP Reno: A Timeout resets the congestion window to 1 MSS and re-enters Slow Start. A Triple Duplicate ACK triggers Fast Recovery instead the congestion window is set to the new ssthresh (roughly half its previous value) and Congestion Avoidance resumes immediately, without dropping back to 1 MSS. Reno treats Triple Duplicate ACK as a milder signal since ACKs are still flowing, meaning the network is not fully congested.

How TCP handles out-of-order packets

TCP uses sequence numbers and the ACK mechanism to detect and reorder packets that arrive out of sequence.

1. Sequence numbers Every byte of data is assigned a sequence number before transmission. This allows the receiver to identify each segment’s position in the original data stream and reorder them correctly, regardless of the order they arrive in.

2. Out-of-order arrival When a packet arrives out of order, the receiver does not discard it. Instead, it is held in a buffer while the receiver waits for the missing segment(s) that should have arrived earlier.

3. Receiver acknowledgement TCP uses cumulative ACKs. The receiver only acknowledges the last in-order byte it has received. If a gap exists (i.e a missing segment), the receiver sends a duplicate ACK for the last in-order byte, signalling to the sender that something is missing.

4. Selective Acknowledgement (SACK) SACK is an optional TCP extension that improves on basic cumulative ACKs. Rather than only reporting the last in-order byte, the receiver tells the sender exactly which segments have been received including out-of-order ones. This allows the sender to identify precisely which segments are missing.

5. Retransmission of missing packets Without SACK, the sender must retransmit everything from the missing segment onward. With SACK enabled, the sender retransmits only the specific missing segments, making recovery faster and more efficient.

What is the purpose of tcpdump?
Tcpdump is a powerful command-line packet analyser.

It allows you to capture, display, and analyse network traffic passing through a network interface in real-time.

It is commonly used for network troubleshooting, traffic monitoring, and security analysis.

Common commands

sudo tcpdump -i eth0 Captures all traffic on a specific interface, in this case eth0. The -i flag specifies which network interface to listen on.

sudo tcpdump -i any host 192.168.1.5 Captures all traffic to and from a specific IP address (192.168.1.5). Using any for the interface tells tcpdump to listen on all available interfaces simultaneously.

sudo tcpdump -i any port 80 Captures all traffic on port 80, which is the default port for unencrypted HTTP traffic. Useful for inspecting web requests and responses.

sudo tcpdump -i any -w capture.pcap Captures raw packets and writes them to a file (capture.pcap) rather than displaying them in the terminal. The .pcap file can be opened later in a tool like Wireshark for deeper visual analysis. The -w flag specifies the output file.

Troubleshooting with tcpdump

tcpdump operates at the raw packet level, making it useful for three common scenarios:

• Verifying connectivity: Confirms whether your machine is actually sending packets (e.g. SYN packets) to a server, rather than the issue being local.
• Diagnosing TLS issues: You can observe the ClientHello and ServerHello packets of a TLS handshake. If the handshake stalls at that point, it typically indicates a certificate problem.
• Identifying unexpected traffic: Reveals any unusual or unrecognised traffic appearing on a given port.

CWR and ECE Flags for Congestion Control

These two TCP flags work together as part of Explicit Congestion Notification (ECN), allowing routers to signal congestion without dropping packets.

ECE — Explicit Congestion Notification Echo When a router detects congestion, it sets the ECN flag in the IP header of passing packets. When the receiver’s TCP stack sees this, it notifies the sender by setting the ECE flag in its ACK, signalling that congestion is occurring in the network.

CWR — Congestion Window Reduced When the sender receives a segment with the ECE flag set, it responds by reducing its congestion window (cwnd). It then sets the CWR flag in its next outgoing segment to inform the receiver that it has acknowledged the congestion signal and has already reduced its sending rate. This prevents the receiver from continuing to echo congestion notifications unnecessarily.

TCP Connection Termination

TCP closes connections gracefully using a 4-way handshake, ensuring both sides finish transmitting before closing. An immediate termination is also possible using a RST packet.

The 4-way handshake

1. The client decides to close and sends a FIN packet to the server. Client state: ESTABLISHED — FIN_WAIT_1.
2. The server receives the FIN and sends an ACK. The server can still send its own data at this point. Server state: ESTABLISHED — CLOSE_WAIT. Client state on receiving ACK: FIN_WAIT_1 — FIN_WAIT_2.
3. When the server is ready to close, it sends its own FIN. Server state: CLOSE_WAIT — LAST_ACK.
4. The client receives the server’s FIN and sends a final ACK. Client state: FIN_WAIT_2 — TIME_WAIT. Server state on receiving ACK: LAST_ACK — CLOSED.
5. The client waits in TIME_WAIT for a period of 2 × MSL (Maximum Segment Lifetime) to ensure the final ACK was received and to allow any delayed duplicate packets to expire. Client state then moves to CLOSED.

Troubleshooting commands

• netstat -an | grep TIME_WAIT — check for connections stuck in TIME_WAIT
• netstat -an | grep CLOSE_WAIT — check for connections stuck in CLOSE_WAIT

TCP Retransmissions

When a segment is lost or corrupted in transit, TCP detects this and retransmits the affected data without involving the application layer.

1. Detecting loss : TCP uses ACK numbers to track received segments. If the sender does not receive an ACK within the Retransmission Timeout (RTO), it assumes the segment was lost or corrupted and retransmits it.

2. Retransmission Timeout (RTO) : The RTO is the duration the sender waits for an ACK before retransmitting. It is dynamically adjusted throughout the connection based on current network conditions, such as round trip time.

3. Fast Retransmit : Rather than always waiting for the RTO to expire, TCP uses Fast Retransmit. If the sender receives three duplicate ACKs (three ACKs for the same sequence number), it infers that a segment has been lost and retransmits it immediately, without waiting for the timeout. This is faster and less disruptive than waiting for the RTO.

4. Retransmission process : The sender resends the original segment with the same sequence number. The receiver acknowledges it on receipt, confirming successful delivery and allowing the connection to continue.

5. Selective Retransmission (SACK) Rather than retransmitting everything from the point of loss, TCP uses Selective Acknowledgement (SACK) to retransmit only the specific missing segments. This avoids redundant retransmissions and makes more efficient use of network resources.

UDP (User Datagram Protocol)

Its a connectionless and unreliable transport layer protocol in the TCP/IP protocol suite.

It provides a minimalistic and lightweight mechanism for sending datagrams between devices on an IP network.

Characteristics

• Connectionless protocol
• Unreliable delivery
• 8 bytes header
• Stateless communication
• Fast transmission
• Broadcast and multicast support

Differences in TCP and UDP

QUIC (Quick UDP Internet Connections)

It was developed by Google and designed to overcome the limitations of the traditional transport protocols such as TCP and UDP.

It provides low latency, reliability and secure transport for web traffic mostly in real time applications and mobile networks.

Its built on top of UDP leveraging its lightweight and connectionless ways.

Multiplexing in QUIC

• Single Socket Communication: In QUIC, all communication, including multiple streams, occurs over a single socket. Unlike TCP, which requires separate connections for each stream, QUIC multiplexes multiple streams within a single connection.
• Stream Identification: Each QUIC stream is uniquely identified by a Stream ID, allowing the client and server to distinguish between different streams within the same connection. Stream IDs are bidirectional, meaning that both the client and server can initiate streams.
• Concurrent and Independent Streams: QUIC allows for concurrent transmission of multiple streams within a single connection. This means that multiple streams can progress simultaneously without being blocked by each other. Each stream operates independently, and the order of the packets within different streams does not affect each other, addressing the head-of-line blocking problem found in TCP.
• Stream Prioritization: QUIC supports stream prioritization, enabling the client or server to assign priority levels to different streams. By assigning priorities, important or time-sensitive streams can be given higher priority, ensuring their delivery and reducing the impact of lower-priority streams on the overall performance.

Benefits of multiplexing

• Increased Efficiency: Multiplexing allows for more efficient use of the network connection by transmitting multiple streams simultaneously. It reduces the need for establishing multiple connections and the associated overhead.
• Reduced Latency: QUIC’s multiplexing capabilities help reduce latency by eliminating the need for multiple round trips to establish separate connections for each stream.
• Enhanced Performance: Multiplexing enables better resource utilization and improves overall performance by allowing parallel processing of multiple streams without blocking.

QUIC INTEGRATION WITH HTTP/3

Port numbers

MSS (Maximum Segment Size)

MSS is the maximum application data payload in a TCP segment, excluding TCP and IP headers.

MSS = MTU — 40 bytes for standard IPv4/TCP.

While MTU is the maximum packet size a network link can carry, including all headers.

MSS is a concept at the transport layer (Layer 4) and is specific to TCP

How is MSS determined? During TCP 3-way handshake, each side advertises its MSS based on its local MTU. The connection uses the smaller of the two advertised values. For example, if client MSS=1460 and server MSS=1360, they’ll use MSS=1360.

MSS prevents IP fragmentation by ensuring TCP segments, when encapsulated with IP and TCP headers, don’t exceed the path MTU. This avoids the performance overhead of fragmentation and reassembly.

For example, in Ethernet, the standard MTU is 1500 bytes. The IP header is 20 bytes (without options) and the TCP header is 20 bytes (without options).

MSS = 1500–20–20 = 1460 bytes

What happens if MSS is set too high? Packets get fragmented by routers, leading to increased overhead, potential out-of-order delivery, and if any fragment is lost, the entire packet must be retransmitted. In worst cases, packets get silently dropped if fragmentation is needed but DF bit is set.

PMTUD is a technique where TCP sets the DF (Don’t Fragment) bit and gradually increases packet size. If a router can’t forward a packet without fragmentation, it sends an ICMP ‘Fragmentation Needed’ message, allowing TCP to discover the path’s minimum MTU.

Why might you manually set MSS? In scenarios like VPN tunnels, PPPoE connections, or when PMTUD fails due to firewalls blocking ICMP, manually setting a lower MSS can prevent connectivity issues and fragmentation problems

MTU (Maximum Transmission unit)

It limits the maximum payload size in a single UDP datagram in an underlying network.

If payload exceeds the MTU, fragmentation may occur.

Differences in MTU and MSS

Interview scenarios

1. Explain how TCP handshake works" and "What's the difference between TCP and 
UDP?

2. TCP flow control and congestion control — covered in the networking 
fundamentals round, alongside packet drop analysis and H-S-R-S-H 
communication scenarios.

3. Describe how the TCP header in an IPv4 packet changes going from 
device to device, and which fields change within the header

4. How would you send packets to remote machines and try to upgrade them 
remotely? How would you troubleshoot if some machines are not updated?

5. Walk me through how you'd troubleshoot a server that's not reachable

6. What's the maximum theoretical number of TCP connections a host may 
have open?

7. You're on-call and monitoring a backend service at Meta. 
A dashboard alert fires: the server has 80,000 sockets in 
TIME_WAIT state. No new connections are being accepted. 
Walk me through what's happening, why it matters, and how you'd resolve it.

8. A Meta data pipeline is transferring large files between two datacenters. 
Engineers report throughput has dropped from 10Gbps to ~200Mbps with no 
changes deployed. When you run a packet capture, you see heavy TCP 
retransmissions. How do you diagnose this and what Layer 4 mechanisms 
are at play?

9. A Meta-facing API endpoint is completely unresponsive to new clients, 
but existing connections are working fine. You check the server and find 
the SYN backlog is full. Explain what's happening at Layer 4 and how you 
would mitigate it without taking the service offline.

10. A product team at Meta wants to migrate a real-time video streaming 
feature from TCP to UDP-based QUIC. Your manager asks you to evaluate the 
trade-offs at the transport layer and list the specific operational 
concerns you'd raise before approving the migration.

11. An internal service at Meta is sending data to a consumer that processes 
it slowly. Engineers notice the producer's send rate has throttled to near 
zero even though the network is healthy. There's no packet loss. 
What Layer 4 mechanism explains this, and how would you investigate and fix it?

12. Meta is running a fleet of NAT gateways for egress traffic. 
Engineers report intermittent connection failures to external API 
roughly 0.1% of requests fail with connection refused or timeout. 
The network path is healthy and packet loss is zero. 
How do you approach this at Layer 4?

13. During a code review, a colleague proposes setting the IP TTL to 1 
for all packets sent between two services in the same datacenter as a 
'security measure to prevent routing outside the DC.' 
You're asked to evaluate this. What Layer 4 and network interactions 
does this affect, and would you approve it?

14. A Meta service migrates from TLS 1.2 to TLS 1.3. 
After rollout, engineers observe that connection setup latency 
dropped measurably, but a small number of enterprise clients start 
failing to connect. Explain the Layer 4 behavior change and why some 
clients might break.

1. Routers and the Internet Protocol
2. Network gateway
3. Route tables
4. IPv4
5. IPv6
6. Differences in both IPv4 and IPv6
7. Static routing
8. Dynamic routing
9. Backup routes
10. L3 switches
11. Routing vs switching
12. NAT (Network Address Translation)
13. Differences in RIP, OSPF, BGP
14. MTU (Maximum Transmission Unit)
15. Interview scenarios

Routers

Connects multiple networks together and forwards data packets between them.

Use routing tables and protocols to determine the best path for data to travel from its source to its destination.

When a packet arrives at one of the interfaces, the router reads the destination IP address and checks its routing table to determine the next hop.

Have the ability to fragment and reassemble IP packets.

Use dynamic routing protocols to automatically update and share routing information with other routers on the network.

Provide features such as NAT , Quality of service (QoS) and VPN support.

Network gateway

It acts as a bridge between 2 networks , allowing devices on one network to communicate with devices on another network.

Route tables

A routing table is a data structure used by routers to determine the best path for forwarding packets to their destination network.

Contains information about directly connected networks, remote networks learned through static and dynamic protocols and the next-hop router or interface to reach each network.

Determines the outgoing interface or next-hop Ip address for a packet on the destination IP address.

Internet Protocol (IP)

Its a network layer protocol that is responsible for routing packets of dta across a network.

Its protocol that provides the internet its name.

IP is connectionless, best effort protocol.

There are 2 versions : version 4 and version 6

Its an end to end protocol hence responsible for delivering packets of data from the source device to the destination device, regardless of the number of networks that the data traverses.

IPv4

Its the most widely used version of the IP(Internet Protocol).

It uses 32 bits addresses which allow a total of approximately 4.3 billion unique addresses.

They are not globally unique and not intended to be routed on the internet.

They are mainly used for internal networks and are not reachable from the internet.

Here are the ranges : — 
- 10.0.0.0–10.255.255.255 (10.0.0.0/8)
- 172.16.0.0–172.31.255.255 (172.16.0.0/12)
- 192.168.0.0–192.168.255.255 (192.168.0.0/16)

IPv4 Header : has a length of 20 -60 bytes.

IPv6

It was developed to address the IPv4 address shortage.

It uses 128 bit addresses allowing a total of approximately 3.4 x 10 ^ 38 unique addresses.

It has an improved routing and security features.

IPv6 has a fixed header at 40 bytes.

Differences in IPv4 and IPv6

Static routing protocol

Manually configuring the routing table on a network router or gateway device.

The network administrator specifies the route for each network or subnet that the router needs to know how to reach manually by entering the IP address of the destination netwotk along with the next hop IP address.

Static routing table determines the best path for packets to travel.

Dynamic routing protocol

Its a protocol that does automatic updates of the routing tables in response to the changes in the network topology.

It improves network efficiency, reduce network downtime and simplify network management.

Types : —

1. Distance vector — protocols determine the best path to a destination based on a measure of distance such as hop count. Example RIP and IGRP
2. Link state — Best path is based on the state of links in the network. Example OSPF and IS — IS
3. Path vector — Best path to a destination is based on information received from other routers. Examples BGP

Differences in static and dynamic routing

Administrative distance — Its a value assigned to a routing protocol to indicate its trustworthiness or reliability relative to other routing protocols.

Used by routers to determine the best path to a destination when there are multiple routing protocols advertising routes to the same destination.

Backup route — Its a secondary path to a destination nlw that is used when primary path is unavailable or fails.

Typically configured in routing protocols using metrics or administrative distances to determine the best path to take.

Configuring a backup route:-

• Manually add a static route with a higher administrative distance value than the primary route
• Configure a backup interface for a dynamic routing protocol such as OSPF or EIGRP
• Use a routing protocol with load balancing capabilities such as Equal Cost Multipath (ECMP)

L3 SWITCHES

It combines the functions of a switch and a router allowing them to route traffic between different subnets.

Operate at both layer 2 and layer 3.

They use hardware-based switching and routing which provides faster performance compared to software based routing used by traditional routers.

Advanced features such as access control lists (ACLs), Quality of Service (QoS) settings and support for routing protocols such as BGP and OSPF.

NAT (Network Address Translation)

It translates private IP addresses into public IP addresses within a local network for internet communication. It maps private IP addresses to public IP addresses when traffic flows.

Addresses the shortage of available IP addresses and enhance network security by concealing internal IP addresses from external sources.

Configured on network devices such as routers, firewalls and gateways that serve as intermediaries between a private network and external networks.

Types of NAT:

• Static NAT — It involves one to one mapping between a private IP address and a public address.
• Dynamic NAT — Allows a pool of public IP addresses to be shared among multiple devices within a private network.
• Port Address Translation (PAT) — maps multiple private IP addresses to a single public IP address using different source port numbers.

NAT66: IPv6 method that translates addresses similar to IPv4 NAT. Converts global IPv6 addresses to local ones.

NAT64: Used for transition from IPv4 to IPv6. Enables IPv6 only devices to communicate with IPv4 only devices by translating between the 2 protocols.

RIP, OSPF, BGP

I have done a separate document that I go in detail concerning OSPF and BGP since they are core in an interview setting.

I will share a table that shows the core differences among the 3 and you can reference the other articles to get a deep dive of the other core parts.

MTU (Maximum Transmission Unit)

Maximum size of a single packet that can be transmitter over a particular network link or protocol.

Measured in bytes.

MTU-related issues can cause network connectivity problems, especially when traversing different network technologies or VPNs. In such cases, adjusting the MTU size or enabling Path MTU Discovery can help resolve the problems.

Interview scenarios

What is your favourite L2/L3 protocol?

Why can't we use OSPF to connect all systems together, 
and what is unique about BGP? What is an autonomous system? 
How is routing information exchanged? What's the difference 
between iBGP and eBGP peers? How does BGP differentiate between 
external and internal peers? How is a BGP session established? 
How do you prevent routing loops? How do you control inbound/outbound 
traffic? Is there any inspection before sending a route to a different 
neighbour, by the sender or receiver?

BGP vs OSPF — differences, explain in depth. 
Network fundamentals — routing, switching, layering.

Describe how the TCP header in an IPv4 packet changes going 
from device to device, and which fields change. Describe the same for IPv6.

Given a scenario of experiencing network performance issues such as 
latency and packet loss , what are the possible reasons? 
What steps would you take to narrow down the issue?

Walk me through how you'd troubleshoot a server that's not reachable.

Happy coding and have a great one.

If I was starting all over again to learn python this are the core things I would focus on and ensure that I have then in my finger tips.

BASICS ARE THE ICING IN THE CAKE.

1. Introduction
2. Strings
3. Arrays
4. Logic and operators
5. Conditional statements
6. Loops
7. Data structures
8. Functions

Introduction

1. What is python
2. How python works
3. Why learn python
4. Variables
5. OOP — Object Oriented Programming in Python
6. Print statements
7. input()
8. Data types
9. Comments

Strings

1. String operators
2. Built in types and methods
3. Indexing
4. Slicing
5. Searching and validating

Arrays

1. Array methods and operators
2. Array functions
3. Comprehensions
4. Slicing

Logic and operators

1. Membership operators
2. Comparison operators
3. Logical operators
4. Identity operator

Conditional statements

1. If, else, elif, nested if, ternary and match cases

Loops

1. For loop — for loop, statements and nested loops
2. While loop

Data structures

1. Lists
2. Dictonaries (hashmaps)
3. Sets
4. Tuples

Functions

1. Types of functions
2. Parameters
3. Arguments
4. Return
5. Types by purpose
6. Clean functions

Happy coding and I hope python becomes your favorite language.

It means ‘Try a choice, explore where it leads, then undo that choice and try another’.

Key ideas:-

• You build a solution step by step
• At each step, you have choices
• You revert (backtrack) after exploring a choice

According to wikipedia:-

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, that incrementally builds candidates to the solutions, and abandons each partial candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.

A nice example to work with is the maze. Imagine to have a maze and you want to find if it has an exit. You can pick a path and realize it wont take you out hence you have to take another one.

A simple pseudo code for traversing a maze and check if there is an exit.

function backtrack(cell):
  
  if is_exit:
    return true
  for each direction of cell:
    if backtrack(next_cell):
      return true    
  
  return false

# Try a path
# If it leads to success - stop
# Otherwise - undo and try another path

Backtracking is almost always implemented with recursion.

In most backtracking problems, you will be building something, either directly (like modifying an array) or indirectly (using variables to represent some state).

Pseudocode for a general backtracking

// let curr represent the thing you are building
// it could be an array or a combination of variables

function backtrack(curr) {
    if (base case) {
        Increment or add to answer
        return
    }

    for (iterate over input) {
        Modify curr
        backtrack(curr)
        Undo whatever modification was done to curr
    }
}

curr
- The partial solution you’re building
(subset, path, string, sequence, coordinates)

Base case
- “Am I done building one valid solution?”

Add to answer
- Save this solution (or count it, or return true)

Loop over choices
- Try every possible next decision

Modify curr
- Make a choice

Recursive call
- Explore deeper with that choice

Undo modification
- Backtrack so the next choice starts clean

Each call to the function backtrack represents a node in the tree. Each iteration in the for loop represents a child of the current node, and calling backtrack in that loop represents moving to a child.

The line where you undo the modifications is the “backtracking” step and is equivalent to moving back up the tree from a child to its parent.

At any given node, the path from the root to the node represents a candidate that is being built. The leaf nodes are complete solutions and represent when the base case is reached. The root of this tree is an empty candidate and represents the scope that the original backtrack call is being made from.

Problems to solve :-

• Subsets
• Permutations
• Combinations

And their variants to help you get a grasp of them.

I hope this helps you ensure you have a deep understanding of backtracking.

Happy coding.