0%

Ranking: 606 / 8175 😔😂😭

Q1. 5177. Reformat Date

Given a date string in the form Day Month Year, where:

Day is in the set {“1st”, “2nd”, “3rd”, “4th”, …, “30th”, “31st”}.
Month is in the set {“Jan”, “Feb”, “Mar”, “Apr”, “May”, “Jun”, “Jul”, “Aug”, “Sep”, “Oct”, “Nov”, “Dec”}.
Year is in the range [1900, 2100].
Convert the date string to the format YYYY-MM-DD, where:

YYYY denotes the 4 digit year.
MM denotes the 2 digit month.
DD denotes the 2 digit day.

Note

Very straight forward. Just do the string conversion.

1
2
3
4
5
6
7
8
class Solution:
def reformatDate(self, date: str) -> str:
m_to_idx = ["Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"]
day, month, year = date.split()
day, month = day[:-2], str(m_to_idx.index(month)+1)
if len(day) < 2: day = '0' + day
if len(month) < 2: month = '0' + month
return f'{year}-{month}-{day}'
Read more »

Ranking: 133 / 14301 😋😋😋

Q1. 1502. Can Make Arithmetic Progression From Sequence

Given an array of numbers arr. A sequence of numbers is called an arithmetic progression if the difference between any two consecutive elements is the same.

Return true if the array can be rearranged to form an arithmetic progression, otherwise, return false.

Note

Was not clear about the description at the very beginning.
The question is easy after fully understand the description.

1
2
3
4
5
class Solution:
def canMakeArithmeticProgression(self, A: List[int]) -> bool:
A = sorted(A)
dis = A[0] - A[1]
return all(a-b==dis for a, b in zip(A, A[1:]))
Read more »

Pre

Before we try to convert any recursive algo into non-recursive, we should be familiar to recursive and non-recursive version of binary tree traversal.
Read binary tree traversal to recap.

Key points

  1. The idea is use stack in heap to mimic the behavior of function call stack.
  2. For post-order traversal, since we need to update parent’s state from child node, we will need to push state of parent along with child node into stack. We will explain this later with example.

Post order

Code skeleton

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
rst = []
stack, cur = [], root
while cur or stack:
while cur:
# Push current node
stack.append(cur)
# move to left or right child
cur = cur.left or cur.right
# all child is processed.
cur = stack.pop()
# update current state based on state from child nodes
rst.append(cur.val)
# upload state to parent
# ...

# Move to right node or previous level
if stack and stack[-1].left == cur:
cur = stack[-1].right
else:
cur = None
return rst
  1. Lowest Common Ancestor of a Binary Tree
    Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
'''
# Recursive
def dfs(cur):
if cur is None: return 0, None
cnt_l, node_l = dfs(cur.left)
cnt_r, node_r = dfs(cur.right)
if cnt_l == 2: return 2, node_l
if cnt_r == 2: return 2, node_r

if (cnt_l+cnt_r+(cur.val in [p.val, q.val])) == 2: return 2, cur

return (1, cur) if cur.val in [p.val, q.val] else ((cnt_l, node_l) if cnt_l else (cnt_r, node_r))
return dfs(root)[1]
'''

# Non-recursive
ret = [0] * 4 # cnt_l, node_l, cnt_r, node_r
stack, cur = [], ((root, [0] * 4), ret, 'l') # Carry all necessary data for current node and parent node
while cur[0][0] or stack:
while cur[0][0]:
stack.append(cur)
if cur[0][0].left: cur = ((cur[0][0].left, [0]*4), cur[0][1], 'l')
else: cur = ((cur[0][0].right, [0]*4), cur[0][1], 'r')
# Pop and unpack node and state
# ((cur_node, cur_state), (parent...), dir)
(node, (cnt_l, node_l, cnt_r, node_r)), p_state, dir = stack.pop()

# Compute local state based on state from childs
if cnt_l == 2: my_ret = 2, node_l
elif cnt_r == 2: my_ret = 2, node_r
elif (cnt_l+cnt_r+(node.val in [p.val, q.val])) == 2: my_ret = 2, node
else: my_ret = (1, node) if node.val in [p.val, q.val] else ((cnt_l, node_l) if cnt_l else (cnt_r, node_r))

# Upload state to parent
if dir == 'l': p_state[:2] = my_ret
else: p_state[2:] = my_ret

# :) Move to right or previous level
if stack and stack[-1][0][0].left == node:
cur = ((stack[-1][0][0].right, [0] * 4), stack[-1][0][1], 'r')
else:
cur = ((None, None), (None, None), None)

return ret[1]

More example

Ranking: 429 / 13808 😋

Q1. 1486. XOR Operation in an Array

Given an integer n and an integer start.
Define an array nums where nums[i] = start + 2*i (0-indexed) and n == nums.length.
Return the bitwise XOR of all elements of nums.

Very straight forward.

1
2
3
4
5
6
7
class Solution:
def xorOperation(self, n: int, start: int) -> int:
arr = [start+2*i for i in range(n)]
rst = 0
for a in arr:
rst ^= a
return rst
Read more »

Ranking: 678 / 8571

Q1. 1475. Final Prices With a Special Discount in a Shop

Given the array prices where prices[i] is the price of the ith item in a shop. There is a special discount for items in the shop, if you buy the ith item, then you will receive a discount equivalent to prices[j] where j is the minimum index such that j > i and prices[j] <= prices[i], otherwise, you will not receive any discount at all.
Return an array where the ith element is the final price you will pay for the ith item of the shop considering the special discount.

Solved it by using brute force in contest. O(N^2)

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def finalPrices(self, prices: List[int]) -> List[int]:
rst = []
for i, price in enumerate(prices):
for j in range(i+1, len(prices)):
if prices[j] <= price:
rst.append(price-prices[j])
break
else:
rst.append(price)
return rst

Intuition

  1. Subtract each value by next smaller number
  2. Equivalent to subtract each value from all its previous greater number
  3. Monotonic stack !!!
1
2
3
4
5
6
7
8
9
class Solution:
def finalPrices(self, prices: List[int]) -> List[int]:
# Next smaller num
stack = []
for i, v in enumerate(prices):
while stack and prices[stack[-1]] >= v:
prices[stack.pop()] -= v
stack.append(i)
return prices
Read more »

Ranking: 2148 / 13794 😭

Q1. 5453. Running Sum of 1d Array

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).
Return the running sum of nums.

Equivalent to compute prefix-sum.

1
2
3
4
5
6
class Solution:
def runningSum(self, nums: List[int]) -> List[int]:
rst = [0] * (len(nums)+1)
for i, v in enumerate(nums):
rst[i+1] = rst[i] + v
return rst[1:]
Read more »

What can Kafka do?

  • Kafka as a Messaging System
    • Combination of two traditional queuing systems
      • queuing
        Scalable but not extendable. Data is gone after consumed
      • publish-subscribe
        Not scalable since every subscriber will receive a copy of new messages
    • Provide string order guarantee in a partition
      YES, no global ordering across multiple partitions in a topic
  • Kafka as a Storage System
    • Data is written on disk and replicated for fault-tolerance
    • Provide write on acknowledgement
    • Perform the same whether the data is 50KB or 50TB
  • Kafka for a Stream Processing
    • Handling out-of-order data
      • Use event time rather than processing time to provide a deterministic result
    • Performing stateful computations
      • uses Kafka for stateful storage
    • Reprocessing input as code changes
Read more »

The following syntax looks very handy in many case.

1
2
3
4
5
6
7
8
Python 3.7.3 (default, Mar 27 2019, 09:23:15)
[Clang 10.0.1 (clang-1001.0.46.3)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> a, *args = [1, 2, 3, 4]
>>> a
1
>>> args
[2, 3, 4]

I can understand what does those code try to do easily. Yeah, this is the magic of Python. :-)
But I had a hard time to find the semantic explanation for the syntax.

I was thinking about

  1. Arbitrary Argument Lists
    But this is not function signature. And Arbitrary Argument Lists will construct *args as a tuple rather than a list.

  2. Unpacking Argument Lists
    As the name suggested, this syntax unpacking a list or tuple rather than create a new list.

Read more »

topological ordering is possible only if the graph is a DAG(Directed Acyclic Graph).

Time Complexity: V + E

  • E is the number of edges
  • V is the number of vertices

Implementation (Kahn’s Algorithm)

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#!/usr/local/bin/python3

from typing import List
from collections import defaultdict

def topological_sort(vertices: int, edges: List[List[int]]) -> List[int]:
'''
Args:
vertices: 0, 1, 2, .... , vertices-1
edges: (start, end, weight)
Return:
A valid topological ordering
Raise:
ValueError: if there is not a valid topological ordering.
'''
# build graph
graph, indegrees = defaultdict(set), [0] * vertices
for (start, end, weight) in edges:
graph[start].add(end)
indegrees[end] += 1
# find vertices have zero indegree
zero_degrees = [vertex for vertex, indegree in enumerate(indegrees) if indegree == 0]
ordering = []
while zero_degrees:
vertex = zero_degrees.pop()
ordering.append(vertex)
for successor in graph[vertex]:
indegrees[successor] -= 1
if indegrees[successor] == 0:
zero_degrees.append(successor)
if len(ordering) != vertices:
raise ValueError('There is not a valid topological ordering')
return ordering


ordering = topological_sort(5, [[0, 1, 2], [0, 2, 5], [1, 3, 3], [2, 4, 10], [3, 4, 3]])
print('->'.join([str(vertex) for vertex in ordering]))
Read more »