How to Prepare for a Career and Land a Job at Apple_5

The Programming Interview 165 How to Prepare When it comes to practicing interview questions, quality matters more than quantity. There are literally thousands of sample inter-view questions online for companies like Google, Microsoft, and Amazon—don’t try to memorize the answers. It’s impossible and won’t help you anyway! The Five-Step Approach to Effective Preparation Take your time solving problems, and try the following approach in practicing questions: 1. Try to solve the problem on your own. I mean, really try to solve it. Many questions are designed to be tough—that’s OK! When you’re solving a problem, make sure to think about both the space and time complexity. Ask yourself if you could improve the time effi ciency by reducing the space efficiency. 2. Write the code for the algorithm on paper. You’ve been coding all your life on a computer, and you’ve gotten used to the many nice things about it: compilers, code completion, and so on. You won’t have any of these in an interview, so you better get used to it now. Implement the code the old-fashioned way, down to every last semicolon. 3. Test your code! By hand, that is. No cheating with a computer! 4. Type your code into a computer exactly as is. Rerun both the test cases you tried and some new ones. 5. Start a list of all the mistakes you made, and analyze what types of mistakes you make the most often. Is it specifi c mistakes? 166 The Google Résumé You can find thousands of coding interview questions on CareerCup.com that candidates have gotten from companies like Google, Microsoft, Amazon, and other major tech companies. What If I Hear a Question I Know? In offering thousands of sample interview questions on CareerCup .com and in my other book, Cracking the Coding Interview, my goal is not to help you memorize questions and then regurgi-tate answers in an interview. Interviewers want to see how you approach problems, so spitting out pre-prepared solutions won’t do you much good. If you get a question you’ve heard before, tell your interviewer! It’s not only the right thing to do; it’s also the smart thing. If you try to hide it and pretend to fumble through the answer, your inter-viewer will probably be suspicious—and lying (or hiding the truth) is perhaps the worst thing you could do in an interview. However, if you are honest and say that you’ve heard the ques-tion before, you’ll win major bonus points. Interviewers care about honesty, even if there’s usually no way to directly test it. “Must Know” Topics Most interviewers won’t ask you about specific algorithms for binary tree balancing or other complex algorithms. Frankly, they probably don’t remember these algorithms either. (Yes, that means you can put down the CLRS algorithms book.) You’re usually expected to know only the basics. Here’s a list of the absolute must-know topics: This is not, of course, an all-inclusive list. Questions may be asked on areas outside of these topics. This is merely a “must know” list. The Programming Interview 167 Data Structures Linked Lists Binary Trees Tries Stacks Queues Vectors/ArrayLists Hash Tables Algorithms Breadth First Search Depth First Search Binary Search Merge Sort Quick Sort Tree Insert/Find/etc. Concepts Bit Manipulation Singleton Design Pattern Factory Design Pattern Memory (Stack vs. Heap) Recursion Big-O Time For each of the topics, make sure you understand how to implement/use them, and (where applicable) the space and time complexity. Practice implementing the data structures and algorithms. You might be asked to implement them directly, or you might be asked to implement a modification of them. Either way, the more com-fortable you are with the implementations, the better. Memory Usage As you’re reviewing data structures, remember to practice comput-ing the memory usage of a data structure or an algorithm. Your interviewer might directly ask you much memory something takes, or you might need to compute this yourself if your problem involves large amounts of data. Data structures. Don’t forget to include the pointers to other data. For example, a doubly linked list that holds 1,000 integers will often use about 12KB of memory (4 bytes for the data, 4 bytes for the previous pointer, and 4 bytes for the 168 The Google Résumé next pointer). This means that making a singly linked list into a doubly linked list can dramatically increase memory usage. Algorithms. A recursive algorithm often takes up dramati-cally more space than an iterative algorithm. Consider, for example, an algorithm to compute the jth to last element of a singly linked list. An approach that uses an array to sort each element may be no better than a recursive algorithm—both use O(n) memory! (The best solution involves using two pointers, where one starts off j spaces ahead.) Many candidates think of their algorithms on only one dimension—time—but it’s important to consider the space com-plexity as well. We must often make a trade-off between time and space, and sometimes, we do sacrifice time effi ciency to reduce memory usage. Coding Questions Interviews are supposed to be difficult. If you don’t get every—or any—answer immediately, that’s OK! In fact, in my experience, maybe only 10 people out of the 1501 that I’ve interviewed have gotten the algorithm right instantly, and all but one of them made later mistakes on the coding. So when you get a hard question, don’t panic. Just start talking aloud about how you would solve it. And, remember: you’re not done until the interviewer says that you’re done! What I mean here is that when you come up with an algo-rithm, start thinking about the problems accompanying it. When you write code, start trying to find bugs. If you’re anything like the other 110 candidates that I’ve interviewed, you probably made some mistakes. 1. Ask your interviewer questions to resolve ambiguity. 2. Design an algorithm. The Programming Interview 169 3. Write pseudo-code first, but make sure to tell your inter-viewer that you’re writing pseudo-code! Otherwise, he/she may think that you’re never planning to write “real” code, and many interviewers will hold that against you. 4. Write your code, not too slow and not too fast. 5. Test your code and carefully fi x any mistakes. Let’s go into each of these in more detail. Step 1: Ask Questions Technical problems are more ambiguous than they might appear, so make sure to ask questions to resolve anything that might be unclear or ambiguous. You may eventually wind up with a very different—or much easier—problem than you had initially thought. In fact, many interviewers (especially at Microsoft) will specifi cally test to see if you ask good questions. Good questions might be things like: What are the data types? How much data is there? What assumptions do you need to solve the problem? Who is the user? Example: “Design an Algorithm to Sort a List” Question: What sort of list? An array? A linked list? Answer: An array. Question: What does the array hold? Numbers? Characters? Strings? Answer: Numbers. Question: And are the numbers integers? Answer: Yes. Question: Where did the numbers come from? Are they IDs? Values of something? Answer: They are the ages of customers. Question: And how many customers are there? Answer: About a million. ... - tailieumienphi.vn