Hacking a Google Interview Practice Questions Person B

[Pages:5]HackingaGoogleInterviewPracticeQuestions?

PersonB

Question:BinarySearchTreeValidity

Writeafunctiontodeterminewhetheragivenbinarytreeofdistinctintegersisa validbinarysearchtree.Assumethateachnodecontainsapointertoitsleftchild,a pointertoitsrightchild,andaninteger,butnotapointertoitsparent.Youmayuse anylanguageyoulike. GoodAnswer:Notethatit'snotenoughtowritearecursivefunctionthatjustchecks iftheleftandrightnodesofeachnodearelessthanandgreaterthanthecurrent node(andcallsthatrecursively).Youneedtomakesurethatallthenodesofthe subtreestartingatyourcurrentnodearewithinthevalidrangeofvaluesallowedby thecurrentnode'sancestors.Thereforeyoucansolvethisrecursivelybywritinga helperfunctionthatacceptsacurrentnode,thesmallestallowedvalue,andthe largestallowedvalueforthatsubtree.Anexampleofthisisthefollowing(inJava): boolean isValid(Node root) {

return isValidHelper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);

}

boolean isValidHelper(Node curr, int min, int max) { if (curr.left != null) { if (curr.left.value < min || !isValidHelper(curr.left, min, curr.value)) return false; } if (curr.right != null) { if (curr.right.value > max || !isValidHelper(curr.right, curr.value, max)) return false; } return true;

} TherunningtimeofthisalgorithmisO(n).

Question:OddManOut You'regivenanunsortedarrayofintegerswhereeveryintegerappearsexactly twice,exceptforoneintegerwhichappearsonlyonce.Writeanalgorithm(ina languageofyourchoice)thatfindstheintegerthatappearsonlyonce.

 GoodAnswer:Setupahashsetthatwewillputtheintegersfromthearrayinto. Haveasecondvariablethatwillkeepasum.Startgoingthroughthearrayandfor eachinteger,checktoseeifit'salreadyinthehashset.Ifitisnot,addthatintegerto thesumandstorethatintegerinthehashset.Ifitisinthehashset,subtractthat integerfromthesum.Whenthealgorithmfinishesgoingthroughthearray,thesum variableshouldbeequaltotheintegerwewerelookingfor,sinceitistheonly numberweneversubtractedfromthesum.ThistakesO(n)timeandO(n)space. int oddManOut(int[] array) {

HashSet s = new HashSet(); int sum = 0; for (int i = 0; i < array.length; i++) {

if (s.contains(array[i])) { sum = sum - array[i];

} else { s.add(array[i]); sum = sum + array[i];

} } return sum; } ReallyAwesomeAnswer:XORallthevaluesofthearraytogether!SinceXORis commutativeandisitsowninverse,eachintegerinthearraythatappearstwicewill cancelitselfout,andwe'llbeleftwiththeintegerwe'relookingfor.ThistakesO(n) timeandO(1)space.Wetoldyoubitwisestuffwashandy! int oddManOut(int[] array) { int val = 0; for (int i = 0; i < array.length; i++) {

val ^= array[i]; } return val; }

Question:DesignaPokerGame (Don'taskallthesequestionsatthesametime;askoneafteranother,sincethey builduponeachother.)Withoutwritinganyactualcode,describeasmuchas possiblehowyouwoulddesignapokergameprogram.Whatclasseswouldyou have?Whatrelationshipswouldtheyhavewitheachother?Whatwouldbethe basicflowoftheprogramandhowwouldthoseclassesplayapart?Ifyouthen wantedtoaddanewtypeofpokergame(suchasTexasHold'em),howwouldthat fitintoyourdesign?

Answer:Therearesomanypossibleanswerstothisproblemthatitwouldbe difficulttosaythatoneansweristhebest.Looktomakesurethattheymake classestosimulatethebasicpartsofapokergame(perhapsahand,thepot,agame typeorrules,around,thedeck,etc.).Usinginheritance(subclassinginobject- orientedprogramming)whereitmakessenseisalsogoodforreusabilityand extendibility.Usingdesignpatters(suchasModel-View-Controller, Listener/Observer,ortheSingletonpattern)isalsoagoodthing.Themainpointis forthemtogetusedtothinkingabouthowtheywoulddesignasystem.Most importantly,theyneedtothinkaboutsimplicity,reusability,andextendibilityin theirdesign.

Question:LeaderElection Describeatechniquetoidentifya"leader"amongagroupof10identicalservers thatareallconnectedtoeveryotherserver.Therearenopriordistinguishing characteristicsofanyofthemandthesameprogramtoidentifytheleaderstarts runningonallofthematthesametime.Afterananswerisgiven,askhowmuch networktrafficitrequiresand,if"ties"arepossible,askhowyoucanbreakties. GoodAnswer:Haveeachserverwaitarandomamountoftimeandthensay"I'mit." The"I'mit"announcementistime-stamped,andthecomputerthattime-stampedits announcementfirstiselectedtheleader.Thisapproachrequiressendingout9 messages.Ifthereisatie,thecomputerscanrepeattheprocedure. Notethatotheranswersarepossible,buteverycorrectanswerwilluserandomness insomeway.

Question:QueueUsingStacks Describeaqueuedatastructurethatisimplementedusingoneormorestacks. Don'tworryaboutrunningtime.Writetheenqueueanddequeueoperationsforthe queue.Youmayuseanylanguageyoulike. Goodanswer:Youcanusetwostacks:an"incoming"stackandan"outgoing"stack. Theenqueueanddequeueoperationswouldlooklikethis(inJava): Stack in; Stack out;

void enqueue(int value) { while (!out.isEmpty()) in.push(out.pop()); in.push(value);

}

int dequeue() {

while (!in.isEmpty())

out.push(in.pop());

return out.pop();

}

Question:InstantMessaging

Describeadesignforaninstantmessagingprogramwherethereareseveral

servers,clientsareconnectedtoeachserver,andtheserverscommunicatewith

eachother.Describetheclasses,interfaces,andsoonthatyouwoulduseandhow

youwouldorganizethem.

Answer:Asinthepreviousdesignquestions,thereisnobestanswer.Goodtopicsto

discussarehoweachclientcommunicateswithaserver,howtheserversmaintain

statewiththeotherservers,howstateinformationiscommunicatedbetween

serversandclients,andthespeed/reliabilityoftheirdesign.

Question:MaximalSubarray

Givenanarray,describeanalgorithmtoidentifythesubarraywiththemaximum

sum.Forexample,iftheinputis[1,-3,5,-2,9,-8,-6,4],theoutputwouldbe[5,-2,

9].

GoodAnswer:Observethatthesumofasubarrayfromelementitoelementjis

equaltothesumofthesubarrayfromelement1toelementjminusthesubarray

fromelement1toelementi-1.Ouralgorithmwilliteratethroughthearray.The

algorithmkeepstrackofthesumxoftheelementsnolaterthantheelement.Itwill

alsokeeptrackoftheminimumsumyofthesubarrayfromthefirstelementtoan

elementnolaterthanthecurrentelement.Finally,Itwillalsokeeptrackofthe

subarrayzwiththemaximumsumsofar.Ateachstep,weupdatexbyaddingthe

currentelementtoit.Weupdateybycheckingwhetherx ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download