Skip to content

Instantly share code, notes, and snippets.

TechiMomi DagnyTagg2013

Block or report user

Report or block DagnyTagg2013

Hide content and notifications from this user.

Learn more about blocking users

Contact Support about this user’s behavior.

Learn more about reporting abuse

Report abuse
View GitHub Profile
@DagnyTagg2013
DagnyTagg2013 / buildNTreeFromParentChildPairs
Created Nov 6, 2017
Build N-Tree from List (Parent,Child)
View buildNTreeFromParentChildPairs
# Build an N-Tree from 2D array of Parent-Child pairs
import logging
from collections import deque
"""
TREE:
3
/ | \
4 5 6
View BFS - Get Phone Num Words
"""
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
View gist:1fbcaf59cbcc6ea19730200e527c5834
# 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)
View gist:cd4411932aa7f9e940974458b4a1a336
# 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)
View Binary Tree - DelNode!
"""
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
View Maze-AllValidPaths
# 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
View MRU Cache
"""
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)
View Nth Node back from END of List
# 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
View QueueFromStacksAndBack
"""
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
DagnyTagg2013 / bfsGraph
Created Nov 6, 2017
BFS from HackerRank
View bfsGraph
# 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
You can’t perform that action at this time.