首页 > 代码库 > 薪资至少10K的一道题,你能拿下吗
薪资至少10K的一道题,你能拿下吗
我所了解的华为:
应届生本科8k+
应届生硕士生10k+
应届生博士生12k+
看到后什么感想?有没有只恨生不逢时运不佳的感觉?
很多人做3年多甚至更久,才能达到这个薪资水平,还不如一个新生。
在我看来,2013年应届生应该在4k~5k,今年应届生应该在5k~6k,如果达不到,自身找原因。对于一个慎重的人,应该慎重的选择你们的衣食父母,选择影响命运。
就扯这么多,好好选择。
以下这道题是今年5月份左右华为的朋友拿来做的(也是闲的无聊,想看看他们那边都有什么玩意可以耍耍)属于华为三级考题,内部使用,相对来说,这道题难度不高,应届生应该就有这个能力,不过审题一定要仔细了,不要因为当初审题不清,需求不明,后来做大量的修改。最忌讳的一点:不清不楚做开发,创造出来都是渣。
这道题大概用了一天时间,说实话,算法很简单,时间用的太长了,也真够渣渣了;
相关的地铁线和站,请去官方网站使用正则匹配获取,当初是这么干的,别手打,15线279多站(不计算重复),累也累死了。
题中给了详细思路
背景概述
城市的地铁网络由多条线路组成
每条线路上有多个车站,线路自身没有交叉点
线路间交叉或重叠时,共用车站,在这些车站上可相互换乘
每条线路都是双向行车 线路有两种:
I形线和O形线 I形线有两个端点,乘客在端点处只能乘坐开往另外一端的地铁,在非端点处则有两个方向可选择。(如图中8号线)
O形线所有车站形成环,没有端点,乘客在任一站都有两个方向可选择。(如图中4号线)
功能需求
在地铁网络中任选一站为起点,任选另一站为终点,中途可换乘,要求输出
1)最短路线长度:从起点到终点经过的最少站数(站数计算不含起点,含终点)
2)最短路线:满足最短路线长度要求的所有路线(可能有多条路线,每条路线从起点到终点顺序输出途经的所有站点,包括起点和终点)
完成功能1和功能2满分100。
3)最优路线:换乘次数最少的最短路线(可能有多条路线)[本题20分,不计入总分,以附加分方式体现,比如“90+15”]
输入说明
地铁网络中的每一个站点用一个唯一的ID标识,ID是一个32位正整数;
一次输入一条线路,线路表示为一个站点ID数组;
例如{2, 3, 6, 9, 10},表示这是一条I形线,2和10为两端,数组元素顺序和从一端到另一端途经站点的顺序一致;
例如{1, 3, 6, 7, 4, 1},首尾站点一样,表示这是一条O形线,数组元素顺序和从站点1出发按某方向绕行一圈途经站点的顺序一致;
两条线路中出现了相同站点(如上面的3、6),表示两条线路在这些站点可相互换乘。
示例
某城市的地铁信息,如图 Line1:{1,2,3,4,5}; Line2:{1,10,9,7,6}; Line3:{5,7,8}; Line4:{11,5}; 从起点站1到终点站11 1)最短路线长度是5 2) 最短路线有2条,分别是{1, 2, 3, 4,5,11}和{1,10,9,7,5,11} 3) 最优路线有1条:{1, 2, 3, 4,5,11} (换乘一次) |
实现接口
说明:所有接口相互独立,没有调用顺序的要求(所谓“调用顺序”是例如:必须先调用2,再调用3,才能保证3的功能正确)
--------------------------------
(1) AddLine
Description
增加某条地铁线路
Prototype
void AddLine(unsigned int LineNo, unsigned int StationNum ,unsigned int *pStationArray);
Input Param
LineNo 地铁线路号;
StationNum 该条地铁线中的站点数目,由调用者保证不小于2;
pStationArray 该条地铁线的所有站点信息,pStationArray指向的存储空间在函数外会被释 放,请自行申请存储空间;
Output Param
无
Return Value
无
--------------------------------
(2) CalcMinPathLen
Description
计算从起点站到终点站的最短路线长度
Prototype
int CalcMinPathLen(unsigned int SrcStation, unsigned int DesStation);
Input Param
SrcStation 起点站;
DesStation 终点站;
Output Param
无
Return Value
起点站到终点站的最短路线长度
-1:任何出错情况(包括路线不存在、站点不存在、起点和终点重叠等等)
--------------------------------
(3) SearchMinPathes
Description
输出从起点站到终点站的最短路线
Prototype
int SearchMinPathes(unsigned int SrcStation, unsigned int DesStation, unsigned int* pPathNum, unsigned int* pPathLen,unsigned int **ppPathes);
Input Param
SrcStation 起点站;
DesStation 终点站;
Output Param
pPathNum 最短路线条数;
pPathLen 最短路线长度;
ppPathes 存储最短路线的内存地址,内存格式见下图,内存空间在本函数内申请,调用者释放;
Return Value
0:成功 -1:任何出错情况(包括路线不存在、站点不存在、起点和终点重叠等等)
--------------------------------
(4) SearchBestPathes(附加题)
Description
输出从起点站到终点站的最优路线
Prototype
int SearchBestPathes(unsigned int SrcStation,unsigned int DesStation,unsigned int *pPathNum, unsigned int* pPathLen,unsigned int** ppPathes);
Input Param
SrcStation 起点站;
DesStation 终点站;
Output Param
pPathNum 最优路线条数;
pPathLen 最短路线长度;
ppPathes 存储最短路线的内存地址,内存格式见下图,内存空间在本函数内申请,调用者释放;
Return Value
0:成功 -1:任何出错情况(包括路线不存在、站点不存在、起点和终点重叠等等)
--------------------------------
(5) Clear
Description 清空所有的线路信息
Prototype
void Clear();
Input Param
无
Output Param
无
Return Value
无
算法提示
说明:提示的并不是本题的唯一算法,考生可根据情况自行选择是否采用。
1)最短路线长度算法提示
step1: 找到从起点出发,前进一站能到达的所有车站,记为SET1,若终点已包含在SET1中,则最短路线长度为1。
step2:对SET1中所有车站,找到前进一站能到达的所有车站,记为SET2,若终点已包含在SET2中,则最短路线长度为2。
...以此类推... stepn:
对SETn-1中所有车站,找到前进一站能到达的所有车站,记为SETn,若终点已包含在SETn中,则最短路线长度为n。
2)最短路线算法提示 最短路线长度算法在遍历过程中未记录路径信息,需要增加用作记录的数据结构设 计,该数据结构在最短路线长度的计算过程中生成。
3)最优路线算法提示 在求出最短路线的基础上,对每一条路线计算换乘最小次数,从所有路线方案中 选择最优解。
薪资至少10K的一道题,你能拿下吗