Chapter 12
Solving Puzzles Is Fun
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.
Knowing What Kind of Problems an Interviewer Will Ask
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.
If you’re not sure whether the puzzle is going to come in one of the two forms we mention, start by finding puzzles that don’t fall into these two forms. (You learn more about finding programming puzzles later in this chapter.) You should also ask your mock interviewing team to come up with two programming puzzles: one that fits one of these two forms and one that doesn’t, so you can feel ready for any curveballs the real interviewers throw your way.
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.
Solving a Programming Puzzle
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:
- Read the problem slowly three times. If the problem isn’t written down, write down the problem as the interviewer says it. Then repeat the problem orally to the interviewer and make any corrections. When you’ve confirmed the text of the problem, read it slowly three times.
- Engage in active listening. For example, you could say something like, “When you said this, my understanding is that …” and then ending your sentence by asking if you’re correct. If not, write down the interviewer’s clarification.
- Ask any follow-up questions that come up after you read or hear the problem.
If your interviewers become agitated by you taking so long to understand the problem or start pressuring you to get started on and/or finish the problem quickly, you should remind them that you take the same approach with any problem you encounter in your job. This approach not only ensures that you get the solution right the first time, but it ends up saving time in the long run. If that argument doesn’t convince your interviewers, perhaps it’s time for you to thank them and leave since they’ve told you what the job and their company culture is like.
Breaking down a problem
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.
A whiteboard will likely be on one of the walls in the interview room, and an interviewer will give you a marker and an eraser to work with. A notepad will suffice during practice if you don’t have a whiteboard at home, but when you go through a mock interview, you should ensure that you find a location that has a whiteboard so you can accurately replicate the actual interview as much as possible. You’ll feel the difference between writing on a notepad by yourself and writing on a whiteboard in front of several people.
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.
Building your solution
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.
By this time, you should be talking with the interviewers about what you’ve done to break down the problem and how you’re going to build your solution. Your interviewers likely won’t be able to see how you’re putting the solution together on paper (and can’t read your mind as far as you know), so it’s important to tell them what you’ve done. If you haven’t talked up to this point and don’t intend to, you will anyway because the interviewers will ask you what you’re doing and keep peppering you with questions as you work.
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:
- Determine the length of the string.
- Use this to figure out the last letter in the string.
- Copy the last letter of the string to the new string.
- Reduce the length of the string by one and repeat until the length is 0.
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?
Realizing What Interviewers Want
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.
Interviewers want to know how you break down problems and work to create solutions. This explains why we’re so insistent that you need to talk out loud as you write your solution so your interviewers can follow along. Your ability to take the complex and make it simple is how you’ll show your interviewers that you’re a good programmer worthy of being hired.
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.
Getting Better at Solving Puzzles
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.
Even if you have mad programming skills, you likely haven’t had to solve algorithm problems in your current or past jobs. You still have to train your brain just like any other programmer to get your brain in the right frame of mind, though your skills may get you up to speed more swiftly than the average bear.
Working on puzzles in books
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.
When you’re in the interview, you’re not going to have a computer in front of you. You’ll either be seated at a table facing a panel of interviewers or sitting at the same table with one or very few interviewers depending on the type of company interviewing you. So, you’ll be working out puzzles on paper or on a whiteboard instead of on a computer screen. By practicing puzzles in books beforehand, this situation will feel more comfortable than if you only worked out puzzles onscreen.
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.
If you buy one or both of these books, you should set aside a block of time on a regular schedule and go through as many problems as possible through one or both books during your scheduled practice time. Though the books we’ve recommended include solutions to the problems, start by writing down the problem, closing the book, and then trying to solve the problem yourself.
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.
Searching online to hone your solving skills
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
CodeKata (http://codekata.com) is a blog that claims that “experience is the only teacher” (see Figure 12-1).
Source: http://codekata.com
FIGURE 12-1: The CodeKata website contains a list of programming exercises that encourage you to practice, practice, practice.
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.
Codility
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).
Source: www.codility.com
FIGURE 12-2: You can view a list of current or past challenges on the left side of the Codility for Programmers web page.
You’ll need to sign up for a Codility account if you want to participate in a challenge. After you click the Start Challenge button in the upper-right corner of the home page, you’ll open a web page that tells you how much time you’ll need to set aside to finish the challenge and if there are any opportunities for you to pause while you try to solve it.
LeetCode
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.
Source: https://leetcode.com
FIGURE 12-3: Click a category name at the top of the LeetCode web page to view questions within that category.
You view questions in all categories by default. Within the table of questions you see the question title in the Title column; click the title to open the question page. If there’s a page icon in the Solution icon, that means the question page includes solutions to the question in various programming languages. If you want to try to solve a problem that doesn’t have a solution, click a title that doesn’t have a Solution icon to the right of the title name.
Programming Praxis
Programming Praxis (https://programmingpraxis.com) is a minimalist blog that regularly posts new puzzles for you to solve (see Figure 12-4).
Source: https://programmingpraxis.com
FIGURE 12-4: The latest puzzles appear in reverse chronological order on the Programming Praxis website.
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
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.
Source: www.topcoder.com
FIGURE 12-5: The most recent challenges appear in the Open for Registration section at the top of the list.
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.
MindCipher
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.
Source: www.mindcipher.com
FIGURE 12-6: View puzzles in a particular category by clicking a tag button within the Popular Tags list on the right side of the web page.
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.
The description web page also shows solutions and questions by readers in the Comments section underneath the question, so you may need to train yourself to look only at the comments. If you want to comment on the site and/or rate the problem’s difficulty, you have to create a MindCipher account to log into or you can log in with your Facebook account.