Chapter 12
IN THIS CHAPTER
Knowing what kinds of puzzle problems an interviewer will ask you
Figuring out how to build puzzle solutions
Understanding that companies want problem-solvers
Getting better at solving puzzles over time
During your interview, it’s likely an interviewer will ask you to solve a programming puzzle. Not only is a puzzle is a good way to test your programming prowess, a puzzle also enables the interviewer (or group of interviewers) to see your problem-solving skills and how both sides of your brain — the logical and the emotional — respond as you work your way toward a solution.
We start this chapter by letting you in on what kind of puzzle problems an interviewer may ask you. Once you know that, we tell you the steps to solving a puzzle, including breaking down the problem and then building your solution.
Next, we talk about why an observation of your problem-solving skills is what interviewers want to see, what you need to focus on as you solve a puzzle, and the importance of talking with your interviewers as you work on your solution.
Finally, we show you where you can find other resources for solving puzzles, including books as well as websites that produce new puzzles you can solve on your own or in competition with others.
When one or more interviewers ask you to solve a puzzle on a whiteboard in the interview room (or even on a large notepad if a whiteboard won’t arrive until Tuesday), most puzzle questions come in one of two forms. (Yes, we said most puzzle questions as there is a wide variety of puzzle questions an interviewer could ask.) One puzzle will be in the form of implementing a data structure, and the other will be in the form of implementing an algorithm that works on a particular data structure.
Good news, everyone: There is a finite number of puzzles that take on one of these forms.
You should also be ready to answer logic or “brain teaser” puzzles that have nothing to do with computer science or programming. Instead, these puzzles are designed to learn how you solve problems. For example, one famous Microsoft interview question asks why manhole covers are round. Later in this chapter, we let you know how to prepare for brain teasers like this, too.
You start to solve a puzzle by preparing your brain to understand it. If you don’t, you may find yourself solving the wrong problem and find yourself intensely embarrassed and possibly dismissed from the interview room after you finish writing your wrong answer on the whiteboard.
So, here’s what you need to do to be careful and understand the problem from the outset:
Once you understand the problem, you need to break it down to its basic level that has a simple solution. For example, if an interviewer asks you to implement a sorting algorithm, you could use a simple solution as a starting point that you can keep in your head or write down as you start to build your final solution.
In this case, think about just three elements that need to be sorted. Can you solve that manually? If so, then go step by step and write down how you solved the problem.
Here’s a more complex example:
The problem the interviewer wants you to solve is to reverse a string. How would you do that manually?
You could create two columns in your head or on a piece of paper with the left column containing the original string and the right column containing the reversed string. Then you would take the right-most letter in the original string and write it down as the first letter in the right column. Then you would take the right-most letter that remains in the left column and add it after the first letter in the right column. You would continue this process until the string is reversed.
Now that you’ve seen how to break down a problem, the next step is to apply that process to a more complicated version of the problem. Since you were able to sort three elements successfully, try sorting five elements, and then ten elements.
As you solve problems that are increasingly complex and gain confidence, the algorithm you’re going to use for the interviewer’s problem should become apparent. You can then take the steps needed to solve the actual problem.
For example, in the case of reversing a string, you would quickly find the algorithm to create that should look something like this:
When you’re confident that those steps will work for any input size, start writing pseudocode. The term pseudo means not genuine, and so this is not the genuine code you’re going to use when you write the solution on the whiteboard. Instead, pseudocode is an informal, high-level code meant for human reading.
For example:
length = originalString.Length;
String newString = “”;
While (length != 0) {
newString.concat(originalString[length-1];
length = length – 1;
}
Return newString;
After you write pseudocode for each step, translate that pseudocode into actual code the computer will understand. Write down input and see how the code processes it. If it works, then you’re ready for the next step: looking for edge cases — that is, scenarios that will break the code you’ve written.
For example, what if the list of elements that you have to sort has no items or just one item in it? What happens if you get the opposite problem and you have a lot of items to sort? Or the data is invalid for some reason? The interviewers won’t expect you to be able to solve all edge cases, but you have to tell them what the edge cases are and what will happen with your code if an edge case happens.
These are the steps you need to build your solution, but what happens if you fail to solve the problem?
We have more good news: When you get a puzzle problem, your interviewers aren’t looking for a solution. It would be nice if you provided one, but that’s not what they’re after.
What’s more, you don’t have to worry about getting the syntax of your code perfectly correct when you write the solution on your whiteboard. This is another “nice to have” feature, but what your interviewers really want to know is if the problem-solving steps you take result in a correct algorithm.
Unlike programming problems, there isn’t a way to really prepare for brain teasers or other logic puzzles even if you talk to someone who’s interviewed with the company before. If you’re lucky, the interviewer will ask you the same brain teaser question you knew about from talking with company employees, and you’ve had a chance to prepare for it.
However, if the interviewer is like a good math teacher who knows students share tests with friends — and the friends hope they get the same test so they can ace it — the interviewer will change the question from the previous interview. In this case you’ll realize the answer you studied doesn’t work and you’ll have to think fast.
So, just keep things simple and remember that your job is to break down the brain teaser problem just as you would a programming problem, because that’s what your interviewers want to see — how you work when you’re presented with a problem.
Take every opportunity to solve programming puzzles and even brain teaser puzzles that you find in books as well as online. Just like an athlete, you need to train your brain to think about breaking down problems. (You may want to train your body, too, since a healthier body leads to a healthier brain, but that’s just a suggestion.)
Though there are an infinite number of possible problems an interviewer can ask, there are also only a finite set of algorithms that operate on data structures. So, once you know these algorithms, you’ll have the toolset you need in your brain to solve any set of problems. Our brains are designed to instinctively recognize patterns as we work to solve problems, and the same is true in programming. As you work on more problems, you’ll feel the rush that comes when you realize instinctively that a problem looks familiar to one you did earlier.
You can access websites that allow you to solve problems interactively. However, you may want to look at books that contain puzzles first. Working on puzzles in books and writing down the answers on paper (or in the book itself) has an advantage over working through problems online in that reading problems in books more accurately reflects the type of questions you’ll receive during your interview.
Where do you find a book with problems in it? Our first choice is the 2018 book, Programming Interviews Exposed: Coding Your Way Through the Interview, Fourth Edition, by Eric Giguere, John Mongan, and Noah Kindler (Wrox). This book contains three different chapters about solving different types of brain teasers, graphical and spatial puzzles, and knowledge-based questions.
If that isn’t enough for you, the self-published book, Cracking the Coding Interview, Sixth Edition, by Gayle Laakmann McDowell contains 189 programming questions and solutions. Though this book is a bit older than Programming Interviews Exposed — as of this writing, McDowell’s book was last published in 2015 — you’ll find the practice problems are still valid and worth the time and effort to solve.
Only after you’ve solved the problem (or you’ve become frustrated trying to solve the problem) should you open up the book and see how well your solution matched up with the one the author has or what step(s) you missed in solving the problems. Then, with that knowledge in mind, go on to the next problem and solve that. You’ll be amazed at how quickly you’ll solve practice problems after you’ve been working on them for a while. You may even start to find yourself looking forward to problem-solving time.
Books only have a specific number of problems, but there are plenty of programming and logic puzzle websites online. Some of these sites may allow you to solve the problems interactively, but resist this temptation as interactive solutions won’t duplicate the conditions in your interview.
You may want to search for puzzles for your specific language, such as typing programming puzzles Java in Google if you need Java-specific puzzles. However, as this is a language-agnostic book, we provide five valuable resources for programming puzzles and a bonus brain teaser website for your enjoyment.
CodeKata (http://codekata.com
) is a blog that claims that “experience is the only teacher” (see Figure 12-1).
Kata is a karate exercise where you repeat a form many times (wax on, wax off), and blogger Dave Thomas has a large repository of exercises that Thomas says takes about 30 to 60 minutes to solve. Thomas freely admits each problem is unlikely to have a single correct answer.
When you click the title of a puzzle under “Recent Posts” on the CodeKata main page, you’ll open a web page that tells you about the puzzle and the goal. You can also leave comments about the puzzle and for Thomas on the site.
In Chapter 8, we talk about Codility as a place where you can take online lessons about all sorts of programming topics to sharpen your skills. If you feel like you have a good grasp of the skills you need, then put them to the test by going to the Codility for Programmers website (https://app.codility.com/programmers
) and then clicking Challenges in the upper-right corner of the website to accept the site’s latest challenge or work on past challenges (see Figure 12-2).
We also talk about LeetCode’s many resources in Chapters 8 and 9, and this website (https://leetcode.com
) also has numerous questions in a wide variety of categories that you can solve, as you see in Figure 12-3.
Programming Praxis (https://programmingpraxis.com
) is a minimalist blog that regularly posts new puzzles for you to solve (see Figure 12-4).
The question appears on the page so you can work on the exercise at your leisure. Click the title of the exercise (such as the Van Eck Sequence shown in Figure 12-4) to open a page that not only contains the problem but also potential solutions in the comments. You don’t even have to sign up for an account to leave your own solution or comment in the Comments section.
View past exercise categories by clicking the Exercises option in the red menu bar at the top of the web page and then clicking a selection in the menu. The list of exercises appears in its own web page with three links: one to view only the exercise, one to view a summary of the solution as well as user comments and/or solutions, and one that shows the solution code in Scheme, the site’s preferred programming language.
Topcoder (www.topcoder.com
) bills itself as a crowdsourcing software development platform, but it’s also a place where you can compete with other Topcoder users to solve challenges for real clients and get real money. When you click the Compete on Topcoder button on the Topcoder website’s home page, the list of challenges appears, as shown in Figure 12-5.
Each challenge title contains a color-coded box to the left of the title: blue for web design and green for coding. You can view total amount of money being offered (not the total amount if you win) by clicking the challenge title name in the list.
After you click the title name, you’ll see the Challenge Summary web page that tells you about the challenge and how much money will be awarded to the first, second, and third place finishers the Topcoder judges select. Some challenges reward all the money to the first person to create a working solution.
The MindCipher website (www.mindcipher.com
) shows a list of brain teaser puzzles in a wide variety of topics, including computer programming, as you see in Figure 12-6. To the right of each puzzle title and brief description, you see a graphic that tells you if MindCipher users find the puzzle easy, doable, or hard.
View the entire puzzle description in the Description web page by clicking the title of the puzzle; you see the full description as well as the Show Answer link below the description. When you click Show Answer, the answer appears below the link.