Google | Onsite about leetcode

[tech-cow]

算法

高频

Money Exchange

计算汇率，类似 LC 399 例子:
把file1分成两个list， 完全转化成了LC399

file1:  
USD, GBP, 0.69 \\USD = 0.69 * GBP
Meter, Yard, 1.09

file2: USD, Yard

output:  
USD, Yard, 0.69*1.09

创建equations和values中间的关系
然后肉一个BFS
最后把queries里面的所有都走一遍。

class Solution(object):
    def calcEquation(self, equations, values, queries):
        self.graph = {}
        self.build_graph(equations, values)
        return [self.find_path(q) for q in queries]
    
    
    def build_graph(self, equations, values):
        def add_edge(f, t, value):
            if f in self.graph:
                self.graph[f].append((t, value))
            else:
                self.graph[f] = [(t, value)]

        for vertices, value in zip(equations, values):
            f, t = vertices
            add_edge(f, t, value)
            add_edge(t, f, 1/value)
            
            
    def find_path(self, query):
        b, e = query
        if b not in self.graph or e not in self.graph:
            return -1.0
        q = collections.deque([(b, 1.0)])
        visited = set()
        while q:
            front, cur_product = q.popleft()
            if front == e:
                return cur_product
            visited.add(front)
            for neighbor, value in self.graph[front]:
                if neighbor not in visited:
                    q.append((neighbor, cur_product*value))
        return -1.0

---

Unique Paths

有个matrix， 从左上角走到右上角多少种方法，走法: (右上，右下，右)
follow up1: 必须经过一些点到达 一共多少种走法
follow up2: 必须越过某column ci 到达左下 一共多少种走法

参考LC里面的unique path，多加几个corner case。

class Solution:
    def uniquePaths(self, m, n):
        if not m or not n:
            return 0
        dp = [[1] * n] * m
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]

---

Minimum Cost to Hire K Workers

LC有这道题了，sort一遍按照(wage/quality)的ratio, 保证放入heap里面的是从性价比最高的考试，当放入的大小超出heap规定的k，找到heap里面quality最高的，因为超出k的时候，代表这个时候放入的值相对应的性价比会拉爆团队，这时候及时之前性价比高的员工，也会因为新的ratio而变得很贵，这时候约高的quality越贵。

class Solution(object):
    def mincostToHireWorkers(self, quality, wage, K):
        workers = []
        for w, q in zip(wage, quality):
            workers.append((float(w)/q, q))
        workers.sort()
        
        res = float('inf')
        qsum = 0
        heap = []
        for r, q in workers:
            heapq.heappush(heap, -q)
            qsum += q
            if len(heap) > K: 
                qsum += heapq.heappop(heap)
            if len(heap) == K: 
                res = min(res, qsum * r)
        return res

---

Delete node in Doubly Linked List

先把可能的edge case都处理了再考虑普通的case。
面试官都问了你会用什么样的test case

'''
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None
'''

def deleteNode(head, pos):
    cur = head
    if pos == 1:
        head = head.next
        head.prev = None
        return
    while cur.next and pos - 1 > 0:
        cur = cur.next
        pos -= 1
    cur.prev.next = cur.next

Array | String | Hash

Maximize Distance to Closest Person

Example 1:

Input: [1,0,0,0,1,0,1]
Output: 2
Explanation:
If Alex sits in the second open seat (seats[2]), then the closest person 
has distance 2.
If Alex sits in any other open seat, the closest person has distance 1.
Thus, the maximum distance to the closest person is 2.

Example 2:

Input: [1,0,0,0]
Output: 3
Explanation:
If Alex sits in the last seat, the closest person is 3 seats away.
This is the maximum distance possible, so the answer is 3.

复杂答案：

class Solution(object):
    def maxDistToClosest(self, nums):
        res = 1
        l, r = 0, 0
        for i, num in enumerate(nums):
            if num == 0:
                r += 1
            elif num == 1:
                r = i
                if nums[l] == 0 :    #0001
                    res = max(res, r - l)
                else:
                    if (r - l - 1) % 2 == 0:      # odd
                        res = max(res, (r - l - 1) // 2)
                    else:                         # even
                        res = max(res, (r - l) // 2)
                l = i   
        return max(res, r - l)

简答：

class Solution:
    def maxDistToClosest(self, seats):
        
        start, n, ans = -1, len(seats), 0
        for index, value in enumerate(seats):
            if value == 0: continue
            ans = index if start == -1 else max(ans, (index-start)//2)
            start = index
        return ans if seats[n-1] == 1 else max(ans, n-1-start)

---

Coins in a Line

• State: 定义一个人的状态: dp[i], 现在还剩i个硬币，现在当前取硬币的人最后输赢状况
• Function: 考虑两个人的状态做状态更新: dp[i] = (!dp[i-1]) || (!dp[i-2])
• Intialize: dp[0] = false , dp[1] = true, dp[2] = true
• Answer: dp[n]

public class Solution {
    public boolean firstWillWin(int n) {
        boolean[] dp = new boolean[n + 1];
        boolean[] flag = new boolean[n + 1];
        return search(n, dp, flag);
    }

    boolean search(int i, boolean[] dp, boolean[] flag) {
        if (flag[i] == true) {
            return dp[i];
        }
        if (i == 0) {
            dp[i] = false;
        } else if (i == 1) {
            dp[i] = true;
        } else if (i == 2) {
            dp[i] = true;
        } else {
            dp[i] = ! (search(i - 1, dp, flag) && search(i - 2, dp, flag));
        }
        flag[i] = true;
        return dp[i];
    }
}

---

Equilibrium index of an array

数组平衡index 就是在数组中找到一个index 他的左边和 跟右边和相等

input : A[] = [-7, 1, 5, 2, -4, 3, 6]
output : 3
3 is an equilibrium index, because:
A[0] + A[1] + A[2]  =  A[4] + A[5] + A[6]

用sum扫一遍得到cur_sum，第二次迭代用一个函数记录到目前为止的left_sum，比对此两个的值，然后相应的增加和减少即可。

import unittest
def equilibrium(nums):
    cur_sum = sum(nums)
    leftsum = 0
    for i, num in enumerate(nums):
        cur_sum -= num
        if leftsum == cur_sum: return i
        leftsum += num
    return -1


class MyTest(unittest.TestCase):
    def test(self):
        self.assertEqual(equilibrium([-7, 1, 5, 2, -4, 3, 0]), 3)
        self.assertEqual(equilibrium([1, 0, 1]), 1)

if __name__ == '__main__':
    unittest.main()

可能变种：

find the center of mass in a 2D array.

---

Extended Word

连续3个相同char，返回他们起始和结尾的index

input: 'helllooo'
output: [2,4,5,7]

Follow up:
给定值word是否在特定的isExtendedInDictionary内
如果 ”helo“，”hello“ 或者 ”hello“ 之中的任何一个在dictionary，就返回 ”helllo“

#给予下面方程
def in_dictionary()

input: "helllo"
dic = ['helo'] #True
dic = ['hello'] #True
dic = ['helllo'] #True

Tree

Tree Traversal

Preorder

class Solution(object):
    def preorderTraversal(self, root):
        res = []
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                res.append(node.val)
                stack.append(node.right)
                stack.append(node.left)
        return res

Postorder

class Solution(object):
    def postorderTraversal(self, root):
        res, stack = [], [(root, False)]
        while stack:
            node, visited = stack.pop()
            if node:
                if visited:
                    res.append(node.val)
                else:
                    stack.append((node, True))
                    stack.append((node.right, False))
                    stack.append((node.left, False))
        return res

Level-order

class Solution(object):
    def levelOrder(self, root):
        res = []
        if not root: return res
        q = [root]
        
        while q:
            res.append([node.val for node in q])
            temp = []
            for node in q:
                if node.left: 
                    temp.append(node.left)
                if node.right:
                    temp.append(node.right)
            q = temp
        
        return res

---

Binary Tree Maximum Path Sum

要考虑 left + right + root.val 和 left + root.val 和 right + root.val的三种最大可能性

class Solution(object):
    def maxPathSum(self, root):
        self.res = - float('inf')
        self.dfs(root)
        return self.res

    
    def dfs(self, root):
        if not root: return 0
        left = self.dfs(root.left)
        right = self.dfs(root.right)
        self.res = max(self.res, left + right + root.val)
        cur_max = max(left, right) + root.val
        return cur_max if cur_max > 0 else 0

---

Binary Expression Tree

一个数组 数组里存着加减乘除的顺序 可能是+-*/ 可能是* - + /之类的

input = '1 * 9 - 3 +2 *7'

output = 

	  + 
    /   \
   -     *
  / \   / \
 *   3 2  7 
/ \
1  9

class Et: 
    def __init__(self , value):
        self.value = value
        self.left = None
        self.right = None
 
def isOperator(c):
    if (c == '+' or c == '-' or c == '*'
        or c == '/' or c == '^'):
        return True
    else:
        return False
 
def inorder(t):
    if t is not None:
        inorder(t.left)
        print t.value,
        inorder(t.right)
 

def constructTree(postfix):
    stack = []
    for char in postfix :
        if not isOperator(char):
            t = Et(char)
            stack.append(t)
        else:
            t = Et(char)
            t1 = stack.pop()
            t2 = stack.pop()
               
            t.right = t1
            t.left = t2
            stack.append(t)
    t = stack.pop()
    
    return t
 

# test
postfix = "ab+ef*g*-"
r = constructTree(postfix)
print "Infix expression is"
inorder(r)

---

220系列 123

120. Triangle

165. Compare Version Numbers

750 Number Of Corner Rectangles

Tree Isomorphism Problem

LC 815. Bus Routes (bfs)
LC 205. Isomorphic Strings (Hash)

输入一个整数n 输出叶子树量为n的所有full binary tree

DFS/BFS

778. Swim in Rising Water

判断一个单词是不是在char[][] array。八个直线方向，上，下，左，右，左上，右上，左下，右 下。不能拐弯。比LC需要dfs的那道题简单

无向图 [A-B，B-C]表示AB和BC直接 相连，AC间接相连，让实现两个函数返回两个点是否直接相连，是否间接相连（DFS）
Follow up: 就是会query很多次这两个函数怎么优化。

图79. Word Search

Rebuild array: given a list of subsequences of an original array, rebuild a shortest unique original array by using the list of subsequence.
e.g., given [[1, 9, 7], [1, 4], [4, 9]], the shortest unique original array is [1, 4, 9, 7]
Follow up: the original array may contain duplicates, return shortest smallest lexicographical order array if multiple arrays can be reconstructed.
e.g.,given [[2, 3], [3, 3, 3]], return [2, 3, 3, 3], 虽然[3, 2, 3, 3], [3, 3, 2, 3]也可以build, 但不是最 小。

n-ary tree

LC 365. Water and Jug Problem

Insert a number in the ordered array.

设计一个api，求解2个狗是否有血缘关系，每个狗在记录里都有可能有爸爸妈妈，然后如果共享 ，就是一家人了 (二叉树)

[tech-cow]

设计

Design Hashmap

前提设定：

• For simplicity, are the keys integers only? Yes
• For collision resolution, can we use chaining? Yes
• Do we have to worry about load factors? No
• Can we assume inputs are valid or do we have to validate them? Assume they're valid
• Can we assume this fits memory? Yes

class Item(object):

    def __init__(self, key, value):
        self.key = key
        self.value = value

class HashTable(object):

    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(self.size)]

    def _hash_function(self, key):
        return key % self.size

    def set(self, key, value):
        hash_index = self._hash_function(key)
        for item in self.table[hash_index]:
            if item.key == key:
                item.value = value
                return
        self.table[hash_index].append(Item(key, value))

    def get(self, key):
        hash_index = self._hash_function(key)
        for item in self.table[hash_index]:
            if item.key == key:
                return item.value
        raise KeyError('Key not found')

    def remove(self, key):
        hash_index = self._hash_function(key)
        for index, item in enumerate(self.table[hash_index]):
            if item.key == key:
                del self.table[hash_index][index]
                return
        raise KeyError('Key not found')

电梯

广告系统