yp onsite 11-20
P11 最后一个中国大哥萌萌哒，跟我聊了半个小时的天，然后让我design yelp's most recent reviews of your friends的API，然后一些简单的runtime问题，最后大哥还非常贴心地介绍了一下Yelp整个的构架。
直接根据timestamp来sort?用一个max heap？然后根据最近的一个一个Pop出来。
P12 第一轮白人大叔还是小哥来着。先让我讲讲我实习的project，然后是coding题目是 leetcode 03
其实我觉得这道题有点难啊
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
start = 0
dic = {}
res = 0
for i in range(len(s)):
if s[i] in dic and start<=dic[s[i]]:
start = dic[s[i]]+1
dic[s[i]] = i
else:
dic[s[i]] = i
res = max(res, i-start+1)
return res
P13 第四轮白人小哥直接做题，leetcode 212 word sarch II https://leetcode.com/problems/word-search/
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
if not board or not board[0]:
return False
for i in range(len(board)):
for j in range(len(board[0])):
if self.bt(board, i, j, word):
return True
return False
def bt(self, board, i, j, word):
if len(word)==1:
if board[i][j] == word[0]:
return True
else:
return False
if board[i][j]==word[0]:
for dp in [(1,0), (-1,0), (0,1), (0,-1)]:
m, n = i+dp[0], j+dp[1]
if 0<=m<len(board) and 0<=n<len(board[0]):
tmp = board[i][j]
board[i][j] = '@'
if self.bt(board, m, n, word[1:]):
return True
board[i][j] = tmp
return False
https://leetcode.com/problems/word-search-ii/
class Node(object):
def __init__(self):
self.dic = {}
self.isWord = False
class Solution(object):
def findWords(self, board, words):
"""
:type board: List[List[str]]
:type words: List[str]
:rtype: List[str]
"""
root = Node()
for w in words:
tmp = root
for c in w:
if c not in tmp.dic:
tmp.dic[c] = Node()
tmp = tmp.dic[c]
tmp.isWord = True
res = []
for i in range(len(board)):
for j in range(len(board[0])):
self.dfs(board, i, j, '', root, res)
return res
def dfs(self, board, i, j, path, node, res):
if node.isWord:
res.append(path)
node.isWord = False
if 0<=i<len(board) and 0<=j<len(board[0]) and board[i][j] in node.dic:
tmp = board[i][j]
board[i][j] = '#'
for dp in [(1,0), (-1,0), (0,1), (0,-1)]:
m, n = i+dp[0], j+dp[1]
self.dfs(board, m, n, path+tmp, node.dic[tmp], res)
board[i][j] = tmp
P14 273. Integer to English Words https://leetcode.com/problems/integer-to-english-words/
难倒不难，就是写起来呀。有点恶心
class Solution(object):
less20 = ['Zero', 'One', 'Two', 'Three', 'Four', 'Five',
'Six', 'Seven', 'Eight', 'Nine', 'Ten', 'Eleven', 'Twelve',
'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen', 'Seventeen', 'Eighteen' 'Nineteen']
tens = ['','Ten', 'Twenty', 'Thirty', 'Fourty', 'Fifty', 'Sixty', 'Seventy', 'Eighty', 'Ninety']
thousands = ['', 'Thousand', 'Million', 'Billion']
def numberToWords(self, num):
"""
:type num: int
:rtype: str
"""
if num==0:
return 'Zero'
res = ''
index = 0
while num:
tmp = num%1000
res = self.less1000(tmp) + ' ' + self.thousands[index] + ' ' + res
index += 1
num = num//1000
return res.strip()
def less1000(self, num):
res = ''
if num>=100:
tmp = num/100
res += self.less20[tmp] + ' Hundred'
num = num%100
if num>=20:
tmp = num/10
res += ' ' + self.tens[tmp]
num = num%10
if num>0:
res += ' ' + self.less20[num]
return res
so = Solution()
ans = so.numberToWords(9999)
print ans
P15 regular expression matching， https://leetcode.com/problems/regular-expression-matching/
class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
dp = [[False]*(len(s)+1) for _ in range(len(p)+1)]
dp[0][0] = True
for i in range(1, len(p)):
dp[i + 1][0] = dp[i - 1][0] and p[i] == '*'
for i in range(len(p)):
for j in range(len(s)):
if p[i] == '*':
if i>0 and p[i-1]=='*': return False
dp[i+1][j+1] = dp[i][j+1] or dp[i-1][j+1]
if p[i-1]==s[j] or p[i-1]=='.':
dp[i+1][j+1] = dp[i+1][j+1] or dp[i+1][j]
else:
dp[i+1][j+1] = dp[i][j] and (p[i]==s[j] or p[i]=='.')
return dp[-1][-1]
P16 https://leetcode.com/problems/permutations-ii/
class Solution(object):
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
self.dfs(nums, [], res)
return res
def dfs(self, nums, path, res):
if not nums:
res.append(path)
for i in range(len(nums)):
if i>0 and nums[i]==nums[i-1]:
continue
self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)
so = Solution()
ans = so.permuteUnique([1,1,2])
print ans
P17 第一轮：why yelp，improvement。题是address similarity，follow up很多
P18 332. Reconstruct Itinerary https://leetcode.com/problems/reconstruct-itinerary/
import collections
class Solution(object):
def findItinerary(self, tickets):
"""
:type tickets: List[List[str]]
:rtype: List[str]
"""
if not tickets:
return []
dic = collections.defaultdict(list)
for s,e in tickets:
dic[s].append(e)
self.res = []
l = len(tickets)+1
self.dfs(dic, 'JFK', l, ['JFK'])
return self.res
def dfs(self, dic, cur, l, path):
if len(path) == l:
self.res = path
return True
chidren = dic[cur]
for c in chidren:
dic[cur].remove(c)
self.dfs(dic, c, l, path+[c])
dic[cur].append(c)
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
so = Solution()
ans = so.findItinerary(tickets)
print(ans)
P19 第二轮：印度男谈一个project谈到了loadbalancer的调度，让实现了一个roundrobin。第二题给你一堆 work (1,3) (2,4) (3,5) (4,8)，怎样选择work能做更多的小时数同时没有冲突。按起始时间sort然后backtraking
class Solution(object):
def mostWork(self, tasks):
if not tasks:
return 0
self.res = 0
self.dfs(tasks, 0, None, [])
return self.res
def dfs(self, tasks, hour, pre, path):
print pre, tasks
if not tasks:
if (hour+pre[1]-pre[0])>self.res:
self.res = hour+pre[1]-pre[0]
for i in range(len(tasks)):
if pre:
cur = tasks[i]
if cur[0]>=pre[1]:
self.dfs(tasks[i+1:], hour+pre[1]-pre[0], cur, path+[pre])
else:
self.dfs(tasks[i+1:], hour, tasks[i], path)
tasks = [(1,3), (2,4), (4,8)]
so = Solution()
ans = so.mostWork(tasks)
print ans
P20 第四轮：白男。给你两个词语，如何根据第一个找到第二个。每个词语你会打开维基百科，然后里面有link指向其他词语。 bfs搞定。follow up：如果分布式系统怎么找。 第二题设计一个类，并且能把这个类generate成json。dfs因为json里可能嵌套json。
class Solution(object):
def canFind(self, dic, a, b):
q = [a]
visited = set()
while q:
tmp = q.pop(0)
visited.add(tmp)
if tmp == b:
return True
if tmp in dic:
children = dic[tmp]
for c in children:
if c not in visited:
q.append(c)
return False
dic = { 'A':['B', 'C'],
'B':['D', 'E'],
'E':['H', 'G']
}
s1 = 'A'
s2 = 'G'
so = Solution()
ans = so.canFind(dic, s1, s2)
print(ans)
class Node(object):
def __init__(self, val):
self.val = val
self.chidren = []
class Solution(object):
def class2json(self, node):
res = {}
if not node.chidren:
res[node.val] = None
else:
chidren = []
for c in node.chidren:
tmp = self.class2json(c)
chidren.append(tmp)
res[node.val] = chidren
return res
a = Node('A')
b = Node('B')
c = Node('C')
d = Node('D')
a.chidren.append(b)
b.chidren.append(c)
b.chidren.append(d)
so = Solution()
ans = so.class2json(a)
print(ans)