yp onsite 21-30
P21 面的Backend的SDE职位。Oncampus投的简历然后就有HR联系给了oncampus的interview。面了45分钟。主要是resume + 白板 + backend设计。面试官是个三哥manager, 人很nice。问的题也很简单。就是给一个只有0, 1的矩阵。0只在1前面出现。求出现1最多的行数。优化到O(m + n)就可以了。
import collections
class Solution(object):
def findMax1(self, matrix):
if not matrix or not matrix[0]:
return -1
index = len(matrix[0])-1
res = 0
for i in range(len(matrix)):
while index>=0 and matrix[i][index]==1:
index -= 1
res = i
return res
matrix = [ [0,0,0,1],
[0,0,1,1],
[0,1,1,1],
[1,1,1,1],
[1,1,1,1]
]
so = Solution()
ans = so.findMax1(matrix)
print(ans)
P22 有一轮题是multiplyString, 说完思路以后，并没有白板写题，而是小哥是让我在他的mac book上写code然后直接跑的。
class Solution(object):
def multiply(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
num1 = num1[::-1]
num2 = num2[::-1]
res = [0]*(len(num1) +len(num2) + 1)
for i in range(len(num1)):
for j in range(len(num2)):
cur = int(num1[i])*int(num2[j])
res[i+j] += cur
res[i+j+1] += res[i+j]//10
res[i+j] = res[i+j]%10
while len(res)>1 and res[-1]==0:
res.pop()
res = ''.join(map(str, res))
return res[::-1]
P23 给一个String，全是小写或者数字，输出他的所有大小写组合。例如输入a2c，输出就是a2c, a2C, A2c, A2C.
class Solution(object):
def combination(self, word):
"""
:type word: str
:rtype: List[str]
"""
res = []
self.dfs(word, '', res)
return res
def dfs(self, word, path, res):
if not word:
res.append(path)
return
if word[0] in '0123456789':
self.dfs(word[1:], path+word[0], res)
else:
self.dfs(word[1:], path+word[0].upper(), res)
self.dfs(word[1:], path+word[0].lower(), res)
s = 'a2b'
so = Solution()
ans = so.combination(s)
print(ans)
P24 Flatten 2D Vector
class Vector2D(object):
def __init__(self, vec2d):
"""
Initialize your data structure here.
:type vec2d: List[List[int]]
"""
self.ary = [e for row in vec2d for e in row]
self.index = 0
def next(self):
"""
:rtype: int
"""
if self.index<len(self.ary):
tmp = self.ary[self.index]
self.index += 1
return tmp
def hasNext(self):
"""
:rtype: bool
"""
return self.index<len(self.ary)
vec2d = [
[1,2],
[3],
[4,5,6]
]
so = Vector2D(vec2d)
print(so.hasNext())
print(so.next())
print(so.next())
print(so.next())
print(so.next())
另外一种写法
class Vector2D(object):
def __init__(self, vec2d):
"""
Initialize your data structure here.
:type vec2d: List[List[int]]
"""
self.matrix = vec2d
self.i = 0
self.j = 0
def next(self):
"""
:rtype: int
"""
i, j = self.i, self.j
if self.i<len(self.matrix) and self.j<len(self.matrix[self.i]):
tmp = self.matrix[i][j]
if j==len(self.matrix[i])-1:
self.i += 1
self.j = 0
else:
self.j +=1
return tmp
def hasNext(self):
"""
:rtype: bool
"""
return self.i<len(self.matrix) and self.j<len(self.matrix[self.i])
vec2d = [
[1,2],
[3],
[4,5,6]
]
so = Vector2D(vec2d)
print(so.hasNext())
print(so.next())
print(so.next())
print(so.next())
print(so.next())
print(so.next())
print(so.next())
print(so.next())
print(so.next())
P25 Merge two sorted Arries
class Solution(object):
def merge(self, l1, l2):
"""
:type l1: List[int]
:type l2: List[int]
:rtype: List[int]
"""
res = []
while l1 and l2:
if l1[0]<l2[0]:
res.append(l1.pop(0))
else:
res.append(l2.pop(0))
res += l1 or l2
return res
l1 = [1,2,3,4,8,9]
l2 = [3,4,5,6,7,8]
so = Solution()
ans = so.merge(l1, l2)
print(ans)
P26 two sum 变形题，返回所有pairs,可重复 （我居然在这上卡了）
class Solution(object):
def findPairs(self, nums, target):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
dic = set()
res = []
for num in nums:
if (target-num) in dic:
res.append((num, target-num))
dic.add(num)
return res
nums = [1,2,3,4,5,6,7,8]
so = Solution()
ans = so.findPairs(nums, 8)
print(ans)
P27 valid anagram, 然后group anagram
class Solution(object):
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
return collections.Counter(s)==collections.Counter(t)
import collections
class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
dic = collections.defaultdict(set)
for s in strs:
dic[''.join(sorted(s))].add(s)
res = []
for k in dic:
res.append(list(dic[k]))
return res
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
so = Solution()
ans = so.groupAnagrams(strs)
print ans
P29 这道题面筋没看过，management pair，\
class Node(object):
def __init__(self, val):
self.val = val
self.chidren = []
class Solution(object):
def buildTree(self, relations):
"""
:type relations: List[List[str]]
:rtype: Node
"""
dic = {}
c_set = set()
for p, c in relations:
if p not in dic:
dic[p] = Node(p)
if c not in dic:
dic[c] = Node(c)
dic[p].chidren.append(dic[c])
c_set.add(c)
root = [k for k in dic if k not in c_set]
return [dic[k] for k in root]
relations = [['a','b'], ['b','c'], ['c','d'], ['e','h']]
so = Solution()
ans = so.buildTree(relations)
print ans
P30 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(len(p)):
for j in range(len(s)):
if p[i]=='*':
dp[i+1][j+1] = dp[i-1][j+1] or dp[i][j+1]
if i>0 and (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]
# '.' Matches any single character.
# '*' Matches zero or more of the preceding element.
so = Solution()
s = 'aa'
p = '.*'
ans = so.isMatch(s, p)
print(ans)