Snippets Collections
#solution where you just take subset I and replace last return statement 
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:

   
        subset = [] 
        result = [] 
        
        #i is index of subset 
        def dfs(i): 
            if i >= len(nums): 
                result.append(subset.copy())
                return 
            
            #decision to include nums[i]
            subset.append(nums[i])
            #this recursive call will be given filled subset 
            dfs(i + 1)
            
            #decision NOT to include nums[i] 
            subset.pop()
            #this recursive call will be given empty subset 
            dfs(i + 1)
        
        dfs(0) 
        
        #need to remove duplicate sublists within result 
        return ([list(i) for i in {*[tuple(sorted(i)) for i in result]}])  
  

#solution to prevent duplicates in the first place
class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:

   
        result = []
		nums.sort() 

		def backtrack(i, subset): 
        	if i == len(nums): 
            	res.append(subset.copy())
				return 
			
			#all subsets that include nums[i] 
            subset.append(nums[i]) 
			backtrack(i + 1, subset) 
			#remove number we just added 
            subset.pop()
            
            #all subsets that don't include nums[i]
        	while i + 1 < len(nums) and nums[i] == nums[i + 1]: 
            	i += 1 
			backtrack(i + 1, subset)
		
		backtrack(0, [])
		
		return result 
        
        
        
        
#solution for array with unique integer array. only last return line is dfferent 
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        subset = [] 
        result = [] 
        
        #i is index of subset 
        def dfs(i): 
            if i >= len(nums): 
                result.append(subset.copy())
                return 
            
            #decision to include nums[i]
            subset.append(nums[i])
            #this recursive call will be given filled subset 
            dfs(i + 1)
            
            #decision NOT to include nums[i] 
            subset.pop()
            #this recursive call will be given empty subset 
            dfs(i + 1)
        
        dfs(0) 
        
        return result 
        
        
        
def solution(n, k):
    return climb(n, k, [])
    
        
        
def climb(n, k, jumps):
    if n == 0:
        return [jumps]
    
    out = []
    
    for i in range(1, k+1):
        if i > n:
            continue
            
        temp = jumps + [i] 
        out += climb(n-i, k, temp)
        
    return out
class Solution:
    #number of permutations = n! 
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
    
        if len(nums) == 1: 
            return [nums[:]] 
        
        for i in range(len(nums)): 
            #pop off first element 
            n = nums.pop(0)
            
            #numswill now have one less value, will append popped value later 
            perms = self.permute(nums) 
            
            for perm in perms: 
                perm.append(n)
            
            result.extend(perms)
            #adding popped back 
            nums.append(n) 
        
        return result 
 
class Solution:

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        
        #i is index of candidates 
        def dfs(i, current, total): 
            if total == target: 
              #if you do not add .copu() it will append empty arrays 
                result.append(current.copy())
                return 
            if i >= len(candidates) or total > target: 
                return 

            #decision tree has 2 options: 1) add candidates[i] or 2) do not add and move on to next index 
            
            #1) try adding candidates[i]
            current.append(candidates[i])
            dfs(i, current, total + candidates[i])
            #2) move on to next index 
            current.pop() 
            dfs(i + 1, current, total)
        
        dfs(0, [], 0)
        return result 
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        subset = [] 
        result = [] 
        
        #i is index of subset 
        def dfs(i): 
            if i >= len(nums): 
                result.append(subset.copy())
                return 
            
            #decision to include nums[i]
            subset.append(nums[i])
            #this recursive call will be given filled subset 
            dfs(i + 1)
            
            #decision NOT to include nums[i] 
            subset.pop()
            #this recursive call will be given empty subset 
            dfs(i + 1)
        
        dfs(0) 
        
        return result 
        
        
class Tree(object):
  def __init__(self, x, left=None, right=None):
    self.value = x
    self.left = left
    self.right = right 

x = Tree(1, Tree(0, Tree(1), Tree(3)), Tree(4))


def solution(t): 
    if not t: 
        return 0 
    
    stack = [(t, 0)]
    branchesSum = 0 
    
    while stack: 
        node, v = stack.pop() 
        if node.left or node.right:
        #depth first search 
        # the v is a little confusing to understand but easier to see in python tutor 
        # it goes from 1 to 10 to 100 etc. based on the height of the branch 
        # can probably do something like str() and converting back to int() as well 
            if node.left: 
                stack.append((node.left, node.value + v * 10)) 
            if node.right: 
                stack.append((node.right, node.value + v * 10)) 
        else: 
            branchesSum += node.value + v * 10 
    return branchesSum 
#
# Binary trees are already defined with this interface:
# class Tree(object):
#   def __init__(self, x):
#     self.value = x
#     self.left = None
#     self.right = None
import math 
def solution(t):
    if t is None: return [] 
    
    stack = [t] 
    result = []
    
    while len(stack) > 0: 
        result.append(max(tree.value for tree in stack)) 
        next_row = [tree.left for tree in stack if tree.left] + [tree.right for tree in stack if tree.right]
        stack = next_row 
    return result 


 #1. Add max value of ‘stack’ to result. 2. Create a new list of all next values for each value in stack. 3. redefine stack to this newly made list. 4. repeat 


#alternate solution 
def solution(t):
    largestValues = []
    q = []
    height = 0
    if t:
        q.append([t, height])
        while q:
            item = q.pop()
            node = item[0]
            currentHeight = item[1]
            if node.left:
                q.insert(0, [node.left, currentHeight + 1] )
            if node.right:
                q.insert(0, [node.right, currentHeight + 1])
            checkLargest(node.value, currentHeight, largestValues)
            
    return largestValues
    
        
def checkLargest(value, height, largestValues):
    if height == len(largestValues):
        largestValues.append(value)
    else:
        if largestValues[height] < value:
            largestValues[height] = value
# //Tree Traversal (visit every node once) 
# //Heavy on recursion 
 
# //Breadth-first (BFS) vs. Depth-first (DFS) 
 
# // DFS: 
# // 1) in order (go in order of value)
# // 2) pre order (start at root)
# // 3) post order (start at botom)
 
 
# //When to use BFS vs. DFS: 
# //For a fully loaded (wide) tree, BFS queue will be overloaded in the start (overloaded space complexity)
# //For a longer tree, DFS will take more memory (more rare, Trees are usually wide)
# //Big O for both is same 
 
# //In order: useful if you want sorted array at end (you don't really know what the root is bc it's in the middle)
# //PreOrder: useful to "export a tree" so that it can be copied bc it flattens it 

class Node: 
  def __init__(self, value): 
    self.value = value 
    self.left = None 
    self.right = None 
 
class BinarySearchTree: 
  def __init__(self): 
    self.root = None 
 
  #adds number to correct place 
  def insert(self, value): 
    #creates new Node   
    new_node = Node(value) 
    #start at root 
    #if no root exists, root becomes new_node 
    if self.root == None: 
      self.root = new_node 
      return self 
    
    current = self.root 
    
    while True: 
      #to handle special case where value is same as current node 
      #you can return None or you can add a counter property 
      if value == current.value: 
        return None 
      #check to see if value is less than current 
      if value < current.value: 
        #check to see if there is node to left 
        #if not, add new_node to left 
        if current.left == None: 
          current.left = new_node 
          return self
        #if there is node to left, move to that node and repeat 
        current = current.left 
      #check to see if value is greater than current 
      else: 
        #check to see if there is node to right 
        #if not, add new_node to right 
        if current.right == None: 
          current.right = new_node 
          return self 
        #if there is node to right, move to that node and repeat 
        current = current.right 
        
  #Breadth first search iterative using queue 
  def BFS(self):
    node = self.root 
    #we will return data 
    data = [] 
    queue = [] 
    #place root node inside queue (recall FIFO)
    queue.append(node) 
    #while queue is not empty 
    while len(queue) > 0: 
      #dequeue node from queue and append to data  
      node = queue.pop(0)
      data.append(node) 
      #if there is left on node dequeued, add to queue 
      if node.left: 
        queue.append(node.left) 
      #if there is right on node dequeued, add to queue 
      if node.right: 
        queue.append(node.right) 
      #above two lines of code could be changed if it was a ternary tree, etc. instead of binary 
      #just loop for all children 
    return data 
  
  #parent down uses recursive 
  def DFSPreoder(self): 
    data = [] 
    #if you want to DFS not from root, create a variable here named current and specify which node to start from 
    #helper function 
    def traverse(node): 
      #all of root node's left will happen first, then right 
      #for other types of DFS, just tweak this order 
      data.append(node.value) 
      if node.left:
        traverse(node.left)
      if node.right: 
        traverse(node.right)
    
    traverse(self.root) 
    return data 
  
  #children up, root should be last value 
  def DFSPostOrder(self): 
    data = []
    
    def traverse(node): 
      if node.left:
        traverse(node.left)
      if node.right: 
        traverse(node.right)
      data.append(node.value)
    
    traverse(self.root)
    return data 
  
  #result data list should be sorted 
  def DFSInOrder(self):
    data = []
    def traverse(node): 
      if node.left: 
        traverse(node.left)
      data.push(node.value)
      if node.right: 
        traverse(node.right)
    traverse(self.root)
    return data 

t = BinarySearchTree() 
t.insert(1)
t.insert(5)
t.insert(6)
t.insert(2)
t.insert(0) 
t.insert(-1)
t.insert(7) 

print(t.DFSInOrder())
# //Used in call stack, undo/redo, routing 
 
# //Array implenentation (just use pop/push or shift/unshift) 
# //Recall that pop/push is more efficient than shift/unshift 
# //Indexes take up memory so linked list implenetation will be better 
 
# //Single linked implenetation of stack:

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

class Stack: 
  def __init__(self, first=None, last=None, size=0): 
    self.first = first
    self.last = last 
    self.size = size 
  
  #Similar to shift or insert(0, value). Adds to stack and returns size. Recall stack is LIFO  
  def push(self, value): 
    new_node = Node(value) 
    if self.first == None: 
      self.first = new_node 
      self.last = new_node 
    else: 
      #stores current 1st property on stack 
      temp = self.first 
      #reset 1st property to be newly created one 
      self.first = new_node 
      #set new next property 
      self.first.next = temp 
    #increment stack 
    self.size += 1  
    return self.size 
  
  #in python, this would be pop(0). Similar to unshift. Removes first element on stack  
  def pop(self): 
    #special case if stakc is empty 
    if self.first == None: 
      return None 
      
    temp = self.first 
    #if there is only 1 node, set 1st node and last property to be None 
    if self.first == self.last: 
      self.last = None
      #self.first = None will be set in next line 
    
    #for all scenarios except empty stack 
    self.first = self.first.next 
    self.size -= 1 
    return temp.value 
    
    #useful to visualize reverse() or any other function works 
  def print_stack_to_list(self): 
    result = []
    current = self.first 
    while current: 
      result.append(current.value)
      current = current.next 
    print(result)


s = Stack() 
s.push(1) 
s.push(2)
s.push(3)
s.print_stack_to_list() # [3, 2, 1]
s.pop()
s.print_stack_to_list() #[2, 1]



# //these methods deal with 1st node bc thats what stacks do (LIFO) 
# // Big O: 
# // Insertion and Removal: O(1) **this is mainly what stacks are good for 
# // Access and Search: O(N) 
      
star

Tue Aug 09 2022 21:41:13 GMT+0000 (UTC) https://app.codesignal.com/interview-practice/task/cAXEnPyzknC5zgd7x/description

#python #depth #first #search #recursive #codesignal #climb
star

Tue Aug 09 2022 20:11:11 GMT+0000 (UTC) https://leetcode.com/problems/permutations/submissions/

#python #depth #first #search #recursive #neetcode
star

Tue Aug 09 2022 19:43:50 GMT+0000 (UTC) https://leetcode.com/problems/combination-sum/submissions/

#python #depth #first #search #recursive #neetcode
star

Tue Aug 09 2022 00:00:39 GMT+0000 (UTC) https://app.codesignal.com/interview-practice/task/2oxNWXTS8eWBzvnRB/description

#python #methods #queue #codesignal #first #search #max #depth

Save snippets that work with our extensions

Available in the Chrome Web Store Get Firefox Add-on Get VS Code extension