james4388

from typing import *
from abc import ABCMeta, abstractmethod
from collections import deque


class PuzzleSolver(metaclass=ABCMeta):
    """Abstract class for solve puzzle that have initial state and end state
    Simple breath first search
    from any state -> generate next reachable state and eliminated duplicate state
    until reach goal or max depth reached

james4388

"""
  Inital we have N empty cup with capacity(c1, c2, c3... cn)
  Posible move:
    empty one cup
    fill one cup
    pour from one cup to another
  We have unlimited water source, find a way to fill a target amount
"""

from collections import deque

james4388

"""
  Merged to sorted array O(M + N) then find median O(1)
  Space: O(M + N) for temporary array
"""
def merge(first: List[int], second: List[int]) -> List[int]:
    M = len(first)
    N = len(second)
    i = j = 0
    result = []
    while i < M and j < N:

james4388

from collections import deque, defaultdict


def tarjan_recursive(graph):
    unvisited = set(graph.keys())
    low_link = {}
    visited_ids = {}  # Node id, also keep track of visited node
    stack_set = set()
    stack = []
    groups = []

james4388

/* Using array to store and search for key. Time complexity O(n) */
class DOMStoreArray {
  constructor () {
    this.data = [];
  }
  
  find (node) {
    for (let item of this.data) {
      if (item[0] === node) {
        return item;

james4388

/*
    apply all tag from tags to the string s
    const tags = [
        [0, 4, 'i'],    // start at index, end at index, style
        [6, 9, 'b'],
        [7, 10, 'u']
    ]
    const s = 'Hello World!'
    return html string: <i>Hell</i>o <b>W<u>orl</u></b><u>d</u>!
    At one index there will be only one open or close;

james4388

from collections import deque

'''
Graph problems
A
    C
        E
            F
    D
        G

james4388

class EventEmitter {
  constructor (isAsync = false) {
    this.events = new Map();
    this.isAsync = isAsync;  // Allow to notify listener async
  }
  
  /*
  * Subcribe a callback to an event. Callback will not be duplicate.
  * return unsibcribe function
  * Usage: const unsub = ee.subcribe(eventName, callback);

james4388

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        
def length(head):
    """Get linked list length"""
    count = 0
    node = head
    while node:

james4388

def range_sum(tree, left_child, right_child):
  return tree[left_child] + tree[right_child]

def build_segment_tree(arr, tree=None,
                       merge_fn=range_sum,
                       node_index=0, lo=0, hi=None, initial=None):
    """
        Build a segment tree based on arr of leaf node
        tree will have the size of 4 * len(arr)
        node_index is tree index