--- layout: post title: The Interview and Beyond of CTCI category: Algoritm tags: [Algoritm, Interview] --- ## The Interview and Beyond ### Handling Behavioral Questions #### Why Behavioral Questions As stated earlier, interviews usually start and end with “chit chat” or “soft skills ”. This is a time to answer questions about your resume or general questions, and also an opportunity for you to ask questions. This part of the interview is targeted not only at getting to know you, but also at relaxing you. #### Be Specific, not Arrogant Arrogance is a red flag, but you still want to make yourself sound impressive. So how do you make yourself sound good without being arrogant? By being specific! Specificity means giving just the facts and letting the interviewer derive an interpretation. Consider an example: * Candidate #1: “I basically did all the hard work for the team ” * Candidate #2: “I implemented the file system, which was considered one of the most challenging components because …” Candidate #2 not only sounds more impressive, but she also appears less arrogant. #### Limit Details When a candidate blabbers on about a problem, it’s hard for an interviewer who isn’t well versed in the subject or project to understand it. CareerCup recommends that you stay light on details and just state the key points. That is, consider something like this: “By examining the most common user behavior and applying the Rabin-Karp algorithm, I designed a new algorithm to reduce search from O(n) to O(log n) in 90% of cases. I can go into more details if you’d like ” This demonstrates the key points while letting your interviewer ask for more details if he wants to. #### Ask Good Questions Remember those questions you came up with while preparing? Now is a great time to use them! #### Stucture Answers Using S.A.R. Structure your responses using S A R : Situation, Action, Response. That is, you should start off outlining the situation, then explaining the actions you took, and lastly, describing the result. Example: “Tell me about a challenging interaction with a teammate.” Situation: On my operating systems project, I was assigned to work with three other people. While two were great, the third team member didn’t contribute much. He stayed quiet during meetings, rarely chipped in during email discussions, and struggled to complete his components. Action: One day after class, I pulled him aside to speak about the course and then moved the discussion into talking about the project. I asked him open-ended questions on how he felt it was going, and which components he was excited about tackling. He suggested all the easiest components, and yet offered to do the write-up. I realized then that he wasn’t lazy – he was actually just really confused about the project and lacked confidence. I worked with him after that to break down the components into smaller pieces, and I made sure to complement him a lot on his work to boost his confidence. Result: He was still the weakest member of the team, but he got a lot better. He was able to finish all his work on time, and he contributing more in discussions. We were happy to work with him on a future project. As you can see, the SAR model helps an interviewer clearly see what you did in a certain situation and what the result was. ### Handling Technical Questions #### General Advice for Technical 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 120+ that I’ve interviewed have gotten the question right instantly. So when you get a hard question, don’t panic. Just start talking aloud about how you would solve it. And, one more thing: you’re not done until the interviewer says that you’re done! What I mean here is that when you come up with an algorithm, 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. #### Five Steps to a Technical Questions * Ask your interviewer questions to resolve ambiguity. * Design an Algorithms. * Write pseudo-code first, but make sure to tell your interviewer 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. * Write your code, not too slow and not too fast. * Test your code and carefully fix any mistakes. 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 specifically 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 We now have a pretty different problem: sort an array containing a million integers between 0 and 130. How do we solve this? Just create an array with 130 elements and count the number of ages at each value. Step 2: Design an Algorithm Designing an algorithm can be tough, but our five approaches to algorithms can help you out. While you’re designing your algorithm, don’t forget to think about: * What are the space and time complexities? * What happens if there is a lot of data? * Does your design cause other issues? (ie , if you’re creating a modified version of a binary search tree, did your design impact the time for insert/find/delete?) * If there are other issues, did you make the right trade-offs? * If they gave you specific data (e g , mentioned that the data is ages, or in sorted order), have you leveraged that information? There’s probably a reason that you’re given it. Step 3: Pseudo-Code Writing pseudo-code first can help you outline your thoughts clearly and reduce the number of mistakes you commit. But, make sure to tell your interviewer that you’re writing pseudo- code first and that you’ll follow it up with “real” code. Many candidates will write pseudo- code in order to ‘escape’ writing real code, and you certainly don’t want to be confused with those candidates. Step 4: Code You don’t need to rush through your code; in fact, this will most likely hurt you. Just go at a nice, slow methodical pace. Also, remember this advice: * Use Data Structures Generously: Where relevant, use a good data structure or define your own. For example, if you’re asked a problem involving finding the minimum for a group of people, consider defining a data structure to represent a Person. This shows your interviewer that you care about good object oriented design. * Don’t Crowd Your Coding: This is a minor thing, but it can really help. When you’re writing code on a whiteboard, start in the upper left hand corner – not in the middle. This will give you plenty of space to write your answer. Step 5: Test Yes, you need to test your code! Consider testing for: * Extreme cases: 0, negative, null, maximums, etc. * User error: What happens if the user passes in null or a negative value? * General cases: Test the normal case. If the algorithm is complicated or highly numerical (bit shifting, arithmetic, etc), consider testing while you’re writing the code rather than just at the end. Also, when you find mistakes(which you will), carefully think through why the bug is oc- curing. One of the worst things I saw while interviewing was candidates who recognized a mistake and tried making “random” changes to fix the error. For example, imagine a candidate writes a function that returns a number. When he tests his code with the number ‘5’ he notices that it returns 0 when it should be returning 1. So, he changes the last line from “return ans” to “return ans+1,” without thinking through why this would resolve the issue. Not only does this look bad, but it also sends the candidate on an endless string of bugs and bug fixes. When you notice problems in your code, really think deeply about why your code failed before fixing the mistake. ### Five Algorithm Approaches There’s no sure fire approach to solving a tricky algorithm problem, but the approaches below can be useful. Keep in mind that the more problems you practice, the easier it will to identify which approach to use. Also, remember that the five approaches can be “mixed and matched ”. That is, once you’ve applied “Simplify & Generalize”, you may want to implement Pattern Matching next. #### Examplify Description: Write out specific examples of the problem, and see if you can figure out a general rule. #### Pattern Matching Description: Consider what problems the algorithm is similar to, and figure out if you can modify the solution to develop an algorithm for this problem. #### Simplify and Generalize Description: Change a constraint (data type, size, etc) to simplify the problem. Then try to solve it. Once you have an algorithm for the “simplified” problem, generalize the problem again. #### Base case and build Description: Solve the algorithm first for a base case (eg, just one element)Then, try to solve it for elements one and two, assuming that you have the answer for element one. Then, try to solve it for elements one, two and three, assuming that you have the answer to ele- ments one and two. #### Data Structure Brainstorm Description: This is hacky, but it often works. Simply run through a list of data structures and try to apply each one. ### Top Ten mistakes Candidates Make #### Practicing on a Computer: using a compiler only to verify your solutions If you were training for a serious bike race in the mountains, would you practice only by bik- ing on the streets? I hope not. The air is different. The terrain is different. Yeah, I bet you’d practice in the mountains. Using a compiler to practice interview questions is like this - and you’ve basically been biking on the streets your entire life. Put away the compiler and get out the old pen and paper. Use a compiler only to verify your solutions. #### Not Rehearsing Behavioral Questions Many candidates spend all their time prepping for technical questions and overlook the behavioral questions. Guess what? Your interviewer is judging those too! And, not only that - your performance on behavioral questions might bias your interviewer’s perception of your technical performance. Behavioral prep is relatively easy and well-worth your time. Looking over your projects and positions and think of the key stories. Rehearse the stories. #### Not Doing a Mock Interview Imagine you’re preparing for a big speech. Your whole school, or company, or whatever will be there. Your future depends on this. And all you do to prepare is read the speech to yourself. Silently. In your head. Crazy, right? Not doing a mock interview to prepare for your real interview is just like this. If you’re an engineer, you must know other engineers. Grab a buddy and ask him/her to do a mock interview for you. You can even return the favor! #### Trying to Memorize Solutions Quality beats quantity. Try to struggle through and solve questions yourself; don’t flip directly to the solutions when you get stuck. Memorizing how to solve specific problem isn’t going to help you much in an interview. Real preparation is about learning how to approach new problems. #### Talking too Much I can’t tell you how many times I’ve asked candidates a simple question like “what was the hardest bug on Project Pod?”, only to have them ramble on and on about things I don’t understand. Five minutes later, when they finally come up for air, I’ve learned nothing - except that they’re a poor communicator. When asked a question, break your answer into three parts (Situation/Action/Response, Issue 1/Issue 2/Issue 3, etc) and speak for just a couple sentences about each. If I want more details, I’ll ask! #### Talking too Little Psst - let me tell you a secret: I don’t know what’s going on in your head. So if you aren’t talk- ing, I don’t know what you’re thinking. If you don’t talk for a long time, I’ll assume that you aren’t making any progress. Speak up often, and try to talk your way through a solution. This shows your interviewer that you’re tackling the problem and aren’t stuck. And it lets them guide you when you get off-track, helping you get to the answer faster. And it shows your awesome communication skills. What’s not to love? #### Rushing: Take your time in a coding probleme - don't rush Coding is not a race, and neither is interviewing. Take your time in a coding problem - don’t rush! Rushing leads to mistakes, and reveals you to be careless. Go slowly and methodically, testing often and thinking through the problem thoroughly. You’ll finish the problem in less time in the end, and with fewer mistakes. #### Not Debugging Would you ever write code and not run it or test it? I would hope not! So why do that in an interview? When you finish writing code in an interview, “run” (or walk through) the code to test it. Or, on more complicated problems, test the code while writing it. #### Sloppy Coding Did you know that you can write bug-free code while still doing horribly on a coding question? It’s true! Duplicated code, messy data structures (ie , lack of object oriented design), etc. Bad, bad, bad! When you write code, imagine you’re writing for real-world maintainability. Break code into sub-routines, and design data structures to link appropriate data. #### Giving Up Have you ever taken a computer adaptive test? These are tests that give you harder questions the better you do. Take it from me - they’re not fun. Regardless of how well you’re actually doing, you suddenly find yourself stumbling through problems.Yikes! ### Frequently Asked Questions #### Do I have to get every question right? No. A good interviewer will stretch your mind. They’ll want to see you struggle with a difficult problem. If a candidate is good, they’ll ask harder and tougher questions until he/she is stumped! Thus, if you have trouble on a question, all it means is that the interviewer is doing their job! #### Should I tell my interviewer if I know a question? Yes! You should definitely tell your interviewer if you’ve previously heard the question. This seems silly to some people - if you already know the question (and answer), you could ace the question, right? Not quite. Here’s why we strongly recommend that you tell your interviewer that you’ve heard the question: * Big honesty points. This shows a lot of integrity. That’s huge. Remember that the interviewer is evaluating you as a potential teammate. I don’t know about you, but I personally prefer to work with honest people! * The question might have changed ever-so-slightly. You don’t want to risk repeating the wrong answer. * If you easily belt out the right answer, it’s obvious to the interviewer. They know how hard a problem is supposed to be. It’s very hard to “pretend” to struggle through a question, because you just can’t approach it the same way other candidates do. #### How should I dress? Generally, candidates should dress one small step above the average employee in their posi- tion, or as nice as the nicest dressed employees in their position. In most software firms, this means that jeans (nice jeans with no holes) or slacks with a nice shirt or sweater is fine. In a bank or another more formal institution, avoid jeans and stick with slacks. #### What language should I use? Many people will tell you “whatever language you’re most comfortable with,” but ideally you want to use a language that your interviewer is comfortable with. I’d usually recommend coding in either C, C++ or Java, as the vast majority of interviewers will be comfortable in one of these languages. My personal preference for interviews is Java (unless it’s a question requiring C / C++), because it’s quick to write and almost everyone can read and understand Java, even if they code mostly in C++ (Almost all the solutions in this book are written in Java for this reason ). #### I didn’t hear back immediately after my interview. Am I rejected? Absolutely not. Responses can be held up for a variety of reasons that have nothing to do with a good or bad performance. For example, an interviewer could have gone on vacation right after your interview. A company will always tell you if you’re rejected (or at least I’ve never heard of a company which didn’t). #### Can I re-apply to a company after getting rejected? Almost always, but you typically have to wait a bit (6 months – 1 year). Your first bad inter- view usually won’t affect you too much when you re-interview. Lots of people got rejected from Google or Microsoft and later got an offer. #### How are interview questions selected? This depends on the company, but any number of ways: * Pre-Assigned List of Questions: This is unusual at bigger companies * Assigned Topics: Each interviewer is assigned a specific area to probe, but decides on his/her own questions * Interviewer’s Choice: Each interviewer asks whatever he/she wants. Usually, under this system, the interviewers have a way of tracking which questions were asked to a candidate to ensure a good diversity of questions.This system usually means that interviewers will each have a “stock” set of five or so questions that they ask candidates. #### What about experienced candidates? This depends a lot on the company. On average though, experienced candidates will slightly get more questions about their background, and they might face higher standards when discussing system architecture (if this is relevant to their experience). For the most part though, experienced candidates face much the same process. Yes, for better or worse, experienced candidate should expect to go through the same coding and algorithm questions. With respect to their performance, they could face either higher standards (because they have more experience) or lower standards (because it’s likely been many years since they worked with certain data structures). ### Additionally #### Special Advice for Software Design Engineers in Test (SDETs) Not only must SDETs master testing, but they also have to be great coders. Thus, we recommend the follow preparation process: * Prepare the Core Testing Problems: For example, how would you test a light bulb? A pen? A cash register? Microsoft Word? The Testing Chapter will give you more background on these problems. * Practice the Coding Questions: The #1 thing that SDETs get rejected for is coding skills. Make sure that you prepare for all the same coding and algorithm questions that a regular developer would get. * Practice Testing the Coding Questions: A very popular format for SDET question is “Write code to do X,” followed up by “OK, now test it ” So, even when the question doesn’t specifically ask for this, you should ask yourself, “how would you test this?” Remember: any problem can be an SDET problem! #### Suggestions and Corrections While we do our best to ensure that all the solutions are correct, mistakes will be made. Moreover, sometimes there is no “right” answer. ## Reference * [Cracking the Coding Interview](http://www.crackingthecodinginterview.com/) * [Solutions of Cracking the coding interview V4. Written in C++.](http://hawstein.com/posts/ctci-solutions-contents.html)