Code Snippets | Sudipta Karmakar

Bash Color Output

This is an example of how output text color can be modified in bash. Here is the main source from Stack Overflow. List of ANSI escape codes here.

# Color codes
Black        0;30     Dark Gray     1;30
Red          0;31     Light Red     1;31
Green        0;32     Light Green   1;32
Orange       0;33     Yellow        1;33
Blue         0;34     Light Blue    1;34
Purple       0;35     Light Purple  1;35
Cyan         0;36     Light Cyan    1;36
Light Gray   0;37     White         1;37
 
# Example:
RED='\033[0;31m'
NC='\033[0m' # No Color
printf "I ${RED}love${NC} New York\n"

Ackermann Function

Python implementation of Ackermann function

def ackermann(m, n):
   """Computes Ackermann function A(m, n)
   :param n, m: non-negative integers
   """
   cache = {}
 
   def ack(x, y):
       if cache.get((x, y)) is not None:
           return cache.get((x, y))
       if x == 0:
           cache[(x, y)] = y + 1
           return y + 1
       if y == 0:
           cache[(x, y)] = ack(x - 1, 1)
           return cache[(x, y)]
       cache[(x, y)] = ack(x - 1, ack(x, y - 1))
       return cache[(x, y)]
 
   return ack(m, n)

Connected Components in a Graph

Python implementation of finding the number of connected components in a Graph

class Node(object):
   def __init__(self, value):
       self.visited = False
       self.connected_to = set()
 
   def connect(self, *nodes):
       self.connected_to.update(nodes)
 
   def neighbors(self):
       for node in self.connected_to:
           yield node
 
def dfs(node):
   for neighbor in node.neighbors():
       if neighbor.visited : continue
       neighbor.visited = True
       dfs(neighbor)
 
def get_components(graph):
   components = 0
   for node in graph:
       if node.visited: continue
       node.visited = True
       components += 1
       dfs(node)
   return components

Two Sum

Given an array of integers and an integer target, return indices of the two numbers such that they add up to target.

from typing import List
 
 
def two_sum(nums: List[int], target: int) -> List[int]:
   memo = dict()
   for i, n in enumerate(nums):
       if (target - n) in memo:
           return (memo[target - n], i)
       memo[n] = i
 
   return ValueError("The input list is invalid")

Rotate Matrix

Rotate a square matrix clockwise in place

from typing import List
 
 
def rotate(matrix: List[List[int]]) -> None:
   width = len(matrix) - 1
   for i in range(len(matrix) // 2):
       for j in range(i, width - i):
           matrix[i][j], matrix[~j][i], matrix[~i][~j], matrix[j][~i] = (
               matrix[~j][i],
               matrix[~i][~j],
               matrix[j][~i],
               matrix[i][j],
           )

Median Finder From Streaming Data

Finding the median from incoming streaming data

import heapq
 
 
class MedianFinder:
   def __init__(self):
       self.lower_half = []  # max heap
       self.upper_half = []  # min heap
 
   def add(self, num: int) -> None:
       if len(self.lower_half) <= len(self.upper_half):  # less than is N/A
           heapq.heappush(self.lower_half, -heapq.heappushpop(self.upper_half, num))
       else:
           heapq.heappush(self.upper_half, -heapq.heappushpop(self.lower_half, -num))
 
   def find_median(self) -> float:
       if len(self.lower_half) > len(self.upper_half):
           return -self.lower_half[0]
       return (-self.lower_half[0] + self.upper_half[0]) / 2.0

Maximum Subarray Sum

Kadane's algorithm for computing maximum contiguous subarray sum

import math
from typing import List
 
 
def maximum_subarray_sum(nums: List[int]) -> int:
   global_max = -math.inf
   local_max = -math.inf
   for num in nums:
       local_max = max(local_max + num, num)
       global_max = max(global_max, local_max)
   return global_max

Remove Nth Node From End of List

Given the head of a linked list, remove the n-th node from the end of the list and return its head

def remove_last_nth_node(head: ListNode, n: int) -> ListNode:
   sentinel = ListNode(-1)
   sentinel.next = head
   trailing = sentinel
 
   while head:
       head = head.next
       n -= 1
       if n < 0:
           trailing = trailing.next
   trailing.next = trailing.next.next
   return sentinel.next

Code Snippets !

Snippets