名企笔试

京东2016算法工程师笔试题（登楼梯）

有一段楼梯台阶有15级台阶，以小明的脚力最多可以一次跨上三级台阶，问有多少种方法登上这段楼梯？

#include<iostream>using namespace std;int compute(int n){       int sum=0; //统计	if(n==1)sum=1;	else if(n==2)sum=2;	else if(n==3)sum=4;//登上一节台阶的方法只有一种，两级台阶的方法有两种，三级台阶有四种{（1,1,1）(1,2) (2,1) (3) }   动态规划的方法	else	{	  sum=compute(n-1)+compute(n-2)+compute(n-3);    }	return sum;}int main(){	cout<<compute(15)<<endl;	return 0;}
什么是拓扑排序 ？  一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E(G)，则u在线性序列中出现在v之前。
 有向无环图才存在拓扑序列
对于一个DAG,可能存在多个拓扑序列
除首任务开始不需要条件，其它任务的执行必须在它的前驱任务完成才能执行（选择一个没有前驱的顶点,删除该顶点和所有以它为起点的有向边,循环直到DAG为空）
名企笔试：滴滴出行2017秋招算法笔试题（拓扑排序）
下面哪个序列不是上图的一个拓扑排序？
A. ebfgadch
B. adchebfg
C. aebdgfch
D. aedbfgch
选择B
腾讯2016校园招聘研发工程师笔试题（全连通图）
n个顶点,m条边的全连通图，至少去掉____边才能构成一棵树？
A. n-1
B. m-1
C. m-n+1
D. m-n-1
N个点如果相连至少n-1条，现在我们有m条边，所以至少减少m-(n-1)
所以选择C