美国软件公司技术面试题及答案（基本算法类）

(15Points)A.Canyougiveanexampleofaheapwithsevendistinctelementssuchthatapre-ordertraversaloftheheapyieldstheelementsinsortedorder?Ifnotwhy?

Answer:

1

2 5

3 467

B.Canyougiveanexampleofaheapwithsevendistinctelementssuchthatanin-ordertraversaloftheheapyieldstheelementsinsortedorder?Ifnotwhy?

Answer:

No.Inain-ordertraversalofatreerootedatnodev,theresultisv.leftChildren(maybeasub-tree),v,v.rightChildren(maybeasub-tree).Ifthetreeisaheap,becauseofHeap-OrderProperty,thereexistsomekey(s)inv.leftChildrengreaterthanthekeyofv,andthesituationisthesamewithv.rightChildren,sotheresultcannotbeinsortedorder.

C.Canyougiveanexampleofaheapwithsevendistinctelementssuchthatapost-ordertraversaloftheheapyieldstheelementsinsortedorder?Ifnotwhy?

Answer:

1

5 2

7 643

(15Points)ConsiderannbynmatrixMwhoseelementsare0’sand1’ssuchthatinanyrow,allthe1’scomebeforeany0’sinthatrow.AssumingAisalreadyinmemory,describeanalgorithmrunninginO(n)timeforfindingtherowofMthatcontainthemostof1’s.

Answer:

AlgorithmfindMaxRow()

i<-0

j<-0

maxCount<-0

maxRow<-0

whilei<n

whileM[i][j]=1

j<-j+1

if(j=n)

returni

ifj>maxCount

maxCount<-j

maxRow<-i

i<-i+1

returnmaxRow

(15Points)ConsiderthesamematrixMinquestion2.DescribeanalgorithmrunninginO(nlogn)forcountingthenumberof1’sinM.

Answer:

Algorithmcount()

i<-0

j<-0

s<-0

whilei<n

whileM[i][j]=1

j<-j+1

whileM[i][j-1]=0

j<-j-1

s<-s+j

returns

Notquite.Youshoulduseabinarysearchoneachrowtofindthelocationoftherightmost1.

(15Points)Wearegiventwon-elementsortedsequencesAandBthatshouldnotbeviewedassets(thatis,AandBmaycontainduplicateelements).DescribeanO(n)methodforcomputingasequencerepresentingthesetAUB(withnoduplicateelements).

Answer:

Assumethattheyaresortedinnon-decreasingorder.

Algorithmunion(A,B,S)

Input:sequenceAandBsortedinnon-decreasingorder,andenemptysequenceS

Output:S,AUB

S.insertLast(min{A.first().element(),B.first().element()})

while(not(A.isEmpty()orB.isEmpty()))

ifA.first().element()<=B.first().element()

ifS.last().element()=A.first().element()

A.remove(A.first())

else

S.insertLast(A.remove(A.first()))

else

ifS.last().element()=B.first().element()

B.remove(B.first())

else

S.insertLast(B.remove(B.first()))

while(notA.isEmpty())

ifS.last().element()=A.first().element()

A.remove(A.first())

else

S.insertLast(A.remove(A.first()))

while(notB.isEmpty())

ifS.last().element()=B.first().element()

B.remove(B.first())

else

S.insertLast(B.remove(B.first()))

(10Points)YouarebeinginterviewedtobehiredasacashierinaDollarStore.TheManagerasksyoutodevelopanefficientgreedyalgorithmformakingchangeforaspecifiedvalueundera$1usingaminimumnumberofcoinsofquarters,dimes,nickels,andpennies.Describeyouralgorithm.Youwillnotbehiredifyouralgorithmisnotgreedy!

Answer:

Algorithm

Input:x,theamountofmoneyintermsofcent

Output:Q,D,N,P------numberofeachunity

Q,D,N,P<-0

while(x>=25)

Q<-Q+1

x<-x-25

while(x>=10)

D<-D+1

x<-x-10

while(x>=5)

N<-N+1

x<-x-5

while(x>=1)

P<-P+1

x<-x-1

(15Points)Giventhestoryinquestion5,ifthedenominationswerenot$0.25,$0.10,$.05,and$0.01(butsomeotherdenominations),doyouthinkyourgreedyalgorithmstillworks?JustifyyouranswerwithsolidargumentsorexamplestobequalifiedforajobatUSTreasury.

Answer:

Yes,Ithinkso.

IftherearedenominationsofD0,D1,...,Dn,andthatD0<D1<...<Dn,D0mustbeafactorofx,namelyxmodD0=0.

SupposeweexpresstheamountofmoneyxinonlyD0,thentotalnumberisCount(D0)+Count(D1)+...+Count(Dn)=x/D0+0+...+0.

IfwetransfertheexpressionfromD0to(D0andDk)(k>0),thetotalnumberwilldecreasetox/Dk+y(y=(xmodDk)/D0).So,thefirstpartx/DkisdecreasingwithDkincreasing,whilethesecondpartyisasub-problemoftheoriginalproblemandwecansolveitwiththesameprinciple.

No,thisisincorrect.Imagineyouhadcoinswithdenominations1c,9c,10candhadtomakechangefor18c,thenthegreedyalgorithmwouldmakechangewitha10cand81ccoins,whilethebestsolutionis29ccoins.

(15Points)Designadivide-and-conqueralgorithmforfindingtheminimumandmaximumelementsofnnumbersusingnomorethan3n/2comparisons.

Answer:

pickarandomelementTargetrandomlyfromtheset

dividetheremainingelementsintotwosets

G:elementsthatgreaterthanTarget

S:elementsthatsmallerthanTarget

(throwawayelementsthatequaltoTarget)

ifGisNULL

Targetisthemaximumelement

ifSisNULL

Targetistheminimumelement

ifGisnotNULL

recursivelydo

pickarandomelementTargetfromtheremainingelements

throwawayelementsthatsmallerthanorequaltoTarget

isSisnotNULL

recursivelydo

pickarandomelementTargetfromtheremainingelements

throwawayelementsthatgreaterthanorequaltoTarget

Fromthesolutions,

Dividethesetofnnumbersn/2groupsoftwoele