sc onsite
P1 找Amicable Number Pairs 就是 数A 的所有因数(包括1，不包括A) 之和 等于 B。B的所有因数之和又刚好为A。 且 A != B. 求[1, N] 中所有符合条件的pair
思路：先用一个array把每个数的因数和全部存起来。然后再遍历这个array找pair就行了。i = record[record[i]]就可以了。
class Solution(object):
def amiPair(self, n):
record = [0]*(n+1)
res = []
# first we record sum
for i in range(1, n):
record[i] = sum(e for e in range(1,i//2+1) if i%e==0)
# then we find the pair
for i in range(1, n):
if i<record[i] and record[i]<n and i == record[record[i]]:
res.append([i, record[i]])
return res
n = 1000
so = Solution()
a = so.amiPair(n)
print a
P2 coding题目是一个矩阵里某些位置有墙，给一个出发点及目的地，求最短距离。 如果只需能否通过，那就DFS。要计算距离，那就BFS。 follwup是现在墙可以打破，没打破一个cost为1，求cost最小的路线。 需要把每个node再加个成员变量cost，在终点取最小的cost，注意中途遇到访问过而且cost小的才不加。一定要画画图。
class Solution(object):
def findPath(self, matrix, start, end):
"""
:type matrix: List[List[int]]
:type start: List[int]
:type end: List[int]
:rtype: Bool
"""
if not matrix or not matrix[0]:
return False
s = [start]
visited = set()
while s:
tmp = s.pop()
for dp in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
i, j = tmp[0]+dp[0],tmp[1]+dp[1]
print i,j
if [i, j] == end:
return True
if 0<=i<len(matrix) and 0<=j<len(matrix[0]) and (i,j) not in visited and matrix[i][j]!=1:
visited.add((i,j))
s.append([i,j])
return False
so = Solution()
matrix=[[0,1],[1,0]]
s, e = [0,0], [1,1]
a = so.findPath(matrix, s, e)
print a
P3 有一堆数, 比如{2,3,5,8}. 每次带2个过去, 比如我选了3和5, cost是最大的那个值. 一旦过去, 还要带回来一个数. 比如带回3, 花销是3. 所以这一趟把5运了过去, 总花销是3+5. 求找出最小的花销运过去所有数字.
思路：天下武功，唯暴力不破。直接暴力dfs吧。优化的解法如下： http://blog.csdn.net/morewindows/article/details/7481851 不过提供面经这个哥们暴力dfs也拿到offer了。所以。还是装作不会最优解吧。科科
class Solution(object):
def lowCost(self, nums):
self.res = float('inf')
self.dfs(nums, [],[], 0)
return self.res
def dfs(self, nums, end, path, cost):
if len(nums)==2:
if cost+max(nums)<self.res:
self.res = cost+max(nums)
for i in range(len(nums)-1):
for j in range(i+1, len(nums)):
# get 2 num from nums
next_nums = nums[:]
next_end = end[:]
next_cost = cost
a, b = next_nums[i], next_nums[j]
next_nums.remove(a)
next_nums.remove(b)
next_cost += max(a,b)
next_end += [a,b]
# get 1 from end
c = min(next_end)
next_cost += c
next_end.remove(c)
next_nums.append(c)
self.dfs(next_nums, next_end, path+[[a,b,c]], next_cost)
nums = [2,3,5,8]
so = Solution()
a = so.lowCost(nums)
print a
p4. 给定数组，只有正数，使用＋和＊和（）。求最大值。 使用DP解决。dp[j] = max(dp[m - 1] + dp[m][j], dp[m - 1] * dp[m][j]);
class Solution(object):
def findmax(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
self.memo = {}
res = self.dfs(nums, 0, len(nums)-1)
return res
def dfs(self, nums, l, r):
if (l, r) in self.memo:
return self.memo[l, r]
if l == r:
return nums[l]
res = 0
for i in range(l, r):
left = self.dfs(nums, l, i)
right = self.dfs(nums, i+1, r)
tmp = max(left + right, left * right)
res = max(res, tmp)
self.memo[(l, r)] = res
return res
nums = [1,2,3]
so = Solution()
a = so.findmax(nums)
print(a)
P5 3d grid，每个点有高度， 给起点和终点，求一个直升机起点到终点高度和最小的路径，注意一点是直升机只能上升不能下降
思路：这道题用我写的 Dijkstra's Algorithm 就行了。你把高度看成cost。想当与就是求（0，0）到（2，2）的最短路径嘛。这只是最简单的Dijkstra，里面的那个Q可以用ordered dict来实现。或者用hashed Priority Queue来优化。面试的时候我觉得写成这样就差不多可以过了。
class Solution(object):
def flyChicken(self, m, start, end):
D = {}
Q = {}
Q[start] = 0
while Q:
v = self.get_min(Q)
D[v] = Q[v]
for dp in [(-1,0), (1,0), (0,1), (0,-1)]:
i, j = v[0]+dp[0], v[1]+dp[1]
if 0<=i<len(m) and 0<=j<len(m[0]):
dist = Q[v] + m[i][j]
if (i, j) in D:
if dist<D[(i,j)]:
raise ValueError
else:
if (i,j) not in Q or dist<Q[(i,j)]:
Q[(i,j)] = dist
del Q[v]
return D[(2,2)]
def get_min(self, Q):
m = (None, float('inf'))
for k in Q:
if Q[k]<m[1]:
m = (k, Q[k])
return m[0]
# example, CLR p.528
Matrix = [[0,1,2],
[1,2,3],
[1,1,4]]
so = Solution()
print so.flyChicken(Matrix, (0,0), (2,2))
P6 E.g. storeBadIps(["7.0.0.0/8", "10.3.0.0/16", "6.7.8.134/32"]) In the example "7.0.0.0/8", "7.0.0.0" is ip ranges from 0.0.0.0 to 255.255.255.255, "8" is how many bits from the beginning it needs to match. in this example any "7.x.x.x" would be a bad ip. In the example "10.3.0.0/16", any "10.3.x.x" would be a bad ip. In the example "6.7.8.134/32", only exact match "6.7.8.134" would be a bad ip.
思路：这题没什么好说的呀，就是建立trie嘛，然后新来的ip.就找在不在trie里面。
class Node(object):
def __init__(self):
self.children = {}
self.isEnd = False
class Solution(object):
def __init__(self, list):
self.root = Node()
for ip in list:
[ip, length] = ip.split('/')
ip = ip.split('.')
head = self.root
for i in range(0, int(length), 8):
if ip[i//8] not in head.children:
head.children[ip[i//8]] = Node()
head = head.children[ip[i//8]]
head.isEnd = True
def badIp(self, ip):
ip = ip.split('.')
head = self.root
for i in range(0, 32, 8):
if ip[i//8] not in head.children:
return False
head = head.children[ip[i//8]]
if head.isEnd==True:
return True
return False
l = ["7.0.0.0/8", "10.3.0.0/16", "6.7.8.134/32"]
so = Solution(l)
ans = so.badIp("6.7.8.x")
print ans
P7. N 个person和N 个bike在一个2维度数组里配对，一个person配对一个bike，要求所有配对的距离加起来和最小，面试官只要求讲思路。并提示greedy算法， 这题目我只给出了bruteforce的枚举法思路，时间复杂度是O(n!)，面试官说还有greedy算法可以优化成O(n^2）复杂度，但事后我觉得此题用greedy 算法只能近似求解，面试官给出的解法根本就无法求解全局最优解嘛。 不知道有没有高手可以用O(n^2)解出来，打我的脸。
思路：我觉得其实面试官就想要一个greedy的次优解法。然后我就按照面试官的要求写了一个。
import math
class Solution(object):
def assignBike(self, p, b):
ps = set(p)
bs = set(b)
dis_list = []
for i in p:
for j in b:
dis = math.sqrt((i[0]-j[0])**2+(i[1]-j[1])**2)
dis_list.append((dis,i,j))
dis_list.sort(key=lambda x: x[0])
cost = 0
res = []
while ps and bs:
[dis, i, j] = dis_list.pop(0)
if i in ps and j in bs:
ps.remove(i)
bs.remove(j)
cost += dis
res.append((i,j))
return cost, res
p = [(1,1), (1,2)]
b = [(2,1), (2,2)]
so = Solution()
ans = so.assignBike(p, b)
print ans
p8 小哥说话挺慢的，先让自我介绍，问了why snapchat, 实习经历里面最exciting的事是啥以及实习过程中有没有不开心的事 题目问了XML parser, LZ不熟悉XML，就改成了HTML Parser, 本质上一样 输入是一个tokenizer对象，可以调用其getNextToken()函数获得下一个token, token结构包括name和tag，name就是具体的文字，tag有open,close,text三种，让把所有的token建成一棵树 比如：
<html>
<user>
<id>aa</id>
<meta>bb</meta>
</user>
</html>
得到的token就是 ("html","open") ("user","open") ("id","open") ("aa","text") ("id","close") ("meta","open") ("bb","text") ("meta","close") ("user","close") ("html","close")
思路：是不是有点过于简单了，简直是放水嘛。还是还是我想错了。
class Node(object):
def __init__(self):
self.text = None
self.children = {}
class Solution(object):
def xmlParser(self, tokens):
root = Node()
s = [root]
for t in tokens:
print t
if t[1]=='open':
tmp = Node()
s[-1].children[t[0]] = tmp
s.append(tmp)
elif t[1]=='close':
s.pop()
elif t[1]=='text':
s[-1].text = t[0]
return root
P9 一个2D平面有一堆雷达（雷达有x, y坐标，以及能探测到的范围r半径）然后又一辆小车要从y=0和y=1的区间里面通过并且不能被雷达探测到。让写一个function看小车能不能通过 我用dfs写了一个。判断2D grid能不能从一边到另外一边的。 下次用union find写一下。
class Solution(object):
def canPass(self, sensor, matrix):
"""
:type sensor: List[tuple]
:type matrix: List[List[int]]
:rtype: Bool
"""
# process the grid
for s in sensor:
x, y, r = s[0], s[1], s[2]
for i in range(x-r, x+r+1):
for j in range(y-r, y+r+1):
if 0<=i<len(matrix[0]) and 0<=j<len(matrix):
dist = ((x-i)**2 + (y-j)**2)**(1.0/2)
if dist<=r:
matrix[i][j]=1
# build the start points and end points
s, end = [], []
for j in range(len(matrix[0])):
if matrix[0][j]==0:
s.append((0,j))
if matrix[len(matrix)-1][j]==0:
end.append((len(matrix)-1,j))
# dfs
visited = set(s)
while s:
tmp = s.pop()
if tmp in end:
return True
for dp in [(-1,0), (1,0), (0,1), (0,-1)]:
i, j = tmp[0]+dp[0], tmp[1]+dp[1]
if 0<=i<len(matrix[0]) and 0<=j<len(matrix)\
and matrix[i][j]==0 and (i,j) not in visited:
visited.add((i,j))
s.append((i,j))
return False
matrix = [[0]*4 for _ in range(4)]
sensor = [(1,0,1), (3,3,1)]
so = Solution()
ans = so.canPass(sensor, matrix)
print ans
P10 题目： ternary expression paser （三目运算符）， input是一个string，其中 'T' 表示true， 'F' 表示false， 要求返回最后运算的结果。
乍一看题目很直接， bool expression ? first result : second result ，但实际上我们通常都用的都是非常简单的形式，但每一部分都可以无限嵌套。例如： T ? T : F ? T : 1 : 2 : F ? 3 : 4; 原本妹子没让我考虑bool expression部分也嵌套的情况，结果我本着把问题分析清楚的原则，成功把问题弄的复杂了，她后来觉得这可以作为follow up。。。.1point3acres缃� 说了两三个简单的solution，然后举例发现有问题。在妹子的提示下，写出了 “不考虑 bool expression”的情况，但是因为已经说出口了，妹子指出我还需要继续考虑。最终时间不够，没有运行代码。 过后发现，确实应该多在纸上找一下规律，理清逻辑在写解法。string的变式题对我来说比较tricky，完全在脑子里思考容易变成一团浆糊。。。。妹子对我我说，没事她比较看重逻辑。我心里只能说谢谢你的安慰。。T.T
class Solution(object):
def boolExpression(self, s):
ops=[]
nums=[]
for i in s:
if i in '0123456789':
nums.append(i)
self.applyOp(ops, nums)
elif i in 'TF':
nums.append(i)
elif i in ':?':
ops.append(i)
return nums[-1]
def applyOp(self, ops, nums):
while len(ops)>1 and ops[-1]==':' and ops[-2]=='?':
x, y = nums.pop(), nums.pop()
b = nums.pop()
res = y if b=='T' else x
nums.append(res)
ops.pop()
ops.pop()
s = 'T?F?1:3:2'
so = Solution()
a = so.boolExpression(s)
print(a)
P10 unique paths I + II
https://leetcode.com/problems/unique-paths/
原题没什么好说的。
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
dp = [[0]*n for _ in range(m)]
for i in range(m):
for j in range(n):
if i==0 or j==0:
dp[i][j]=1
else:
dp[i][j] = dp[i-1][j]+dp[i][j-1]
return dp[-1][-1]
2
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
"""
:type obstacleGrid: List[List[int]]
:rtype: int
"""
if not obstacleGrid or not obstacleGrid[0]:return -1
m, n = len(obstacleGrid), len(obstacleGrid[0])
dp = [[0]*n for _ in range(m)]
for i in range(m):
for j in range(n):
if obstacleGrid[i][j]==1:
dp[i][j]==0
else:
if i==0 and j==0:
dp[i][j]=1
elif i == 0:
dp[i][j] = dp[i][j-1]
elif j ==0:
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[-1][-1]