Sentence Similarity II

Posted on September 25, 2019 by elfsong

Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar.

For example, words1 = ["great", "acting", "skills"] and words2 = ["fine", "drama", "talent"] are similar, if the similar word pairs are pairs = [["great", "good"], ["fine", "good"], ["acting","drama"], ["skills","talent"]].

Note that the similarity relation is transitive. For example, if “great” and “good” are similar, and “fine” and “good” are similar, then “great” and “fine” are similar.

Similarity is also symmetric. For example, “great” and “fine” being similar is the same as “fine” and “great” being similar.

Also, a word is always similar with itself. For example, the sentences words1 = ["great"], words2 = ["great"], pairs = [] are similar, even though there are no specified similar word pairs.

Finally, sentences can only be similar if they have the same number of words. So a sentence like words1 = ["great"] can never be similar to words2 = ["doubleplus","good"].

Note:

The length of words1 and words2 will not exceed 1000.
The length of pairs will not exceed 2000.
The length of each pairs[i] will be 2.
The length of each words[i] and pairs[i][j] will be in the range [1, 20].

class Solution:
    def areSentencesSimilarTwo(self, words1: List[str], words2: List[str], pairs: List[List[str]]) -> bool:
        parent = {}
        
        if len(words1) != len(words2):
            return False
        
        def find(w):
            if w not in parent:
                return w
            if parent[w] != w:
                w = find(parent[w])
            return w
        
        
        def union(w1, w2):
            parent[w1] = w2
        
        
        for pair in pairs:
            union(find(pair[0]), find(pair[1]))
        
        
        for word_pair in zip(words1, words2):
            if word_pair[0] == word_pair[1]:
                continue
            else:
                leader1 = find(word_pair[0])
                leader2 = find(word_pair[1])
                if leader1 == leader2:
                    continue
                else:
                    return False
        return True

Campus Bikes II

Posted on September 24, 2019 by elfsong

On a campus represented as a 2D grid, there are N workers and M bikes, with N <= M. Each worker and bike is a 2D coordinate on this grid.

We assign one unique bike to each worker so that the sum of the Manhattan distances between each worker and their assigned bike is minimized.

The Manhattan distance between two points p1 and p2 is Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.

Return the minimum possible sum of Manhattan distances between each worker and their assigned bike.

Example 1:

Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]
Output: 6
Explanation: 
We assign bike 0 to worker 0, bike 1 to worker 1. The Manhattan distance of both assignments is 3, so the output is 6.

Example 2:

Input: workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]
Output: 4
Explanation: 
We first assign bike 0 to worker 0, then assign bike 1 to worker 1 or worker 2, bike 2 to worker 2 or worker 1. Both assignments lead to sum of the Manhattan distances as 4.

Note:

0 <= workers[i][0], workers[i][1], bikes[i][0], bikes[i][1] < 1000
All worker and bike locations are distinct.
1 <= workers.length <= bikes.length <= 10

from functools import lru_cache

class Solution:
    def dis(self, a, b):
        return abs(a[0] - b[0]) + abs(a[1] - b[1])
        
    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:
        @lru_cache(None)
        def dfs(p, arr):
            return 0 if p == self.W else min([self.dis(bikes[i], workers[p]) + dfs(p + 1, arr + 2 ** i) for i in range(self.B) if not (arr>>i) & 1])

        self.W = len(workers)
        self.B = len(bikes)
        
        return dfs(0, 0)

Delete Nodes And Return Forest

Posted on September 23, 2019 by elfsong

Given the root of a binary tree, each node in the tree has a distinct value.

After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).

Return the roots of the trees in the remaining forest. You may return the result in any order.

Example 1:

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

Constraints:

The number of nodes in the given tree is at most 1000.
Each node has a distinct value between 1 and 1000.
to_delete.length <= 1000
to_delete contains distinct values between 1 and 1000.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:    
    def delNodes(self, root, to_delete):
        """
        :type root: TreeNode
        :type to_delete: List[int]
        :rtype: List[TreeNode]
        """
        self.forests = []
        self.delete = to_delete
        
        node = self.divideAndConquer(root)
        
        if node:
            self.forests.append(node)
        
        return self.forests
    
    def divideAndConquer(self, node):
        
        if not node:
            return None
        
        left = self.divideAndConquer(node.left)
        right = self.divideAndConquer(node.right)
        
        if node.val not in self.delete:
            node.left = left
            node.right = right
            return node
        else:
            if left:
                self.forests.append(left)
            if right:
                self.forests.append(right)
                
            return None

Mood Journey

Posted on September 23, 2019 by elfsong

今天是周一，联系了一下之前微软的Manager。

正好他也是我AA面试的面试官，所以想问问他我面试的情况。

不过不太好的消息是，根据他的反馈，小冰今年的HC有点吃紧，候选人有点多。其实感觉就是变相劝退了。

知道这个消息当然是有点难受的。不过总会遇到挫折的嘛，还有很多机会在等着我。

我猜这是最后一篇Microsoft Time的文章了，希望可以安心刷题，找到心仪的工作吧。

Union-Find Python Implementation

Posted on September 22, 2019 by elfsong

class UF:
    def __init__(self, n):
        self.p = list(range(n))

    def union(self, x, y):
        self.p[self.find(x)] = self.find(y)

    def find(self, x):
        if x != self.p[x]:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

Minimum Knight Moves

Posted on September 21, 2019 by elfsong

In an infinite chess board with coordinates from -infinity to +infinity, you have a knight at square [0, 0].

A knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.

Return the minimum number of steps needed to move the knight to the square [x, y]. It is guaranteed the answer exists.

Example 1:

Input: x = 2, y = 1
Output: 1
Explanation: [0, 0] → [2, 1]

Example 2:

Input: x = 5, y = 5
Output: 4
Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]

class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        x, y = abs(x), abs(y)
        
        q = collections.deque([(0,0,0)])
        seen = set([(0,0)])

        while q:
            s_x, s_y, s = q.popleft()
            if (s_x, s_y) == (x,y):
                return s

            d = []
            for dx, dy in [(-2,-1),(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2)]:
                n_x = s_x + dx
                n_y = s_y + dy
                if -2 <= n_x <= x and -2 <= n_y <= y:
                    d.append((n_x,n_y))

            d.sort(key=lambda e: abs(x-e[0]) + abs(y-e[1]))

			# only enqueue towards the 2 directions closest to the x,y
            for n_x,n_y in d[:2]:
                if (n_x, n_y) not in seen:
                    q.append((n_x,n_y,s+1))
                    seen.add((n_x,n_y))

Sum Root to Leaf Numbers

Posted on September 21, 2019 by elfsong

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Note: A leaf is a node with no children.

Example:

Input: [1,2,3]
    1
   / \
  2   3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        def getNumbers(root, previous, result):
            if not root:
                return
            
            current = previous*10 + root.val
            
            if not root.left and not root.right:
                result[0] += current
            
            getNumbers(root.left, current, result)
            getNumbers(root.right, current, result)
            
        ans = [0]
        getNumbers(root, 0, ans)
        return ans[0]

Decode ways

Posted on September 20, 2019 by elfsong

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

class Solution:
    def numDecodings(self, s: str) -> int:        
        if s[0] == '0': return 0
        
#         N = len(s)
#         dp = [1 for i in range(N+1)]
        
        for i in range(1, len(s)):
            if s[i] == '0':
                # dp[i] = 0
                b = 0
            if int(s[i-1:i+1]) <= 26:
                # dp[i+1] = dp[i] + dp[i-1]
                c = b+a
            else:
                # dp[i+1] = dp[i]
                c = b
            a=b
            b=c
            
        return dp[-1]

Unique Binary Search Trees II

Posted on September 20, 2019 by elfsong

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.

Example:

Input: 3
Output:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from functools import lru_cache

class Solution:
    def generateTrees(self, n):
        if n == 0: return []
        
        @lru_cache(maxsize=None)
        def generate(start, end):
            ans = []
            
            if start > end: return [None]

            for i in range(start, end+1):
                for left_node in generate(start, i-1):
                    for right_node in generate(i+1, end):
                        node = TreeNode(i)
                        node.left = left_node
                        node.right = right_node
                        ans.append(node)

            return ans

        return generate(1, n)

2 Keys Keyboard

Posted on September 19, 2019 by elfsong

Initially on a notepad only one character ‘A’ is present. You can perform two operations on this notepad for each step:

Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
Paste: You can paste the characters which are copied last time.

Given a number n. You have to get exactly n ‘A’ on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n ‘A’.

Example 1:

Input: 3
Output: 3
Explanation:
Intitally, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.

Note:

The n will be in the range [1, 1000].

from functools import lru_cache

class Solution:
    def minSteps(self, n: int) -> int:
        
#         @lru_cache(None)
#         def operation(notepad, current):
#         def operation(notepad, current):
#             if len(current) <= n:
#                 if len(current) == n:
#                     return 0

#                 # no notepad
#                 t1 = (operation(current, current) if not notepad else 0x7777777) + 1

#                 # paste from notepad
#                 t2 = (operation(notepad, current + notepad) if notepad else 0x7777777) + 1

#                 # update notepad
#                 t3 = (operation(current, current) if notepad and notepad != current else 0x7777777) + 1

#                 return min(t1, t2, t3)

#             else:
#                 return 0x7777777

#         result = operation(0, "A")

#         return result

        if n == 1: 
            return 0
        
        for i in range(2,n+1):
            if n % i == 0: 
                return i + self.minSteps(int(n/i))

凛冬之怒

无为善道止战非攻

Author Archives: elfsong

Sentence Similarity II

Campus Bikes II

Delete Nodes And Return Forest

Mood Journey

Union-Find Python Implementation

Minimum Knight Moves

Sum Root to Leaf Numbers

Decode ways

Unique Binary Search Trees II

2 Keys Keyboard