liyunrui

class Solution:
    """
    Problem Clarification
        -We must ask interviewer to go through the examples.
        -You can even go through another examples to make sure there's no misunderstanding.
        -Ask edge case, input and output data structure, sorted or not sorted, Positive or Negative, duplicates?
    
    Thought Process:
        DP
        

liyunrui

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        """
        Greedy Approach
        
        To determine Greedy strategy:
            1.What's our locally optimal solution at each step(index)?
                1.1. if max position the one could reach starting from the current index i or before less than current index i --> impossible to reach current index i from index < i. Clearly, it leads to impossible to reach the last index.
                
                1.2. keep track max position the one could reach starting from the current index i or before.

liyunrui

class Solution:
    def jump(self, nums: List[int]) -> int:
        """
        Greedy Approach
        
        To determine Greedy strategy:
            1.What's our locally optimal solution at each step(index)?
                1.1. if maxi step we can jump befor index i is less than current index i, we need one more jump, and we choose longest jump we can do to minimize the number of jump.
                1.2. keep track max position the one could reach starting from the current index i or before it as longest jump when we needed
            2.How do determine our global solution? 

liyunrui

class Solution:
    """
    PC:
        1.so no guarantee the given node is connected graph or not
    Goal:
        1.to return maximum time from given node to alls nodes
        2.time from given node to another node comes downs to shortest path problem
    Problem formulation:
        1.Firts of all, we can model this problem as weighted directed graph problem.
        2.And our goal is, given a directed weighted graph with n nodes, find the shortest path between node K (starting node) and rest of other nodes. If cannot reach all the other nodes from node K, return -1. If can, return maximum time out of those shortest distances from k to others node is our answer

liyunrui

class Solution:
    def findCheapestPrice(self, n, flights, src, dst, k):
        """
        Approach-Dijkstra's algorithm
        
        We can model this problem as graph problem and use shortest path algorithm to solve it.
        
        Problem formulation:
            Given a directed weighted graph with n nodes, find the shortest path between src (starting node) and dst (ending node) with up to pass k nodes.
        

liyunrui

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        """
        1st approach: BFS + nodes coloring
        
        Graph is already in adjacency list representation
        
        Given n nodes and edge list of undirected graph, to see if nodes in the graph could be colored using two colors so that there are no adjacent nodes with the same color.
        
        seeh hashmap: index is node, corresponding value is color (1: blue, -1: red)

liyunrui

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        """    
        It's all pairs shortest path problems.
        
        Given an undirected and weighted graph with n nodes and path distance threshold, find the city with the smallest number of cities.
        
        Step1: We can simply use Floyd-Warshall algorithm to find the minium distance any two cities.(we need shortest path between any two nodes ih the graph)
        Step2: Calculate number for each city that this city can reach satisfying distance threshold
        Step3: Return city with fewest number from itself to others city and wi

liyunrui

class Solution:
    def treeDiameter(self, edges: List[List[int]]) -> int:
        """
        The problem is to calculate diameter of tree, given a graph with tree characteristics. 
        
        Note:
            1. The path with same diameter is not unique.
            2. The diameter of a tree is the longest length of a path between two nodes.

            

liyunrui

class Solution:
    """
    PC:
        1. no repeated edges?
        2. since given input is guaranteed to be a tree. So, the graph must be
            -acyclic
            -connected
            -n-1 edges
            
    PF:

liyunrui

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []
"""

class Solution:
    """