Chapter 10
Identifying Design Patterns and Using Recursion
IN THIS CHAPTER
Recognizing design patterns
Understanding how to solve a recursion test
Finding recursion examples
The overall goal of this book is to put you ahead of your competition to get the job you want. You may not succeed in your first attempt to get a job, but the fact that you have this book means you’re dedicated to that goal, too. One of the most important aspects of a job interview that will set you apart is your ability to recognize and understand design patterns.
When can you expect to receive a question about design patterns? You’ll most likely get these sorts of questions if you’re programming in high-level C++, but you may also get design pattern questions if the job requires you to program in other object-oriented languages, including Java, Python, and Ruby.
This chapter starts by showing you how to recognize some of the common design patterns, including the singleton, adapter, and several other patterns. Next, you learn how to use recursion, which is a function present in many design patterns, to solve problems.
Then you learn what kind of recursion tests you may encounter in an interview and how to solve those tests successfully. Finally, we tell you where to find more recursion examples and resources online so you can hone your skills and dazzle your interviewers with your recursion prowess.
Recognizing Design Patterns
Don’t feel bad if wrapping your head around design patterns only ends up giving you a headache. They are hard to understand in part because there are a lot of patterns to remember: 23 of them, to be exact.
Thankfully, some design patterns are more important than others, and it’s these design patterns you need to know. This section not only tells you why you should use design patterns, but also about the essential design patterns programmers use.
Many modern programming languages have eliminated the need for many of the 23 design patterns that exist, so you should check on the web and/or in a book about design patterns to find out if you will need to learn any design patterns beyond the ones discussed in this book.
Understanding the basics
In programming, design patterns are reusable solutions to common programming problems. They were modeled after design patterns in architecture — you know, the field where you build actual buildings, not the software term. A good example is an arch, which is a common architectural pattern used to distribute a large amount of weight across a span. You don’t have to explain every detail of an arch to architects — they understand what an arch is as soon as you say the word.
The same is true when programmers tell you they’re using a singleton in an application. You should know that a singleton means a single instance of an object. (Okay, it’s only slightly more complicated than that, and we go into more detail about it later in this chapter.)
If you want or feel you need more information about all 23 design patterns for the job you’re interviewing for, pick up a copy of the seminal book, Design Patterns: Elements of Reusable Object-Oriented Software by Gamma, Helm, Johnson, and Vlissides. You may hear this book referred to as the “Gang of Four” book in programming circles. This book was published by Addison-Wesley in 1994 and is the first book published about design patterns.
Knowing when to use design patterns
It’s important to know design patterns, but they’re not a be-all, end-all solution to every programming problem you have. It’s tempting to simply add a design pattern because you think it’s going to work only to find that the solution
- is more complex than you thought it would be,
- puts in a lot more lines of code than another solution, and/or
- causes the program not to run at all after you compile it.
So, why do we have a chapter about design patterns in the first place? Because they’re building blocks. Just as we used our fingers to count and add numbers when we were young, using fingers doesn’t work when you’re adding large numbers or multiplying numbers. When you add large numbers, you may add some numbers on your fingers when the situation calls for it.
The same is true when you’re programming — design patterns are primary tools you learn in programming that you can use when they can perform the function you need.
When an interviewer asks you to solve a problem on a whiteboard, as you write the code you may find a design pattern that works — or you start to write the pattern and it doesn’t work. In either case, tell the interviewers about the design pattern you’re using, and why it’s working or not working. If it doesn’t work, discuss what you’ll try instead. You may not solve the problem, but if you show that you know about design patterns and if and when to apply them, it shows you can think. Interviewers like that.
Learning about singleton, adapter, façade, and more
When you’re asked about design patterns, you may only be asked if you know some of the common design patterns, what they do, and if you can provide examples of some of them and how they work. Let’s prepare: place the bar down on top of your lap, keep your hands inside the car, and let’s take a tour of seven common design patterns.
Modern languages implement many design patterns right into their frameworks. So, after you read this section, you can check your programming language framework for design patterns.
singleton
We’re starting with the most basic design pattern there is: the singleton, which is a pattern where there is only one instance of, and a global point of access to, an object or class.
For example, you can write a program that connects to a physical printer so that a user can print data from the program. Any time you need to print something, you don’t need to use multiple instances of that printer because there’s only one that’s connected to the computer and has jobs queued up. So, a singleton design pattern works in this case.
factory
The factory design pattern allows you to create subclasses so that each subclass decides what objects it will create. Think of the factory design pattern as a smart creator that standardizes the way objects are created. Then you can create algorithms that can get specific objects because you know the factory design pattern assigned the attributes you need to the objects you want.
builder
A builder design pattern consists of a class that can build another object. The most common example is a string builder that you’ve probably encountered when you’ve created programs since most programming languages have string builders included in their frameworks. The string builder allows you to add characters to the string. When you’re finished, you can construct the string.
adapter
An adapter design pattern matches the interfaces of different classes so both classes work together in your algorithm. Think of the adapter pattern as a home electrical plug adapter. Many older homes still have two-prong electrical plugs and nearly all modern electrical plugs have three-prong connectors. You can go to your local hardware store and buy a three-prong to two-prong adapter. When you plug the three-prong power cord into the adapter and then plug the adapter with the attached cord into the two-prong electrical plug, your electrical device turns on.
façade
One definition of a façade in the dictionary is a deceptive outward appearance. In the case of a façade design pattern, the pattern is not trying to deceive you; instead, it’s a class that makes it easy for you (and/or the program user) to interface with a subsystem that’s far more complex.
An example is the controls in a modern car — the steering wheel, gas pedal, and brake. All three are easy to interface with. Turn the wheel to turn the car in the direction you want to go. Press your foot on the gas pedal to accelerate. Press on the brake to slow down or stop. Easy-peasy.
You don’t have to control or even know about the carburetor, the engine, the fuel injection system, or even the gear shifter in your car. You just drive the car using that simple interface that acts as a façade for the complex system that gets you where you want to go.
proxy
A proxy design pattern is just as the name says: an object representing another object. This pattern is often used as a security measure to protect a component or other object in your algorithm. For example, you can write a proxy class so only user account objects that contain the admin username can access the protected object.
iterator
The iterator design pattern sequentially accesses elements within a collection. When you know there is a data structure within a collection but you don’t know what it is, the iterator pattern returns all the elements within the collection. Then you can see the elements within the collection in the order the collection stores those elements.
Knowing What You Need about Recursion
Now that you know the basic design patterns, it’s time to learn about a nifty feature present many of them: recursion. Recursion is a feature that allows the algorithm to continue to call itself to solve your problem by breaking it down into smaller and smaller problems. (That kind of sounds like the process to find a new programming job, doesn’t it?)
There are two different types of recursion: direct and indirect.
Direct versus indirect
Direct recursion occurs when the recursion function directly calls itself from within itself. For example, you may want to sort a big list of items such as information about all the businesses in a large metropolitan area. Your goal with your algorithm is to keep breaking the list down until you get the types of businesses in your area that you want to contact about potential programming jobs.
One thing you can do is use recursion to break the list in half and then sort two lists. Then break each of those two lists in half and continue that pattern until you have then two small lists of items you want to sort. Now you can sort the two lists together and get the master list of businesses so you can sell yourself and your skills (like your ability to use recursion).
Indirect recursion occurs when Function A calls Function B, and then Function B refers back to Function A. For example, if Function A is responsible for maintaining the hierarchy of a folder, then that function can call Function B that processes the files within that folder. Those features will continue to call on each other until there are no other files to process … provided you’ve added code in your algorithm to end the indirect recursion cycle.
Here’s simple example of direct recursion:
def is_even_direct(n):
if n == 0:
return True
else:
return not is_even_direct(n - 1)
def is_odd_direct(n):
if n == 0:
return False
else:
return not is_odd_direct(n - 1)
And an example of indirect recursion:
def is_even(n):
if n == 0:
return True
else:
return is_odd(n - 1)
def is_odd(n):
if n == 0:
return False
else:
return is_even(n - 1)
The real stack overflow
A common problem with recursive algorithms, or recursive functions within an algorithm, is that you need to remember to include an end condition within the algorithm. This is true of both direct and indirect recursion. Fortunately, modern programming languages include classes so you can end the recursion after a certain number of recursion calls.
If you don’t add the appropriate class, the algorithm will continue to call on itself repeatedly until it sucks up all of your computer’s memory and you receive the dreaded stack overflow message. (Stack overflow isn’t just the name of an important website.)
If you’re not sure if your programming language supports recursion, and which design patterns support recursion, you have three ways to find out: Check your programming language documentation and/or frameworks, search on Google, and find a design patterns book for the specific programming language you’re using and read the chapter on design patterns.
Understanding Your Recursion Test
If you get word from mock interviewers and/or programmers who interviewed with the company before that you’ll be asked about recursion, you should presume that an interviewer will ask you to solve a recursion problem.
Common examples of recursion algorithms include:
- The Fibonacci series
- The Tower of Hanoi puzzle
- Searching algorithms
- Copying a string
- Permutations such as combinations in a string of digits
Even if you don’t receive a question to solve a recursion problem specifically, a question an interviewer asks you may require recursion to solve properly. In that case, be prepared to point out the recursion when you use a design pattern in your algorithm that solves the interviewer’s problem.
Solving a recursion word problem example
We’ll use a common recursion algorithm as an example of how to solve a recursion word problem: the palindrome. If you remember, a palindrome is a word (or words) or a number that reads the same backward and forward. Palindromic words include civic, kayak, level, madam, and race car. The last year that had a palindromic number was 2002, and shorthand dates such as 9/19/19 are also palindromic (at least if you live in the United States).
So, how can you find out if a string is a palindrome? When you begin to write your algorithm, start by having the program check the first and last letters of the word to see if they’re the same. If they’re not, then the word isn’t a palindrome.
The next part of the algorithm will then check the second letter and the second-from-last letter in the word to see if they’re the same. If those letters are the same, the algorithm will check the third letter and third-from-last letter and so on until you run out of characters in the word.
The easiest and most effective way to do solve this problem is by using a recursive function within your algorithm. All you have to do is write a function that compares the first and last letters. If they are the same, then the function shortens the string by removing the first and last letter of the word and then compares the first and last letters of the shorter word.
The recursive function calls itself repeatedly to repeat these actions with the word until there was a string length of one or zero, and then the function would end. You could also have the algorithm send a message to the screen that the word is a palindrome or not.
Don’t believe us? This problem is easy enough that you can try yourself in any programming language you’re using. See if you can solve it.
Finding more examples and resources
Though we’re language agnostic in this book, it’s easy to find recursion examples in the language of your choice. All you have to do is go to Google and type recursive program examples followed by the name of your programming language. Then you can browse through the results and view the pages that include samples.
Your interviewer may also ask you to implement some functions recursively instead of solve a recursion problem that already exists. In that case, you should also explain to your interview team about how to implement them iteratively as well. (Free reminder: Iterative means a loop is executed repeatedly until a certain condition is met.) Showing that you know the difference between recursion and iteration is another way to keep your interviewers smiling.