SoftwareEngineeringPrepDoc

Bestofluckinyourupcominginterview!Herearesometipstohelpyouprepare.Wehopeyoulltakethe
timetoreviewthelinksandtipsinthisdocument.Pleasekeepinmindthatmanyofthesearethirdparty
resourcesandthatthisadviceisnotdirectlyendorsedbyGoogle.

1)PlanAhead :
Phoneinterview:
Foryourphoneinterviewyou'llneedacomputerwithinternetaccess.Beforeyourinterviewyou'llreceive
thelinktotheGoogleDocthatyou'llbeusinginyourinterview,mainlyforthecodingquestions.

Onsiteinterviews:
Foronsiteinterviewsmakesuretogiveyourselfplentyoftimetoarriveatourofficeonthemorningofyour
interviews.Bereadyforafulldayoftechnicalinterviews,youwanttobeatyourbestforthelastinterview,
too!

2)WhattoExpect :
Theinterviewer(s)willbeinterestedinyourknowledgeofcomputerscienceprinciples(codingability,data
structures,algorithms,systemsdesign,bigOnotation,etc.)andhowtheycanbeusedinyoursolutions.Be
preparedforsomeopenendeddiscussionofprojectsyouveworkedoninschool,atpreviousjobs,orin
yoursparetime.

3)InterviewQuestions :
Interviewtopicsmaycover:anythingonyourresume,whiteboardcodingquestions,buildinganddeveloping
complexalgorithmsandanalyzingtheirperformancecharacteristics,logicproblems,systemsdesign,and
corecomputerscienceprinciples(hashtables,stacks,arrays,etc.).ComputerSciencefundamentalsarea
prerequisiteforallengineeringrolesatGoogle,regardlessofseniority,duetothecomplexitiesandglobal
scaleoftheprojectsyoullworkon.

Topracticeforyourinterview,youmaywanttovisitthewebsitewww.topcoder.com .Launchthe"Arena"
widgetandthengotothepracticerooms.Wesuggestdoingtheproblemsinthefirst/seconddivisiontohelp
youwarmupforyourinterviews.

4)HowtoSucceed :
AtGoogle,webelieveincollaborationandsharingideas.You'lllikelyneedmoreinformationfromthe
interviewertoanalyzeandanswerthequestiontoitsfullestextent.

ItsOKtoquestionyourinterviewer!
Ifyoudon'tunderstand,askforhelporclarification.
Ifyouneedtoassumesomething,feelfreetoaskyourinterviewerifitsacorrectassumption.
Whenaskedtoprovideasolution,firstdefineandframetheproblemasyouseeit.
Describehowyouwouldliketotacklesolvingeachpartofthequestion.
Letyourinterviewerknowwhatyourethinkingbecausehe/shewillbejustasinterestedinyour
thoughtprocessasinyoursolution.
 Finally,LISTEN!EngineersarealwayscollaboratinghereatGoogle,soitsimportantthatyoucan
listentoyourinterviewerespeciallyintheeventthathe/sheistryingtoassistyou.

5)WhatisGooglelookingfor ?
Wearenotsimplylookingforengineerstosolvetheproblemstheyalreadyknowtheanswerstoweare
interestedinengineerswhocanworkouttheanswerstoquestionstheyhadnotcomeacrossbefore.

Interviewerslookattheapproachtothequestionasmuchastheanswer.Someimportantquestionsare:
Doesthecandidate...

Listencarefullyandcomprehendthequestion?
Askthecorrectquestionsbeforeproceeding?
Enjoyfindingmultiplesolutionsbeforechoosingthebestone?
Seeknewideasandmethodsfortacklingtheproblem?
Seemflexibleandopentothoughtsandnewideas?
Havetheabilitytosolveevenmorecomplexproblems?

Googleemphasizesreallyhighquality,efficient,andclearcode.Becauseallengineers(ateverylevel)
collaboratethroughouttheGooglecodebase,withanefficientcodereviewprocess,itsessentialthatevery
engineerworksatthesamehighstandard.

6)TechnicalPreparationtips

AlgorithmComplexity:
Pleasereviewcomplexalgorithms,includingbigOnotation.Formoreinformationon
algorithms,visitthelinksbelowandyourfriendlylocalalgorithmstextbook.
OnlineResources: TopcoderDataScienceTutorials,
TheStonyBrookAlgorithm
Repository
BookRecommendations: ReviewofBasicAlgorithms:IntroductiontotheDesign
andAnalysisofAlgorithms byAnanyLevitin,
AlgorithmsbyS.Dasgupta,C.H.
Papadimitriou,andU.V.Vazirani,Algorithms ForInterviewsbyAdnanAzizand
AmitPrakash, CourseMaterialsbyJeffErickson,
Algorithms
Introductionto
Algorithms byThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivestand
CliffordStein
Sorting:
Knowhowtosort.Don'tdobubblesort.
Youshouldknowthedetailsofatleastonen*log(n)sortingalgorithm,preferablytwo(say,
quicksortandmergesort).Mergesortcanbehighlyusefulinsituationswherequicksortis
impractical,sotakealookatit.
HashTables:
Bepreparedtoexplainhowtheywork,andbeabletoimplementoneusingonlyarraysin
yourfavoritelanguage,inaboutthespaceofoneinterview.
TreesandGraphs:
Studyupontrees:treeconstruction,traversal,andmanipulationalgorithms.Youshouldbe
familiarwithbinarytrees,narytrees,andtrietreesattheveryleast.Youshouldbefamiliar
withatleastoneflavorofbalancedbinarytree,whetherit'sared/blacktree,asplaytreeor
anAVLtree,andyoushouldknowhowit'simplemented.
Moregenerally,therearethreebasicwaystorepresentagraphinmemory(objectsand
pointers,matrix,andadjacencylist),andyoushouldfamiliarizeyourselfwitheach
representationanditsprosandcons.
 Treetraversalalgorithms:BFSandDFS,andknowthedifferencebetweeninorder,
postorderandpreordertraversal(fortrees).Youshouldknowtheircomputational
complexity,theirtradeoffs,andhowtoimplementtheminrealcode.
Ifyougetachance,studyuponfancieralgorithms,suchasDijkstraandA*(forgraphs).
Otherdatastructures:
Youshouldstudyuponasmanyotherdatastructuresandalgorithmsaspossible.You
shouldespeciallyknowaboutthemostfamousclassesofNPcompleteproblems,suchas
travelingsalesmanandtheknapsackproblem,andbeabletorecognizethemwhenan
interviewerasksyouthemindisguise.
OperatingSystems,SystemsProgrammingandConcurrency:
Knowaboutprocesses,threads,andconcurrencyissues.Knowaboutlocks,mutexes,
semaphoresandmonitors,andhowtheywork.Knowaboutdeadlockandlivelockandhow
toavoidthem.
Knowwhatresourcesaprocessesneeds,athreadneeds,howcontextswitchingworks,
andhowit'sinitiatedbytheoperatingsystemandunderlyinghardware.
Knowalittleaboutscheduling.Theworldisrapidlymovingtowardsmulticore,soknowthe
fundamentalsof"modern"concurrencyconstructs.
Coding:
Youshouldknowatleastoneprogramminglanguagereallywell,preferablyC/C++,Java,
Python,Go,orJavascript.(OrC#sinceit'ssimilartoJava.)
Youwillbeexpectedtowritecodeinyourinterviewsandyouwillbeexpectedtoknowafair
amountofdetailaboutyourfavoriteprogramminglanguage.
BookRecommendation: ProgrammingInterviewsExposedSecretstolandingyournext
jobbyJohnMonaganandNoahSuojanen(WileyComputerPublishing)
RecursionandInduction:
Youshouldbeabletosolveaproblemrecursively,andknowhowtouseandrepurpose
commonrecursivealgorithmstosolvenewproblems.
Conversely,youshouldbeabletotakeagivenalgorithmandproveinductivelythatitwilldo
whatyouclaimitwilldo.
DataStructureAnalysisandDiscreteMath:
Someinterviewersaskbasicdiscretemathquestions.ThisismoreprevalentatGoogle
thanatothercompaniesbecausewearesurroundedbycountingproblems,probability
problems,andotherDiscreteMath101situations.
Spendsometimebeforetheinterviewontheessentialsofcombinatoricsandprobability.
Youshouldbefamiliarwithnchoosekproblemsandtheirilkthemorethebetter.
SystemDesign:
Youshouldbeabletotakeabigproblem,decomposeitintoitsbasicsubproblems,andtalk
abouttheprosandconsofdifferentapproachestosolvingthosesubproblemsasthey
relatetotheoriginalgoal.
Googlesolvesalotofbigproblemsherearesomeexplanationsofhowwesolvedafewto
getyourwheelsturning.
OnlineResources: ResearchatGoogle:DistributedSystemsandParallel
Computing
GoogleFileSystem
GoogleBigtable
GoogleMapReduce
DevelopmentPracticesandOpenEndedDiscussion:
Sampletopicsincludevalidatingdesigns,testingwhiteboardcode,preventingbugs,code
maintainabilityandreadability,refactor/reviewsamplecode.
Sampletopics:biggestchallengesfaced,best/worstdesignsseen,performanceanalysis
andoptimization,testingandideasforimprovingexistingproducts.

7)Askmorequestions
!
MakesureyouhaveadecentunderstandingofGoogleasabusiness,beyondGoogle'smainproducts.Find
outmoreabout whatwedohereatGoogle .

Attheendoftheinterview,mostinterviewerswillaskyouifyouhaveanyquestionsaboutthecompany,
workenvironment,theirexperience,etc..Itsagoodideatohavesomequestionsreadyforeachinterview,
butdon'tworrytoomuchifyourmindgoesblank.Ifyouhavequestionsabouttheinterviewprocess,
remuneration,oryourperformance,pleasedirectthesetoyourrecruiter.

8)OtherHelpfulLinks
InterviewingatGoogle
FiveEssentialPhoneScreenQuestionsbySteveYegge
ProjectEuler
TopCoderDataScienceTutorials
GoogleProducts
GoogleStudentsBlog
Google+forStudentspage
AboutGoogle

Ifyouhaveanyadditionalquestions,pleaseletmeknow.

GOODLUCK!!!