Skip to content

Instantly share code, notes, and snippets.

View DagnyTagg2013's full-sized avatar

TechiMomi DagnyTagg2013

View GitHub Profile
"""
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
# 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)
# 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
DagnyTagg2013 / Binary Tree - DelNode!
Created November 28, 2017 20:41
BinTree - 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
@DagnyTagg2013
DagnyTagg2013 / Maze-AllValidPaths
Created November 18, 2017 21:13
Maze - All Valid Paths
# 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
DagnyTagg2013 / MRU Cache
Created November 13, 2017 22:31
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)
@DagnyTagg2013
DagnyTagg2013 / Nth Node back from END of List
Created November 8, 2017 21:44
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
@DagnyTagg2013
DagnyTagg2013 / QueueFromStacksAndBack
Created November 8, 2017 12:36
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 November 6, 2017 17:29
BFS from HackerRank
# 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
@DagnyTagg2013
DagnyTagg2013 / detectValidExpressionBracketsMatch
Created November 6, 2017 06:48
detectValidExpressionBracketsMatch
"""
MATCH BRACKETS
"""
"""
BAM: dynamic STACK - append opens, then match-pop on closes
DICT to match CLOSE to OPEN (as BACK-MATCH),