10.1.1 Lessons Learned Per Chapter

Let’s recap about what was taught in each chapter and what you should have learned.

Mathematical: The chapter on basic mathematical knowledge introduced the modulo operator, which is quite essential, for example, for the extraction of digits and in the calculation of checksums. The exercises on combinatorics showed how small tricks can easily reduce the running time by an order of magnitude. Also, prime numbers offer some interesting facets, for example, variants to their calculation. In retrospect, this turns out to be much easier than perhaps first thought. In general, when trying to find a solution for a problem, the algorithm and the approach should be roughly understood, because then, for example, even decomposition into prime factors loses its possible horror.

Recursion: The introductory chapter on recursion laid the foundation for a good understanding. The exercises expanded your knowledge. Additionally, you were able to use the acquired basic knowledge profitably in the following chapters. A prime example is various algorithms on trees, which can often be easily expressed recursively—iteratively, for example, a postorder traversal is already challenging, whereas with recursion it is effortless.

However, you recognized that simple recursion does not only possess advantages, but also sometimes requires some patience due to long running times. In the advanced chapter on recursion, you significantly expanded your toolbox with memoization and backtracking. This allowed you to increase performance and to solve entertaining and amusing puzzles, such as Sudoku puzzles or the n-Queens problem. It was also possible to find a way out of a maze. All this required a bit more programming effort but could be implemented without too much complexity.

Strings: Strings are an integral part of almost every program. Besides simple tasks for palindrome checking or string reversing, some tasks could be significantly simplified using suitable auxiliary data structures, such as sets or dictionaries. These helped when checking for well-formed braces, converting a word into Morse code, and other tasks. In general, solving problems is easier the more basic knowledge you have in different areas.

Basic data structures: This chapter deepened your knowledge of basic data structures like lists, sets, and dictionaries. This knowledge is essential in business applications. Not only individually but also in combination, they are useful for solving many tasks, such as the deletion of duplicates from lists. In addition, the exercise of the magic triangle, for example, trains abstract thinking. A small delicacy was to program the auto-completion of Excel itself. It is quite surprising what an elegant implementation this results in. Finally, you developed some functionality for merging lists. This is an elementary component for Merge Sort.

Arrays: Just like strings, arrays are basic building blocks in many programming languages. In Python, lists are often favored, since arrays are not nicely supported in the language. However, there is a valid alternative with NumPy, with which arrays can be easily defined and which can offer significant performance improvements compared to lists.

In particular, it is important to avoid tricky off-by-one errors. In this chapter, you created small helper functions that, when used appropriately, can make algorithms more understandable. For two-dimensional arrays, you learned, among other things, how to model directions and how this helps with filling areas with patterns. More challenging tasks were the spiral traversal as well as the deletion and filling of a Jewels or Minesweeper playfield.

Binary trees: The most complex topic in this book is probably binary trees . Since Python does not provide them, they are presumably not familiar to every Python developer. However, because binary trees are suitable to solve many problems elegantly, this chapter gave an introduction. The exercises helped you get to know binary trees and their possibilities. Besides things like rotation, even mathematical calculations, for example, can be represented and processed very smartly using binary trees. Something to puzzle over was certainly the determination of the least common ancestor. This is especially true for the check for completeness and the graphical output of a binary tree.

Search and sort: Nowadays, you will hardly program a search or sorting algorithm yourself. Still, it is helpful for algorithmic understanding to have dealt with it once. While naive implementations often have a running time of O(n²), this can usually be reduced to O(n . log(n)) with Merge Sort and Quick Sort. It is fascinating to see how a fixed range of values can have a significant effect. Bucket Sort with a running time of O(n) plays out its strengths with these constraints.

10.1.2 Noteworthy

When presenting the solutions, I have sometimes deliberately shown a wrong way or a suboptimal brute force variant to demonstrate the learning effect when working on an improvement. In everyday work, too, it is often preferable to proceed iteratively because the requirements may not be 100 % precise, new requests arise, etc. Therefore, it is a good idea to start with a comprehensible implementation of the task, which allows it to be modified afterward without any problems. It is often even acceptable to take a not-yet-optimal solution that handles the problem in a conceptually correct way.

10.2.1 Gold Bags–Detect the Fake

This puzzle is about 10 gold bags, each filled with 10 coins, each of which weighs 10 g. Thus, each gold bag should weigh 100 g (Figure 10-1).

An impostor has exchanged the gold coins in a bag for fakes, which, at 9 g instead of 10 g per coin, are somewhat lighter. Find the gold bag containing the fakes with only one weighing. However, you may take different numbers of coins from any bag and weigh them together.

Solution

At first, this task sounds almost impossible since multiple weighing and comparing are not allowed. You might come up with the following trick with a bit of pondering: Line up the bags and number them from 1 to 10. Now work position-based and place as many coins from each corresponding bag as matches its position, and then weigh them all together, as shown in Figure 10-2.

Without fakes, the result would be as follows:

Let’s assume that bag 5 contains the fakes and look at the result:

Let’s now assume that bag 2 contains the fakes and determine the result:

According to this, you can identify the corresponding bag based on the difference to 550:

10.2.2 Horse Race–Determine Fastest Three Horses

This puzzle is about solving the following: 25 racehorses are offered for sale, and you want to buy the three fastest. There is a racetrack with space for a maximum of five horses. Still, you have neither a stopwatch nor any other way of measuring time. However, the horses can compete against each other in races, and you may note the order. Under these restrictions, how do you determine the fastest three, and how do you proceed? How many races with which horses do you have to organize at best?

As a simplification, let’s assume here that the horses are not exhausted by the races, run exactly the same speed in each race, and also that no two horses are the same speed (just like in a photo finish, there is always an order and a winner).

Solution

Again , you have to think quite a bit at first to arrange the right races by a clever exclusion procedure and additionally perform as few of them as possible. In fact, only seven races are necessary to determine the fastest three horses. How do you go about it?

Step 1: You let five horses compete against each other in any five races and thus determine the winners of these races. For better traceability, all horses get a number between 1 and 25, which normally says nothing about the placement. In the following, the number is used for better distinguishability. It is possible to label the horses just as well with A, B, C, ... but then you need further distinctions for the races’ winners.

You thus determine the winners from all five races and can directly remove all horses in the respective fourth and fifth places from your selection for the next races by the exclusion procedure shown in Figure 10-3.

As a result, 15 horses remain, and if you would like to compare them with each other, at least three races would yet be necessary after these five races. According to my statement, however, a total of seven races is enough, so only two races are still allowed. Consequently, you nevertheless have to reduce the number of horses to be compared to suitably.

Step 2: To have significantly less than 15 horses left for further selection, you need to run another race, one with all the winners. Why? So far, you only know something about the horses within the groups themselves, but not between the groups. To get some information about the relative speeds of the winners, you let them race against each other. Again, the last two cannot be among the fastest three horses. See Figure 10-4.

However, this will automatically eliminate the horses with numbers 17 and 18 (slower than the horse with number 16) and the horses with numbers 22 and 23 (slower than the horse with number 21) as candidates.

Step 3: You mark the exclusions in a matrix, and then you combine the gained knowledge to proceed with the next exclusion. To do this, you insert a > notation for faster than into the matrix of horses. Because horse 1 also won in the winner’s race, you are sure that horse 1 is definitely the fastest. See Figure 10-5.

However, there are still nine horses left—actually only eight candidates, since horse 1 is the fastest. That would indicate at least two more races. Let’s now consider a bit. You know the orders by the previous races. Since you want to determine only the fastest three, the horses numbered 8, 12, and 13 are eliminated, and five horses now remain, namely those numbered 2, 3, 6, 7, and 11. See Figure 10-6.

Thus, you only have to let the other horses (i.e., 2, 3, 6, 7, and 11) compete against each other. The winner and runner-up of this race are the overall second and third horse. This results in the following possible combinations as the final result:

• 1, 2, 3

• 1, 2, 6

• 1, 6, 2

• 1, 6, 7

• 1, 6, 11

10.3.1 Introduction to Algorithms and Data Structures

Of the three books listed here, this is the most comprehensive. It goes far beyond the previous ones in terms of the topics presented. However, it offers fewer explanatory illustrations and is not written as intuitively as the others.

10.3.2 Basic Books

This book by Mark Allen Weiss offers a slightly more practical approach than the previously mentioned one. Due to the publication year of 2010, it uses more modern concepts like generics for the implementation of the data structures. However, this book uses Java as the explanatory language.

10.3.3 Specializing in Interview Questions

This is another book that provides a lot of information and also exercises including solutions for algorithms and data structures. It focuses on small programming tasks for every day and is based on Python.

10.3.4 Supplements for Job Interviews at Top Companies