Tech for good

Completely Binary Tree (CBT)Completely Binary Tree: CBT; Perfect Binary Tree: PBT Not-efficient approach - O(n)# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def countNodes(self, root: Optional[TreeNode]) -> int: if not root: ..

class Solution: def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]: pq = [] for x, y in points: d = x * x + y * y pq.append((d, (x,y))) # make it a tuple heapify(pq) res = [] for i in range(k): res.append(heappop(pq)[1]) # heappop(pq) = (d, (x, y)) return res

class Solution: def lastStoneWeight(self, stones: List[int]) -> int: # what is heap? => find min/max using push() or pop() # it allows handling new value effeciently when we even insert new values. pq = [-x for x in stones] # pq = [-2, -7, -4, -1, -8, -1] heapify(pq) # heapify() -> make it into binarry tree for efficiency (only half-through traversa..

def count_components(adjacency_dict): # Write your code here visited = set() cnt = 0 def dfs(node): visited.add(node) for neighbor in adjacency_dict[node]: if neighbor not in visited: dfs(neighbor) for node in adjacency_dict: if node not in visited: dfs(node) cnt += 1 return cnt

from collections import deque, defaultdictdef has_path(adjacency_dict, start, destination): # Write your code here if start == destination: return True graph = defaultdict(list, adjacency_dict) q = deque([start]) visited = set([start]) while q: curr = q.popleft() if curr == destination: return True for neighbor ..

class Solution: def numIslands(self, grid: List[List[str]]) -> int: n_rows, n_cols = len(grid), len(grid[0]) res = 0 visited = set() def dfs(r, c): visited.add((r,c)) neighbors = [(r-1, c), (r+1, c), (r, c-1), (r, c+1)] # check if visited or not for n_r, n_c in neighbors: if n_r in range(n_rows) and n_c in ..

class Solution: def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool: # 1. Make a graph ## To figure out neighbor using hash-map ## 0 => [1,2] graph = defaultdict(list) for u, v in edges: graph[u].append(v) graph[v].append(u) # 2. BFS from source q = deque([source]) visited = se..

Properties 1The town judge trusts nobody.Properties 2Everybody (except for the town judge) trusts the town judge.Properties 3There is exactly one person that satisfies properties 1 and 2.class Solution: def findJudge(self, n: int, trust: List[List[int]]) -> int: # To figure out in-degree/out-degree using hash-map in_degree = defaultdict(int) out_degree = defaultdict(int)..

# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool: if not root: return False return self.sameTree(root, subRoot) or self.isSubtree(root..