美国软件公司技术面试题及答案高级算法类-豆柴文库

您所在位置：网站首页 / 美国软件公司技术面试题及答案高级算法类.docx / 文档详情

在线预览结束，喜欢就下载吧，查找使用更方便

20 金币

下载文档

/ 4

下载提示

如果您无法下载资料，请参考说明：

1、部分资料下载需要金币，请确保您的账户上有足够的金币

2、已购买过的文档，再次下载不重复扣费

3、资料包下载后请先用软件解压，在使用对应软件打开

文本预览

(15Points)Drawasimple,connected,undirected,weightedgraphwith8verticesand16edges,eachwithuniqueedgeweights.IllustratetheexecutionofPrim-Jarnikalgorithmonthisgraph.(Notethatsincethegraphisconnectedwithdistinctweights,thereisonlyoneminimumspanningtreeforthisgraph.)
1
2
3
4
5
6
7
8
1
2
3
4
5
7
6
8
9
10
11
12
13
14
15
16
Answer:
1
2
3
4
5
6
7
8
1
2
3
4
5
7
6
8
9
10
11
12
13
14
15
16
	












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













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
















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













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
















(15Points)Whatistheworst-caserunningtimeoftheFord-Fulkersonifalledgecapacitiesareboundedbyaconstant?Justifyyouranswer.
Answer:
	Lettheconstantbek;sbethesource;tbethesink;theworst-caserunningtimeoftheFord-FulkersonisO(m*min{deg(s),deg(t)}).
	Proof:
	Sinceeveryedgecapacityisk,
	soifthereisanaugmentingpath,theΔmustbek;
		soaflowofkunitswillbepushedalongoneoftheoutgoingedgeofs,
		andthisflowwillbefilloneoftheingoingedgeoft.
	Sincethetotalunitsgoingoutofsareequaltothetotalunitscomingintot,
	sothemaximumflow|f*|isk*min{deg(s),deg(t)}.
	Thus,O(m*|f*|)
		=O(m*k*min{deg(s),deg(t)})
		=O(m*min{deg(s),deg(t)})(kisaconstant).
	

(15Points)Considertheproblemofelectingaleaderprocessorinaringofprocessors,eachofwhichhasauniqueid.DesignasynchronousalgorithmwhoserunningtimeandmessagecomplexityisO(nlogn).

Hint:Consideranalgorithmwithlognphases,whereyouhaveeachprocessorwho,inphasei,thinksitmightbealeader,sendouta“probe”messageineachdirectionthatgoes2ihopsandcomesbackifitfindsnoprocessorwithloweridvalue.
Answer:
AlgorithmRingLeader(id):
phase<-0
done<-false
happy<-true
repeat
	ifhappythen
		phase<-phase+1
		M<-[Candidateisid.2^phase]
		sendMtopreviousprocessorandn