之前找了小米的内推，上周四下午来电预约面试，约了这周二下午面试。预约面试的时候《剑指offer》还有几乎一半没看，慌得不行啊。四天半的时间刷完了剩下的一半，当然很多都没搞明白，搞明白的也有没AC的。然后看机器学习基础知识，看Faster R-CNN系列、看语义分割的那些论文，都没看完，感觉凉凉。

一面

自我介绍，就讲了下自己是谁，哪儿来的，现在在做啥（在做的项目应该多说一点的，失误）。

一道算法题：旋转数组中的最小数字，《剑指offer》原题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def minNumberInRotateArray(rotateArray):
    low, high = 0, len(rotateArray) - 1
    while rotateArray[high] <= rotateArray[low]:
        if high -low == 1:
            break
        mid = (low + high) / 2
        if rotateArray[high] == rotateArray[mid] == rotateArray[low]:
            ret = rotateArray[low]
            for i in range(low, high):
                if ret < rotateArray[i]:
                    ret = rotateArray[i]
            return ret
        if rotateArray[mid] >= rotateArray[low]:
            low = mid
        elif rotateArray[mid] <= rotateArray[high]:
            high = mid
    print(low, high)
    return rotateArray[high]

第一道题写得不是很顺，然后又来了一道：求二叉树中的最长路径，还是一道经典的题，写得又不顺。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class TreeNode(object):
	def __init__(x):
		self.val = x
		self.left = None
		self.right = None
def unit(pRoot):
	# 根据我的设计，这里的PRoot不可能是None
	depth, path = None, None # 分别表示以PRoot为根节点的二叉树的深度和最大路径长度
	if pRoot.left == None and pRoot.right == None:
		depth, path = 1, 0
	elif pRoot.left and pRoot.right == None:
		depth, path = unit(pRoot.left)
		depth += 1
	elif pRoot.left == None and pRoot.right:
		depth, path = unit(pRoot.right)
		depth += 1
	else:
		depth1, path1 = unit(pRoot.left)
		depth2, path2 = unit(pRoot.right)
		depth = max(depth1, depth2) + 1
		path = max([path1, path2, depth1 + depth2 + 2])
	return depth, path
def solution(pRoot):
	if pRoot == None:
		return 0
	depth, path = unit(pRoot)
	return depth

然后是一道大数据的题：给定一个长度特别大的数组，如何快速求出Top 100？

1
使用MapReduce的方法，首先将数组分成K份，在每一份上去求Top 100，之后再去做汇总。

问了百度比赛的方法，最后效果。

ResNet结构，有什么作用。

过拟合的解决方法。

GAN的原因，GAN/DCGAN/WGAN的区别。

问文本分类怎么做，回答不太了解，然后面试官给简单讲了『分词-向量化-模型』的过程。（简要的其实都知道）

最后问了一下实习时间，能不能七月之前来。然后就去叫二面面试官了。

二面

一面大概面了不到一小时，等了十多分钟二面面试官就来了。先说了一下语言的问题，实际业务中还是要用C/C++/Java的，然后开始做题。（平常都用Python，C/C++都忘得差不多了，得抓紧时间复习啊。）

第三道题：快排的非递归方法。想了两分钟没想出来，面试官问计算机是如何实现递归的，答用栈，面试官说那你想想能不能自己用栈来实现递归。豁然开朗，想了两分钟开始动笔，写的过程中方法也就清晰了。下面给出我的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def QuickSort(array):
	if len(array) < 2:
		return array
	low, high, n = 0, len(array)-1, len(array)
	stack = list()
	stack.append([low, high])
	while len(stack)>0:
		low, high = stack.pop()
		tmp1, tmp2, pivot = low, high, array[low]
		while low < high:
			while low < high and array[high] > pivot:
				high -= 1
			array[low] = array[high]
			while low < high and array[low] < pivot:
				low += 1
			array[high] = array[low]
		A[low] = pivot
		if low-1 > tmp1:
			stack.append([tmp1, low-1])
		if tmp2 > low+1:
			stack.append([low+1, tmp2])

第四道题：摘要算法。给定一长一短两个字符串，字符串中只会出现小写英文字母。首先统计短的字符串中有哪些字母出现，然后在长字符串中寻找包含短字符串中所有字母的最短的最靠左边的一个子串，返回子串的起始位置和长度。

1
2
例子1：长字符串『adbca』，短字符串『abcab』，短字符串中出现的字母为{a,b,c}，因此只需要在长串中寻找包含{a,b,c}的子串，如adbc、bca，因为bca最短，所以返回bca的起始位置和长度。
例子2：长字符串『adbacba』，短字符串『abcab』，子串adbac、bac、acb、cba均包含{a,b,c}，但bac最短且在长度为3的子串中最靠左，因此返回bac的起始位置和长度。（室友去面了腾讯有这道题，才知道叫『摘要算法』，应该是从搜索的业务中抽象出来的。）

下面给出我的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def isOk(dic):
	for k in dic.keys():
		if dic[k] == 0：
			return False
	return True
def solution(long, short):
	if len(long) == 0 or len(short) == 0:
		return -1
	d = dict()
	for c in short:
		d.setdefault(c, 0)
	index1, index2, res, l = 0, 1, 0, len(long)
	if long[index1] in d:
		d[long[index1]] += 1
	while index1<n and index2<n:
		if not isOk(d):
			if long[index2] in d:
				d[long[index2]] += 1
			index2 += 1
		else:
			if index2 - index1 > l:
				l = index2 - index1
				res = index1
			if long[index1] in d:
				d[long[index1]] -= 1
			index1 += 1
			while long[index1] not in d:
				index1 += 1
	return res, l

总结

不要慌，不就是一场面试么，大不了就是挂。

讲项目一定要讲得尽可能细致，首先自己不能觉得自己项目水（虽然实际上很水）；提前给项目做一个细致的总结，能够回答面试官的各种细节问题。我的项目讲得太了了，以后要加强。

coding能力是敲门砖，机器学习、深度学习的基础要扎实。

更新：周二下午面试，周四下午收到了offer。没有凉，二面只做了两道题，应该是一面机器学习基础知识回答得尚可，二面主要再考察coding能力。所以coding能力还是很重要啊：coding与机器学习基础，两手都要抓，两手都要硬。