資料講義教案成果cracking the coding interview fourth edition150programming questions and solutions

1、FOURTH EDITIONCRACKING THEC O D I N GI N T E R V I E W150 programming interview questions and solutions Plus:Five proven approaches to solving tough algorithm questions Ten mistakes candidates make - and how to avoid them Steps to prepare for behavioral and technical questionsInterviewer war stories

2、: a view from the interviewers sideGAYLE LAAKMANNFounder and CEO, CareerCCRACKING THECODINGINTERVIEWCRACKING THEC O D I N GI N T E R V I E W150 Programming Interview Questions and SolutionsGAYLE LAAKMANNFounder and CEO, CareerCCareerCup, LLC Seattle, WACRACKING THE CODING INTERVIEW, FOURTH EDITIONCo

3、pyright 2008 - 2010 by Gayle Laakmann.s.Published by CareerCup, LLC, Seattle, WA. Version 3.21090410302210.Visit our website at:duced in any mannertions in critical articles or reviews. No part of this book may be used or repro- rmission except in the case of brief quota-For more information, contac

4、t support.Printed in United States of America978-1-450-59320-5 9781450593205 (ISBN 13)Table of ContentsForeword 4 Introduction 5 Behind the Scenes 7 The Microsoft Interview 8The Amazon Interview 9TheInterview 10The Apple Interview 11 The Yahoo Interview 12 Interview War Stories 13 Before the Intervi

5、ew 20 Resume Advice 21 Behavioral Preparation 23 Technical Preparation 25 The Interview and Beyond 28 Handling Behavioral Questions 29 Handling Technical Questions 31 Five Algorithm Approaches 34 The Offer and Beyond 37 Top Ten Mistakes Candidates Make 39 Frequently Asked Questions 41 Interview Ques

6、tions 44 Data Structures 46 Chapter 1 | Arrays and Strings 47 Chapter 2 | Linked Lists 49 Chapter 3 | Stacks and Queues 51 Chapter 4 | Trees and Graphs 53 Concepts and Algorithms 56 Chapter 5 | Bit Manipulation 57Chapter 6 | Brain Teasers 591Cracking the Coding InterviewTable of ContentsChapter 7 |

7、Object Oriented Design 61 Chapter 8 | Recursion 63 Chapter 9 | Sorting and Searching 65 Chapter 10 | Mathematical 67 Chapter 11 | Testing 69 Chapter 12 | System Design and Memory Limits 71 Knowledge Based 74 Chapter 13 | C+ 75 Chapter 14 | Java 77 Chapter 15 | Databases 79 Chapter 16 | Low Level 81

8、Chapter 17 | Networking 83 Chapter 18 | Threads and Locks 85 Additional Review Problems 88 Chapter 19 | Moderate 89 Chapter 20 | Hard 91 Solutions 94 Index 301 Mock Interviews 303About the Author 304CareerCup com2ForewordDear Readers,Welcome to the 4th edition of Cracking the Coding Interview This v

9、olume updates the 3rd edition with new content and refreshed information Be sure to check out our website, www careercup com, to connect with other candidates and to discover new resources For those of you new to technical interviews, the process can seem overwhelming Inter- viewers throw questions

10、at you, expect you to whip up brilliant algorithms on the spot, andthen ask you to write beautiful code on a whit Luckily, everyone else is in the sameboat, and youre already working hard to prepare Good job!As you get ready for your interviews, consider these suggestions:Write Code on Paper: Most i

11、nterviewers wont give you a computer and will insteadexpect you to write code on a whitor on paper To simulate this environment, tryanswering interview problems by writing code on paper first, and then typing them intoa computer as-is Whit with constant practice / paper coding is a special skill, wh

12、ich can be masteredKnow Your Resume: While technical skills are extremely important, thats no reason to neglect your own resume Make sure to prepare yourself to give a quick summary of any project or job you were involved with, and to discuss the hardest and most interesting problems you encountered

13、 along the day Dont Memorize Solutions: While this book offers a representative sample of interview questions, there are still thousands of interview questions out there Memorizing solu- tions is not a great use of your time Rather, use this book to explore approaches to problems, to learn new conce

14、pts, and to practice your skills Talk Out Loud: Interviewers want to understand how you think and approach prob- lems, so talk out loud while youre solving problems Let the interviewer see how youre tackling the problem, and they just might guide you as well And remember - interviews are hard! In my

15、 years of interviewing at, I saw someinterviewers ask “easy” questions while others ask harder questions But you know what? Getting the easy questions doesnt make it any easier to get the offer Receiving an offer is not about solving questions flawlessly (very few candidates do!), but rather, it is

16、about answering questions better than other candidates So dont stress out when you get a tricky question - everyone else probably thought it was hard too!Im excited for you and for the skills you are going to develop Thorough preparation will give you a wide range of technical and communication skil

17、ls It will be well-worth it no matter where the effort takes you!Study hard, practice, and good luck!Gayle LaakmannCareerCup com4IntroductionSomethings WrongWe walked out of the hiring meeting frustrated, again Of the ten “passable” candidates we reviewed that day, none would receive offers Were we

18、being too harsh, we wondered?I, in particular, was disappointed We had rejected one of my candidates A former student One who I had referred He had a 3 73 GPA from the University of Washington, one of the best computer science schools in the world, and had done extensive work on open source projects

19、 He was energetic He was creative He worked hard He was sharp He was a true geek, in all the best ways But, I had to agree with the rest of the committee: the data wasnt there Even if my emphatic recommendation would sway them to reconsider, he would surely get rejected in the later stages of the hi

20、ring process There were just too many red flags Though the interviewers generally believed that he was quite intelligent, he had struggled to develop good algorithms Most successful candidates could fly through the first ques- tion, which was a twist on a well known problem, but he struggled to deve

21、lop his algorithm When he came up with one, he failed to consider solutions that optimized for other scenar- ios Finally, when he began coding, he flew through the code with an initial solution, but it was riddled with mistakes that he then failed to catch Though he wasnt the worst candidate wed see

22、n by any measure, he was far from meeting “the bar ” Rejected When he asked for feedback over the phone a couple of weeks later, I struggled with what to tell him Be smarter? No, I knew he was brilliant Be a better coder? No, his skills were on-par with some of the best Id seen Like many motivated c

23、andidates, he had prepared extensively He had read K&Rs classic C book and hed reviewed CLRS famous algorithms textbook He could describe in detail the myriad of ways of balancing a tree, and he could do things in C that no sane programmer should ever want to do I had to tell him the unfortunate tru

24、th: those books arent enough Academic books prepareyou for fancy research, but theyre not going to help you mun interview Why? Ill giveyou a hint: your interviewers havent seen Red-Black Trees since they were in school either To crack the coding interview, you need to prepare with real interview que

25、stions You must practice on real problems, and learn their patterns Cracking the Coding Interview is the result of my first-hand experience interviewing at top companies It is the result of hundreds of conversations with candidates It is the result of the thousands of candidate- and interviewer- con

26、tributed questions And its the result of seeing so many interview questions from so many firms Enclosed in this book are 150 of the best interview questions, selected from thousands of potential problems 5Cracking the Coding InterviewIntroductionMy ApproachThe focus of Cracking the Coding Interview

27、is algorithm, coding and design questions Why? Because while you can and will be asked behavioral questions, the answers will be as varied as your resume Likewise, while many firms will ask so-called “trivia” questions (e g , “What is a virtual function?”), the skills developed through practicing th

28、ese questions are limited to very specific bits of knowledge The book will briefly touch on some of these questions, to show you what theyre like, but I have chosen to allocate space where theres more to learn My PassionTeaching is my passion I love helping people understand new concepts, and giving

29、 them tools so that they can excel in their passions My first experience“officially” teaching was in college at the University of Pennsylvania, when I became a teaching assistant for an undergraduate Computer Science course during my second year I went on to TA for several other courses, and eventua

30、lly launched my own CS course at the university focused on “hands-on” skills As an engineer at, training and mentoring “Nooglers” (yes, thats really what they callnewemployees!) were some of the things I enjoyed most I went on to use my “20%time” to teach two Computer Science courses at the Universi

31、ty of Washington Cracking the Coding Interview and CareerCup com reflect my passion for teaching Even now, you can often find me “hanging out” at CareerCup com, helping users who stop by for assistance Join us Gayle LaakmannCareerCup com6Behind the ScenesFor many candidates, interviewing is a bit of

32、 a black box You walk in, you get pounded with questions from a variety of interviewers, and then somehow or other you return with an of- fer or not Have you ever wondered:How do decisions get made?Do your interviewers talk to each other? What does the company really care about?Well, wonder no more!

33、CareerCup sought out interviewing experts from five top companies - Microsoft, G Amazon, Yahoo and Apple - to show you what really happens “behind the scenes ” These experts will walk us through a typical interview day and describe whats taking place outside of the interviewing room, and what happen

34、s after you leave Our interviewing experts also told us whats different about their interview process From barraisers (Amazon) to Hiring Committees (), each company has its own quirks Knowingthese idiosyncrasies will help you to react better to a super-tough interviewer, or to avoid being intimidate

35、d when two interviewers show up at the door (Apple!) In addition, our specialists offered insight as to what their company stresses in their inter- views While almost all software firms care about coding and algorithms, some companies focus more than others on specific aspects of the interview Wheth

36、er this is because of the companys technology or its history, now youll know what and how to prepare So, join us as we take you behind the scenes at Microsoft, ple , Amazon, Yahoo and Ap-7Cracking the Coding InterviewBehind the Scenes | The Microsoft InterviewMicrosoft wants smart people Geeks Peopl

37、e who are passionate about technology You probably wont be tested on the ins and outs of C+ APIs, but you will be expected to writecode on th In a typical interview, youll show up at Microsoft at some time in the morning and fill out initial paper work Youll have a short interview with a recruiter w

38、here he or she will give you a sample question Your recruiter is usually there to prep you, and not to grill you on techni- cal questions Be nice to your recruiter Your recruiter can be your biggest advocate, evenpushing to re-interview you if you stumbled on your first interview They can to be hire

39、d - or not!for youDuring the day, youll do four or five interviews, often with two different teams Unlike many companies, where you meet your interviewers in a conference room, youll meet with your Microsoft interviewers in their office This is a great time to look around and get a feel for the team

40、 culture Depending on the team, interviewersmay or may not share their feedback on you with the rest of the interview loop When you complete your interviews with a team, you might speak with a hiring manager If so, thats a great sign! It likely means that you passed the interviews with a particular

41、team Its now down to the hiring managers decision You might get a decision that day, or it might be a week After one week of no word from HR, send them a friendly asking for a status update CareerCup com8Definitely Prepare:“Why do you want to work for Microsoft?”In this question, Microsoft wants to

42、see that youre passionate about technology. A great answer might be, “Ive been using Microsoft software as long as I can re- member, and Im really impressed at how Microsoft manages to create a product that is universally excellent. For example, Ive been using Visual Studio recently to learn game pr

43、ogramming, and its APIs are excellent.” Note how this shows a passion for technology!Whats Unique:Youll only reach the hiring manager if youve done well, but if you do, thats a great sign!Behind the Scenes | The Amazon InterviewAmazons recruiting process usually begins with one or two phone screens

44、in which you in- terview with a specific team The engineer who interviews you will usually ask you to write simple code and read it aloud on the phone They will ask a broad set of questions to explore what areas of technology youre familiar with Next, you fly to Seattle for four or five interviews w

45、ith one or two teams which have selectedyou based on your resume and phone interviews You will have to code on a whit,and some interviewers will stress other skills Interviewers are each assigned a specific area to probe and may seem very different from each other They can not see other feedback unt

46、il they have submitted their own and they are discouraged from discussing it until the hiring meeting Amazons “bar raiser” interviewer is charged with keeping the interview bar high They at- tend special training and will interview candidates outside their group in order to balance out the group its

47、elf If one interview seems significantly harder and different, thats most like-ly the bar raiser Thishas bothsignificant experience with interviews and veto power in the hiring decision You will meet with your recruiter at the end of the day Once your interviewers have entered their feedback, they w

48、ill meet to dis- cuss it They will be the people making the hiring decision While Amazons recruiters are excellent at following up with candidates, occa- sionally there are delays If you havent heard from Amazon within a week, werecommend a friendly 9Cracking the Coding InterviewDefinitely Prepare:A

49、mazon is a web-based company, and that means they care about scale. Make sure you prepare for questions in “Large Scale.” You dont need a backgroundin distributed systems to answer these questions. See our recommendations in the System Design and Memory Limits Chapter.Additionally, Amazon tends to a

50、sk a lot of questions about object oriented design. Check out the Object OrientedDesign chapter for sample questions and suggestions.Whats Unique:The Bar Raiser, who is brought in from a different team to keep the bar high.Behind the Scenes | TheInterviewThere are many scary stories floating around

51、about Ginterviews, but its mostly justthat: stories The interview is not terribly different from Microsofts or Amazons However,because munication HR can be a little disorganized, we recommend being proactive in com-Aengineer performs the first phone screen, so expect tough technical questions On your