<jupyter_start><jupyter_text>dfs(vertex):    vertex set visited = Ture:    print vertex    for v in vertex.neibors:        if v is not visited:            dfs(v)dfs(vertex):    stack-> Last in, first out LIFO structure    stack.push(vertex)    while stack not empty:        actual=stack.pop()        actual set visited = True:        for v in actual.neibors:            if v is not visited:                stack.push(v)<jupyter_code># Max Item in Stacks
# O(1) but the memory complextiy is O(n)
class MaxStack:
    def __init__(self):
        self.main_stack=[]
        self.max_stack=[]
        
    def push(self,data):
        self.main_stack.append(data)
        if (len(self.main_stack)==1):
            self.max_stack.append(data)
            return
        if data>self.max_stack[-1]:
            self.max_stack.append(data)
        else:
            self.max_stack.append(self.max_stack[-1])

            
    def pop(self):
        self.max_stack.pop()
        return self.max_stack.pop()

    def get_max(self):
        return self.main_stack.pop()
if __name__=="__main__":
    max_stack_running=MaxStack()
    max_stack_running.push(1000)
    max_stack_running.push(100)
    max_stack_running.push(10)
    max_stack_running.push(10000)
    max_stack_running.push(1)
    print(max_stack_running.get_max())
CAPACITY=10

class Heap:
    def __init__(self):
        self.heap_size=0 # Actual number of items in the heap
        self.heap=[0]*CAPACITY # the underlying data structure
    def insert(self,items):
        if self.heap_size==CAPACITY:
            return
        self.heap[self.heap_size]=items
        self.heap_size+=1
        # this is to insure the item inserted in the next location
        self.fix_up(self.heap_size-1) # heapify
    
    # Log N complexity since it worst case will be from bottom to the top
    def fix_up(self,index):
        # if we have an index i, then the left child will be 2i+1 and the right index will be 2i+2
        parent_index=(index-1)//2 # no matter it is a left child or a right child
        if index>0 and self.heap[index]>self.heap[parent_index]:
            self.heap[index],self.heap[parent_index]=self.heap[parent_index],self.heap[index]
            self.fix_up(parent_index)
    def get_max(self):
        """This function returns the max item with O(1) Complexity"""
        
        return self.heap[0]
    
    # Remove the root node from the heap
    def poll(self):
        max_item=self.get_max()
        self.heap[0],self.heap[self.heap_size-1]=self.heap[self.heap_size-1],self.heap[0]
        self.heap_size-=1
        
        self.fix_down(0)
        
        return max_item
    def fix_down(self,index):

        left_index=2*index+1
        right_index=2*index+2
        largest_index=index
        
        if left_index<self.heap_size and self.heap[left_index]>self.heap[index]:
            largest_index=left_index
        if right_index<self.heap_size and self.heap[right_index]>self.heap[largest_index]:
            largest_index=right_index
        if index!=largest_index:
            self.heap[index],self.heap[largest_index]=self.heap[largest_index],self.heap[index]
            self.fix_down(largest_index)
    
    def heap_sort(self):
        for _ in range(self.heap_size):
            max_item=self.poll()
            print(max_item)
if __name__=="__main__":
    myheap=Heap()
    myheap.insert(13)
    myheap.insert(-2)
    myheap.insert(-0)
    myheap.insert(8)
    myheap.insert(1)
    myheap.insert(-5)
    myheap.insert(99)
    print(myheap.heap)
    myheap.heap_sort()
import heapq
# it is the min heap implenmentation
heap=[4,7,3,-2,1,0]
heapq.heapify(heap)

wordladderi("hit","cog",["hot","dot","dog","lot","log","cog"])
from collections import defaultdict
def findladders(beginword,endword,wordlist):
    #wordlist
    if endword not in wordlist:
        return []
    n=len(beginword)
    graph=defaultdict(list)
    for word in wordlist:
        for i in range(n):
            graph[word[:i]+'-'+word[i+1:]].append(word)
    
    queue=deque()
    queue.append((beginword,1,[beginword]))
    seen=set()
    groups=[]
    minlevel=len(wordlist)+2
    
    while queue:
        current,level,prev=queue.popleft()
        seen.add(current)
        intermediates=[]
        for i in range(n):
            
findladders("hit","cog",["hot","dot","dog","lot","log","cog"])
class NewNode:
    def __init__(self,key):
        self.data=key
        self.left=None
        self.right=None
        self.hd=0
def topview(root):
    if root==None:
        return []
    queue=deque()
    mydict=dict()
    hd=0
    root.hd=hd
    
    queue.append(root)
    while queue:
        root=queue.popleft()
        hd=root.hd
        if hd not in mydict:
            mydict[hd]=root.data
        if(root.left):
            root.left.hd=hd-1
            queue.append(root.left)
        if(root.right):
            root.right.hd=hd+1
            queue.append(root.right)
    for i in sorted(mydict):
        print(mydict[i])
        
root=NewNode(1)
root.left=NewNode(2)
root.right=NewNode(3)
root.left.right=NewNode(4)
root.left.right.right=NewNode(5)
root.left.right.right.right=NewNode(6)
topview(root)
# LRU Using OrderDict
from collections import OrderedDict
class LRUCache():
    def __init__(self,capacity):
        self.capacity=capacity
        self.cache=OrderedDict()
    def get(self,key):
        if key not in self.cache:
            return -1
        value=self.cache[key]
        self.cache.pop(key)
        self.cache[key]=value
        return value
    def put(self,key,value):
        if key in self.cache:
            self.cache.pop(key)
            self.cache[key]=value
       
    else:
            if len(self.cache.keys())==self.capacity:
                self.cache.popitem(last=False)
            else:
                self.cache[key]=value
#max contiguous subarray
def maxsubarray(arr,i,j):
    T=arr[0]
    vmax=arr[0]
    Tmin=min(0,T)
    for k in range(1,len(arr)):
        T+=arr[k]
        if T-Tmin > vmax:
            vmax=T-Tmin
            j=k
        if T<Tmin:
            Tmin=T
            i=k+1
    return (i,j,vmax)
maxsubarray([1,-2,-5,4,-3,-2,6,-5,-1],0,0)
#Leetcode 724
def findpivot(nums):
    l,r=0,sum(nums)
    for l in range(len(nums)):
        r-=nums[i]
        if r==l: return i
        l+=nums[i]
    return -1
#leetcode 1282
#[2,1,3,3,3,2] -> [[1],[0,5],[2,3,4]]
import collections
def groupthepeople(groupsize):
    res,groupmap=[],collections.defaultdict(list)
    for i,gs in enumerate(groupsize):
        groupmap[gs].append(i)
    for k,ids in groupmap.items():
        i=0
        while i<len(ids):
            res.append(ids[i:i+k])
            i+=k
    return res
#sliding puzzle
def board_sliding(board):
    krows=2
    kclos=3
    goal='123450'
    pass
def max_n_of_apples(arr):
    arr.sort(0)
    res,t=0,0
    for i,v in enumerate(arr):
        t+=v
        if t>5000:
            break
        res+=1
    return res<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12464265294453973, 'fraction_numerical': 0.01815323041738136, 'mean_word_length': 2.2973609802073516, 'pattern_counts': {'":': 2, '<': 9, '<?xml version=': 0, '>': 14, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '409189', 'license': 'MIT', 'n_tokens_mistral': 2451, 'n_tokens_neox': 2395, 'n_words': 476, 'path': 'leetcodes/Interview_Prep_2.ipynb', 'repo_name': 'HaoLiNick/Coding2021', 'size': '6996'}