<jupyter_start><jupyter_text>singly linked list<jupyter_code>"""The LinkedList code from before is provided below.
Add three functions to the LinkedList.
"get_position" returns the element at a certain position.
The "insert" function will add an element to a particular
spot in the list.
"delete" will delete the first element with that
particular value.
Then, use "Test Run" and "Submit" to run the test cases
at the bottom."""

class Element(object):
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList(object):
    def __init__(self, head=None):
        self.head = head

    def append(self, new_element):
        current = self.head
        if self.head:
            while current.next:
                current = current.next
            current.next = new_element
        else:
            self.head = new_element

    def get_position(self, position):
        counter = 1
        current = self.head
        if position < 1:
            return None
        while current and counter <= position:
            if counter == position:
                return current
            current = current.next
            counter += 1
        return None

    def insert(self, new_element, position):
        counter = 1
        current = self.head
        if position > 1:
            while current and counter < position:
                if counter == position - 1:
                    new_element.next = current.next
                    current.next = new_element
                current = current.next
                counter += 1
        elif position == 1:
            new_element.next = self.head
            self.head = new_element

    def delete(self, value):
        current = self.head
        previous = None
        while current.value != value and current.next:
            previous = current
            current = current.next
        if current.value == value:
            if previous:
                previous.next = current.next
            else:
                self.head = current.next

# Test cases
# Set up some Elements
e1 = Element(1)
e2 = Element(2)
e3 = Element(3)
e4 = Element(4)

# Start setting up a LinkedList
ll = LinkedList(e1)
ll.append(e2)
ll.append(e3)

# Test get_position
# Should print 3
print (ll.head.next.next.value)
# Should also print 3
print (ll.get_position(3).value)

# Test insert
ll.insert(e4, 3)
# Should print 4 now
print (ll.get_position(3).value)

# Test delete
ll.delete(1)
# Should print 2 now
print (ll.get_position(1).value)
# Should print 4 now
print (ll.get_position(2).value)
# Should print 3 now
print (ll.get_position(3).value)

print (ll.head.value)<jupyter_output>3
3
4
2
4
3
2<jupyter_text>doubly linked list<jupyter_code># create this<jupyter_output><empty_output><jupyter_text>stack in python - can use list<jupyter_code>stack = [3, 4, 5]
stack.append(6)
stack.append(7)
print(stack)

stack.pop()
print(stack)<jupyter_output>[3, 4, 5, 6, 7]
[3, 4, 5, 6]<jupyter_text>custom stack<jupyter_code>"""Add a couple methods to our LinkedList class,
and use that to implement a Stack.
You have 4 functions below to fill in:
insert_first, delete_first, push, and pop.
Think about this while you're implementing:
why is it easier to add an "insert_first"
function than just use "append"?"""

class Element(object):
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList(object):
    def __init__(self, head=None):
        self.head = head

    def append(self, new_element):
        current = self.head
        if self.head:
            while current.next:
                current = current.next
            current.next = new_element
        else:
            self.head = new_element

    def insert_first(self, new_element):
        new_element.next = self.head
        self.head = new_element

    def delete_first(self):
        node = self.head if self.head else None
        if self.head:
            self.head = self.head.next
        return node
        
class Stack(object):
    def __init__(self,top=None):
        self.ll = LinkedList(top)

    def push(self, new_element):
        self.ll.insert_first(new_element)

    def pop(self):
        return self.ll.delete_first()
    
# Test cases
# Set up some Elements
e1 = Element(1)
e2 = Element(2)
e3 = Element(3)
e4 = Element(4)

# Start setting up a Stack
stack = Stack(e1)

# Test stack functionality
stack.push(e2)
stack.push(e3)
print (stack.pop().value)
print (stack.pop().value)
print (stack.pop().value)
print (stack.pop())
stack.push(e4)
print (stack.pop().value)<jupyter_output>3
2
1
None
4<jupyter_text>custom queue<jupyter_code>"""Make a Queue class using a list!
Hint: You can use any Python list method
you'd like! Try to write each one in as 
few lines as possible.
Make sure you pass the test cases too!"""

class Queue(object):
    def __init__(self, head=None):
        self.storage = [head]

    def enqueue(self, new_element):
        self.storage.append(new_element)

    def peek(self):
        return self.storage[0]

    def dequeue(self):
        return self.storage.pop(0)
    
# Setup
q = Queue(1)
q.enqueue(2)
q.enqueue(3)

# Test peek
# Should be 1
print(q.peek())

# Test dequeue
# Should be 1
print(q.dequeue())

# Test enqueue
q.enqueue(4)
# Should be 2
print(q.dequeue())
# Should be 3
print(q.dequeue())
# Should be 4
print(q.dequeue())
q.enqueue(5)
# Should be 5
print(q.peek())<jupyter_output>1
1
2
3
4
5<jupyter_text>binary searchhttp://www.cs.armstrong.edu/liang/animation/web/BinarySearch.htmlhttps://www.cs.usfca.edu/~galles/visualization/Search.html<jupyter_code>"""You're going to write a binary search function.
You should use an iterative approach - meaning
using loops.
Your function should take two inputs:
a Python list to search through, and the value
you're searching for.
Assume the list only has distinct elements,
meaning there are no repeated values, and 
elements are in a strictly increasing order.
Return the index of value, or -1 if the value
doesn't exist in the list."""

def binary_search(inp, value):
    """Your code goes here."""
    low = 0
    high = len(inp) - 1
    while low <= high:
        mid = int((low + high) / 2)
        if inp[mid] == value:
            return int(mid)
        elif inp[mid] < value:
            low = mid + 1
        else:
            high = mid - 1
    return -1

test_list = [1,3,9,11,15,19,29]

test_val1 = 25
print (binary_search(test_list, test_val1))

test_val2 = 15
print (binary_search(test_list, test_val2))<jupyter_output>-1
4<jupyter_text>sort with minimum swaps (similar to a non-comparison sorting algorithm)<jupyter_code>def minimumSwaps(arr):
    swaps = 0
    i = 0
    while i < len(arr) - 1:
        if arr[i] != i+1:
            temp = arr[i]
            loc = arr[i]-1
            temp2 = arr[loc]
            arr[i] = temp2
            arr[loc] = temp
            i -= 1
            swaps += 1
        i += 1

    return swaps
            

arr = list(map(int, '4 3 1 2'.rstrip().split()))
res = minimumSwaps(arr)
print(res)<jupyter_output>3<jupyter_text>recursion<jupyter_code>"""Implement a function recursively to get the desired
Fibonacci sequence value.
Your code should have the same input/output as the 
iterative code in the instructions."""
"""
fib_seq = []
fib_seq[0] = 0
fib_seq[1] = 1
fib_seq[2] = 1
fib_seq[3] = 2
fib_seq[4] = 3
fib_seq[5] = 5
fib_seq[6] = 8
fib_seq[7] = 13
fib_seq[8] = 21
fib_seq[9] = 34
"""

def get_fib(position):
    if position == 0 or position == 1:
        return position
    return get_fib(position - 1) + get_fib(position - 2)
    
# Test cases
print (get_fib(9))
print (get_fib(11))
print (get_fib(0))

# # fix this
# def get_fib2(position):
#     end_pos  = position
#     curr_pos = 0
#     if end_pos == 0:
#         return 0
#     value = 1
#     if end_pos == curr_pos:
#         return value
#     curr_pos += 1
#     value += value
#     return get_fib(curr_pos)

# # Test cases
# print (get_fib2(9))
# print (get_fib2(11))
# print (get_fib2(0))<jupyter_output>34
89
0<jupyter_text>merge sort - time complexity: O(nlogn), auxiliary space: O(n)top-down and bottom-up merge sort  sorting algorithms complexitieshttps://en.wikipedia.org/wiki/Sorting_algorithmComparison_of_algorithms  sorting referenceshttps://algs4.cs.princeton.edu/20sorting/https://www.toptal.com/developers/sorting-algorithmshttp://panthema.net/2013/sound-of-sorting/  sorting considerations Comparison based sorting –In comparison based sorting, elements of an array are compared with each other to find the sorted array. Non-comparison based sorting –In non-comparison based sorting, elements of array are not compared with each other to find the sorted array. No comparison sorting includes Counting sort which sorts using key value, Radix sort, which examines individual bits of keys, and Bucket Sort which examines bits of keys. These are also known as Liner sorting algorithms because they sort in O(n) time. They make certain assumption about data hence they don't need to go through comparison decision tree.  In-place/Outplace technique –A sorting technique is inplace if it does not use any extra memory to sort the array.Among the comparison based techniques discussed, only merge sort is outplace technique as it requires an extra array to merge the sorted subarrays.Among the non-comparison based techniques discussed, all are outplace techniques. Counting sort uses counting array and bucket sort uses hash table for sorting the array. Online/Offline technique –A sorting technique is considered Online if it can accept new data while the procedure is ongoing i.e. complete data is not required to start the sorting operation.Among the comparison based techniques discussed, only Insertion Sort qualifies for this because of the underlying algorithm it uses i.e. it processes the array (not just elements) from left to right and if new elements are added to the right, it doesn’t impact the ongoing operation. Stable/Unstable technique –A sorting technique is stable if it does not change the order of elements with the same value.Out of comparison based techniques, bubble sort, insertion sort and merge sort are stable techniques. Selection sort is unstable as it may change the order of elements with the same value. For example, consider the array 4, 4, 1, 3.In the first iteration, minimum element found is 1 and it is swapped with 4 at 0th position. Therefore, order of 4 with respect to 4 at 1st position will change. Similarly, quick sort and heap sort are also unstable.Out of non-comparison based techniques, Counting sort and Bucket sort are stable sorting techniques whereas radix sort stability depends on the underlying algorithm used for sorting. Analysis of sorting techniques :When the array is almost sorted, insertion sort can be preferred.When order of input is not known, merge sort is preferred as it has worst case time complexity of nlogn and it is stable as well.When the array is sorted, insertion and bubble sort gives complexity of n but quick sort gives complexity of n^2.  best for non-parallel sortingOnly a few items: Insertion SortItems are mostly sorted already: Insertion SortConcerned about worst-case scenarios: Heap SortInterested in a good average-case result: QuicksortItems are drawn from a dense universe: Bucket SortDesire to write as little code as possible: Insertion Sort  quick sort- take last element as pivot, compare to first element- if first element is greater, move it to the last element position; move last element position one forward; move the element that used to be in this second to last position to the beginning- repeat until compared the same pivot with all previous items- split at pivot, repeat this process for items below and above pivot- keep repeating until all sorted<jupyter_code>def partition(array, begin, end):
    pivot = begin
    for i in range(begin+1, end+1):
        if array[i] <= array[begin]:
            pivot += 1
            array[i], array[pivot] = array[pivot], array[i]
    array[pivot], array[begin] = array[begin], array[pivot]
    return pivot

def quicksort(array, begin=0, end=None):
    if end is None:
        end = len(array) - 1
    def _quicksort(array, begin, end):
        if begin >= end:
            return
        pivot = partition(array, begin, end)
        _quicksort(array, begin, pivot-1)
        _quicksort(array, pivot+1, end)
    return _quicksort(array, begin, end)

arr = [21, 4, 1, 1, 3, 9, 20, 25, 6, 21, 14]
quicksort(arr)
print(arr)
def quick_sort_not_inplace(array):
    less = []
    equal = []
    greater = []

    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            elif x == pivot:
                equal.append(x)
            else:  # x > pivot
                greater.append(x)
        # Don't forget to return something!
        return quick_sort(less) + equal + quick_sort(greater)  # Just use the + operator to join lists
    # Note that you want equal ^^^^^ not pivot
    else:  # You need to hande the part at the end of the recursion - when you only have one element in your array, just return the array.
        return array

test = [21, 4, 1, 1, 3, 9, 20, 25, 6, 21, 14]
res = quick_sort_not_inplace(test)
print(res)<jupyter_output>[1, 1, 3, 4, 6, 9, 14, 20, 21, 21, 25]<jupyter_text>maps/dictionaries - can retrieve key's value in REAL TIME<jupyter_code>locations = {'North America': {'USA': ['Mountain View']}}
locations['North America']['USA'].append('Atlanta')
locations['Asia'] = {'India': ['Bangalore']}
locations['Asia']['China'] = ['Shanghai']
locations['Africa'] = {'Egypt': ['Cairo']}

print (1)
usa_sorted = sorted(locations['North America']['USA'])
for city in usa_sorted:
    print (city)

print (2)
asia_cities = []
for countries, cities in locations['Asia'].items():
    city_country = cities[0] + " - " + countries 
    asia_cities.append(city_country)
asia_sorted = sorted(asia_cities)
for city in asia_sorted:
    print (city)<jupyter_output>1
Atlanta
Mountain View
2
Bangalore - India
Shanghai - China<jupyter_text>hashing load factorWhen we're talking about hash tables, we can define a "load factor":>Load Factor = Number of Entries / Number of BucketsThe purpose of a load factor is to give us a sense of how "full" a hash table is. For example, if we're trying to store 10 values in a hash table with 1000 buckets, the load factor would be 0.01, and the majority of buckets in the table will be empty. We end up wasting memory by having so many empty buckets, so we may want to rehash, or come up with a new hash function with less buckets. We can use our load factor as an indicator for when to rehash—as the load factor approaches 0, the more empty, or sparse, our hash table is. On the flip side, the closer our load factor is to 1 (meaning the number of values equals the number of buckets), the better it would be for us to rehash and add more buckets. Any table with a load value greater than 1 is guaranteed to have collisions.   hash table<jupyter_code>"""Write a HashTable class that stores strings
in a hash table, where keys are calculated
using the first two letters of the string."""

class HashTable(object):
    def __init__(self):
        self.table = [None]*10000

    def store(self, string):
        hv = self.calculate_hash_value(string)
        if hv != -1:
            if self.table[hv] != None:
                self.table[hv].append(string)
            else:
                self.table[hv] = [string]

    def lookup(self, string):
        hv = self.calculate_hash_value(string)
        if hv != -1:
            if self.table[hv] != None:
                if string in self.table[hv]:
                    return hv
        return -1
    
    def calculate_hash_value(self, string):
        '''
        You can assume that the string will have at least two letters, 
        and the first two characters are uppercase letters (ASCII values from 65 to 90). 
        You can use the Python function ord() to get the ASCII value of a letter, 
        and chr() to get the letter associated with an ASCII value. 
        '''
        value = ord(string[0])*100 + ord(string[1])
        return value
    
# Setup
hash_table = HashTable()

# Test calculate_hash_value
# Should be 8568
print (hash_table.calculate_hash_value('UDACITY'))

# Test lookup edge case
# Should be -1
print (hash_table.lookup('UDACITY'))

# Test store
hash_table.store('UDACITY')
# Should be 8568
print (hash_table.lookup('UDACITY'))

# Test store edge case
hash_table.store('UDACIOUS')
# Should be 8568
print (hash_table.lookup('UDACIOUS'))<jupyter_output>8568
-1
8568
8568<jupyter_text>trees Traversal- DFS - Depth First Search    - pre-order: start at top, go to left all the way to leaf while checking each node.  Check each family on the way back up, repeat for right side    - in-order: start from left-most leaf, check this, plus its immediate family, go one level up, repeat    - post-order: start at left-most leaf, check everything at that level, go to right-most leaf, check everything at that level, then check next level up- BFS - Breadth First Search efficiency of binary trees (leaves, or nodes with 1 or 2 children)- search: O(n)- delete (remove element then rearrange to fill element): O(n)- insert (every level you double the amount of elements you can add): O(logn) special case- if tree is UNBALANCED, means it's more skewed to one side, which means its more similar to a linked list, and will have more linear efficiency properties (worst case)  binary tree<jupyter_code>class Node():
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree():
    def __init__(self, root):
        self.root = Node(root)

    def search(self, find_val):
        return self.preorder_search(tree.root, find_val)

    def print_tree(self):
        return self.preorder_print(tree.root, "")[:-1]

    def preorder_search(self, start, find_val):
        if start:
            if start.value == find_val:
                return True
            else:
                return self.preorder_search(start.left, find_val) or self.preorder_search(start.right, find_val)
        return False

    def preorder_print(self, start, traversal):
        if start:
            traversal += (str(start.value) + "-")
            traversal = self.preorder_print(start.left, traversal)
            traversal = self.preorder_print(start.right, traversal)
        return traversal


# Set up tree
tree = BinaryTree(1)
tree.root.left = Node(2)
tree.root.right = Node(3)
tree.root.left.left = Node(4)
tree.root.left.right = Node(5)

# Test search
# Should be True
print (tree.search(4))
# Should be False
print (tree.search(6))

# Test print_tree
# Should be 1-2-4-5-3
print (tree.print_tree())<jupyter_output>True
False
1-2-4-5-3<jupyter_text>binary search trees (BST)- numbers are organized left to right so that you can tell which path to go down if your search value is less than or greater than the comparison value- search and insert efficiency are both O(logn)- delete (remove element then rearrange to fill element): O(n)<jupyter_code>class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BST(object):
    def __init__(self, root):
        self.root = Node(root)

    def insert(self, new_val):
        self.insert_helper(self.root, new_val)

    def insert_helper(self, current, new_val):
        if current.value < new_val:
            if current.right:
                self.insert_helper(current.right, new_val)
            else:
                current.right = Node(new_val)
        else:
            if current.left:
                self.insert_helper(current.left, new_val)
            else:
                current.left = Node(new_val)

    def search(self, find_val):
        return self.search_helper(self.root, find_val)

    def search_helper(self, current, find_val):
        if current:
            if current.value == find_val:
                return True
            elif current.value < find_val:
                return self.search_helper(current.right, find_val)
            else:
                return self.search_helper(current.left, find_val)
        return False
    
# Set up tree
tree = BST(4)

# Insert elements
tree.insert(2)
tree.insert(1)
tree.insert(3)
tree.insert(5)

# Check search
# Should be True
print (tree.search(4))
# Should be False
print (tree.search(6))<jupyter_output>True
False<jupyter_text>Heaps- max heaps: parent always greater than child- min heaps: parent always less than child- parents can have any number of children (not max of two like in binary) search- max heaps: finding max happens in constant time, O(1)- min heaps: finding min happens in constant time, O(1)- searching worst case still O(n), but since can quit search if greater than max or less than min, average is O(n/2) insertion (Heapify)- add to end then keep swapping child with parent until fits pattern- O(logn) worst case, roughly as many operations as the height deletion- similar to insertion, except take a random leaf and place it at place of deletion, then swap where necessary- O(logn) worst case, roughly as many operations as the height implementation- given sorted array, know how many heap/tree elements per level, just keep level as a counter and insert that many- trees take up more space than array  self balancing trees- balances itself out when inserting or deleting- Red/Black tree: assign Red or Black as property to each node.  Each leaf must end with a null, colored Black.  When inserting/deleting, ensure the same number of Black in each path    - also follows BST rules    - insert red nodes only, and only change color as needed     - if the parent and the parent's sibling is red, switch to black, and the grandparent switches to red    - if red, left parent has a red, right child, perform "left rotation".  "left rotation" is done by moving the child up one, and making the initial parent a left child.  Then will have a previous case so we can continue self balancing    - since at every step the tree won't be too unbalanced, the runtimes won't be too large  graphs- Trees are a subset of graphs, where any node/vertex is connected to any other via an edge- either nodes or edges can store data- if we want edges to be one directional, these are "Directed Graphs."  If going back and forth between the same two nodes, the two nodes can share two edges directed in opposite ways- non-directional graphs are called "Undirected Graphs"- cycle can happen if start at one node, and can end up at same node.  Could result in infinite loop- Directed Acyclic Graph (DAG) is common, it's a directed graph with no cycles- "Graph Theory" is the study- connectivity    - connected graph has all nodes connected to at least one edge    - disconnected graph has at least one disconnection    - "connectivity" is also the number of edges that can be removed before a graph becomes disconnected representation in code- can create an "edge list", list of nodes that are connected to eachother via an edge    - `[ [0, 1], [1, 2], [1, 3], [2, 3] ]`- "adjacency list": each index of the list represents that number node.  The items in that index location represent the nodes it's connected to    - `[ [1], [0, 2, 3], [1, 3], [1, 2] ]`- adjacency matrix    - probably fastest to tell how many nodes a particular node is connected to<jupyter_code># adjacency matrix example

# The Graph class contains a list of nodes and edges. 
# You can sometimes get by with just a list of edges, since edges contain references to the nodes they connect to, or vice versa. 
# However, our Graph class is built with both for the following reasons: 
    # If you're storing a disconnected graph, not every node will be tied to an edge, so you should store a list of nodes.
    # We could probably leave it there, but storing an edge list will make our lives much easier when we're trying to print out different types of graph representations. 
        # Unfortunately, having both makes insertion a bit complicated. We can assume that each value is unique, but we need to be careful about keeping both nodes and edges
        # updated when either is inserted. 

class Node(object):
    def __init__(self, value):
        self.value = value
        self.edges = []

class Edge(object):
    def __init__(self, value, node_from, node_to):
        self.value = value
        self.node_from = node_from
        self.node_to = node_to

class Graph(object):
    def __init__(self, nodes=[], edges=[]):
        self.nodes = nodes
        self.edges = edges

    def insert_node(self, new_node_val):
        new_node = Node(new_node_val)
        self.nodes.append(new_node)
        
    def insert_edge(self, new_edge_val, node_from_val, node_to_val):
        from_found = None
        to_found = None
        for node in self.nodes:
            if node_from_val == node.value:
                from_found = node
            if node_to_val == node.value:
                to_found = node
        if from_found == None:
            from_found = Node(node_from_val)
            self.nodes.append(from_found)
        if to_found == None:
            to_found = Node(node_to_val)
            self.nodes.append(to_found)
        new_edge = Edge(new_edge_val, from_found, to_found)
        from_found.edges.append(new_edge)
        to_found.edges.append(new_edge)
        self.edges.append(new_edge)

    def get_edge_list(self):
        edge_list = []
        for edge_object in self.edges:
            edge = (edge_object.value, edge_object.node_from.value, edge_object.node_to.value)
            edge_list.append(edge)
        return edge_list
    
    def get_adjacency_list(self):
        max_index = self.find_max_index()
        adjacency_list = [None] * (max_index + 1)
        for edge_object in self.edges:
            if adjacency_list[edge_object.node_from.value]:
                adjacency_list[edge_object.node_from.value].append((edge_object.node_to.value, edge_object.value))
            else:
                adjacency_list[edge_object.node_from.value] = [(edge_object.node_to.value, edge_object.value)]
        return adjacency_list
    
    def get_adjacency_matrix(self):
        max_index = self.find_max_index()
        adjacency_matrix = [[0 for i in range(max_index + 1)] for j in range(max_index + 1)]
        for edge_object in self.edges:
            adjacency_matrix[edge_object.node_from.value][edge_object.node_to.value] = edge_object.value
        return adjacency_matrix
    
    def find_max_index(self):
        max_index = -1
        if len(self.nodes):
            for node in self.nodes:
                if node.value > max_index:
                    max_index = node.value
        return max_index

graph = Graph()
graph.insert_edge(100, 1, 2)
graph.insert_edge(101, 1, 3)
graph.insert_edge(102, 1, 4)
graph.insert_edge(103, 3, 4)
# Should be [(100, 1, 2), (101, 1, 3), (102, 1, 4), (103, 3, 4)]
print (graph.get_edge_list())
# Should be [None, [(2, 100), (3, 101), (4, 102)], None, [(4, 103)], None]
print (graph.get_adjacency_list())
# Should be [[0, 0, 0, 0, 0], [0, 0, 100, 101, 102], [0, 0, 0, 0, 0], [0, 0, 0, 0, 103], [0, 0, 0, 0, 0]]
print (graph.get_adjacency_matrix())<jupyter_output>[(100, 1, 2), (101, 1, 3), (102, 1, 4), (103, 3, 4)]
[None, [(2, 100), (3, 101), (4, 102)], None, [(4, 103)], None]
[[0, 0, 0, 0, 0], [0, 0, 100, 101, 102], [0, 0, 0, 0, 0], [0, 0, 0, 0, 103], [0, 0, 0, 0, 0]]<jupyter_text>graph traversal- Depth First Search (DFS): go as deep into a node as possible before searching another    - start anywhere, add visited node to a stack, then go to a connected node, repeat    - if already seen, pop off stack    - O(|E| + |V|)    - can also do with recursion    - https://www.cs.usfca.edu/~galles/visualization/DFS.html- Breadth First Search (BFS): search all adjacent nodes first before searching other areas    - start anywhere, add visited node to a queue, then visit all adjacent nodes and add to a queue    - when run out of edges, dequeue, and use next node as a starting place    - O(|E| + |V|)    - https://www.cs.usfca.edu/~galles/visualization/BFS.html<jupyter_code>class Node(object):
    def __init__(self, value):
        self.value = value
        self.edges = []
        self.visited = False

class Edge(object):
    def __init__(self, value, node_from, node_to):
        self.value = value
        self.node_from = node_from
        self.node_to = node_to

# You only need to change code with docs strings that have TODO.
# Specifically: Graph.dfs_helper and Graph.bfs
# New methods have been added to associate node numbers with names
# Specifically: Graph.set_node_names
# and the methods ending in "_names" which will print names instead
# of node numbers

class Graph(object):
    def __init__(self, nodes=None, edges=None):
        self.nodes = nodes or []
        self.edges = edges or []
        self.node_names = []
        self._node_map = {}

    def set_node_names(self, names):
        """The Nth name in names should correspond to node number N.
        Node numbers are 0 based (starting at 0).
        """
        self.node_names = list(names)

    def insert_node(self, new_node_val):
        "Insert a new node with value new_node_val"
        new_node = Node(new_node_val)
        self.nodes.append(new_node)
        self._node_map[new_node_val] = new_node
        return new_node

    def insert_edge(self, new_edge_val, node_from_val, node_to_val):
        "Insert a new edge, creating new nodes if necessary"
        nodes = {node_from_val: None, node_to_val: None}
        for node in self.nodes:
            if node.value in nodes:
                nodes[node.value] = node
                if all(nodes.values()):
                    break
        for node_val in nodes:
            nodes[node_val] = nodes[node_val] or self.insert_node(node_val)
        node_from = nodes[node_from_val]
        node_to = nodes[node_to_val]
        new_edge = Edge(new_edge_val, node_from, node_to)
        node_from.edges.append(new_edge)
        node_to.edges.append(new_edge)
        self.edges.append(new_edge)

    def get_edge_list(self):
        """Return a list of triples that looks like this:
        (Edge Value, From Node, To Node)"""
        return [(e.value, e.node_from.value, e.node_to.value)
                for e in self.edges]

    def get_edge_list_names(self):
        """Return a list of triples that looks like this:
        (Edge Value, From Node Name, To Node Name)"""
        return [(edge.value,
                 self.node_names[edge.node_from.value],
                 self.node_names[edge.node_to.value])
                for edge in self.edges]

    def get_adjacency_list(self):
        """Return a list of lists.
        The indecies of the outer list represent "from" nodes.
        Each section in the list will store a list
        of tuples that looks like this:
        (To Node, Edge Value)"""
        max_index = self.find_max_index()
        adjacency_list = [[] for _ in range(max_index)]
        for edg in self.edges:
            from_value, to_value = edg.node_from.value, edg.node_to.value
            adjacency_list[from_value].append((to_value, edg.value))
        return [a or None for a in adjacency_list] # replace []'s with None

    def get_adjacency_list_names(self):
        """Each section in the list will store a list
        of tuples that looks like this:
        (To Node Name, Edge Value).
        Node names should come from the names set
        with set_node_names."""
        adjacency_list = self.get_adjacency_list()
        def convert_to_names(pair, graph=self):
            node_number, value = pair
            return (graph.node_names[node_number], value)
        def map_conversion(adjacency_list_for_node):
            if adjacency_list_for_node is None:
                return None
            return map(convert_to_names, adjacency_list_for_node)
        return [map_conversion(adjacency_list_for_node)
                for adjacency_list_for_node in adjacency_list]

    def get_adjacency_matrix(self):
        """Return a matrix, or 2D list.
        Row numbers represent from nodes,
        column numbers represent to nodes.
        Store the edge values in each spot,
        and a 0 if no edge exists."""
        max_index = self.find_max_index()
        adjacency_matrix = [[0] * (max_index) for _ in range(max_index)]
        for edg in self.edges:
            from_index, to_index = edg.node_from.value, edg.node_to.value
            adjacency_matrix[from_index][to_index] = edg.value
        return adjacency_matrix

    def find_max_index(self):
        """Return the highest found node number
        Or the length of the node names if set with set_node_names()."""
        if len(self.node_names) > 0:
            return len(self.node_names)
        max_index = -1
        if len(self.nodes):
            for node in self.nodes:
                if node.value > max_index:
                    max_index = node.value
        return max_index

    def find_node(self, node_number):
        "Return the node with value node_number or None"
        return self._node_map.get(node_number)
    
    def _clear_visited(self):
        for node in self.nodes:
            node.visited = False

    def dfs_helper(self, start_node):
        """The helper function for a recursive implementation
        of Depth First Search iterating through a node's edges. The
        output should be a list of numbers corresponding to the
        values of the traversed nodes.
        ARGUMENTS: start_node is the starting Node
        REQUIRES: self._clear_visited() to be called before
        MODIFIES: the value of the visited property of nodes in self.nodes 
        RETURN: a list of the traversed node values (integers).
        """
        ret_list = [start_node.value]
        start_node.visited = True
        edges_out = [e for e in start_node.edges
                     if e.node_to.value != start_node.value]
        for edge in edges_out:
            if not edge.node_to.visited:
                ret_list.extend(self.dfs_helper(edge.node_to))
        return ret_list

    def dfs(self, start_node_num):
        """Outputs a list of numbers corresponding to the traversed nodes
        in a Depth First Search.
        ARGUMENTS: start_node_num is the starting node number (integer)
        MODIFIES: the value of the visited property of nodes in self.nodes
        RETURN: a list of the node values (integers)."""
        self._clear_visited()
        start_node = self.find_node(start_node_num)
        return self.dfs_helper(start_node)

    def dfs_names(self, start_node_num):
        """Return the results of dfs with numbers converted to names."""
        return [self.node_names[num] for num in self.dfs(start_node_num)]

    def bfs(self, start_node_num):
        """An iterative implementation of Breadth First Search
        iterating through a node's edges. The output should be a list of
        numbers corresponding to the traversed nodes.
        ARGUMENTS: start_node_num is the node number (integer)
        MODIFIES: the value of the visited property of nodes in self.nodes
        RETURN: a list of the node values (integers)."""
        node = self.find_node(start_node_num)
        self._clear_visited()
        ret_list = []
        # Your code here
        queue = [node]
        node.visited = True
        def enqueue(n, q=queue):
            n.visited = True
            q.append(n)
        def unvisited_outgoing_edge(n, e):
            return ((e.node_from.value == n.value) and
                    (not e.node_to.visited))
        while queue:
            node = queue.pop(0)
            ret_list.append(node.value)
            for e in node.edges:
                if unvisited_outgoing_edge(node, e):
                    enqueue(e.node_to)
        return ret_list

    def bfs_names(self, start_node_num):
        """Return the results of bfs with numbers converted to names."""
        return [self.node_names[num] for num in self.bfs(start_node_num)]

graph = Graph()

# You do not need to change anything below this line.
# You only need to implement Graph.dfs_helper and Graph.bfs

graph.set_node_names(('Mountain View',   # 0
                      'San Francisco',   # 1
                      'London',          # 2
                      'Shanghai',        # 3
                      'Berlin',          # 4
                      'Sao Paolo',       # 5
                      'Bangalore'))      # 6 

graph.insert_edge(51, 0, 1)     # MV <-> SF
graph.insert_edge(51, 1, 0)     # SF <-> MV
graph.insert_edge(9950, 0, 3)   # MV <-> Shanghai
graph.insert_edge(9950, 3, 0)   # Shanghai <-> MV
graph.insert_edge(10375, 0, 5)  # MV <-> Sao Paolo
graph.insert_edge(10375, 5, 0)  # Sao Paolo <-> MV
graph.insert_edge(9900, 1, 3)   # SF <-> Shanghai
graph.insert_edge(9900, 3, 1)   # Shanghai <-> SF
graph.insert_edge(9130, 1, 4)   # SF <-> Berlin
graph.insert_edge(9130, 4, 1)   # Berlin <-> SF
graph.insert_edge(9217, 2, 3)   # London <-> Shanghai
graph.insert_edge(9217, 3, 2)   # Shanghai <-> London
graph.insert_edge(932, 2, 4)    # London <-> Berlin
graph.insert_edge(932, 4, 2)    # Berlin <-> London
graph.insert_edge(9471, 2, 5)   # London <-> Sao Paolo
graph.insert_edge(9471, 5, 2)   # Sao Paolo <-> London
# (6) 'Bangalore' is intentionally disconnected (no edges)
# for this problem and should produce None in the
# Adjacency List, etc.

import pprint
pp = pprint.PrettyPrinter(indent=2)

print ("Edge List")
pp.pprint(graph.get_edge_list_names())

print ("\nAdjacency List")
pp.pprint(graph.get_adjacency_list_names())

print ("\nAdjacency Matrix")
pp.pprint(graph.get_adjacency_matrix())

print ("\nDepth First Search")
pp.pprint(graph.dfs_names(2))

# Should print:
# Depth First Search
# ['London', 'Shanghai', 'Mountain View', 'San Francisco', 'Berlin', 'Sao Paolo']

print ("\nBreadth First Search")
pp.pprint(graph.bfs_names(2))
# test error reporting
# pp.pprint(['Sao Paolo', 'Mountain View', 'San Francisco', 'London', 'Shanghai', 'Berlin'])

# Should print:
# Breadth First Search
# ['London', 'Shanghai', 'Berlin', 'Sao Paolo', 'Mountain View', 'San Francisco']<jupyter_output>Edge List
[ (51, 'Mountain View', 'San Francisco'),
  (51, 'San Francisco', 'Mountain View'),
  (9950, 'Mountain View', 'Shanghai'),
  (9950, 'Shanghai', 'Mountain View'),
  (10375, 'Mountain View', 'Sao Paolo'),
  (10375, 'Sao Paolo', 'Mountain View'),
  (9900, 'San Francisco', 'Shanghai'),
  (9900, 'Shanghai', 'San Francisco'),
  (9130, 'San Francisco', 'Berlin'),
  (9130, 'Berlin', 'San Francisco'),
  (9217, 'London', 'Shanghai'),
  (9217, 'Shanghai', 'London'),
  (932, 'London', 'Berlin'),
  (932, 'Berlin', 'London'),
  (9471, 'London', 'Sao Paolo'),
  (9471, 'Sao Paolo', 'London')]

Adjacency List
[ <map object at 0x7f11c8228828>,
  <map object at 0x7f11c8228898>,
  <map object at 0x7f11c8228908>,
  <map object at 0x7f11c8228978>,
  <map object at 0x7f11c82289e8>,
  <map object at 0x7f11c8228a58>,
  None]

Adjacency Matrix
[ [0, 51, 0, 9950, 0, 10375, 0],
  [51, 0, 0, 9900, 9130, 0, 0],
  [0, 0, 0, 9217, 932, 9471, 0],
  [9950, 9900, 9217, 0, 0, 0, 0],
  [0, 9130, 932, 0, 0, 0, 0][...]
{'fraction_non_alphanumeric': 0.09410926849119951, 'fraction_numerical': 0.021187302879234916, 'mean_word_length': 2.857633437990581, 'pattern_counts': {'":': 2, '<': 79, '<?xml version=': 0, '>': 77, 'https://': 6, 'lorem ipsum': 0, 'www.': 5, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '15', 'dir': 'jupyter-structured-clean-dedup', 'id': '215371', 'license': 'MIT', 'n_tokens_mistral': 12646, 'n_tokens_neox': 11751, 'n_words': 4384, 'path': 'code/algorithms/.ipynb_checkpoints/google_algo_course_notes-checkpoint.ipynb', 'repo_name': 'vicb1/miscellaneous', 'size': '39316'}