Programming

Given the heads of two singly linked-lists  headA  and  headB , return  the node at which the two lists intersect . If the two linked lists have no intersection at all, return  null . Note: Has an easy solution, but O(N) good solution is Medium. a + c + b = b + c + a def getIntersectionNode ( headA : ListNode , headB : ListNode ):             pA = headA     pB = headB     while pA != pB :         pA = headB if pA is None else pA .next         pB = headA if pB is None else pB .next     return pA     # Note: In the case lists do not intersect, the pointers for A and B     # will still line up in the 2nd iteration, just that here won't be     # a common node down the list and both will reach their respective ends     # at the same time. So pA will be NULL in that case

class Trie :        class Node :         def __init__ ( self ):             self . children = {}             self . isEnd = False     def __init__ ( self ):         self . root = Trie . Node ()             def insert ( self , word : str ):         p = self . root                 for ch in word :             if ch not in p . children :                 p . children [ ch ] = Trie . Node ()             p = p . children [ ch ]         p . isEnd = True     def search ( self , word : str ):         p = self . root                 for ch in word :       ...

Given an integer array  nums  and an integer  k , return  the   k   most frequent elements . You may return the answer in  any order .   Example: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] def topKFrequent ( self , nums : List [ int ], k : int ):             freq = Counter ( nums )         return heapq . nlargest ( k , freq . keys (), key = freq . get )    

Given an unsorted array of integers  nums , return  the length of the longest  continuous increasing subsequence  (i.e. subarray) . The subsequence must be  strictly  increasing. A  continuous increasing subsequence  is defined by two indices  l  and  r  ( l < r ) such that it is  [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]]  and for each  l <= i < r ,  nums[i] < nums[i + 1] . def findLengthOfLCIS ( nums : List [ int ]):         ans = start = 0         for i in range ( len ( nums )):         if i and nums [ i ] <= nums [ i - 1 ]:             start = i         ans = max ( ans , i - start + 1 )             return ans      

Given a string  s  and a dictionary of strings  wordDict , return  true  if  s  can be segmented into a space-separated sequence of one or more dictionary words. Note  that the same word in the dictionary may be reused multiple times in the segmentation.   Example: Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code".   def wordBreak ( s : str , wordDict : List [ str ]):             word_set = set ( wordDict )     dp = [ False ] * ( len ( s ) + 1 )     dp [ 0 ] = True     for i in range ( 1 , len ( s ) + 1 ):         for j in range ( i ):             if dp [ j ] and s [ j : i ] in word_set :                 dp [ i ] = True                 break   ...

Given an array of integers arr, find the sum of  min(b) , where  b  ranges over every (contiguous) subarray of  arr . Since the answer may be large, return the answer  modulo   10 9  + 7 .   Example: Input: arr = [3,1,2,4] Output: 17 Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Sum is 17. def sumSubarrayMins ( self , arr : List [ int ]):             L = len ( arr ), total = 0 , M = ( 10 ** 9 + 7 )         left =  [ i + 1 for i in range ( L )]     right = [ L - i for i in range ( L )]         p = [], n = []         for i in range ( L ):                 while p :                             if p [- 1 ][ 0 ] <= arr [...

Given an integer array  nums  and an integer  k , return  the   k th   largest element in the array . Note that it is the  k th  largest element in the sorted order, not the  k th  distinct element. You must solve it in  O(n)  time complexity.   Example: Input: nums = [3,2,1,5,6,4], k = 2 Output: 5 def findKthLargest ( nums : List [ int ], k : int ):             heap = nums [: k ]     heapq . heapify ( heap )             N = len ( nums )     for i in range ( k , N ):                     heapq . heappush ( heap , nums [ i ])                               heapq . heappop ( heap )             return heap [ 0 ]

A linked list of length  n  is given such that each node contains an additional random pointer, which could point to any node in the list, or  null . Construct a  deep copy  of the list. The deep copy should consist of exactly  n   brand new  nodes, where each new node has its value set to the value of its corresponding original node. Both the  next  and  random  pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state.  None of the pointers in the new list should point to nodes in the original list . Return  the head of the copied linked list . Note: This code is copy-pasted. I didn't type it. def copyRandomList ( head ):     if not head :         return head     # Creating a new weaved list of original and copied nodes.     ptr = head     while ptr :...

The  median  is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values. For example, for  arr = [2,3,4] , the median is  3 . For example, for  arr = [2,3] , the median is  (2 + 3) / 2 = 2.5 . Note: Two heap Python's heapq is min heap. We negate values to get max heap. The chosen policy here is to allow one more item to maxQ the lower half queue when there are odd number of elements. class MedianFinder :         def __init__ ( self ):                     self . maxQ = [] # smaller half         self . minQ = [] # larger half     def addNum ( self , num : int ) -> None :                 heapq . heappush ( self . maxQ , - num )         heapq . heappush ( self . minQ , - heapq . he...

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the  MinStack  class: MinStack()  initializes the stack object. int getMin()  retrieves the minimum element in the stack. You must implement a solution with  O(1)  time complexity for each function. class MinStack :         def __init__ ( self ):         self . minTrace = []         self . minStack = []     def push ( self , val : int ):         self . minStack . append ( val )         if not self . minTrace or val < self . minTrace [- 1 ]:             self . minTrace . append ( val )         else :             self . minTrace . append ( self . minTrace [- 1 ])     def pop ( self ):         self . minStack . pop ()  ...

You are given an array representing a row of  seats  where  seats[i] = 1  represents a person sitting in the  i th  seat, and  seats[i] = 0  represents that the  i th  seat is empty  (0-indexed) . There is at least one empty seat, and at least one person sitting. Alex wants to sit in the seat such that the distance between him and the closest person to him is maximized.  Return  that maximum distance to the closest person . def maxDistToClosest ( self , seats : List [ int ]):                     taken = []         for i , occupied in enumerate ( seats ):         if occupied :             taken . append ( i )         S = len ( seats )     T = len ( taken )                 maxDist = max ( taken [ 0 ], S - taken [- 1 ] - 1 ) ...

An array  arr  a  mountain  if the following properties hold: arr.length >= 3 There exists some  i  with  0 < i < arr.length - 1  such that: arr[0] < arr[1] < ... < arr[i - 1] < arr[i] arr[i] > arr[i + 1] > ... > arr[arr.length - 1] Given a mountain array  arr , return the index  i  such that  arr[0] < arr[1] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] . You must solve it in  O(log(arr.length))  time complexity. def peakIndexInMountainArray ( self , arr : List [ int ]):             lo , hi = 0 , len ( arr ) - 1         while lo < hi :         mid = ( lo + hi ) // 2                 if arr [ mid + 1 ] > arr [ mid ]: # Still increasing             lo = mid + 1         else ...

Design a class to find the  k th  largest element in a stream. Note that it is the  k th  largest element in the sorted order, not the  k th  distinct element. Implement  KthLargest  class: KthLargest(int k, int[] nums)  Initializes the object with the integer  k  and the stream of integers  nums . int add(int val)  Appends the integer  val  to the stream and returns the element representing the  k th  largest element in the stream. class KthLargest :         def __init__ ( self , k : int , nums : List [ int ]):         self . k = k         self . heap = nums         heapq . heapify ( self . heap )                 while len ( self . heap ) > k :             heapq . heappop ( self . heap )     def add ( self , val : int ) -> int : ...

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. Example: Note: Not sure if the the order can be improved. Is it O(N) already? def lowestCommonAncestor ( root : ' TreeNode ', p : ' TreeNode ', q : ' TreeNode '):             if not root :         return None     if root == p or root == q :         return root     leftLCA  = lowestCommonAncestor ( root .left,   p , q )     rightLCA = lowestCommonAncestor ( root .right, p , q )     if leftLCA and rightLCA :         return root     if leftLCA :         return leftLCA ;     return rightLCA

The board is made up of an  m x n  grid of cells Any live cell with fewer than two live neighbors dies as if caused by under-population. Any live cell with two or three live neighbors lives on to the next generation. Any live cell with more than three live neighbors dies, as if by over-population. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction. Notice: We need to assign decode[0] and decode[1] manually. We need this in counting how many alive around a cell and for the cells that are still holding original value      we still need to decode them. So 0->0 and 1->1 def gameOfLife ( self , board : List [ List [ int ]]):             m , n = len ( board ), len ( board [ 0 ])             encode = {         ( 0 , 0 ) : 2 , # Nothing happening to dead         ( 0 , 1 ) : 3 , # Rule-4: Comes alive ...