---
# System prepended metadata

title: 亞麻OA 校招

---

# 亞麻OA 校招


### Searching in a 2D matrix

```java
class Point {
    int x;
    int y;
}

Point isInMatrix(int[][] matrix, int target){
    int row = matrix.length;
    int column = matrix[0].length;
    int r = 0;
    int c = column - 1;
    while (r < row && c >= 0){
        if (matrix[r][c] == target){
            return new Point(r,c);
        }
        if (matrix[r][c] > target){
            c--;
        } else {
            r++;
        }
    }
    return new Point(-1,-1);
}
```



### Critical connections

```python
class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        graph = collections.defaultdict(list)
        for i, j in connections:
            graph[i].append(j)
            graph[j].append(i)
        ans = []
        states = [-1] * n
        
        #Start from 0, if we find the step is smaller or equal to the minimum step, it means ring exist.
        def dfs(curr, parents, steps):            
            states[curr] = steps + 1 #Min step now            
            for child in graph[curr]:
                if child == parents: continue #go back and forth
                elif states[child] == -1: #haven't vistied
                    states[curr] = min(states[curr], dfs(child, curr, steps + 1))
                else: #if we find smaller step, update it
                    states[curr] = min(states[curr], states[child])
            
            #Check if the step changes, but 0 which is the starting point should be excluded
            if states[curr] == steps + 1 and curr != 0:
                ans.append([parents, curr])
            return states[curr]
        
        dfs(0, -1, 0)
        return ans
```



### Copy List with Random Pointer

   ```python
   class Node:
       def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
           self.val = int(x)
           self.next = next
           self.random = random
   
   class Solution:
       def copyRandomList(self, head: 'Node') -> 'Node':
           dummy = Node(0)
           nodeDict = {}
           newHead, curr = dummy, head
           while curr:
               node = Node(curr.val)
               nodeDict[curr] = node
               newHead.next = node
               newHead = newHead.next
               curr = curr.next
           curr = head
           while curr:
               if curr.random:
                   nodeDict[curr].random = nodeDict[curr.random]
               curr = curr.next
           return dummy.next
   ```

### Jenny(題目沒看到只記得有個人叫Jenny)

```python
from collections import defaultdict, deque

N, M, K = map(int, input().split())
graph = defaultdict(list)
v, max, cost, ans = [False] * (N + 1), 0, 0, 0

def BFS(start, ok = False):
   if v[start]:
       return
   global max, cost, ans
   v[start], nr, edges = True, 1, set()
   queue = deque([start])
   while queue:
       node = queue.popleft()
       for next_node in graph[node]:
           if not v[next_node]:
               nr += 1
               v[next_node] = True
               queue.append(next_node)
           if not (node, next_node) in edges and not (next_node, node) in edges:
               edges.add((node, next_node))
   ans += nr * (nr - 1) // 2 - len(edges)
   if ok:
       if (nr > max):
           max = nr
   else:
       global nr_without_water
       ans += nr_without_water * nr
       cost += nr_without_water * nr
       nr_without_water += nr
   
   
while M:
   M -= 1
   x, y = map(int, input().split())
   graph[x].append(y)
   graph[y].append(x)

for water_point in map(int, input().split()): # 1
   BFS(water_point, True)

nr_without_water = 0                          # 2
for i in range(1, N + 1):
   BFS(i)

ans += max * nr_without_water                 # 3
cost += max * nr_without_water

print(ans, cost)                              # 4
   ```

### Connecting city with minimum cost

```python
def minimumCost(self, N: int, connections: List[List[int]]) -> int:
   parents = [x for x in range(N)]
   ranks = [1] * N

   def find(u):
       while u != parents[u]:
           parents[u] = parents[parents[u]]
           u = parents[u]
       return u

   def union(u, v):
       root_u, root_v = find(u), find(v)
       if root_u == root_v: return False
       if ranks[root_v] > ranks[root_u]:
           root_u, root_v = root_v, root_u
       parents[root_v] = root_u
       ranks[root_u] += ranks[root_v]
       return True

   connections.sort(key = lambda x: x[2])
   ans = 0
   for u, v, val in connections:
       if union(u-1, v-1): ans += val
   groups = len({find(x) for x in parents})
   return ans if groups == 1 else -1
   ```

### Subtree with Maximum Average
```python
class TreeNode:
    def __init__(self, val, children):
        self.val = val
        self.children = children

class Solution:
    def maxAverage(self, root):
        if not root or not root.children:
            return None
    
        # self.res = [max average, tree node of the max average]
        self.res = [float('-inf'), root)]
        self.dfs(root)

        return self.res[1]

    def dfs(self, root):
        if not root.children:
            return [root.val, 1]

        cur_val, cur_count = root.val, 1

        for node in root.children:
            child_val, child_count = self.dfs(node)
            cur_val += child_val
            cur_count += child_count

        cur_average = cur_val / float(cur_count)

        if cur_average > self.res[0]:
            self.res = [cur_average, root]

        return [cur_val, cur_count]
```


```python
def maximumAverageSubtree(self, root):
    self.res = 0
    def helper(root):
        if not root: return [0, 0.0]
        n1, s1 = helper(root.left)
        n2, s2 = helper(root.right)
        n = n1 + n2 + 1
        s = s1 + s2 + root.val
        self.res = max(self.res, s / n)
        return [n, s]
    helper(root)
    return self.res
```

### Battle Ship

```python
S = "1B 2C,2D 4D" 
T = "2B 2D 3D 4D 4A"

tothit, totsunk = 0,0

def noPos(i):
    no = ''
    pos = ''
    for j in i:
        if(0 <= ord(j) - ord('0') <=9):
            no+=j
        else:
            pos+=j

    no = int(no)
    pos = ord(pos)-ord('A')
    return[no, pos]

target = []
S = S.split(',')
T = T.split()

for i in T:
    target.append(noPos(i))

for i in S:
    i = i.split()
    hit, sunk, count = 0,0,0
    rlow, rhigh, clow, chigh =0,0,0,0
    cc= 0
    for k in i :
        if(cc == 0):
            rlow, clow = noPos(k)
            cc+=1
        else:
            rhigh, chigh = noPos(k)

    for r in range(rlow, rhigh+1):
        for c in range(clow, chigh+1):
            count+=1
            if([r, c] in target):
                hit+=1
    if hit == count:
        totsunk+=1
    elif(0<hit<count):
        tothit+=1

print("total ships hit are ", tothit, " and total sunk are ", totsunk)
```

### Robot throw, robotic challenge

```python
class Solution(object):
    def calPoints(self, ops):
        # Time: O(n)
        # Space: O(n)
        history = []
        for op in ops:
            if op == 'C':
                history.pop()
            elif op == 'D':
                history.append(history[-1] * 2)
            elif op == '+':
                history.append(history[-1] + history[-2])
            else:
                history.append(int(op))
        return sum(history)
```

### Distance Between Nodes in BST

```python
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        

def insert(root, val):
    if root == None:
        return TreeNode(val=val)

    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)

    return root

bst = []
def preorder(root):
    if root == None:
        bst.append(None)
        return
    bst.append(root.val)
    preorder(root.left)
    preorder(root.right)

def lowestCommonAncestor(root, p, q):
    """
    :type root: TreeNode
    :type p: int
    :type q: int
    :rtype: TreeNode
    """
    parent_val = root.val

    if p < parent_val and q < parent_val:
        return lowestCommonAncestor(root.left, p, q)

    if p > parent_val and q > parent_val:
        return lowestCommonAncestor(root.right, p, q)

    return root
        
def height(root, val):
    if root.val == val:
        return 0
    
    if val < root.val:
        return (height(root.left, val) + 1)
    else:
        return (height(root.right, val) + 1)

l = [4, 2, 7, 1, 3, 5]
p = 1
q = 2
root = None
for val in l:
    root = insert(root, val)
preorder(root)

print bst
lca = lowestCommonAncestor(root, p, q)
print lca.val
h1 = height(lca, p)
h2 = height(lca, q)
print h1, h2
print h1 + h2
```

### Treasure Island

```python
def solution(m):
    if len(m) == 0 or len(m[0]) == 0:
        return -1  # impossible

    matrix = [row[:] for row in m]
    nrow, ncol = len(matrix), len(matrix[0])

    q = deque([((0, 0), 0)])  # ((x, y), step)
    matrix[0][0] = "D"
    while q:
        (x, y), step = q.popleft()

        for dx, dy in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            if 0 <= x+dx < nrow and 0 <= y+dy < ncol:
                if matrix[x+dx][y+dy] == "X":
                    return step+1
                elif matrix[x+dx][y+dy] == "O":
                    # mark visited
                    matrix[x + dx][y + dy] = "D"
                    q.append(((x+dx, y+dy), step+1))

    return -1
```

### Valid Parentheses

```python
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        d = {"[": "]", "{":"}", "(":")"}  
        for i in s:a
            if i in d:
                stack.append(i)
            else:
                if not stack or d[stack.pop()] != i : return False            
        return True if not stack else False
```

### Longest Palindromic Substring

```python
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        def getLen(s, l, r):
            while l >= 0 and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            return r - l -1
        start, length, end = 0, 0, 0
        for i in range(n):   
            curr = max(getLen(s, i, i), getLen(s, i, i+1))
            if curr < length: continue
            length = curr
            start = i - (length-1) // 2
            end = start + length
        return s[start: end]
```

### Search Suggestions System , Keyword Suggestions

```python
def suggestedProducts(self, A, word):
    A.sort()
    res, prefix, i = [], '', 0
    for c in word:
        prefix += c
        i = bisect.bisect_left(A, prefix, i)
        res.append([w for w in A[i:i + 3] if w.startswith(prefix)])
    return res
```

### Count teams

```python
import math
def solution(num, skills, minAssociates, minLevel, maxLevel):
    satis = 0
    for skill in skills:
      if minLevel <= skill <= maxLevel:
        satis+=1
      ans = 0
      for i in range(minAssociates, satis+1):
        ans += math.factorial(satis) / math.factorial(i) * math.factorial(satis - i)
    return ans
```

### Fetch Item to display

```java
public class Main {    
    public static List<String> fetchItemsToDisplay(int numOfItems, HashMap<String, Pair<Integer, Integer>> items, int sortParameter, int sortOrder, int itemsPerPage, int pageNumber) {
        
        if(items.size() == 0)
           return Collections.EMPTY_LIST;

        SortedSet<Map.Entry<String, Pair<Integer, Integer>>> set = new TreeSet<>(new Comparator<Map.Entry<String, Pair<Integer, Integer>>>() {
            @Override
            public int compare(Map.Entry<String, Pair<Integer, Integer>> entry1, Map.Entry<String, Pair<Integer, Integer>> entry2) {
                if(sortParameter == 0) {
                    if(sortOrder == 0)
                        return entry1.getKey().compareTo(entry2.getKey());
                    return entry2.getKey().compareTo(entry1.getKey());
                }
                
                if(sortParameter == 1) {
                    if(sortOrder == 0)
                        return (int) entry1.getValue().getKey() - (int) entry2.getValue().getKey();
                    return (int) entry2.getValue().getKey() - (int) entry1.getValue().getKey();
                }
                
                if(sortParameter == 2) {
                    if(sortOrder == 0)
                        return (int) entry1.getValue().getValue() - (int) entry2.getValue().getValue();
                    return (int) entry2.getValue().getValue() - (int) entry1.getValue().getValue();
                }
                return 0;
            }
        });

        set.addAll(items.entrySet());

        List<String> result = new ArrayList<>();
        for(Map.Entry<String,Pair<Integer, Integer>> entry : set)
            result.add(entry.getKey());

       int start = pageNumber * itemsPerPage;
       int end = (start + itemsPerPage) > result.size() ? result.size() : start + itemsPerPage;

       return result.subList(start, end);
    }
    
    public static void main(String[] args) {
        int numOfItems = 3;
        HashMap<String, Pair<Integer, Integer>> items = new HashMap<>();
        items.put("item1", new Pair<Integer, Integer>(10, 15));
        items.put("item2", new Pair<Integer, Integer>(3, 4));
        items.put("item3", new Pair<Integer, Integer>(17, 8));
        
        int sortParameter = 1;
        int sortOrder = 0;
        int itemsPerPage = 2;
        int pageNumber = 1;
        
        System.out.println(fetchItemsToDisplay(numOfItems, items, sortParameter, sortOrder, itemsPerPage, pageNumber));
    }
}
```

### Find the highest profit

```python
suppliers = [3, 5]
order = 6
import heapq

max_heap = []
for product in suppliers:    
    heapq.heappush(max_heap, -product)

profit = 0
while max_heap and order > 0:
    product = heapq.heappop(max_heap)
    product_profit = -product
    profit += product_profit
    if product_profit > 0:
        product_profit -= 1
        heapq.heappush(max_heap, -product_profit)
```

### Break a Palindrome

```python
def breakPalindrome(self, S):
    for i in xrange(len(S) / 2):
        if S[i] != 'a':
            return S[:i] + 'a' + S[i + 1:]
    return S[:-1] + 'b' if S[:-1] else ''
```

###  Fill The Truck

```python
import heapq
def fillTheTruck(num, boxes, unitSize, unitsPerBox, truckSize):
  pq = []

  for i in range(len(boxes)):
    for j in range(boxes[i]):
      heapq.heappush(pq, -unitsPerBox[i])
  ans = 0
  while truckSize > 0 and pq:
    ans += - heapq.heappop(pq)
    truckSize -= 1
  return ans
```

### Optimal Utilization

```python
class Solution:
    def findPairs(self, a, b, target):
        a.sort(key=lambda x: x[1])
        b.sort(key=lambda x: x[1])
        l, r = 0, len(b) - 1
        ans = []
        curDiff = float('inf')
        while l < len(a) and r >= 0:
            id1, i = a[l]
            id2, j = b[r]
            if (target - i - j == curDiff):
                ans.append([id1, id2])
            elif (i + j <= target and target - i - j < curDiff):
                ans.clear()
                ans.append([id1, id2])
                curDiff = target - i - j
            if (target > i + j):
                l += 1
            else:
                r -= 1
        return ans
```

### Cut off Rank

```python
def GetRanks(cutOffRank, numScores, scores):
    scores.sort()
    rank = []
    if cutOffRank == numScores:
        return numScores
    rank.append(1)
    for i in reversed(range(1, len(scores))):
        if scores[i] == scores[i-1]:
        rank.append(i-1)
    else:
        rank.append(i)
    ans = 0
    for j in range(len(rank)):
        if rank[j] <= cutOffRank:
        ans += 1
  return ans
```

### Min Cost to Connect Rope

 ```python
def minCost(ropes: List[int]) -> int:
    if not ropes: return 0
    if len(ropes) == 1: return ropes[0]
    heapify(ropes)
    cost = 0
    while len(ropes) > 1:
        a, b = heappop(ropes), heappop(ropes)
        cost += a+b
        if ropes:
           heappush(ropes, a+b)
    return cost
 ```

### Amazon Fresh Promotion

```python
secret_code = [['apple', 'apple'], ['banana', WILD_CARD, 'banana']]
user_purchase = ['apple', 'apple', 'apple', 'banana']
expected 0

secret_code = [['apple', 'apple']]
user_purchase = ['apple', 'apple', 'apple', 'banana']
expected 1

secret_code = []
user_purchase = ['apple', 'apple', 'apple', 'banana']
expected 1

WILD_CARD = 'anything'
# Time complexity is O( n + m )
def is_winner(secret_code, shopping_cart):
    if not secret_code:
        return True
    shopping_cart_length = len(shopping_cart)
    shopping_cart_index = 0  # Moving index to scan through shopping cart
    secret_index = 0  # Moving index to scan through each secret
    start_cart_index = 0  # to be able to reset search if partial secret was found
    previous_scan_index = 0  # If one secret was found, we want to offset the search by the last index in the shopping cart
    for i in range(len(secret_code)):
        secret = secret_code[i]  # Current secret we are looking for
        secret_l = len(secret)  # Length of current secret we are looking for
        secret_index = 0
        matched_secret = 0
        while matched_secret != secret_l:
            if (start_cart_index + shopping_cart_index) >= shopping_cart_length:
                return 0
            item = shopping_cart[start_cart_index+shopping_cart_index]

            if item == secret[secret_index] or secret[secret_index] == WILD _CARD:
                secret_index += 1
                matched_secret += 1
                shopping_cart_index += 1
            else:
                shopping_cart_index = previous_scan_index
                start_cart_index += 1
                if secret_index != 0:
                    secret_index = 0
                    matched_secret = 0

        previous_scan_index = shopping_cart_index
    if secret_index == len(secret_code[-1]):
        return 1

return 0
```

```python
def isWinner(secret, shoppingCart):
  def isMatch(source, target):
    return target == "anything" or target == source

  index = 0
  secretIndex = 0 
  newIndex = index
  secretWordIndex = 0
  while secretIndex < len(secret) and newIndex < len(shoppingCart):
      if isMatch(shoppingCart[newIndex], secret[secretIndex][secretWordIndex]):
        newIndex+=1
        secretWordIndex+=1
        if secretWordIndex==len(secret[secretIndex]):
          index+=1
          index=newIndex
          secretWordIndex=0
      else:
        index+=1
        newIndex=index
        secretWordIndex=0
  return 1 if secretIndex == len(secret) else 0
```

### Items in Containers

```python
def numberOfItems(s, startIndicies, endIndicies):
  n = len(s)
  preSum = [0] * n
  leftCompIdx =[0] * n
  rightCompIdx = [0] * n
  sum = 0
  result = [0] * len(startIndicies)
  for i in range(n):
    if s[i] =="*":
      sum += 1
    preSum[i] = sum

  seen = -1
  for i in range(n):
    if s[i] =="|":
      seen = i
    leftCompIdx[i] = seen

  seen = -1
  for i in range(n-1, -1, -1):
    if s[i] =="|":
      seen = i
    rightCompIdx[i] = seen
  k = 0
  while k < len(startIndicies):
    start = startIndicies[k] - 1
    end = endIndicies[k] - 1
    if rightCompIdx[start] != -1 and leftCompIdx[end] != -1:
      result[k] = preSum[leftCompIdx[end]]- preSum[rightCompIdx[start]]
    k+=1

  return result
```

### Largest Item Association

```python
from collections import deque, defaultdict

def largest_item_association(item_association):

    item_map = defaultdict(set)

    for item_pair in item_association:
        item_map[item_pair[0]].add(item_pair[1])
        item_map[item_pair[1]].add(item_pair[0])

    largest_group = []
    visited = set()

    for key in item_map.keys():
        if key not in visited:
            curr_group = []
            q = deque()
            q.append(key)
            while q:
                curr = q.popleft()
                visited.add(curr)
                curr_group.append(curr)
                for neighbor in item_map[curr]:
                    if neighbor not in visited:
                        q.append(neighbor)
            if len(curr_group) > len(largest_group):
                largest_group = curr_group
            elif len(curr_group) == len(largest_group): 
                if largest_group > curr_group:
                    largest_group = curr_group

    largest_group.sort()
    return largest_group
```

### Turnstile

```python
def turnstile(time, direction):
    en, ex = [], []
    res = [0] * len(time)
    for i, t in enumerate(time):
        if direction[i] == 1:
            ex.append([time[i], i])
        else:
            en.append([time[i], i])
    
    timeCounter, lastTurn = 0, -1 # time is 0 at the beginning and -1 
                                # indicates nothing happened at prior time
    while ex or en:
        # Process the exit queue if and only if following conditions are satisfied
        # If exit queue is not empty and the person at the front of the queue can go out based on his time stamp
        # and ( Nothing happened at last time stamp i.e. nobody moved in or out so lastTurn will be -1 in this case
        # or, somebody moved out at last time stamp, in this case lastTurn will be 1
        # or, nobody is there in the entrance queue
        # or, at last time stamp somebody got in but the person at the front of the queue can't go in due to their timestamp  
        if ex and ex[0][0] <= timeCounter and \
        (lastTurn == -1 or lastTurn == 1 or not en or (lastTurn == 0 and en[0][0] > timeCounter)):
            res[ex[0][1]] = timeCounter
            lastTurn = 1
            ex.pop(0)
        elif en and en[0][0] <= timeCounter:
            res[en[0][1]] = timeCounter
            lastTurn = 0
            en.pop(0)
        else:
            lastTurn = -1

        timeCounter += 1
    
    return res
```

### Five Star Sellers

  ```python
def fiveStartReviews(productRatings, ratingsThreshold):
    count = 0
    tempList = productRatings.copy()

    while(getRating(tempList) < ratingsThreshold / 100):
        distinctList = []
        for productRating in tempList:
            distinct = ((productRating[0] + 1) / (productRating[1] + 1)
                        ) - ((productRating[0]) / (productRating[1]))
            distinctList.append(distinct)

        index = distinctList.index(max(distinctList))
        tempList[index][0] = tempList[index][0] + 1
        tempList[index][1] = tempList[index][1] + 1
        count = count + 1

    return count


def getRating(productRatings):
    sum = 0
    for i in productRatings:
        sum = i[0]/i[1] + sum

    return sum / len(productRatings)
  ```

### Minimum Difficulty of a Job Schedule/Best Beta

```python
def minDifficulty(self, A, d):
    n, inf = len(A), float('inf')
    if n < d: return -1
    dp = [inf] * n + [0]
    for d in range(1, d + 1):
        for i in range(n - d + 1):
            maxd, dp[i] = 0, inf
            for j in range(i, n - d + 1):
                maxd = max(maxd, A[j])
                dp[i] = min(dp[i], maxd + dp[j + 1])
    return dp[0]
```

### Autoscale Policy

```python
def autoScale(ins, A):
    lim_l, lim_h, th_l, th_h, idle = 1, int(1e8), 25, 60, 10
    i, n, ans = 0, len(A), ins
    while i < n:
        print(f'{i}-th second, utility is {A[i]}, instance number before action is {ans}')
        if A[i] < th_l and ans > lim_l:
            ans, i = (ans + 1) // 2, i + idle
        elif A[i] > th_h and ans <= lim_h:
            ans, i = ans * 2, i + idle
        i += 1
    return ans
```

### Top K Frequently Mentioned Keywords

```python
import collections
import heapq
import string
def topMentioned(keywords, reviews, k):
  def preprocess(word):
    result = ""
    for c in word:
      if c not in string.punctuation:
        result += c.lower()
    return result

  count = collections.Counter()
  kw = set([w.lower() for w in keywords]) 
  for review in reviews:
    seen = set() 
    words = review.split(" ") 
    for word in words:
      w = preprocess(word) 
      if w in kw and w not in seen:
        count[w] += 1
        seen.add(w)

  pq = []
  for key, val in count.items():
      heapq.heappush(pq, (-val, key))
  
  return [heapq.heappop(pq)[1] for _ in range(k)]
```

### Transaction Logs

```python
import heapq
import collections
def getFrauds(logs, threshold):
  count = collections.Counter()
  for log in logs:
    log = log.split(" ")
    user1 = log[0]
    user2 = log[1]
    count[user1] += 1
    count[user2] += 1
  pq = []
  for k, v in count.items():
    heapq.heappush(pq, (-int(k), v, k))
  ans = []
  for _ in range(len(pq)):
    _, freq, id = heapq.heappop(pq)
    if freq >= threshold: 
      ans.append(id)

  return ans
getFrauds(logs, threshold)
```

### Substrings of size K with K distinct chars

```python
def substringk(s, k):
    if not s or k == 0:
        return []
    
    letter, res = {}, set()
    start = 0
    for i in range(len(s)):
        if s[i] in letter and letter[s[i]] >= start:
            start = letter[s[i]]+1
        letter[s[i]] = i
        if i-start+1 == k:
            res.add(s[start:i+1])
            start += 1
    return list(res)
```

### Substrings of size K with K distinct chars

```python
import collections
def substringk(s, k):
    if not s or k == 0:
        return []
    ch = collections.Counter()
    ans = set()

    l, r = 0, 0
    while l <= r and r < len(s):
      ch[s[r]] += 1
      while ch[s[r]] > 1:
        ch[s[l]] -= 1
        l += 1
      if r - l + 1 == k:
        ans.add(s[l:r+1])
        ch[s[l]] -= 1
        l += 1 
      r += 1
    return list(ans)
```

### Number of islands

```python
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m = len(grid)
        if m < 1:
            return 0
        n = len(grid[0])
        
        def dfs(i,j):
            grid[i][j] = "0"
            if i + 1 < m and grid[i+1][j] == "1":
                dfs(i+1, j)
            if i - 1 >= 0 and grid[i-1][j] == "1":
                dfs(i-1, j)
            if j + 1 < n and grid[i][j+1] == "1":
                dfs(i, j+1)
            if j - 1 >= 0 and grid[i][j-1] == "1":
                dfs(i, j-1)
        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    dfs(i,j)
                    ans += 1
        return ans
```

### Most common words

```python
class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        bannedSet = set(banned)
        words = re.findall(r'\w+', paragraph.lower())
        counts = collections.Counter(w for w in words if w not in bannedSet)
        return max(counts, key=counts.get)
```

### K closest points to origin

```python
def kClosest(self, points, K):
        """
        :type points: List[List[int]]
        :type K: int
        :rtype: List[List[int]]
        """

        def quickSelect(arr, left, right, k):
            p = left
            l, r = left, right
            
            while l < r:
                while l < r and arr[r][0] >= arr[p][0]:
                    r -= 1
                while l < r and arr[l][0] < arr[p][0]:
                    l += 1

                arr[l], arr[r] = arr[r], arr[l]
            arr[p], arr[l] = arr[l], arr[p]  
            if l + 1 == k:
                return arr[:l+1]
            elif l + 1 < k:
                return quickSelect(arr, l + 1, right, k)
            else:
                return quickSelect(arr, left, l - 1, k)
        
        _index = {(points[i][0]**2 + points[i][1]**2): i for i in range(len(points))}  
        arr = [((y**2 + x**2), [y,x]) for y, x in points]
        kClosest = quickSelect(arr, 0, len(arr)-1, K)
        
        return [kClosest[i][1] for i in range(K)]
```

### Friend circle

```python
class Solution:
    def findCircleNum(self, M: List[List[int]]) -> int:
        ans, n = 0, len(M)
        for i in range(n):
            if M[i][i] == 1:
                self.dfs(M, i, n)
                ans += 1
        return ans
        
    def dfs(self, M, curr, n):
        for i in range(n):
            if M[curr][i] == 1:
                M[curr][i] = M[i][curr] = 0
                self.dfs(M, i, n)
```

### Partition label

```python
class Solution:
    def partitionLabels(self, S: str) -> List[int]:
        rightmost = {c: i for i,c in enumerate(S)}
        l, r = 0, 0
        ans = []
        for i, c in enumerate(S):
            # The rightmost position of the letter in the interval we visited so far
            r = max(r, rightmost[c])
            if i == r:
                ans.append(r - l + 1)
                l = i + 1
        return ans
```

### wildcard matching

```python
class Solution:
    def isMatch(self, s, p):
        length = len(s)
        #patter太長，字串太短
        if len(p) - p.count("*") > length: return False
        dp = [True] + [False] * length
        for i in p:
            if i != "*":
                for j in reversed(range(length)):
                    dp[j+1] = dp[j] and (i == "?" or i == s[j])
            else:
                for j in range(1, length + 1):
                    dp[j] = dp[j-1] or dp[j]
            dp[0] = dp[0] and i == "*"
        return dp[-1]  
```

### Recorder Data in log files

```python
class Solution:
    def reorderLogFiles(self, logs: List[str]) -> List[str]:
        def order(s):
            id_, payload = s.split(' ', 1)
            if payload[0].isalpha():
                return (0, payload, id_)
            else:
                return (1, None, None)
        
        return sorted(logs ,key=order)
```

### Shopping pattern

```python
import collections
def shoppingPattern(numOfProducts, products_from , products_to):
  map = collections.defaultdict(set)
  
  for i in range(len(products_from)):
    map[products_from[i]].add(products_to[i])
    map[products_to[i]].add(products_from[i])

  count = float('inf')
  for i in range(1, numOfProducts - 2):
    if len(map[i]) < 2: continue
    for j in range(i+1, numOfProducts - 1):
      for k in range(j+1, numOfProducts):    
        if j in map[i] and k in map[j] and i in map[k]:
          p = (len(map[i]) + len(map[j]) + len(map[k])) - 6
          count = min(count, p)
  return -1 if count == 0 else count
```

### Maximum Product of Splitted Binary Tree

```python
def maxProduct(self, root):
    self.res = total = 0

    def s(root):
        if not root: return 0
        left, right = s(root.left), s(root.right)
        self.res = max(self.res, left * (total - left), right * (total - right))
        return left + right + root.val

    total = s(root)
    s(root)
    return self.res % (10**9 + 7)
```

### Design a Stack With Increment Operation

```python
def __init__(self, maxSize):
        self.n = maxSize
        self.stack = []
        self.inc = []

    def push(self, x):
        if len(self.inc) < self.n:
            self.stack.append(x)
            self.inc.append(0)

    def pop(self):
        if not self.inc: return -1
        if len(self.inc) > 1:
            self.inc[-2] += self.inc[-1]
        return self.stack.pop() + self.inc.pop()

    def increment(self, k, val):
        if self.inc:
            self.inc[min(k, len(self.inc)) - 1] += val
```

### Third Maximum Number

```python
class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        max1 = -2**32
        max2 = -2**32
        max3 = -2**32
        for x in nums:
            if x == max1 or x == max2 or  x == max3: continue
            if x > max1:
                max3 = max2
                max2 = max1
                max1 = x
            elif x > max2:
                max3 = max2
                max2 = x
            elif x > max3:
                max3 = x
        return max1 if max3 == -2**32 else max3
```

### Sliding Window maximum

```python
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = collections.deque()
        ans = []
        for i in range(len(nums)):
            while q and nums[i] > q[-1]:
                q.pop()
            q.append(nums[i])
            #窗口的第一個>＝0
            if i - k + 1 >= 0: 
                ans.append(q[0])
            if nums[i - k + 1] == q[0]:
                q.popleft()
        return ans
```

### Longest Substring with At Most K Distinct Characters

```python
class Solution(object):
    def lengthOfLongestSubstringKDistinct(self, s, k):
        # Use dictionary d to keep track of (character, location) pair,
        # where location is the rightmost location that the character appears at
        d = {}
        low, ret = 0, 0
        for i, c in enumerate(s):
            d[c] = i
            while len(d) > k:
                tmp = low
                low = min(d.values())
                print(tmp, low)
                del d[s[low]]
                low += 1
            ret = max(i - low + 1, ret)
        return ret
```

### Split Array Largest Sum

```python
class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        l, r = max(nums), sum(nums) + 1
        
        def minSum(nums, limit):
            total = 0
            groups = 1
            for num in nums:
                if total + num > limit:
                    total = num
                    groups += 1
                else:
                    total += num
            return groups
                    
        while l < r:
            limit = (r - l) // 2 + l
            if minSum(nums, limit) > m:
                l = limit + 1
            else:
                r = limit 
        return l
```

### Label System

```python
k = 2
s = sorted(s)
length = len(s)
flag = 0
remains = list()
alike = s[-1] 
for i in range(len(s)-1,-1,-1):
    toset = list()
    if s[i] == alike and i == 0 :
        flag+=1
        toset = s[i+k : flag]
        del s[i+k : flag]
    elif s[i] == alike  :
        flag += 1
        continue
    elif s[i] != alike :
        if flag > k :
            j = i
            toset = s[i+1 : i+1+flag-k]
            del s[i+1 : i+1+flag-k]
            while toset and j >= 0 :
                if len(toset)<k :
                    while toset :
                        s.insert(j,toset[0])
                        toset.pop(0)
                else:
                    p = 0
                    while p < k :
                        s.insert(j,toset[0])
                        toset.pop(0)
                        p+=1
                j-=1
        flag = 1
        alike = s[i]
    if toset :
        remains.append(toset)

for i in range(len(remains)):
    j = 0
    while remains[i] and j < len(s)-1 :
        if s[j] != remains[i][0] and s[j+1] != remains[i][0] :
            if len(remains[i]) > k :
                p = 0
                while p < k :
                    s.insert(j+1,remains[i][0])
                    remains[i].pop(0)
                    p+=1
            else :
                while remains[i] :
                    s.insert(j+1,remains[i][0])
                    remains[i].pop(0)
        elif s[j] == remains[i][0] and s[max(0,j-1)] != remains[i][0]:
            if s[j:j+k+1].count(remains[i][0]) < k :
                rem = k - s[j:j+k+1].count(remains[i][0]) 
                while rem and remains[i] :
                    s.insert(j,remains[i][0])
                    remains[i].pop(0)
                    rem-=1 
        elif s[j+1] != remains[i][0] and j+1 == len(s)-1:
            p = 0
            while remains[i] and p < k :
                s.append(remains[i][0])
                remains[i].pop(0)
                p+=1
        j += 1

result = ''.join([i for i in s[::-1]])
print(result)
```

### Labelling System

```python
def newLabel(s, limit):
  n = len(s)
  charset = [0] * 128

  def nextAvailableChar(charset, start):
    for i in range(start - 1,-1,-1):
      if charset[i] > 0:
        charset[i] -= 1
        return chr(i)
    return None

  for i in range(n):
    charset[ord(s[i])] += 1
  ans = ""
  for i in range(len(charset) - 1, -1, -1):
    count = 0 
    while charset[i] > 0:
      ans += chr(i)
      charset[i] -= 1
      count += 1
      if charset[i] > 0 and count == limit:
        next = nextAvailableChar(charset, i)
        if not next:
          return ans
        ans += next
        count = 0
  return ans
```

### Merge two sorted list

```python
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(0)
        curr = dummy
        while l1 and l2:
            if l1.val > l2.val:
                l1, l2 = l2, l1
            curr.next = l1
            l1 = curr.next.next
            curr = curr.next
        curr.next = l1 or l2      
        return dummy.next 
```

### subtree of another tree

```python 
class Solution:
    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        if not s and not t: return True
        if not s or not t: return False
        return self.sameTree(s, t) or self.isSubtree(s.left, t) or self.isSubtree(s.right, t) 
    
    def sameTree(self, s, t):
        if not s and not t : return True
        if not s or not t: return False
        return s.val == t.val and self.sameTree(s.left, t.left) and self.sameTree(s.right, t.right)
```

### Maximal Square

```python
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if len(matrix) == 0: return 0
        m, n = len(matrix), len(matrix[0])
        dp = [[0] * (n+1) for _ in range(m+1)]
        dp[1][1] = 1
        for i in range(1, m+1):
            for j in range(1, n+1):
                if matrix[i-1][j-1] == "1":
                    dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
                else:
                    dp[i][j] = 0
        return max(map(max, dp)) ** 2
```

### throttling gateway

```python
import collections
def droppedRequests(requestTime):
    # Write your code here

    Q1 = []
    Q20 = []
    Q60 = []
    count = 0
    for v in requestTime:
        while len(Q1) > 0 and  v - Q1[0] >= 1:
            Q1.pop(0)
        while len(Q20) > 0 and  v - Q20[0] >= 10:
            Q20.pop(0)
        while len(Q60) > 0 and  v - Q60[0] >= 60:
            Q60.pop(0)
        drop = 0
        if len(Q1) < 3:
            Q1.append(v)
        else:
            drop = 1
            if len(Q1) > 0:
                Q1.pop(0)
                Q1.append(v)

        if len(Q20) < 20:
            Q20.append(v)
        else:
            drop = 1
            if len(Q20) > 0:
                Q20.pop(0)
                Q20.append(v)
        
        if len(Q60) < 60:
            Q60.append(v)
        else:
            drop = 1
            if len(Q60) > 0:
                Q60.pop(0)
                Q60.append(v)
        count += drop
        # print(Q1, Q20, Q60)


    return count
```

### Unique Device Name

```python
import collections
def getUniqueNames(num, devices):
  seen = collections.Counter()
  for i in range(len(devices)):
    name = devices[i]
    if devices[i] in seen:
      name = devices[i] + str(seen[devices[i]])    
    seen[devices[i]] += 1
    devices[i] = name
  return devices
```

### Slow key press

```python
class Solution:
    def slowestKey(self, releaseTimes: List[int], keysPressed: str) -> str:
        maximum, ans = releaseTimes[0], keysPressed[0]
        for i in range(1, len(releaseTimes)):
            diff = releaseTimes[i] - releaseTimes[i-1]
            word = keysPressed[i]
            if diff > maximum:
                maximum, ans = diff, word
            elif diff == maximum and word > ans:
                ans = word
        return ans
```

### Unique pairs

```python
def uniqueTwoSum(nums, target):
    ans = set()
    for n in nums:
        c = target-n
        if c in nums and c >= n:
            ans.add((n, c))
    return len(ans)
```


### Amazon music pair

```python
class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        cache = [0] * 60
        ans = 0
        for t in time:
            ans += cache[t%60]
            cache[-t%60] += 1         
        return ans
```


