美国留学生今日头条后台开发面经（挂经）
5.8面的头条后台开发，挂于二面，纯写题……
远程视频面试，上来面试官让我做个自我介绍，然后我顺带就把简历给一块介绍了，感觉面试官好像不是很在乎简历，直接说给我出道算法题。
题目是剑指offer上的顺时针打印矩阵，当时没刷过剑指offer，做的都是leetcode的题目，所以做的不是很利索，用了一种设置方向变量，然后遍历达到边界条件之后再变换方向，
同时设置一个二维数组记录已经被遍历过的位置，这样每次到边界的变换方向就是一定的了。后来看了剑指offer上其他人的解答，感觉还是旋转魔方的方法更简单，并且更好写。
以下贴上这道题，以防很多留学生都只刷过leetcode而没见过这道题（据说leetcode上也有，但是我是按公司tag刷的所以就没刷到）。
题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
以下是旋转魔方的解法（转载）：
class Solution:
# matrix类型为二维列表，需要返回列表
def printMatrix(self, matrix):
# write code here
result = []
while(matrix):
result+=matrix.pop(0)
if not matrix or not matrix[0]:
break
matrix = self.turn(matrix)
return result
def turn(self,matrix):
num_r = len(matrix)
num_c = len(matrix[0])
newmat = []
for i in range(num_c):
newmat2 = []
for j in range(num_r):
newmat2.append(matrix[j][i])
newmat.append(newmat2)
newmat.reverse()
return newmat
之后面试官好像不是特别满意，觉得我写的有点磕磕绊绊，然后让我手写了一个二分搜索，看看熟练程度，结果还比较满意就顺利进入到下一轮了。
第二轮在几个小时后，hr电话通知的第二轮面试时间。
面试官上来稍微问了问简历，然后就开始让我继续做题。（个人感觉头条是最接近北美面试的一家公司，基础问的不多，基本上都是算法题）
这回是道leetcode原题673 number of longest increasing subsequence
说来惭愧，动归刷的少，这道题只做过更简单的版本，而这道动归相对麻烦一点，当时就没写出来，果不其然面试官就进入了“好了，你还有什么问题要问吗”
的节奏。然后，两天就收到了拒信，后来自己再把这道题好好的写了一遍，有比较详细的注释，希望能帮到大家。
题目描述我就不贴上了，大家自行搜索leetcode 673
class Solution(object):
def findNumberOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
第一种情况：1，3，5
第二种情况: 1,3,5,4
第三种情况:1,3,5,4,7
maxval，count是为了第二种第三种情况来设计的，即最长递增子序列长度更新的同时，数量也沿用内层循环中cnts的数量，即两个n-1的子序列两条分支都走向n,例如下图
5
/ \
1-3 7
\ /
4
"""
if not nums:
return 0
lens,cnts = [1]* len(nums),[1]*len(nums)
count,maxval=1,1
for i in range(1,len(nums)):
for j in range(i):
if nums[i]>nums[j]:#只有递增的情况下才对lens和cnts进行更新
if lens[j]+1>lens[i]:#lens的比较是和longest increasing subsequence是一样的动归，只是这题是双重动归。
lens[i],cnts[i]=lens[j]+1,cnts[j]#是递增的情况最长递增序列长度才+1，而如果最长序列长度增加的话，最长子序列的数量又再次归一
elif lens[j]+1==lens[i]:#这种情况就是在i之前的j出现了非递增序列比如【1,3,5,4,7】中7前面的5和4，遇到这种情况，cnts相当于cnt[j]+\\
cnts[i]+=cnts[j]#如果出现1，3，【5】，4,7的情况，7前面存在5和4两个子序列时才会进入这个判断条件，即len[i]在1，3，5的时候已经变成了3，而1，3，5，4的时候压根没进入外层的nums[i]>nums[j]的循环，所以1，3，5，4，7时在i=7,j=5时已经被更新了lens，所以j=4时lens[j]+1才会等于lens[i]即i=7时，所以此时下面的count直接等于cnts[i]=2,没有进入第二个elif，因为最大长度得到了更新。
if lens[i]>maxval:#每次循环更新最大长度，同时记录这个长度下递增子序列的数量，适用于1，3，5，4，7这种情况
maxval,count=lens[i],cnts[i]
elif lens[i]==maxval:#如果最大长度没有更新的话，记录数量+1，适用于1,3,5,4这种情况
count+=cnts[i]
return count 最后，推荐北美地区转cs的同学可以多试试今日头条，相对来说不会问太多转专业的人缺乏的基础知识，更看重解题，相对来说比较适合。
```
#面经##实习##春招#
