CCJ’s Coding Note 2021 (1) - Basic Knowledge Points Summary

Written by CCJ, Monday, Jan 18, 2021 @ Secaucus, NJ, USA.

DFS - Path Finding

• find a path between two given vertices u an z;

• Use a stack S to keep track of the path between the start vertex and the current vertex

DFS - Cycle Finding

• use a stack S to keep track of the path between the start vertex and the current vertex

• As soon as a back edge (v, w) is encountered, we return the cycle as the protion of the stack from the top to vertex 𝑤w

• Shown as below:

Graph - Adjacency List Representation

• Graph in Python can be implemented by defaultdict;

• DFS and BFS are implemented below;

# Python3 program to print DFS traversal 
# from a given given graph 
from collections import defaultdict 

# This class represents a directed graph using 
# adjacency list representation 
class Graph: 

    # Constructor 
    def __init__(self): 
        # default dictionary to store graph
        # Using List as defaultdict's default_factory
        self.graph = defaultdict(list) 

    # function to add an edge to graph 
    def addEdge(self, u, v): 
        self.graph[u].append(v) 

    # A recursive function used by DFS 
    def DFSUtil(self, v, visited): 
        # Mark the current node as visited and print it 
        visited[v] = True
        print(v, end = ' ') 

        # Recur for all the vertices adjacent to this vertex 
        for i in self.graph[v]: 
            if visited[i] == False: 
                self.DFSUtil(i, visited) 

    # The function to do DFS traversal. It uses 
    # recursive DFSUtil() 
    def DFS(self, v): 
        # Mark all the vertices as not visited 
        visited = [False] * (max(self.graph)+1) 

        # Call the recursive helper function to print DFS traversal 
        self.DFSUtil(v, visited) 

    # Function to print a BFS of graph 
    def BFS(self, s): # s is int value;
        # Mark all the vertices as not visited 
        visited = [False] * (len(self.graph)) 

        # Create a queue for BFS 
        queue = []

        # Mark the source node as visited and enqueue it 
        queue.append(s) 
        visited[s] = True

        while queue: 
            # Dequeue a vertex from queue and print it
            # current vertex v:
            # and the first value of v will be the starting node s;
            v = queue.pop(0) 
            print (v, end = " ") 

            # Get all adjacent vertices of the 
            # dequeued vertex v. If an adjacent 
            # has not been visited, then mark it 
            # visited and enqueue it 
            for i in self.graph[v]: # for all incidentEdges(v), that is,edge (v, i)
                if visited[i] == False: 
                    queue.append(i) 
                    visited[i] = True

---

Heap and Heapify

1) Definition

A heap is a binary tree storing keys at its internal nodes and satisfying the following properties:

• Heap-Order: for every internal node other than the root, key() key(parent()).

• Complete Binary Tree: let be the height of the heap

  • for , there are nodes of depth ;

  • at depth , the internal nodes are to the left of the external nodes. By saying that all the internal nodes on level are “to the left” of the external nodes, we mean that all the internal nodes on this level will be visited before any external nodes on this level in an inorder traversal.

The last node of a heap is the rightmost internal node of depth h − 1.

2) Height of a Heap

3) Insertion into a Heap and Up-heap Bubbling

• Method insertItem(k): insert a key to the heap.

• Up-heap bubbling after an insertion: restore the heap-order property after insertion.

4) Removal from a Heap and Down-heap Bubbling

• Method removeMin(): remove of the root key from the heap.

• Down-heap bubbling after a Removal: restore the heap-order property after removal.

5) Here we consider a Max-heap:

""" array representation of Max-heap """

class heapq(object):
    def __init__(self):
        self.arr = []
        self.n = 0
    def print_heap(self):
        print ("heap = %s" %self.arr)

    # calling insertNode for each element;
    def heapify(self, lst):
        print ("loading list = %s" %lst)
        for i in lst:
            self.insertNode(key=i)
        print ("heapified list = %s" %self.arr)

    # Function to heapify ith node in a Heap 
    # of size n following a Bottom-up approach 
    def heapify_upheap(self, idx): 
        #Find parent 
        parent = (idx - 1) // 2 
        if parent >= 0: 
            #For Max-Heap 
            #If current node is greater than its parent 
            #Swap both of them and call heapify again for the parent 
            if (self.arr[idx] > self.arr[parent]):
                self.arr[idx], self.arr[parent] = self.arr[parent], self.arr[idx] #swap
                # Recursively heapify the parent node
                self.heapify_upheap(parent)

    # insert the key to heap
    def insertNode(self, key):
        # Insert the element at end of Heap  
        #Increase the size of Heap by 1
        self.arr.append(key)
        self.n += 1

        #Heapify the new node following a 
        #Bottom-up approach 
        self.heapify_upheap(self.n - 1)


    # To heapify a subtree rooted with node with index idx;
    def heapify_downheap(self, idx):
        largest_idx = idx # initialize largest as root
        # since we idx=0
        l = 2*idx + 1 # left node 
        r = 2*idx + 2 # right node

        # if left child is larget that root
        if (l < self.n and self.arr[l] > self.arr[largest_idx]):
            largest_idx = l

        # if right child is larget that root
        if (r < self.n and self.arr[r] > self.arr[largest_idx]):
            largest_idx = r

        # If largest_idx is not root
        if largest_idx != idx:
            # swap
            self.arr[idx], self.arr[largest_idx] = self.arr[largest_idx], self.arr[idx]
            # Recursively heapify the affected sub-tree 
            self.heapify_downheap(largest_idx)

    # Function to delete the root from Heap
    def deleteRoot(self):
        # get the last element
        lastElement = self.arr.pop() # If not passed, the default index -1 is passed;
        root = self.arr[0]

        #Replace root with first element 
        self.arr[0] = lastElement

        #Decrease size of heap by 1 
        self.n -= 1

        # heapify the root node
        self.heapify_downheap(0)
        return root

See the results:

Binary Search

Please pay attention to the boundary cases:

• Initial Condition: lo = 0, hi = len(nums) - 1;

• Termination: lo > hi (i.e., while (lo <= hi) will keep searching!)

• Find middle: mid = (left + right) // 2 (or mid = (left + right+1) // 2 also works)

• Searching Left: hi = mid - 1

• Searching Right: lo = mid + 1

1) Iterative Version

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return -1

        n = len(nums)
        #print (n)
        if n == 1:
            return 0 if nums[0] == target else -1
        else:
            lo, hi = 0, n-1
            while (lo <= hi):
                mid = (lo + hi) // 2
                if nums[mid] < target:
                    #print (1)
                    lo = mid + 1
                elif nums[mid] > target:
                    #print (2)
                    hi = mid -1
                else:
                    return mid
            return -1

• LeetCode Submission (Passed):

2) Recursive Version

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """


        def search_rec(nums, lo, hi, target):
            # Check base case 
            if lo <= hi:
                mid = (lo + hi)//2
                if nums[mid] < target:
                    return search_rec(nums, mid+1, hi, target)
                elif nums[mid] > target:
                    return search_rec(nums, lo, mid-1, target)
                else:
                    return mid
            else:
                return -1

        # main function
        if not nums:
            return -1

        n = len(nums)
        if n == 1:
            return 0 if nums[0] == target else -1
        else:
            return search_rec(nums, lo=0, hi = n-1, target= target)

• LeetCode Submission (Passed):

Small Graph Knowledge Points:

Connected Component

• A connected component or simply component of an undirected graph is a subgraph in which each pair of nodes is connected with each other via a path.

• In connected components, all the nodes are always reachable from each other.

Tree and Spanning Tree

• In graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph.

• A spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G, with a minimum possible number of edges.

• In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree.

• If all of the edges of G are also edges of a spanning tree T of G, then G itself is a tree and is identical to T (that is, a tree has a unique spanning tree and it is itself).

Properties of DFS

Properties of BFS

Binary Search Tree (BST)

• A binary search tree is a binary tree storing keys at its internal nodes and satisfying:

  • key(left_subtree(v)) < key(v) < key(right_subtree(v))

• An inorder traversal of a BST visits the keys in increasing order.

• Construct a BST via insert note:

class Node:
    def __init__(self, x):
        self.left= None
        self.right = None
        self.val = x

def binary_insert(root, node):
    if root is None:
        root = node
        return root
    else:
        if node.val < root.val:
            root.left = binary_insert(root.left, node)
        else:
            root.right = binary_insert(root.right, node)
        return root

---

Small Python/C++ Knowledge Points

1) nonlocal

nonlocal keyword –> Yes in Python3 , No Python2.

2) defaultdict

• defaultdict does not have KeyError, compared with regular dictionary.

from collections import defaultdict
# default dictionary to store graph
# Using List as defaultdict's default_factory
self.graph = defaultdict(list) 

3) sorted

 A_sort = sorted(A, key = lambda x: x[0], reverse = False)

4) last index -1

• a = [1, 2, 3]

• a[-1] = 3

• a[0:-1] = [1, 2], since s_idx:e_idx indexing will include the element at s_idx, and exclude the element at e_idx.

5) DFS VS BFS

• DFS –> recursive, can be changed to iterative version by using stack;

• BFS –> iterative, BFS uses the queue(e.g., implemented by a list in Python) to

  • i) Push the root into the queue.

  • ii) Pop-out a node from the left.

  • iii) Push the left child into the queue, and then push the right child.

6) Python list

• pop(): removes the last element;

• pop(0): remove the first element;

• pop(index): removes the one with index;

7) Queue: python list

• Queue: FIFO

• enqueue(e) –> some_list.append(e)

• dequeue() –> some_list.pop(0)

8) Stack: python list

• Stack: LIFO

• push(e) –> some_list.append(e)

• pop() –> some_list.pop(), i.e., to remove and return last element

9) MAX and MIN number

• in Python:

  • float('-inf') for minimum number;

  • float('inf') for maximum number.

• in C++:

  • INT_MIN (i.e., );

  • INT_MAX (i.e., );

  • LONG_MIN (i.e., );

  • LONG_MAX (i.e., );

10) Deque (Doubly Ended Queue)

• Deque (Doubly Ended Queue): Deque is preferred over list in the cases where we need quicker append and pop operations from both the ends of container, as deque provides an O(1) time complexity for append and pop operations as compared to list which provides O(n) time complexity.

• popleft() - This function is used to delete an argument from the left end of deque.

• appendleft() - This function is used to insert the value in its argument to the left end of deque.

• append() - This function is used to insert the value in its argument to the right end of deque.

• pop() - This function is used to delete an argument from the right end of deque.

11) print - end

• print ( v, end = ” “)

• print ( v, end = “, “)

12) bit shift

• a << 1 ==> a*=2

13) heap queue - heapq

• Heap data structure is mainly used to represent a priority queue.

• A heap is a binary tree storing keys at its internal nodes and satisfying the following properties:

• i) Heap-Order: for every internal node other than the root, key() key(parent()).

• ii) Complete Binary Tree: let be the height of the heap

  • for , there are nodes of depth ;

  • at depth , the internal nodes are to the left of the external nodes. By saying that all the internal nodes on level are “to the left” of the external nodes, we mean that all the internal nodes on this level will be visited before any external nodes on this level in an in-order traversal.

• The property of this data structure in Python is that each time the smallest of heap element is popped(min heap).

• Whenever elements are pushed or popped, heap structure in maintained.

• The heap[0] element also returns the smallest element each time.

• heapify(iterable) :- This function is used to convert the iterable into a heap data structure. i.e. in heap order.

• heappush(heap, ele) :- This function is used to insert the element mentioned in its arguments into heap. The order is adjusted, so as heap structure is maintained.

• heappop(heap) :- This function is used to remove and return the smallest element from heap. The order is adjusted, so as heap structure is maintained.

# importing "heapq" to implement heap queue 
import heapq 

# initializing list 
li = [5, 7, 9, 1, 3] 

# using heapify to convert list into heap 
heapq.heapify(li) 

# printing created heap 
print ("The created heap is : ",end="") 
print (list(li)) # The created heap is : [1, 3, 9, 7, 5];

# using heappush() to push elements into heap 
heapq.heappush(li,4) 

# printing modified heap 
print ("The modified heap after push is : ",end="") 
print (list(li)) # The modified heap after push is : [1, 3, 4, 7, 5, 9]

# using heappop() to pop smallest element 
print ("The popped and smallest element is : ",end="") 
print (heapq.heappop(li)) # The popped and smallest element is : 1

14) ASCII Code - ord

• ord('A') = 65

• ord('a') = 97

• Big letter + 32 ==> small letter

• ord('C') - ord('A') ==> relative index distance;

15) reversed list

• reversed(range(0,6)) ==> [5,4,3,2,1,0]

16) Binary Search in Python via bisect

• import bisect

• Bisect algorithm is to find a position in list where an element needs to be inserted to keep the list sorted.

• bisect(list, num, beg, end): This function returns the position in the sorted list, where the number passed in argument can be placed so as to maintain the resultant list in sorted order. If the element is already present in the list, the right most position where element has to be inserted is returned. This function takes 4 arguments, list - which has to be worked with, num - number to insert, beg - starting position in list to consider, end - ending position which has to be considered.

import bisect 

# initializing list 
li = [1, 3, 4, 4, 4, 6, 7] 

# using bisect() to find index to insert new element 
# returns 5 ( right most possible index ) 
print ("The rightmost index to insert, so list remains sorted is  : ", end="") 
print (bisect.bisect(li, 4)) # ==> 5

# using bisect_left() to find index to insert new element 
# returns 2 ( left most possible index ) 
print ("The leftmost index to insert, so list remains sorted is  : ", end="") 
print (bisect.bisect_left(li, 4)) # ==> 2

# using bisect_right() to find index to insert new element 
# returns 4 ( right most possible index ) 
print ("The rightmost index to insert, so list remains sorted is  : ", end="") 
print (bisect.bisect_right(li, 4, 0, 4)) # ==> 4
print (bisect.bisect_right(li, 4)) # ==> 5

17) C++ typedef

• typedef type new_name;

typedef int feet;
feet distance = 0; // <==> int distance = 0;

18) Logic Operators

• logic and: &&(C++) VS and(Python);

• logic or: ||(C++) VS or(Python);

• logic not: !(C++) VS not(Python);

19) Bitwise Operators in Python:

• In Python, bitwise operators are used to perform bitwise calculations on integers. The integers are first converted into binary and then operations are performed on bit by bit, hence the name bitwise operators. Then the result is returned in decimal format.

• Note: Python bitwise operators work only on integers.

• Bitwise not operator: Returns one’s compliment of the number.

• Bitwise xor operator: two different numbers get 1, and two same numbers get 0;

• Example:

a = 10 #1010 (Binary)
b = 4  #0100 (Binary)
a & b  # = 1010 & 0100 = 0000 = 0 (Decimal)
a | b # = 1010| 0100 = 1110 = 14 (Decimal)
~a # = ~1010 = -(1010 + 1) = -(1011) = -11 (Decimal)
a ^ b # = 1010 ^ 0100 = 1110 = 14 (Decimal)

20) Bitwise Operators in C++:

• C++ has the same bitwise Syntax as Python: including

  • & (bitwise AND)

  • | (bitwise OR)

  • ~ (bitwise NOT)

  • ^ (bitwise XOR)

  • << (left shift)

  • >> (right shift)

21) C++11 Constexpr

• constexpr double gravity {9.8};

22) Python isdigit()

'A'.isgigit() # False
'1'.isdigit() # True

23) How to Round Numbers in Python?

Syntax: round(number, number of digits)

Parameters: 

- number: The number to be rounded
- number of digits (Optional): The number of digits up to which the given number is to be rounded

For example:

# For floating point 
a = round(22.7) # ==> a = 23.0
a = int(round(22.7)) # ==> a = 23
a = int(round(22.4)) # ==> a = 22

a = int(round(22.5)) # ==> a = 23 in Python2
a = int(round(22.5)) # ==> a = 22 in Python3

• Note: 0.5 will be rounded up to 1.0 in Python2, but rounded down to 0.0 in Python3.

Binary Tree Right Side View - DFS

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution(object):
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if root is None:
            return []

        rightside = []

        def dfs(node, level):
            #---------------------
            # do right child first, 
            # so when recursive right child done, 
            # then turn to left child, the 
            # len(rightside) has been larger than 
            # the level the left child has.
            if level == len(rightside):
                rightside.append(node.val)

            #---------------------
            # do right child first, 
            for v in [node.right, node.left]:
                if v:
                    dfs(v, level+1)

        # launch it
        dfs(root, 0)
        return rightside

Binary Tree Right Side View - BFS

• Deque (Doubly Ended Queue): Deque is preferred over list in the cases where we need quicker append and pop operations from both the ends of container, as deque provides an O(1) time complexity for append and pop operations as compared to list which provides O(n) time complexity.

class Solution(object):
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        from collections import deque
        if root is None:
            return []

        queue = deque([root,])
        rightside = []

        while queue:
            level_length = len(queue)

            for i in range(level_length): # corresponding to for all the edges;
                node = queue.popleft() #delete an argument from the left end of deque.

                # if it's the rightmost element
                if i == level_length-1:
                    rightside.append(node.val) #to the right end of deque

                # add child nodes in the queue 
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        return rightside

---

Written by CCJ, Monday, Jan 18, 2021 @ Secaucus, NJ, USA.