团队负责公司核心业务，欢迎加入

简历发送至：wangyangyoung@didichuxing.com

【社招】策略算法工程师(D6/7/8)

工作地点：北京中关村软件园1期钻石大厦

职位类别：技术

所属部门：智能出行部

职位描述

综合使用运筹优化、机器学习和经济学方法，优化平台长期经济收益。

任职要求

1. 计算机或数学或运筹等相关专业毕业，有扎实的数据结构和算法基础，或者有较好的数学功底；

2. 在机器学习或数据挖掘方向有较强的积累，熟悉经典的算法并有实践经验优先；

3. 编程基础扎实，熟练使用C++、Go、Java、Scala或Python等一种编程语言，有扎实的数据结构和算法基础；

4. 有使用Hadoop/Hive/Spark分析海量数据的能力和经验；

5. 在机器学习或数据挖掘方向有较强的积累，熟悉经典的算法并有实践经验，包括LR、SVM、GBDT、Reinforcement Learning、Deep Learning；

6. 有学习热情，关注业界前沿技术，follow人工智能国际会议研究动态，不断提升自己在机器学习、运筹优化、机制设计、数理统计。

7. 有顶级会议发表研究成果者优先。

【实习】深度增强学习算法工程师

职位类别：技术

工作地点：北京中关村软件园1期钻石大厦

职位类别：技术

所属部门：智能出行部

职位描述：

1. 从事深度学习，迁移学习，增强学习相关研究工作

任职要求：

1. 逻辑清晰、思维活跃，善于分析和解决问题，有学习热情。
2. 计算机、统计数学等专业硕士及以上学历，有数据算法方向的项目经验。
3. 在机器学习或数据挖掘方向有一定的积累。
4. 熟悉TensorFlow/PyTorch等常用深度学习工具；
5. 有顶级会议发表研究成果者优先 。

备注：
这个实习的职位主要是面向研究生低年级，会研究深度学习，增强学习，迁移学习相关的topic，比较前沿，实习周期比较长。

我个人会遇到这样一种场景，虽然手中或者头脑中有很多的素材和信息，也大概知道自己的目的，却无法很清晰的将自己的意图传达给他人，譬如老板，譬如同事。明显的后果是邮件虽然发了，效果却不是当初想要的。Manuscript虽然写了，导师却表示不知所云。在如何把信息有效的表达这件事上，金字塔思维给了一个很好的参考。

为什么要使用金字塔结构?

为什么说表达信息需要把信息组织成金字塔的结构，这和人处理信息的两个特点是分不开的。

一是对受众最容易理解的顺序往往是：先了解主要的，抽象的思想，再去了解次要的思想和支持的证据。
二是人类的记忆容量受到7这个魔数的限制，同一层次无结构的信息无法同时记忆太多。

这两点就要求我们要将信息组织成结构，同时又要将主要的思想首先说出来。

金字塔结构是什么?

将主要的思想首先说出来，简而言之就是“结论先行”。如果我们使用递归的思维，保证在每一个层次上的思想都是对下一层的总结，那么就可以形成一个金字塔状的结构。需要注意的是这个金字塔上的每一个节点需要是一个“思想”。而“思想”是指能够给受众提供新的信息并引发受众疑问的语句。

举个栗子，“解决问题的3个方法”并不是一个合适的“思想”。“降低用户流失”可能是个更合适的说法。

怎么组织?

金字塔中相邻节点直接的关系只有两种：横向关系(兄弟)，纵向关系(父子)。

横向关系

多个属于同一范畴的思想共同组成一个逻辑推理过程。

• 什么叫同一范畴?

  1. 可以用单一名词表示该组的所有思想。

什么是逻辑推理过程?

仅有两种逻辑推理过程: 1.演绎；2.归纳。

演绎

1. 阐述已存在的某种情况。
2. 针对第一点的主语或谓语阐述同时存在的相关情况。
3. 说明这两种情况同时存在时隐含的含义。

举栗子。(1)“值得投资的高科技的创业公司的特点是有一个好的CEO和一个好的教授。” -> (2)“Beta有一个多次创业成功的CEO和专利颇多的哈佛教授。” -> (3)“Beta是一家值得投资的高科技创业公司。”

也可以是如下步骤:

1. 出现的问题或存在的现象
2. 产生问题的根源、原因
3. 解决问题的方案

归纳

同组思想具有类似的主语或谓语

可以按照以下三种方式将同组思想排序

1. 时间
   主要参考事物发展和做事情的先后顺序。
2. 结构
   分组时需要保证不重不漏。
3. 程度顺序
   可以依照该组思想任何一个共同特性的程度进行排序。

编码 — 记忆 — 提取

1 学习误解的厘清

• 拥抱困难。Learning is deeper and more durable when it’s effortful.
• 重复阅读和重复练习(rereading text & massed practice)是最低效的。
• 提取型练习（Retrieval practice）是比rereading更高效的方法(e.g. 小卡片)。
• 间隔时间，改变环境，打乱练习内容有利于信息的长久沉淀。
• 在不知道答案的时候解答问题有利学习，即使犯错也没关系。
• 关于某些人是某种类型的学习者(比如视觉型)并没有坚实的证据支持，人们完全可以尝试更多样的方式。

2 靠提取来学习

• 对于所发生的事情复盘，同时进行一些假设，是不是可以做的更好，是不是有更危险的走向被无意避免了。
• 经常“月考”，即使给予反馈。

3 打乱你的练习

• 不要只尝试练习某个局部，而要尽可能地让练习尽可能的接近真实情况。以棒球练习为例，有三种球速和路线。Group A 分别将这三种分成Block进行练习，111122223333。练习的时候击中率还不错。Group B把这三种混在一起进行练习，123213212332121。练习的时候老打不中。Group B在最终比赛中Performance 更高。
• （个人Note）不要总在同一个环境下学习同一个东西，以后离开了那个环境有时候东西就提取不出来了。本质上要多挂钩一些情境为好。

4 拥抱困难

• 学习分为 编码-巩固-提取 (encoding-consolidation-retrieval)三个阶段

• 直面困难的努力可以在这几个方面起作用:

  • 不同尝试更新提取的线索
  • 提取需要重构长期记忆
  • 反复提取尝试以及各种打乱使得多种信息能创造心理模型(mental model)。
  • 因为在不同的时间和情境下应用或练习，拓展了知识的运用范围。
    • 使用一种生成式的方法。“想认识大脑是怎样工作的最好是尝试自己造一个大脑”。
    • 应该避免的困难：1) 解决了这个问题对你的成长帮助很小。2) 现在用任何方式都无法解决。

问题

(来自编程之美3.7)实现一个有MaxElement()方法的队列，并使得MaxElement方法的时间复杂度尽可能的低。

初步想法

拿一个指针指向最大值，每次enqueue的时候更新这个指针。这个想法比较天真，当dequeue的时候，如果正好这个指针所指的元素要被删除，现在全队列中第二大的元素应该变成新的最大的元素，但是现在找不到。

优化

第一步

那么现在问题变成保证：

1. 当头部不是最大值时，随便dequeue。
2. 当头部是最大值时，他应该有指针指向除了他以外谁是最大的。

所以1)我们应该有一个指针始终指向当前最大值，2)另外每个元素自己拥有一个指针指向他后面的元素中的最大值next_max[]。

注意到2)中每个元素自己进入队列的时候是无法知道后面的元素的情况的，所以我们可以尝试利用一个后进先出的结构试着让每个元素知道他后面所有元素的情况。

比如我们现在有队列[3,1,2]。先push 2，最大值是2，没有比他小的next_max[0]=-1 。再push 1，最大值还是2，因为1比现在的最大值小，所以删除无所谓next_max[1]=-1。再push 3, 此时3>2 所以最大值变成了3，next_max[2]=0(指向2所在的位置)。

第二步

问题又来了，如果这时我们需要enqueue几个元素比如{4,7,5} 怎么办? 理论上我们得等到第一步那个stack清空后才能放入这几个元素。同时这几个新添加的元素中也可能有最大值, 我们也需要记录下来。这时我们可以回顾一下初步想法，当队列不发生dequeue时，我们完全可以只用一个变量记录最大值就好了。最后我们考虑到第一步的enqueue需要从后往前放，我们不妨使用一个普通的stack来存储enqueue进来但暂时还不能放入第一步的stack中的元素。

复杂度

一个元素的一个生命周期最多被弹3次，所以分摊复杂度是O(1)的。

定义

• 连通图: 图中任意两点均是可达的。
• 子图: 一个图的一部分。
• 全连通图:一个图中的每个点与图中任意其他点均有边连接。
• 极大全连通子图: 在全连通子图上添加图上其他任意一点，均破坏其全连通性质。

问题

给一个连通图,找出其中所有的极大全连通子图，如下图中 {1,2,3},{3,4},{4,5}都是极大全连通子图。

初步想法

从一个点开始遍历，扩展全连通子图，直至不能继续扩展。同时将访问过的边标记为已访问。

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

while (!isEmpty(vertexList)){
	Vertex cur = vertexList.peek();
	Queue maxSubG = new LinkedList<Vertex>();
	maxSubG.add(cur);
	//极大连通子图最少两个点
	if (isEmpty(cur.Edges())) continue;
	Vertex other = cur.Edges.poll().other(cur);
	removeEdge(cur, other);
	for (Vertex neighbour : cur.Edges()){
		int cnt = 0;
		int common = 0;
		for (Vertex nn: neighbour.Edges()){
			if (maxSubG.contains(nn)){
				common ++;
			}
			if (nn == cur || nn == other){
				cnt++; 
			}
			if (cnt >=2 ) break;
		}
		if (cnt == 2 && common == maxSubG.size()){
			maxSubG.add(neighbour);
			removeEdge(neighbour, cur);
			removeEdge(neighbour, other);
		}
	}
}

Bad case

见下图，如果我们用上述的方法可能会漏掉{1，3，4}这个极大连通子图，而误将{1,4}看做一个极大连通子图。

下面我们就要开始着手解决这个问题。首先我们可以发现极大连通子图至少有一条边，这提示我们是否可以按照边而不是顶点来进行遍历呢？其次，我们观察造成我们遗漏{1,3,4}这个子图的罪魁祸首是{1,3}和{3,4}这两条边被错误的删除了。注意到删除{1,3}时，{1,3}除了2以外，还有另一个可扩展的点4，所以其还有利用价值，不能直接删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

while (!isEmpty(edgeList)){
	Edge init = edgeList.peek();
	Set<Vertex> maxSubG = new Set<Vertex>();
	Vertex one = init.one();
	Vertex other = init.other();
	maxSubG.add(one);
	maxSubG.add(other);
	for (Edge e : union(one.edges(), other.edges()){
		Set<Vertex> common = intersect(e);
		if (intersect(common, maxSubG).size() = maxSubG.size()){
			maxSubG.add(e.other(one));
			if (common.size() == maxSubG.size()){
				edgeList.remove(e);
			}
		}
	}
	if (intersect(init).size() == maxSubG.size()){
		edgeList.remove(init);
	}
}

题目

给定一个int[] prices，以及最多可以进行k轮交易(一轮表示分别买一次卖一次)。
每天可以进行一次交易，问最多能取得多大的利润。链接

解释

这个其实跟买股票系列之二很像，即是在prices.length 这么多个price中选出2k个，看哪种选法利润更大。当2k > prices.length 时，本题就可化归为买股票系列之二(可以选任意个)。

状态转移方程

设f[i][j] 表示在[0, i]中选price，进行到第j次交易能获得的最大利润。

f[i][j] >= f[i-1][j] (1)
f[i][j] >= f[i][j-1] + prices[i]*{1,-1}[j%2] (2)
其中不等式(1)表明我多增加了一个选项，能获得的最大利润肯定不小于少一个选项的情况。
不等式(2)表示我每次用prices[i]去尝试，看能不能比之前获得更大的利润。实际上在交易j处，我们可以尝试prices[j-1,…,i]，但是i之前的我们在之前的步骤中已经尝试过了所以不必重复。
最后需要注意的一点是，选择的位置<=2*k。而如果我们到达第i+1个交易位置，这是我们只能用prices[i]去尝试，没有更多的选择，所以此处

f[i][i+1] = f[i][i] + prices[i]*{1,-1}[i%2]

为了处理边缘情况，我们令f[i][0] = 0，这样当k == 0 时则返回0。

同时当j = 1时:
f[i][j]>= prices[i]*{1,-1}[j%2] = f[i][0] + prices*{1,-1}[j%2]

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public int maxProfit(int k, int[] prices) {
    if (k>prices.length/2) return maxProfit2(prices);//买股票系列II
    int[] dp = new int[2*k+1];
    int[] sell = new int[]{1,-1};
    for (int i = 0; i < prices.length;i++){
        for (int j=1; j <= Math.min(2*k,i+1);j++)
            if (j==i+1)
                dp[j] = dp[j-1] + prices[i]*sell[j%2];
            else
                dp[j] = Math.max(dp[j], dp[j-1]+prices[i]*sell[j%2]);
    }
    int max_profit = 0;
    for (int i=0; i<= 2*k; i++){
        max_profit=Math.max(max_profit,dp[i]);
    }
    return max_profit;
}

题目

Largest Rectangle in Historgram. 给你一组从左至右排列的柱子的高度，其中每个柱子宽1并且紧靠，要求算出这群柱子下面最大的矩形面积。
比如给你 [2,1,5,6,2,3]， 最大面积由高为5和6的两个柱子组成=10。
Vespa 同学说的这段话非常有道理

每次想算法题，我的基本思路就是，首先先想最直观的解法，不行，就再想分治或者动规这种，再不行，就从数据结构下手！其实这类算法题，根据我的经验，你只要有意识去想分治的思想，如果分治解法存在，那么你总可以想到这个解法的。

暴力法

暴力法是一切的基础，咳咳。
我们可以找以每个柱子为最小高度可以获得的最大面积，所有柱子中最大的最大面积就是答案。
O(n^2)用两层循环，在内循环中每次从a[i]开始向左向右扩张，直到遇到第一个比a[i]小的数a[j],作为边界。这样就可以求得a[i]*n 为最小面积，n是扩张的长度。

分治法

每次找到给定子问题中高度最小的地方。
那么最大面积就是 = max(左边的最大值，amin*length, 右边的最大值)

当然极端情况下会超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public int largestRectangleArea(int[] height) {
       return largestRect(height, 0, height.length-1);
}
   
   private int largestRect(int[] height, int lo, int hi){
       if (hi-lo <0) return 0;
       int minIdx = minIndex(height,lo,hi);
       int valueM = height[minIdx]*height.length;
       int valueL = largestRect(height, lo, minIdx-1);
       int valueH = largestRect(height, minIdx+1, hi);
       return valueH > valueL? Math.max(valueH, valueM): 
           Math.max(valueL, valueM);
   }
   
   private int minIndex(int[] height, int lo, int hi){
       if (hi-lo <1) return lo;
       int index, i;
       for (i =lo+1, index = lo; i <= hi; i++){
           if (height[i] < height[index])
               index = i;
       }
       return index;
   }

堆栈法

MST

(当一个图是连通的时候)最小生成树就是一颗利用已知边把所有点连起来，并且保证边的总长度最短的一颗树。

1

这里我们假设所有的城市之间边就是一条直线。

开始画出来的图是这样的。

然后。。。擦，为啥从拉萨到乌鲁木齐比从兰州还近？然后我意识到这几个西部城市之间距离太远，由于我没有使用劣弧计算产生了较大的偏差。

然后老老实实算劣弧：

1
2
3
4
5
6

设经度是	theta 纬度是 phi
x = cos(phi)*cos(theta)
y = cos(phi)*sin(theta)
z = sin(phi)
劣弧角度 = acos(<v1,v2>)// 求个内积

感觉好多了。连了三条边的城市有：石家庄，太原，郑州，兰州，合肥，贵阳，南昌，澳门(忽略这货)。

其实武汉和郑州都有实力连四条边。话说前一张图跟京广线重合度真高。找不到更多槽点了，也许可以考虑弄一个算法控制枢纽的数量。

神马是AHP

层次分析法（Analytic Hierarchy Process）简称AHP，是一种半定量的方法。假设我们有一个目标y，同时我们有三个标准$x_1, x_2, x_3$，需要评价目标$y$，用矩阵表示就是$Ax=y$。那么我们怎么确定各个x的权重$a_1, a_2, a_3$呢？当然可以老板拍脑袋随便蹦出三个数。但是为了让这个三个数字看起来更有说服力，我们还是使用打分的方法。

两两比较

通常的直觉的想法是1-9分你按照$x$对$y$的重要性打分吧，但是这样有个问题，就是如果有10个变量要打分我有一个是1分，一个是9分，但是中间几个就不知道该给几分才好。这是因为人天性是对两两比较比较敏感，很多个放一起往往让人不知所措。于是在层次分析法中使用的是两两比较，总数推荐别超过9个。

分层模型

AHP的另一个优点是它可以分层处理问题，当然实际上一般三层比较常用，多了很难解释。从结构上说有点类似于以数据为基础的多层线性回归。

用AHP选方案？

AHP除了能算出来最下面一层各个变量对目标的重要性外，其实还可以用来选方案。如果最下面一层是多个方案，因为权重是可以排序的，那么同样的投入，权重是最大的方案带来的目标改善最大。下面举个选旅游方案的栗子(百度文库)

1 2分查找时，上界一般是开区间，这样取均值最后总会收敛到up-1。

2 数组问题边界一定要注意，看问题是否考虑完全。

3 开闭区间端点认真对待。

4 Arrays.asList(1,2,3,4) => 变成一个Collection， 可以批量初始化。

5 List 避免重复可以先check list.contains(x) 也可以

1
2

ArrayList<ArrayList<Integer>> newList = new 
ArrayList<ArrayList<Integer>>(new HashSet<ArrayList<Integer>>(oldList);

6 Bit operator: ~是非。 ^是xor。

7 char 是 primitive 类型，木有自己的方法。得Character.isDigit(curr)
Character.isLetter(curr)。

8 kmp 中 最后返回的 i-j 其实就是文字串跳出时的长度 - PatternString跳出的长度。 1) 成功匹配，那就是匹配的起始点。2)没找到，那么 i - j > n - m (i = n, j < m)。

9 kmp 中 匹配则 i++ , j++, next[i] = j // 反应的是j前匹配情况和i前一致，所以这个i如果匹配失败的话则应该用j匹配。 然后根据 A[i] 是否= A[j] 判断是否 next[i] = next[j]。
如果不匹配呢？ i不动，j=-1，那么下一次一定能匹配了(P[-1] = '*')。

10 ArrayDeque offerLast & removeLast 做Stack用比较方便。

11 SearchARange 中 可以使用 find upperbound 以及 lowerbound, 结果是[lower, upper)。 注意区间开闭。 二分法的核心是:

1
2
3
4
5
6
7
8
9
10

// upperbound
if (target >= *mid)
    first = ++mid; //开区间 )
else
    last = mid;
// lowerbound
if (target > *mid)
    first = ++mid; 
else 
    last = mid; //闭区间 [

12 数组初始化 new int[]{1,2,3,4} 或者 int[] rt = {1,2,3,4}

13 通常Array 或者 LinkedList => BST 都采用二分法，那么很重要的参数即是数列的长度。

14 字符串缓存通常使用StringBuilder, 配套方法有append(), toString()。

15 Subset II,

If S = [1,2,2], a solution is:

1
2
3
4
5
6
7
8

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

采用增量法处理，每次在之前的每个set的基础上加一。特殊情况就是如果当前项与前一项相同，那么会重复前一项完成的添加。所以需要从前一项处理对象的后一项开始。其他情况依然从零开始，关键代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13

// ...
for (int i = 0; i < num.length; ++i){
    int start = 0;
    if (i > 0 && num[i] == num[i-1])
        start = last; //last last
        last = subsets.size();
    for (int j = start; j < last; ++j){
        List<Integer> subset = new ArrayList<Integer>(subsets.get(j));
        subset.add(num[i]);
        subsets.add(subset);
    }
}
// ...