DagnyTagg2013

# Build an N-Tree from 2D array of Parent-Child pairs

import logging
from collections import deque

"""
   TREE:
            3
          / | \
        4   5  6

DagnyTagg2013

"""

PROBLEM:

  4-digit number:  2284
  - assume have dictionary isWord(String word)
  - assume have phonenum pad digit to set of letters
  - print all possible words of ANY length up to 4-digits 
  
  eg 2->A,B,C   

DagnyTagg2013

# calculate 1D stats on data

data = [10, 2, 38, 23, 21, 5, 38, 23]

# sum
dataSum = sum (data)
print ('sum is:  {}'.format(dataSum))

# COUNT 
count = len (data)

DagnyTagg2013

# 2D Matrix Ops
import sys
from functools import partial

# SLICING
"""
=> operates on SHALLOW REFERENCE PTR to COMPLEX types (like list, array); 
                    OR actual VALUES of PRIMITIVE types (like char, int)
- https://www.python-course.eu/deep_copy.php
a[start:end] # items start through end-1 (ie NOT inclusive of END)

DagnyTagg2013

"""
DELETE node from Binary Tree

CORE CASES:
*** CAREFUL/INTERESTING
-- need to distinguish applicable SIDE(left or right child); INTO TARGET from  
PARENT, as well as OUT of TARGET
- target is root => reset root to None
- target has no child; and target is LEFT or RIGHT child of parent 
            => reset parent's child (specific side) to None

DagnyTagg2013

# PROBLEM:  Count and Construct All Distinct Valid Paths Through a Maze

# TRICK0:  
# - mutable heap-allocated structure to accumulate results to
# - cross-recursion-level visibility
# - use TUPLE to group MUTABLE ELEMENTs for state accumulation
# - globalValidPathCounter as first item of mutable LIST
# - used as INDEX into globalValidPaths Dict

DagnyTagg2013

"""

PROBLEM:  Implement MRU Cache 
- i.e. cache the MOST-MOST-RECENTLY-USED-OR-ACCESSED, and drop LEAST-RECENTLY-USED

- FIXED-size cache
initialized with a size, never to exceed that size
- put(key, val), O(1)
- get(key) -> val (or None), O(1)

DagnyTagg2013

# Given:  1=>2=>3=>4=>5
# Write function that takes head of list, n=2, and returns node 4 where n is distance from end

# TRICK:  Need to traverse TWICE always in FORWARD direction
#         1) count index from 0 to LENGTH to find the END so we can calculate 
#            complement FORWARD distance!
#         2) traverse counting from 0 to (LENGTH - n) to return reference to node!

# CAREFUL:  => Need to handle out-of-bounds on BOTH LOWER, and HIGHER end List
#           and since this deals with (LENGTH - n), this translates to

DagnyTagg2013

"""
PROBLEM - Stack from two Queues
"""

"""

STACK - LIFO, I/O from the SAME, ONE side
      - tracks TOP
      - push/pop on TOP
QUEUE - FIFO, Input at END, Output from FRONT; from DIFFERENT, TWO sides

DagnyTagg2013

# ATTN: import Q for BFS traversal 
# https://stackoverflow.com/questions/717148/queue-queue-vs-collections-deque
from collections import deque
# ATTN: import simplest DICT for Graph Adjacency list 
# https://stackoverflow.com/questions/5900578/how-does-collections-defaultdict-work
from collections import defaultdict
# ATTN:  import simplest COUNTER dictionary for Distance accum for EQUAL-weighted OCCURRENCE counts but LESS GENERAL-FLEXIBLE than adding VARIABLE edge weight using DefaultDict!
# https://pymotw.com/2/collections/counter.html
from collections import Counter
from sys import maxsize