Yong's Blog
0%

Posted on In Views: Valine:

Ranking: 1197 / 15151 😔😂😭

Q1. 1518. Water Bottles

Given numBottles full water bottles, you can exchange numExchange empty water bottles for one full water bottle.

The operation of drinking a full water bottle turns it into an empty bottle.

Return the maximum number of water bottles you can drink

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def numWaterBottles(self, A: int, B: int) -> int:
        ret = 0
        while A:
            if A >= B:
                drink = (A // B) * B
            else:
                drink = A
            ret += drink
            A = A - drink + drink // B
        return ret
Read more »

Posted on Edited on In Views: Valine:

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 »

Posted on In Views: Valine:

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 »

Posted on Edited on In Views: Valine:

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

Posted on Edited on In Views: Valine:

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 »

Posted on In Views: Valine:

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 »

Posted on In Views: Valine:

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 »

Posted on Edited on In Views: Valine:

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 »

Posted on In Views: Valine:

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 »