### Input Data for Top K Frequency Examples

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_python_datastrcutures.ipynb

Initializes sample data (`nums` list) and a variable `k` for subsequent examples demonstrating how to find the top K frequent elements.

```python
nums = [1,1,1,2,2,3]
k = 2
```

--------------------------------

### Initialize List for Binary Search Examples

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_decrease_and_conquer.ipynb

Initializes a list of sorted integers to be used as input for various binary search function examples.

```python
nums = [1, 3, 4, 6, 7, 8, 10, 13, 14, 18, 19, 21, 24, 37, 40, 45, 71]
```

--------------------------------

### Example Usage of All Paths Function (Python)

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_combinatorial_search.ipynb

This snippet demonstrates how to use the `all_paths` function to find and print all paths starting from node 0 in the defined graph. It initializes the path and answer lists, then iterates through the results to print each path.

```python
ans = []
path = [0]
all_paths(al, 0, path, ans)
for path in ans:
  path = [str(i) for i in path]
  print('->'.join(path), end = ', ')
```

--------------------------------

### Setup for Linked List Cycle Detection (Python)

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/Advanced_Search_on_Linear_Data_Structures.ipynb

Demonstrates how to create a cyclic linked list for testing cycle detection algorithms. Includes an `iterate` function that would get stuck in an infinite loop if called on a cyclic list, illustrating the problem that cycle detection solves.

```python
head_cycle = getLinkedList([1, 2, 3, 4, 5, 6, 3])

# Looping over a cyclic linked list makes the program stuck 
def iterate(head):
  cur = head_cycle
  while cur:
    print(cur.val)
    cur = cur.next
```

--------------------------------

### Python Min-Heap Push Operation Example

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_python_datastrcutures.ipynb

Demonstrates the usage of the custom `push` function on a sample min-heap, showing how an element is added and the heap property is restored.

```python
heap = [None, 6, 7, 12, 10, 15, 17] 
push(heap, 5)
print(heap)
```

--------------------------------

### Python Min-Heap Heapify Example (Top-Down with Float)

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_python_datastrcutures.ipynb

Demonstrates building a min-heap from a list using the custom `heapify` function (top-down with float).

```python
a = [21, 1, 45, 78, 3, 5]
heapify(a)
```

--------------------------------

### Python Min-Heap Heapify Example (Bottom-Up with Sink)

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_python_datastrcutures.ipynb

Demonstrates building a min-heap from a list using the custom `heapify` function (bottom-up with sink).

```python
a = [21, 1, 45, 78, 3, 5]
heapify(a)
```

--------------------------------

### Python Example Usage for Swapping Permutation Function

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_combinatorial_search.ipynb

This snippet demonstrates how to use the `permutate` function to generate all permutations of a list `a` using the swapping method. It initializes the list and calls the function with the starting depth, then implicitly shows the `ans` list which will contain all generated permutations.

```python
a = [1, 2, 3]
permutate(a, 0)
ans
```

--------------------------------

### Dataclass Example with `repr=False` and Defaults

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_python_datastrcutures.ipynb

A simple example demonstrating dataclass features, specifically using `field(repr=False)` to exclude fields from the default `__repr__` output and setting default values for fields.

```python
@dataclass
class C:
    x: int
    y: int = field(repr=False)
    z: int = field(repr=False, default=10)
    t: int = 20

a = C(1, 2)
print(a)
```

--------------------------------

### Example Keys for BST Operations

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_decrease_and_conquer.ipynb

A list of integer keys that can be used to construct or test Binary Search Tree operations.

```python
keys = [8, 3, 10, 1, 6, 14, 4, 7, 13]
```

--------------------------------

### Construct a Simple N-ary Tree Example

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_tree_data_structure_and_traversal.ipynb

This code demonstrates how to instantiate `NaryNode` objects and connect them to form a basic N-ary tree structure. It shows assigning children to a root node, illustrating a simple tree setup.

```python
root = NaryNode(1, 2)
left = NaryNode(2, 2)
right = NaryNode(3, 2)
# connect root to its left and right, the order does not matter
root.children[0] = left
root.children[1] = right
left = NaryNode(4, 0)
right = NaryNode(5, 5)
```

--------------------------------

### Initialize Adjacency Lists for SCC Examples

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/Colab Notebooks/graph_search_application.ipynb

Initializes two adjacency lists (`al2` and `al1`) to demonstrate strongly connected components. `al2` is a copy of a previous directed graph setup, and `al1` adds an edge to `al2`.

```python
'''in the second undirected graph'''
al2 = [[] for _ in range(7)]

# set 8 edges
al2[0] = [1]
al2[1] = [2]
al2[2] = [0, 4]
al2[4] = [3]
al2[5] = [6]

print(al)

'''in the first undirected graph'''
al1 = al2[::]

al1[3].append(1)

print(al1)
```

--------------------------------

### Python: Example Usage of Prim's Algorithm (Vertex PQ)

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Easy-Book/source-code/chapter_advanced_graph_search.ipynb

This snippet demonstrates how to call the `prim2` function with the example graph `a` to compute its Minimum Spanning Tree using the vertex-based priority queue approach. It shows the function's invocation and prints the resulting MST edges.

```python
print(prim2(a))
```

--------------------------------

### Example Usage: Construct Binary Tree from List

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/Colab Notebooks/tree_data_structure.ipynb

Shows how to use the 'constructTree' function with a sample list to build a binary tree.

```python
nums = [1, 2, 3, 4, 5, None, 6]
root = constructTree(nums, 0)
```

--------------------------------

### Python Min-Heap Pop Operation Example

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_python_datastrcutures.ipynb

Demonstrates the usage of the custom `pop` function on a sample min-heap, showing how the smallest element is removed and the heap property is restored.

```python
k = pop(heap)
print(k, heap)
```

--------------------------------

### Python: Experimenting with Hoare Partition (Commented Out Example)

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/Colab Notebooks/chapter_14_sorting.ipynb

Shows a commented-out example of how to test the Hoare partition function. It would demonstrate the partitioning of a sample list and print the resulting list and pivot index, similar to the Lomuto partition experiment.

```python
# lst = [9, 10, 2, 8, 9, 3, 7]
# print(partition_hoare(lst, 0, len(lst)-1))
# print(lst)
```

--------------------------------

### Python: Example Usage of Initial Subarrays With Sum Function

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/Advanced_Search_on_Linear_Data_Structures.ipynb

This snippet demonstrates calling the `numSubarraysWithSum` function with the previously defined `a` and `S` values. It shows how to execute the initial two-pointer implementation.

```python
numSubarraysWithSum(a, S)
```

--------------------------------

### Example Usage: Arrange Coins Math Solution

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_decrease_and_conquer.ipynb

Demonstrates calling the mathematical `arrangeCoins` function with an input of 8 coins to find the number of complete rows.

```python
arrangeCoins(8)
```

--------------------------------

### Python: Example Usage of Prim's Algorithm (Edge PQ)

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Easy-Book/source-code/chapter_advanced_graph_search.ipynb

This snippet demonstrates how to call the `prim` function with the example graph `a` to compute its Minimum Spanning Tree using the edge-based priority queue approach. It showcases the function's invocation with a sample graph.

```python
prim(a)
```

--------------------------------

### Example Usage of Powerset Function (Python)

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_combinatorial_search.ipynb

This snippet demonstrates how to use the `powerset` function to generate all subsets of the list `[1, 2, 3]`. It initializes the list and prints the resulting power set.

```python
a = [1, 2, 3]
n = len(a)
ans = []
powerset(a, n, 0, [], ans)
ans
```

--------------------------------

### Python: Example Usage of Suffix Array Construction

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/Colab Notebooks/suffix_array.ipynb

Demonstrates the usage of the cyclic_shifts_sort function with an example string 'ababaa' to illustrate the suffix array construction process.

```python
s = 'ababaa'
cyclic_shifts_sort(s)
```

--------------------------------

### Using Python's Built-in `queue.PriorityQueue`

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_python_datastrcutures.ipynb

Illustrates how to use Python's standard library `queue.PriorityQueue` for managing prioritized items. It shows initialization, adding items with `put()`, and retrieving them in priority order with `get()`.

```python
from queue import PriorityQueue
data = [[3, 'e'], [3, 'd'], [10, 'c'], [5,'b'], [3, 'a']]
pq = PriorityQueue()
for d in data:
  pq.put(d)
  
process_order = []
while not pq.empty():
  process_order.append(pq.get())
process_order
```

--------------------------------

### Python DAG Example for Topological Sort

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Easy-Book/source-code/chapter_advanced_graph_search.ipynb

An example adjacency list representation of a Directed Acyclic Graph (DAG) `dag`, specifically prepared for demonstrating topological sort algorithms.

```Python
dag = [[1], [2], [], [2, 4, 5], [], [6], []]
dag
```

--------------------------------

### Example Usage of solveNQueensSymmetry Function

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_combinatorial_search.ipynb

This snippet demonstrates how to call the `solveNQueensSymmetry` function with an input `n=7`. It prints the total number of valid N-Queens configurations for a 7x7 board, showcasing the function's output.

```python
print(solveNQueensSymmetry(7))
```

--------------------------------

### Example Usage of Permutation Generation (Swapping Method)

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_combinatorial_search.ipynb

Demonstrates how to use the `permutate` function with a sample list `[1, 2, 2, 3]` to generate and store its unique permutations in the global `ans` list.

```python
a = [1,2, 2, 3]
permutate(a, 0)
ans
```

--------------------------------

### Example Usage: Arrange Coins Binary Search Solution

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_decrease_and_conquer.ipynb

Demonstrates calling the binary search based `arrangeCoins` function with an input of 8 coins to find the number of complete rows.

```python
arrangeCoins(8)
```

--------------------------------

### Example Usage: Binary Search with Lower Bound

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_decrease_and_conquer.ipynb

Demonstrates the `lower_bound_bs` function with existing and non-existing target values to show its behavior in finding the first suitable position.

```python
# Binary Search with lower bound
l1 = lower_bound_bs(nums, 4)
l2 = lower_bound_bs(nums, 5)
print(l1, l2)
```

--------------------------------

### Example Usage: Standard Binary Search with Existing Target

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_decrease_and_conquer.ipynb

Demonstrates calling the `standard_binary_search` function with a target value that exists in the `nums` list, expecting a valid index as output.

```python
# When target exists
standard_binary_search(nums, 7)
```

--------------------------------

### Example Usage of `heapq` based Heapsort

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/Colab Notebooks/chapter_8_heap_priority_queue.ipynb

Demonstrates how to call the `heapsort` function implemented using the `heapq` module with a sample list, showcasing its simplicity for sorting.

```python
lst = [21, 1, 45, 78, 3, 5]
heapsort(lst)
```

--------------------------------

### Example Usage of Counter-based Permutation Generation

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_combinatorial_search.ipynb

Illustrates how to call the `permuteDup` function with a sample list `[1, 2, 2, 3]` and print the total count and the generated unique permutations.

```python
nums = [1,2, 2, 3]
ans = permuteDup(nums, 4)
print(len(ans), ans)
```

--------------------------------

### BFS Test on Free Tree

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Easy-Book/source-code/chapter_search_strategies.ipynb

Tests the 'bfs' function on a free tree structure starting from node 0, demonstrating its path tracking and cycle avoidance capabilities.

```python
bfs(ft, 0)
```

--------------------------------

### Example Usage of Breadth-First Graph Search in Python

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Easy-Book/source-code/chapter_search_strategies.ipynb

This snippet demonstrates how to call the `bfgs_state` function with a directed cyclic graph `dcg` starting from node 0. It shows a typical invocation of the BFGS algorithm.

```python
bfgs_state(dcg, 0)
```

--------------------------------

### Get Shortest Path Recursively

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Easy-Book/source-code/chapter_search_strategies.ipynb

A recursive utility function to reconstruct a path from a 'parent' list ('pl'), given a start node 's' and a target node 't'. It appends nodes to the 'path' list in order.

```python
def get_path(s, t, pl, path):
  if s == t:   
    pass
  elif pl[t] is None:
    print('no path from ', s, ' to ', t)
  else:
    get_path(s, pl[t], pl, path)   
  path.append(t)
  return
```

--------------------------------

### Instantiate and Run Branch and Bound Algorithm in Python

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_combinatorial_search.ipynb

Demonstrates how to create an instance of the `BranchandBound` class using the predefined problem parameters and execute both the DFS and BFS based optimization methods to find the best solution.

```python
bnb = BranchandBound(c, v, w)
bnb.runDfs()
bnb.runBfs()
```

--------------------------------

### Example Usage: Binary Search with Upper Bound

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_decrease_and_conquer.ipynb

Demonstrates the `upper_bound_bs` function with existing and non-existing target values to show its behavior in finding the last suitable position.

```python
# Binary Search with upper bound
l1 = upper_bound_bs(nums, 4)
l2 = upper_bound_bs(nums, 5)
print(l1, l2)
```

--------------------------------

### Python: Example Usage of Two Sum Function

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/Advanced_Search_on_Linear_Data_Structures.ipynb

This snippet demonstrates how to call the `twoSum` function with a sample array `a` and a `target` value of 9. It shows a typical invocation of the previously defined function.

```python
a = [2, 5, 7, 11, 15]
target = 9
twoSum(a, target)
```

--------------------------------

### Demonstrate SudokuSolver Class Usage

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/Colab Notebooks/graph_search.ipynb

Provides an example of how to use the `SudokoSolver` class. It initializes a sample Sudoku board, creates an instance of the solver, and then calls both `backtrackSolver()` and `backtrackSolverSorted()` methods to solve the puzzle, demonstrating the class's functionality and potentially comparing the performance of the two solving strategies.

```python
board = [[5, 3, None, None, 7, None, None, None, None],
         [6, None, None, 1, 9, 5, None, None, None],
         [None, 9, 8, None, None, None, None, 6, None],
         [8, None, None, None, 6, None, None, None, 3],
         [4, None, None, 8, None, 3, None, None, 1],
         [7, None, None, None, 2, None, None, None, 6],
         [None, 6, None, None, None, None, 2, 8, None],
         [None, None, None, 4, 1, 9, None, None, 5],
         [None, None, None, None, 8, None, None, 7, 9]]
solver = SudokoSolver(board)
solver.backtrackSolver()
solver.backtrackSolverSorted()
```

--------------------------------

### Get Path from BFS Results (Iterative)

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/Colab Notebooks/graph_data_structure.ipynb

Example usage of the iterative `get_path` function to find the path from node 0 to node 5 using the BFS predecessor list.

```python
get_path(0, 5, pi)
```

--------------------------------

### Compare N-Queens Solver Performance

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_combinatorial_search.ipynb

This script demonstrates how to instantiate the `Solution` class and use both `solveNQueens` and `solveNQueens2` methods. It measures and prints the execution time for each approach for a given `n` (e.g., n=4), allowing for a basic performance comparison between the two implemented algorithms.

```python
import time
s = Solution()
n = 4
t0 = time.time()
ans = s.solveNQueens(n)
print(ans)
t1 = time.time()
print('time: ', t1-t0)
ans2 = s.solveNQueens2(n)
t2 = time.time()
print('time: ', t2-t1)
```

--------------------------------

### Initialize Singly Linked List Head with Dummy Node

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_python_datastrcutures.ipynb

Initializes the head of a singly linked list with a dummy `Node`, which simplifies operations by providing a consistent starting point.

```python
head = Node(None)
```

--------------------------------

### Initialize and Populate Nested Defaultdict in Python

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_python_comparison_sorting.ipynb

Provides an example of initializing a nested `defaultdict` where inner dictionaries are also `defaultdict`s of lists. It then populates this structure with random integer data and prints both the dictionary and its sorted top-level keys.

```python
from collections import defaultdict
import random
dic = defaultdict(lambda: defaultdict(list)) # a dictionary of a dictionary of list dic[a][b] = [3, 1, 2, 4]
for i in range(10):
  a = random.randint(1, 101)
  b = random.randint(1, 101)
  dic[a][b] = [random.randint(1, 101) for _ in range(10)]
print(dic) 
sorted_dic = sorted(dic)
print(sorted_dic)
```

--------------------------------

### Get Path from BFS Results (Recursive)

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/Colab Notebooks/graph_data_structure.ipynb

Example usage of the recursive `get_path` function to find the path from node 0 to node 5 using the BFS predecessor list, printing the resulting path.

```python
path = []
get_path(0, 5, pi, path)
print(path)
```

--------------------------------

### Demonstrate All Paths and Shortest Path Functions

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Easy-Book/source-code/chapter_advanced_graph_search.ipynb

Executes the `all_paths` and `get_shortest_path` functions using the predefined graph 'g'. It initializes the necessary lists and variables, then calls the functions to find and extract shortest paths, illustrating their combined usage.

```python
ans, path, cost = [], ['s'], 0
all_paths(g, 's', path, cost, ans  )
get_shortest_path(ans, g)
```

--------------------------------

### Python Execute Directed Cycle Detection on Cyclic Graph

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Easy-Book/source-code/chapter_advanced_graph_search.ipynb

Demonstrates the execution of the `cycleDetectDirected` function on the `dcg` (directed cyclic graph) example to confirm cycle detection.

```Python
cycleDetectDirected(dcg)
```

--------------------------------

### Example Usage: Standard Binary Search with Non-Existing Target

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_decrease_and_conquer.ipynb

Demonstrates calling the `standard_binary_search` function with a target value that does not exist in the `nums` list, expecting -1 as output.

```python
# When target does not exist
standard_binary_search(nums, 42)
```

--------------------------------

### Example Usage of C_n_k Function (Python)

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_combinatorial_search.ipynb

This snippet demonstrates how to use the `C_n_k` function to find all combinations of 2 items from the list `[1, 2, 3]`. It initializes the list, sorts it, and prints the resulting combinations.

```python
a = [1, 2, 3]
n = len(a)
ans = []
a.sort()
C_n_k(a, n, 2, 0, 0, [], ans)
print(ans, a)
```

--------------------------------

### Python Priority Queue: Setting up Entry Finder

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_python_datastrcutures.ipynb

Initializes a priority queue and an associated `entry_finder` dictionary to quickly locate and invalidate tasks. Each task in the heap is linked to its entry in the dictionary.

```python
# A heap associated with entry_finder
counter = itertools.count()
entry_finder
```

--------------------------------

### Implement Combination (C_n_k) using Backtracking in Python

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/Colab Notebooks/graph_search.ipynb

This snippet provides the C_n_k function for generating all combinations of k items chosen from n items. It employs a recursive backtracking strategy, using a 'start' index to ensure unique combinations and avoid duplicates. The example code shows how to invoke the function and print the resulting combinations.

```python
def C_n_k(a, n, k, start, depth, curr, ans):
  '''
  Implement combination of k items out  of n items
  start: the start of candinate
  depth: start from 0, and represent the depth of the search
  curr: the current partial solution
  ans: collect all the valide solutions
  '''
  if depth == k: #end condition
    ans.append(curr[::]) 
    return
  
  for i in range(start, n):    
    # generate the next solution from curr
    curr.append(a[i])
    # move to the next solution
    C_n_k(a, n, k, i+1, depth+1, curr, ans)

    #backtrack to previous partial state
    curr.pop()
  return
```

```python
a = [1, 2, 3]
n = len(a)
ans = [[None]]
ans = []
C_n_k(a, n, 2, 0, 0, [], ans)
print(ans)
```

--------------------------------

### Illustrate Uniform-Cost Search (UCS) Expansion

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Easy-Book/source-code/chapter_search_strategies.ipynb

Demonstrates the step-by-step expansion process of the Uniform-Cost Search (UCS) algorithm. It shows how the priority queue `q` evolves as nodes are expanded and new paths with their accumulated costs are added.

```text
q = [(0, S)]
Expand S, add A and B
q = [(4, A), (5, B)]
Expand A, add G
q = [(5, B), (11, G)]
Expand B, add G
q = [(8, G), (11, G)]
Expand G, goal found, terminate.
```

--------------------------------

### Find Start Node of Cycle in Linked List (Python)

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/Advanced_Search_on_Linear_Data_Structures.ipynb

Extends Floyd's Cycle Detection to find the starting node of a cycle in a linked list. Once a cycle is detected, one pointer is reset to the head, and both pointers move one step at a time until they meet, which is the cycle's start.

```python
def detectCycle(head):
    slow = fast = head

    def getStartNode(slow, fast, head):
      # Reset slow pointer      
      slow = head
      while fast and slow != fast:
          slow = slow.next
          fast = fast.next
      return slow

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        # A cycle is detected
        if slow == fast: 
            return getStartNode(slow, fast, head)
    
    return None

detectCycle(head_cycle).val, detectCycle(head1)
```

--------------------------------

### Example Usage: Standard Binary Search with Duplicates

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_decrease_and_conquer.ipynb

Demonstrates calling the `standard_binary_search` function on a list containing duplicates of the target value, showing how it finds one of the occurrences.

```python
# When there exists duplicates of the target
standard_binary_search(nums, 4)
```

--------------------------------

### Initialize Python Lists with Various Elements

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_python_datastrcutures.ipynb

Demonstrates different ways to initialize lists in Python, including empty lists, lists with single elements, and lists with multiple elements of various types.

```python
lst_lst = [[], [1], ['1'], [1, 2], ['1', '2']]
```

--------------------------------

### Python Directed Cyclic Graph Example

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Easy-Book/source-code/chapter_advanced_graph_search.ipynb

An example adjacency list representation of a directed graph `dcg` that contains a cycle, used for testing cycle detection algorithms.

```Python
dcg = [[1], [2], [0, 4], [], [3], [6], []]
```

--------------------------------

### Python Execute Kahn's Sort on DAG

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Easy-Book/source-code/chapter_advanced_graph_search.ipynb

Demonstrates the execution of Kahn's algorithm for topological sort on the `dag` (directed acyclic graph) example, expecting a valid topological ordering.

```Python
kahns_topo_sort(dag)
```

--------------------------------

### Initialize Python Tuples and Use namedtuple

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_python_datastrcutures.ipynb

Shows basic tuple creation and introduces `collections.namedtuple` for creating tuple subclasses with named fields, improving readability and access to elements.

```python
record1 = ('Bob', 12345, 89)
from collections import namedtuple
Record = namedtuple('Computer_Science', 'name id score')
record2 = Record('Bob', id=12345, score=89)
print(record1, record2)
```

--------------------------------

### Python Custom Class Comparison Example

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_python_comparison_sorting.ipynb

Example of comparing instances of the `Person` class, which has rich comparison operators defined using `total_ordering`, demonstrating how custom comparison logic works.

```text

```

--------------------------------

### Python Undirected Cyclic Graph Example

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Easy-Book/source-code/chapter_advanced_graph_search.ipynb

An example adjacency list representation of an undirected graph `ucg` that contains a cycle, used for testing undirected cycle detection algorithms.

```Python
ucg=[[1, 2], [0, 2], [0, 4], [], [2, 3], [6], [5]]
```

--------------------------------

### Python Heapq: Basic Heapify Usage

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_python_datastrcutures.ipynb

Demonstrates how to use Python's built-in `heapq.heapify` function to convert a regular list into a min-heap in-place.

```python
from heapq import heappush, heappop, heapify
h = [21, 1, 45, 78, 3, 5]
heapify(h)
h
```

--------------------------------

### Python: Test Quick Sort Algorithm

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_sorting_and_selection_algorithms.ipynb

This snippet demonstrates how to use the `quickSort` function to sort a list in-place. It applies the algorithm to a sample list and then prints the list to show the sorted result.

```python
quickSort(lst, 0, len(lst) - 1)
lst
```

--------------------------------

### Python Directed Acyclic Graph Example

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Easy-Book/source-code/chapter_advanced_graph_search.ipynb

An example adjacency list representation of a directed acyclic graph `dag`, used for testing cycle detection algorithms to ensure no cycles are reported.

```Python
dag = [[1, 2], [2], [4], [], [3], [6], []]
```

--------------------------------

### Python Sudoku Solver Execution and Performance Comparison

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_combinatorial_search.ipynb

This code demonstrates how to instantiate the 'Sudoku' solver with different boards and execute both the 'naive_solve' and 'solve' methods. It also includes a basic time measurement to compare the performance of the two algorithms.

```python
for board in [board_easy, board_hard]:
  solver = Sudoku(board)

  import time
  t0 = time.time()
  solver.init()
  solver.naive_solve()
  print(solver.board)
  print('total time using naive solver: ', time.time()-t0, 's')

  t0 = time.time()
  solver.init()
  solver.solve()
  print(solver.board)
  print('total time using smart solver: ', time.time()-t0, 's')
```

--------------------------------

### Python: Example Usage of SCC Function

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Easy-Book/source-code/chapter_advanced_graph_search.ipynb

This snippet demonstrates how to call the `scc` function with a graph `dg` to compute its strongly connected components. It serves as a simple example of the function's invocation.

```python
scc(dg)
```

--------------------------------

### Visualize Individual Shortest Path Trees

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Easy-Book/source-code/chapter_advanced_graph_search.ipynb

Uses `graphviz` (via `Digraph`) and `opencv` (`cv2_imshow`) to generate and display visualizations for each shortest path tree. For each source node, it renders the full graph with the corresponding shortest path tree highlighted in a distinct color, saving and displaying the image.

```python
from google.colab.patches import cv2_imshow
import cv2

for idx, s in enumerate(list(shortest_path_tree_dic.keys())):
  # stric so that one edge wont be repeat but keep the last time's edit
  dot = Digraph(comment='directed_graph', engine="neato", format='png', strict=True)
  # Generate grapg
  v_pos = {'s': '0,0!', 't': '1,1!', 'x': '3, 1!', 'y': '1,-1!', 'z': '3,-1!'}
  for u, p in v_pos.items():
    dot.node(u, _attributes={'pos': str(p), 'fillcolor': "#d62728"})
    for v, w in g[u]:
      dot.edge(u, v, _attributes={'xlabel': str(w)})
  
  # Color one tree
  colors = ['red', 'green', 'yellow', 'blue', 'purple']
  dot.node(s, _attributes={'pos': str(v_pos[s]), 'color': colors[idx]})
  for x, y in shortest_path_tree_dic[s]:
    dot.edge(x, y, _attributes={'color': colors[idx]}  )

  dot.render(f'test-output/shortest_path_trees_{idx}', view=True) 
  img = cv2.imread(f'test-output/shortest_path_trees_{idx}.png')
  cv2_imshow(img)
```

--------------------------------

### BFS with Multiple Starting Nodes (Python)

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Easy-Book/source-code/chapter_search_strategies.ipynb

Implements a Breadth-First Search (BFS) algorithm that can start from multiple initial nodes. It processes nodes level by level, marking them as visited to prevent re-processing. This is useful for scenarios where the search originates from a set of sources.

```Python
#Multiple Starts
def BFSLevel(starts):
    q = starts # a list of nodes
    #root.visited = 1
    while q:
        new_q = []
        for node in q:
            for neig in node.adjacent:
               if not neig.visited:
                   neig.visited = 1
                   new_q.append(neig)
        q = new_q
```

--------------------------------

### Remove Cycle from Linked List (Python)

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/Advanced_Search_on_Linear_Data_Structures.ipynb

Removes a cycle from a linked list. After detecting the cycle and finding its start, it identifies the node just before the cycle's start (using the fast pointer) and sets its `next` pointer to `None`, effectively breaking the cycle.

```python
def resetLastNode(slow, fast, head):
    slow = head
    while fast and slow.next != fast.next:
        slow = slow.next
        fast = fast.next
    fast.next = None

def removeCycle(head):
    slow = fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        # A cycle is detected
        if slow == fast: 
            resetLastNode(slow, fast, head)
            return  
    return 

removeCycle(head_cycle)
iterate(head_cycle)
```

--------------------------------

### Construct Binary Search Tree (Alternative Insert)

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_decrease_and_conquer.ipynb

Shows another method for constructing a binary search tree, starting with the first key and then inserting subsequent keys using the `insert2` function. The `%%time` magic command is used to measure execution time.

```python
root = BiNode(keys[0])
for k in keys[1:]:
  insert2(root, k)
```

--------------------------------

### BFS Helper for Connected Components

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/Colab Notebooks/graph_search_application.ipynb

Performs a Breadth-First Search (BFS) starting from a given node, marking visited nodes and collecting them into an order list. Used to find all nodes reachable from a starting point.

```python
def bfs(g, s, state):
  state[s] = True
  
  q, orders = [s], [s]
  while q:
    u = q.pop(0)
    
    for v in g[u]:
      if not state[v]:
        state[v] = True
        q.append(v)
        orders.append(v)
  return orders
```

--------------------------------

### Python DCG Example for Topological Sort

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Easy-Book/source-code/chapter_advanced_graph_search.ipynb

An example adjacency list representation of a Directed Cyclic Graph (DCG) `dcg`, used to show how topological sort algorithms handle graphs with cycles (i.e., they cannot produce a valid topological order).

```Python
dcg = [[1], [2], [3], [2, 4, 5], [], [6], []]
dcg
```

--------------------------------

### Python Undirected Acyclic Graph Example and Execution

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Easy-Book/source-code/chapter_advanced_graph_search.ipynb

An example adjacency list representation of an undirected acyclic graph `uag`, used for testing undirected cycle detection algorithms to ensure no cycles are reported. The snippet also includes its execution.

```Python
# delete edge (0, 2)
uag = [[1], [0, 2], [4], [], [2, 3], [6], [5]]
cycleDetectUndirected(uag)
```

--------------------------------

### Python Priority Queue: Dataclass Usage Example (Issue)

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_python_datastrcutures.ipynb

Attempts to use the `PrioritizedItem` dataclass directly with `heapify`. This example highlights a common issue where items with identical priorities might not maintain a stable sort order without an explicit tie-breaker.

```python
# it does not seem working
h = [PrioritizedItem(3, 'c'), PrioritizedItem(3, 'a'), PrioritizedItem(10, 'b'), PrioritizedItem(5,'c'), PrioritizedItem(3, 'b')]
heapify(h)
print(h)
```

--------------------------------

### Python: Example Usage of Kruskal's Algorithm

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Easy-Book/source-code/chapter_advanced_graph_search.ipynb

This snippet defines an example graph `a` represented as an adjacency list with edge weights, and then demonstrates how to call the `kruskal` function with this graph to find its Minimum Spanning Tree. It shows the expected input format for the `kruskal` function.

```python
a= {1:[(2, 2), (3, 12)], 2:[(1, 2), (3, 4), (5, 5)], 3:[(1, 12), (2, 4), (4, 6), (5, 3)], 4:[(3, 6),  (5, 7)], 5:[(2, 5), (3, 3), (4, 7)]}
kruskal(a)
```

--------------------------------

### Python Sudoku Solver Usage Example

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_combinatorial_search.ipynb

This snippet demonstrates how to instantiate the `SudokoSolver` class with a sample Sudoku board and then invoke its two primary solving methods: `backtrackSolver()` which uses an arbitrary order for empty cells, and `backtrackSolverSorted()` which prioritizes empty cells with the fewest possible values. The output will include the time taken for each solving approach.

```python
board = [[5, 3, None, None, 7, None, None, None, None],
         [6, None, None, 1, 9, 5, None, None, None],
         [None, 9, 8, None, None, None, None, 6, None],
         [8, None, None, None, 6, None, None, None, 3], 
         [4, None, None, 8, None, 3, None, None, 1], 
         [7, None, None, None, 2, None, None, None, 6], 
         [None, 6, None, None, None, None, 2, 8, None], 
         [None, None, None, 4, 1, 9, None, None, 5],
         [None, None, None, None, 8, None, None, 7, 9]]
solver = SudokoSolver(board)
solver.backtrackSolver()
solver.backtrackSolverSorted()
```

--------------------------------

### BibTeX Citation for Hands-on Algorithmic Problem Solving

Source: https://github.com/liyin2015/python-coding-interview/blob/master/README.md

A BibTeX entry for citing the 'Hands-on Algorithmic Problem Solving' content, useful for academic or project references.

```BibTeX
@misc{handsondsa,
    author       = {Li Yin},
    title        = {Hands-on Algorithmic Problem Solving},
    howpublished = {\url{https://github.com/liyin2015/python-coding-interview/}},
    year         = {2021}
}
```

--------------------------------

### Python max() with Single Iterable

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_python_comparison_sorting.ipynb

Example of using the `max()` function with a single list iterable to find the largest element.

```python
# One iterable
lst1 = [4, 8, 9, 20, 3]
max([4, 8, 9, 20, 3])
```

--------------------------------

### Using Python's `bisect` Module for Bounds (Part 1)

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_decrease_and_conquer.ipynb

Illustrates the use of `bisect_left`, `bisect_right`, and `bisect` functions from Python's built-in `bisect` module to find insertion points for various target values in a sorted list.

```python
#@title Use Python Module bisect
from bisect import bisect_left,bisect_right, bisect
l1 = bisect_left(nums, 4)
r1 = bisect_right(nums, 5)
l2 = bisect_right(nums, 4)
r2 = bisect_right(nums, 5)
p3 = bisect(nums, 5)
print(l1, r1, l2, r2)
```

--------------------------------

### Combinatorial Calculation Example

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_combinatorial_search.ipynb

This snippet performs a simple combinatorial calculation, which might be a preliminary thought or unrelated calculation, demonstrating basic arithmetic and printing in Python.

```python
n=(64*63*62*61*60*59*58*57)/(8*7*6*5*4*3*2*1)
print(n)
```

--------------------------------

### Execute Combined Iterative Traversal

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_tree_data_structure_and_traversal.ipynb

This snippet calls the `iterative_traversal` function to get both preorder and inorder lists from the tree, then displays both results as a tuple.

```python
preorders, inorders = iterative_traversal(root)
preorders, inorders
```

--------------------------------

### Execute DFS Helper for Longest Path on UCG

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Easy-Book/source-code/chapter_search_strategies.ipynb

Executes the 'dfs_helper' function on an undirected cyclic graph (ucg) starting from node 0, collecting paths and traversal orders.

```python
paths, orders = [], []
dfs_helper(ucg, 0, [0])
paths, orders
```

--------------------------------

### Test Successor and Predecessor in BST

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_decrease_and_conquer.ipynb

Demonstrates and tests various functions for finding the successor and predecessor of a node in a binary search tree, including cases with and without parent pointers.

```python
s1 = successor(root, 14)
s2 = successor(root, 3)
s3 = successor(root, 4)
s4 = successor(root, 7)
if s1:
  print(s1)
print(s2.val, s3.val, s4.val)
root.p = None
node = findNodeAddParent(root, 4)
suc = successor2(node)
print(suc.val)
print(predecessorInorder(root, suc).val, successorInorder(root, suc).val)
```

--------------------------------

### Using Python's `bisect` Module for Bounds (Part 2)

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_decrease_and_conquer.ipynb

Further demonstrates the `bisect_left`, `bisect_right`, and `bisect` functions from Python's `bisect` module, specifically focusing on a target value with duplicates.

```python
p1 = bisect_left(nums, 4)
p2 = bisect_right(nums, 4)
p3 = bisect(nums, 4)
print(p1, p2, p3)
```

--------------------------------

### Python max() with Empty Iterable and Default Value

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_python_comparison_sorting.ipynb

Example of using the `default` argument in `max()` to provide a fallback value when the input iterable is empty, preventing a `ValueError`.

```python
max([], default=0)
```

--------------------------------

### DFS Test on Free Tree

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Easy-Book/source-code/chapter_search_strategies.ipynb

Initial test of a generic DFS function on a free tree structure, demonstrating basic traversal and path/order collection.

```python
paths, orders = [], []
dfs(ft, 0, [0])
paths, orders
```

--------------------------------

### Python Heapq: Max Heap using Negation Trick

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_python_datastrcutures.ipynb

Demonstrates the common technique to simulate a max-heap using a min-heap by negating all values before pushing them and negating them back when popping.

```python
from heapq import _heapify_max
h = [21, 1, 45, 78, 3, 5]
h = [-n for n in h]
heapify(h)
a = -heappop(h)
a
```

--------------------------------

### Execute Recursive Graph Search on Free Tree

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Easy-Book/source-code/chapter_search_strategies.ipynb

Executes the 'recursive' graph search function on a free tree (ucg) starting from node 0, collecting all paths and visited nodes.

```python
recursive(ucg, 0, [0])
```

--------------------------------

### Python: Initializing Array and Target Sum for Subarray Problem

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/Advanced_Search_on_Linear_Data_Structures.ipynb

This snippet initializes a sample array `a` and a target sum `S` for the subsequent subarray sum problem. These variables serve as input for the `numSubarraysWithSum` function.

```python
a = [1, 0, 1, 0, 1]
S = 2
```

--------------------------------

### Execute BFS on an Adjacency List

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/Colab Notebooks/graph_data_structure.ipynb

Demonstrates how to call the `bfs` function with an adjacency list (`al`) and a starting node (0) to perform a Breadth-First Search.

```python
orders, pi, dist = bfs(al, 0)
```

--------------------------------

### Python Example Usage for p_n_m Permutation Function

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_combinatorial_search.ipynb

This snippet demonstrates how to call the `p_n_m` function to generate all permutations of a list `a`. It initializes the necessary parameters like `used` array and an empty `ans` list to store the results, then prints the final list of permutations.

```python
a = [1, 2, 3]
n = len(a)
ans = [[None]]
used = [False] * len(a)
ans = []
p_n_m(a, n, n, 0, used, [], ans)
print(ans)
```

--------------------------------

### Execute DFS Helper for Edge Tracking on UCG

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Easy-Book/source-code/chapter_search_strategies.ipynb

Executes the 'dfs_helper' function for edge tracking on an undirected cyclic graph (ucg), initializing 'tracker' and 'edges' data structures. It prints the collected paths, orders, edges, and tracker state.

```python
paths, orders = [], []
tracker = defaultdict(int) # node: maximum count
edges = defaultdict(list) # node: node
dfs_helper(ucg, 0, [0])
paths, orders, edges, tracker, len(orders)
```

--------------------------------

### Example Usage: Binary Search in Rotated Array

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_decrease_and_conquer.ipynb

Demonstrates calling the `RotatedBinarySearch` function with a sample rotated array and a target value to find its index.

```python
nums = [7,0,1,2,3,4,5,6]
RotatedBinarySearch(nums, 3)
```

--------------------------------

### Test Segment Tree Construction and Node Retrieval

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_decrease_and_conquer.ipynb

Demonstrates how to build a segment tree from a sample array `nums` using `_buildSegmentTree` and then verifies its structure by printing all nodes using `getNodes`.

```python
nums = [2, 9, 4, 5, 8, 7]
root = _buildSegmentTree(nums, 0, len(nums) - 1)
print(getNodes(root))
```

--------------------------------

### Python: Test Quick Select Algorithm

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_sorting_and_selection_algorithms.ipynb

This snippet demonstrates the usage of the `quickSelect` function. It finds the element at a specific index (k-th smallest) in a sample list, showcasing how the algorithm can efficiently locate an element without fully sorting the entire list.

```python
lst = [9, 10, 2, 8, 9, 3, 7]
quickSelect(lst, 0, len(lst) - 1, 2)
```

--------------------------------

### Re-initialize List with Duplicates for Binary Search Examples

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_decrease_and_conquer.ipynb

Re-initializes the `nums` list with duplicate values to test binary search behavior with repeated elements.

```python
nums = [1, 3, 4, 4, 4, 4, 6, 7, 8]
```

--------------------------------

### Python Backtracking Template with DFS

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/chapter_combinatorial_search.ipynb

This snippet provides a general template for implementing backtracking algorithms using a Depth-First Search (DFS) approach. It outlines the structure for state management, candidate generation, and the recursive `dfs` function with state setting and resetting for backtracking.

```python
def backtrack():
  # initialization
  A #a working data structure, either a list of candidates or a graph or a matrix representing a board
  state_tracker = []*n
  assist_state_tracker
  # main backtracking
  def dfs(d, n):
    '''d: depth representing level in the tree'''
    if d == n:
      return
    candidates = generate_candidates(state_tracker, assist_state_tracker)
    for c in candidates: 
      set_state(state_tracker, assist_state_tracker, c)
      dfs(d+1, n)
      reset_state(state_tracler, assist_state_tracker, c)
      
  dfs(0, n)
```

--------------------------------

### Example Usage: Print Binary Tree Level Order

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/Colab Notebooks/tree_data_structure.ipynb

Demonstrates how to call the 'LevelOrder' function with a previously constructed binary tree root to print its nodes level by level.

```python
LevelOrder(root)
```

--------------------------------

### Python: Example Usage of Refined Subarrays With Sum Function

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Colab_Codes/Advanced_Search_on_Linear_Data_Structures.ipynb

This snippet demonstrates calling the refined `numSubarraysWithSum` function with the previously defined `a` and `S` values. It shows how to execute the improved three-pointer implementation.

```python
numSubarraysWithSum(a, S)
```

--------------------------------

### Define Graph Examples for Search Algorithms in Python

Source: https://github.com/liyin2015/python-coding-interview/blob/master/Easy-Book/source-code/chapter_search_strategies.ipynb

Provides various adjacency list representations of graphs for testing search algorithms. Includes a free tree, a directed cyclic graph, and an undirected cyclic graph, demonstrating different graph structures.

```python
# Prepare Graph Example
# Adjacency List with cycle
ft = [[1], [2], [4], [], [3, 5], []]
```

```python
# directed cyclc graph
dcg = [[1], [2],[0, 4], [1], [3, 5], [] ]
```

```python
# Prepare Graph Example
# Adjacency List with cycle
ucg = [[1, 2], [0, 2, 3], [0, 1,  4], [1, 4], [2, 3, 5], [4]]
```