Skip to content

Instantly share code, notes, and snippets.

View DagnyTagg2013's full-sized avatar

TechiMomi DagnyTagg2013

View GitHub Profile
@DagnyTagg2013
DagnyTagg2013 / buildNTreeFromParentChildPairs
Created November 6, 2017 06:30
Build N-Tree from List (Parent,Child)
# Build an N-Tree from 2D array of Parent-Child pairs
import logging
from collections import deque
"""
TREE:
3
/ | \
4 5 6
@DagnyTagg2013
DagnyTagg2013 / getPhoneNumWords
Created November 6, 2017 06:38
getPhoneNumWords
"""
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
@DagnyTagg2013
DagnyTagg2013 / wordPermutations
Created November 6, 2017 06:43
Word Permutations
"""
Given String "ABC", print all 3-letter permutations of this
"""
# SOLUTION: - FULL decision tree
# - each level is character place,
# each branch a choice of one char
# - REMAINING unchosen characters
@DagnyTagg2013
DagnyTagg2013 / buildFriendshipsAdjacencyList
Created November 6, 2017 06:45
build Friendships Adjacency List
#
# You have data for social network on who is friends with whom.
# You need to write a function that returns this data in the form of an adjacency list representation, i.e. a mapping of each employee ID to a list of his/her friends on the site
# #
# You have two input data sets to work with. The first data set is the employees at your company, and the second is all the pairs of employees who are virtually friends so far. It does not matter which employee's ID is in which column, the friendships are bidirectional.
#
# employees_input = [
# "1,Richard,Engineering",
# "2,Erlich,HR",
# "3,Monica,Business",
@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),
@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 / 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 / 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 / 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 / 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