Python Coding Interview Preparation

The book is organized into four main pillars designed to take a learner from fundamentals to advanced interview patterns:

1. Preparation: Covers the global picture of algorithmic problem solving, abstract data structures, math (recurrence relations), and hands-on Python practice.
2. Principles: Focuses on design and principles (e.g., Complexity Analysis, Search Strategies, Reduce and Conquer) to provide guidance rather than just memorizing algorithms.
3. Classical Algorithms: Applies core principles to a database of classical problems (e.g., Sorting, Selection, Dynamic Programming, Greedy Algorithms).
4. Problem Patterns: Categorizes problems by pattern (e.g., Array, Linked List, Tree, Graph) to help tackle interview questions topic by topic.

The book is written in LaTeX. Non-code content is located in the Easy-Book folder.

To contribute:

1. Review the high-level structure of the book.
2. Read the How to contribute? guide for detailed instructions.
3. Submit pull requests with your improvements.

Significant contributors will be listed as authors in the project.

You can access the complete book as a single PDF or read specific chapters individually. The content covers Data Structures and Algorithms (DSA) using Python, focusing on LeetCode-style problem patterns and design principles.

• Full Book: main.pdf
• Chapter-based reading: Use the Table of Contents to navigate to specific topics like Python Data Structures, Search Strategies, or Problem Patterns.

Contributions to this project involve editing LaTeX source files located in the Easy-Book folder. You can use one of the following two methods to set up your environment:

1. Local Environment: Set up a local Visual Studio Code environment configured for LaTeX. A guide for this can be found at: https://dev.to/ucscmozilla/how-to-create-and-compile-latex-documents-on-visual-studio-code-3jbk
2. Cloud Environment: Use GitHub Codespaces to edit and compile directly in your browser.

Many chapters include corresponding Python source code, often provided as Jupyter Notebooks (.ipynb) via Google Colab. This allows you to run and experiment with the implementations directly.

Examples of available source code include:

• Python Data Structures: Colab_Codes/chapter_python_datastrcutures.ipynb
• Search Strategies: Colab_Codes/chapter_search_strategies.ipynb and Colab_Codes/chapter_tree_data_structure_and_traversal.ipynb
• Combinatorial Search: Colab_Codes/chapter_combinatorial_search.ipynb
• Decrease and Conquer: Colab_Codes/chapter_decrease_and_conquer.ipynb
• Sorting and Selection: Colab_Codes/chapter_sorting_and_selection_algorithms.ipynb and Colab_Codes/chapter_python_comparison_sorting.ipynb
• Advanced Search on Linear Data Structures: Colab_Codes/Advanced_Search_on_Linear_Data_Structures.ipynb

To check if the $i$-th bit is set, create a bit mask by shifting 1 left by $i$ positions (1 << i) and perform a bitwise AND with the value.

def get_bit(val, i):
    mask = 1 << i
    if val & mask:
        return 1
    return 0

# Example: Check if bit 0 is set in 240 (11110000)
print(get_bit(240, 4)) 

A formal implementation of Depth-First Search using the three-color scheme to classify nodes:

• STATE.white (0): Unvisited.
• STATE.gray (1): Currently being visited (on the recursion stack).
• STATE.black (2): Fully explored (all neighbors visited).

class STATE:
    white = 0
    gray = 1
    black = 2

# Recursive implementation with three states
def dfs(g, s, colors, orders, complete_orders):
  colors[s] = STATE.gray
  orders.append(s)
  for v in g[s]:
    if colors[v] == STATE.white:
      dfs(g, v, colors, orders, complete_orders)
  # complete
  colors[s] = STATE.black
  complete_orders.append(s)
  return

A successor is the node with the smallest value greater than the target. A predecessor is the node with the largest value smaller than the target.

If the node has a right child, the successor is the minimum of the right subtree. If not, you must traverse up the tree (requires parent pointers) or use an inorder traversal approach.

# Successor using inorder traversal
def successorInorder(root, node):
  if not node:
    return None
  if node.right is not None:
    return minimum(node.right)
  # Inorder traversal
  succ = None
  while root:
    if node.val > root.val:
      root = root.right
    elif node.val < root.val:
      succ = root
      root = root.left
    else:
      break
  return succ

To allow custom objects to be compared using standard operators (like >, <, ==), implement the rich comparison methods (__eq__, __lt__, etc.). Using the @functools.total_ordering decorator allows you to only define __eq__ and one other comparison method (like __lt__), and Python will automatically generate the rest.

from functools import total_ordering

@total_ordering
class Person(object):
    def __init__(self, firstname, lastname):
        self.first = firstname
        self.last = lastname

    def __eq__(self, other):
        return ((self.last, self.first) == (other.last, other.first))

    def __lt__(self, other):
        return ((self.last, self.first) < (other.last, other.first))

    def __repr__(self):
        return "%s %s" % (self.first, self.last)

p1 = Person('Li', 'Yin')
p2 = Person('Bella', 'Smith')
print(p1 > p2)

A Segment Tree is used for efficient range queries and updates.

• Build: Construct the tree by recursively dividing the range [s, e] into halves.
• Range Query: Retrieve the sum (or other aggregate) of elements in a given range [i, j].
• Update: Update a single element at index i and propagate the change up the tree.

class TreeNode:
  def __init__(self, val, s, e):
    self.val = val
    self.s = s
    self.e = e
    self.left = None
    self.right = None

def _rangeQuery(root, i, j, s, e): 
  if s == i and j == e:
    return root.val if root else 0 
  m = (s + e)//2
  if j <= m:
    return _rangeQuery(root.left, i, j, s, m)
  elif i > m:
    return _rangeQuery(root.right, i, j, m+1, e)
  else:
    return _rangeQuery(root.left, i, m, s, m) + _rangeQuery(root.right, m+1, j, m+1, e)

There are three primary ways to represent a graph in Python:

1. Adjacency Matrix: A 2-D array where am[i][j] = 1 indicates an edge between node i and j.
2. Adjacency List: A list of lists where al[i] contains the neighbors of node i.
3. Edge List: A list of tuples/lists where each element is a pair [u, v] representing an edge.

You can also use collections.defaultdict to convert an edge list into an adjacency list or a dictionary-based adjacency structure.