sc onsite 21-30
P21 regular和wildcard match准备一波 regular expression 这两道题真的是把本宝宝写哭了。就是各种corner case！ 其实基本思想就是dp.
遇到.和相同的时候，应该选左上角进行dp,如果是星星，那么可以继承上面和上上面的结果，作用分别是消除掉前面那个char和相做不存在。然后还可以不停地copy前一个，这里就需要当前一个与s中的字母相同时，可以dp s前的前一个char的结果，总之很绕。
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]=='.':
dp[i+1][j+1] = dp[i][j]
elif p[i]==s[j]:
dp[i+1][j+1] = dp[i][j]
elif p[i]=='*':
dp[i+1][j+1] = dp[i][j+1] or dp[i-1][j+1]
if i>0 and p[i-1]=='.' or p[i-1]==s[j]:
dp[i+1][j+1] = dp[i+1][j+1] or dp[i+1][j]
print i+1, dp[i+1]
return dp[-1][-1]
wildcard matching https://leetcode.com/problems/wildcard-matching/ 我还是觉得2D dp要好理解得多，面试如果要我优化成1D的DP。那我可是要跪地求饶给他看！
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(len(p)):
for j in range(len(s)):
if p[i]=='?':
dp[i+1][j+1] = dp[i][j]
elif p[i]==s[j]:
dp[i+1][j+1] = dp[i][j]
elif p[i]=='*':
dp[i+1][j+1] = dp[i][j+1] or dp[i][j] or dp[i+1][j]
print dp[i+1]
return dp[-1][-1]
s = 'aaa'
p = 'aa'
so = Solution()
ans = so.isMatch(s, p)
print(ans)
P22 1. 1. find all amicable numbers.输入一个正整数，找出所有小于这个数的amicable pairs。 看之前的面经有时间复杂度O(nlogn)，空间复杂度O(n)的算法。 感觉对于每一个数字求解是sqrt(n). 总的复杂度是n * log(n)。求解答怎么得到nlogn的算法 下面有大神回答：跟count prime类似的思想，通过n log n的复杂度求因子和
我没太听懂，不过还是写一遍count prime好了。aicable number之前写过一次就不写了
class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
if n<2:
return 0
p = [True]*n
p[0], p[1]=False, False
for i in range(2, (int(n**0.5)+1)):
if not p[i]:
pass
else:
for j in range(i*i, n, i):
p[j]=False
return sum(p)
P23 第一轮题目是给一堆会议时间，选出从早7点到晚7点的free时间，比如给了 8-11, 12:30-17:00, 15:00-17:30,就输出7-8, 11-12:30, 5:30-19:00，我想了好一阵，然后说用stack一个一个处理，结果面试官说为啥要用stack，我才意识到用一个结束时间就可以，一开始设置成7:00，处理一个时间就更新一些结束时间，然后输出就行了，不过写完了有一个bug，然后面试小哥说这是一个serious bug，我当时感觉他就有点不满意，囧，加了if else判断处理掉bug
整体不难吧。主要是corner case处理比较麻烦？
class Solution(object):
def findFreeTime(self, d, ms):
"""
:type d: str
:type m: List[str]
:rtype: list[str]
"""
# split times
meetings = []
for m in ms:
s,e = m.split('-')
meetings.append([s,e])
# merge times
mergedMeetings = [meetings[0]]
for i in range(1,len(meetings)):
if mergedMeetings[-1][1]>meetings[i][0]:
mergedMeetings[-1][1]=meetings[i][1]
else:
mergedMeetings.append(meetings[i])
# build result
s, e = d.split('-')
res = []
for m in mergedMeetings:
if m[0]>s:
res.append([s, m[0]])
s = m[1]
if s<e:
res.append([s, e])
return res
day = '7:00-19:00'
meetings = ['8:00-11:00', '12:30-17:00', '15:30-17:30']
so = Solution()
ans = so.findFreeTime(day, meetings)
print ans
P24 中国小哥 + shadow， 聊天， 问project， 问的问题是longest incresing subsequence， 似乎是lintcode上的题？还有一题是大数乘法。
大数乘法如下 https://qiuzhihui.gitbooks.io/r-book/content/big_integer.html LIS如下https://leetcode.com/problems/longest-increasing-subsequence/ 中国大哥就是给力！
class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
dp = [1]*len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[i]>nums[j]:
dp[i] = max(dp[i],dp[j]+1)
return max(dp)
nums = [10, 9, 2, 5, 3, 7, 101, 18]
so = Solution()
ans = so.lengthOfLIS(nums)
print ans
P25 第四轮，国人小哥。我也不知道他后来有没有放水，反正是挂了。但过程中他给了很多的提示。题目是这样的：一棵树，代表上司和员工的关系，然后每个节点都有一个对应的权值。然后公司开了一个party，为了让员工们更好的交流，有个规定，如果上司去参加party，那么他的直接下属（直接孩子节点)就不去（同理，如果下属去了，直接上司，父节点就不去）。然后设计一个算法，参加party的人的权值总和最高。这是一道动态规划题，思路是每次计算一个员工去的权值之和与不去的权值之和，从叶子开始。 这不就是house robber 3么？ https://leetcode.com/problems/house-robber-iii/
思路：这道题很像dp。就是一直返回最优。根据取不去root的值可以分成2类情况来讨论，因为要返回两个情况的最优，所以需要新建一个helper function。这里提一句，什么时候需要helper function呢？ 一般是我们想到这道题需要递归，原来的fuction不能满足这种递归的结构。 dfs也是其中的一种原方程不能满足结构的情况。
Top to bot with memo
class Solution(object):
def rob(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.memo = {}
return self.helper(root)
def helper(self, root):
if not root: # if not root
return 0
if root not in self.memo: # if it is not in memo
val = 0
if root.left: # we calculate not have left
val += self.helper(root.left.left) + self.helper(root.left.right)
if root.right: # we calculate not have right
val += self.helper(root.right.left) + self.helper(root.right.right)
f = root.val+val # max include root
s = self.helper(root.left) + self.helper(root.right) # max not include root
self.memo[root] = max(f, s)
return self.memo[root]
bot to top solution
class Solution(object):
def rob(self, root):
"""
:type root: TreeNode
:rtype: int
"""
return max(self.helper(root))
def helper(self, root):
if not root:
return [0, 0]
l = self.helper(root.left)
r = self.helper(root.right)
f = root.val + l[1] + r[1]
s = max(l[0]+r[1], l[1]+r[0], l[0]+r[0], l[1]+r[1])
return [f, s]
P26 第一轮是一个大胡子白人，扎着马尾辫。看起来还是挺严肃的。先聊简历，聊了很多。他问到有个我做过的项目，如果想再做一遍的话，问我想怎样改进。编程题是给定一个有向关系图，在给定2个名字，求出这两个人的共同朋友（即2个点能达到的共同节点，类似树的共同祖先）
思路：就是dfs然后求一个交集？
import collections
class Solution(object):
def commonFriends(self, relation, a, b):
if not relation:
return []
dic = collections.defaultdict(set)
for r in relation:
a, b = r
dic[a].add(b)
s, af = [a], set([a])
while s:
tmp = s.pop()
children = dic[tmp]
for c in children:
if c not in af:
s.append(c)
af.add(c)
s, bf = [b], set([b])
while s:
tmp = s.pop()
children = dic[tmp]
for c in children:
if c not in bf:
s.append(c)
bf.add(c)
return list(af&bf)
relation = [[1,2],[2,3],[3,4],[6,5],[5,4]]
a, b = 1, 6
so = Solution()
ans = so.commonFriends(relation, a, b)
print ans
P27 第二轮是一个白人小哥，人很nice。简单的聊了一下简历后就开始编程。题目是如果通讯录里从某一个名字开始翻转了，请把这个名字找出来。类似leetcode这道题：。这题我二分搜索算法犯了个低级错误，大概被扣分不少。 这道题就是find min in rotated array啊。 https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
class Solution(object):
def findR(self, names):
if not names:
return
l, r = 0, len(names)-1
while l<r:
mid = (l+r)//2
if names[mid]<names[r]:
r = mid
else:
l = mid+1
return names[l]
names = ['case', 'doug', 'aron', 'bob']
so = Solution()
ans = so.findR(names)
print ans
P28 我觉得吧game of life得再写一遍
正常的
class Solution(object):
def gameOfLife(self, board):
"""
:type board: List[List[int]]
:rtype: void Do not return anything, modify board in-place instead.
"""
if not board or not board[0]:
return
for i in range(len(board)):
for j in range(len(board[0])):
cnt = 0
for dp in [(1,0),(-1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)]:
m, n = i+dp[0], j+dp[1]
if 0<=m<len(board) and 0<=n<len(board[0]):
if board[m][n]&1==1:
cnt += 1
if board[i][j]==1 and 2<=cnt<=3:
board[i][j] = board[i][j]^2
if board[i][j]==0 and cnt==3:
board[i][j] = board[i][j]^2
for i in range(len(board)):
for j in range(len(board[0])):
board[i][j] = board[i][j]>>1
print board
board = [[0,0,0,0],[0,1,1,0],[0,1,1,0],[0,0,0,0]]
so = Solution()
so.gameOfLife(board)
用hash直接来存坐标 输入和输出都不变，为了好验证
class Solution(object):
def gameOfLife(self, board):
"""
:type board: List[List[int]]
:rtype: void Do not return anything, modify board in-place instead.
"""
if not board or not board[0]:
return
dic = {}
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j]==1:
dic[(i,j)] = [1,0]
keys = dic.keys()
for k in keys:
tmp = dic[k]
for dp in [(1,0),(-1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)]:
i, j = k[0] + dp[0], k[1]+dp[1]
if (i,j) in dic:
dic[(i,j)][1] += 1
else:
dic[(i,j)] = [0,1]
keys = dic.keys()
for k in keys:
if dic[k][0]==1:
if 2<=dic[k][1]<=3:
dic[k] = [1,0]
else:
del dic[k]
else:
if dic[k][1]==3:
dic[k] = [1,0]
else:
del dic[k]
for i in range(len(board)):
for j in range(len(board[0])):
if (i,j) in dic:
board[i][j]==1
else:
board[i][j]==0
print board
board = [[0,0,0,0],[0,1,1,0],[0,1,1,0],[0,0,0,0]]
so = Solution()
so.gameOfLife(board)
P29 Reconstruct Itinerary
backtracking的经典题型，找一个path试，可以就返回，不可以就试下一个。
import collections
class Solution(object):
def findItinerary(self, tickets):
"""
:type tickets: List[List[str]]
:rtype: List[str]
"""
maxL = len(tickets)+1
dic = collections.defaultdict(list)
for f,t in tickets:
dic[f].append(t)
for k in dic:
dic[k].sort()
self.res = None
print self.dfs(dic, 'JFK', ['JFK'], maxL)
print self.res
def dfs(self, dic, cur, path, maxL):
if len(path)==maxL:
self.res = path
return True
for i in range(len(dic[cur])):
c = dic[cur].pop(0)
if self.dfs(dic, c, path+[c], maxL):
return True
dic[cur].append(c)
tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
so = Solution()
so.findItinerary(tickets)
感觉自己不是很熟悉backtracking,那我们就把N-Queen II写一遍好了。
class Solution(object):
def totalNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
board = [['.']*n for _ in range(n)]
dic = set()
res = []
self.bt(0, 0, board, dic, [], n, res)
return res
def bt(self, m, n, board, dic, path, l, res):
if len(path)==l:
return True
for i in range(m, len(board)):
for j in range(len(board[0])):
if (0,i-j) not in dic and (1,i+j) not in dic and\
(2,i) not in dic and (3,j) not in dic:
dic.add((0,i-j))
dic.add((1,i+j))
dic.add((2,i))
dic.add((3,j))
board[i][j]= 'Q'
if self.bt(i, j, board, dic, path+[(i,j)], l, res):
res.append(map(''.join, [k for k in board]))
dic.remove((0,i-j))
dic.remove((1,i+j))
dic.remove((2,i))
dic.remove((3,j))
board[i][j]= '.'
so = Solution()
ans = so.totalNQueens(4)
print ans
P30 然后就做一道类似knight move的题目，给了一个函数list nextMoves()，返回所有下一个有效的move，棋盘无穷大，输出到目的地的最短路径。bfs就可以做好，另开一个hash表记录上一步。follow-up是输出所有的最短路径。用hash表记录上一步所有可能的位置，然后dfs返回所有路径。这道题是在电脑上编译通过的。讲完follow-up时已经没时间了，问了个小问题国人小哥就走了。
感觉这道题目跟P14 很像，那就用bfs写吧。最短路径我总感觉只有唯一解啊。实在不行，我就用level order traversal的办法好了。具体代码就不写了。