Python Challenges : 100 Proven Programming Tasks Designed to Prepare You for Anything

Augment your knowledge of Python with this entertaining learning guide, which features 100 exercises and programming puzzles and solutions. Python Challenges will help prepare you for your next exam or a job interview, and covers numerous practical topics such as strings, data structures, recursion, arrays, and more. Each topic is addressed in its own separate chapter, starting with an introduction to the basics and followed by 10 to 15 exercises of various degrees of difficulty, helping you to improve your programming skills effectively. Detailed sample solutions, including the algorithms used for all tasks, are included to maximize your understanding of each area. Author Michael Inden also describes alternative solutions and analyzes possible pitfalls and typical errors. Three appendices round out the book: the first covers the Python command line interpreter, which is often helpful for trying out the code snippets and examples in the book, followed by an overview of Pytest for unit testing and checking the solutions. The last explains the O notation for estimating performance. After reading this book, you'll be prepared to take the next step in your career or tackle your next personal project. All source code is freely available for download via the Apress website. What You Will Learn Improve your Python knowledge by solving enjoyable but challenging programming puzzles Solve mathematical problems, recursions, strings, arrays and more Manage data processing and data structures like lists, sets, maps Handle advanced recursion as well as binary trees, sorting and searching Gamify key fundamentals for fun and easier reinforcement Who this book is for: Programmers, software developers who are either professionals or makers, as well as students and teachers. At least some prior experience with the Python programming is recommended. Table of Contents About the Author About the Technical Reviewers Preface Chapter 1: Introduction 1.1 Structure of the Chapters 1.1.1 Introduction 1.1.2 Exercises 1.1.3 Solutions 1.2 Basic Structure of the PyCharm Project 1.3 Basic Framework for Unit Tests with Pytest 1.4 Note on Programming Style 1.4.1 Thoughts on Source Code Compactness 1.4.2 Example 1 1.4.3 Example 2 1.4.4 Decorators and Sanity Checks at the Beginning of Functions 1.4.5 Block Comments in Listings 1.4.6 PEP 8 and the Zen of Python PEP 8 Coding Standard The Zen of Python 1.4.7 More Information 1.5 Note on the Exercises 1.6 Trying Out the Examples and Solutions 1.7 Let’s Go: Discovering the Python Challenge Part I: Fundamentals Chapter 2: Mathematical Problems 2.1 Introduction 2.1.1 Short Introduction to Division and Modulo 2.1.2 Short Introduction to Divider 2.1.3 Short Introduction to Prime Numbers 2.1.4 Roman Numbers Rules Examples Noteworthy 2.1.5 Number Games Perfect Numbers Armstrong Numbers Algorithm for a Simple Checksum 2.1.6 Getting Started with Lambdas Lambda Syntax Lambdas in Action with sort() 2.2 Exercises 2.2.1 Exercise 1: Basic Arithmetic (★✩✩✩✩) Exercise 1a: Basic Arithmetic Operations (★✩✩✩✩) Examples Exercise 1b: Statistics (★★✩✩✩) Examples Exercise 1c: Even or Odd Number (★✩✩✩✩) 2.2.2 Exercise 2: Number as Text (★★✩✩✩) Examples 2.2.3 Exercise 3: Perfect Numbers (★★✩✩✩) Examples 2.2.4 Exercise 4: Prime Numbers (★★✩✩✩) Examples 2.2.5 Exercise 5: Prime Number Pairs (★★✩✩✩) Examples 2.2.6 Exercise 6: Checksum (★★✩✩✩) Examples 2.2.7 Exercise 7: Roman Numbers (★★★★✩) Exercise 7a: Roman Numbers ➤ Decimal Numbers (★★★✩✩) Exercise 7b: Decimal Numbers ➤ Roman Numbers (★★★★✩) Examples 2.2.8 Exercise 8: Combinatorics (★★✩✩✩) Exercise 8a: Computation of a2 + b2 = c2 Exercise 8b: Computation of a2 + b2 = c2 + d2 2.2.9 Exercise 9: Armstrong Numbers (★★✩✩✩) Examples 2.2.10 Exercise 10: Max Change Calculator (★★★★✩) Examples 2.2.11 Exercise 11: Related Numbers (★★✩✩✩) Examples 2.2.12 Exercise 12: Prime Factorization (★★★✩✩) Examples 2.3 Solutions 2.3.1 Solution 1: Basic Arithmetic (★✩✩✩✩) Solution 1a: Basic Arithmetic Operations (★✩✩✩✩) Examples Solution 1b: Statistics (★★✩✩✩) Examples Solution 1c: Even or Odd Number (★✩✩✩✩) Verification 2.3.2 Solution 2: Number as Text (★★✩✩✩) Examples Verification 2.3.3 Solution 3: Perfect Numbers (★★✩✩✩) Examples Verification Implementation Optimization 2.3.4 Solution 4: Prime Numbers (★★✩✩✩) Examples Verification 2.3.5 Solution 5: Prime Number Pairs (★★✩✩✩) Examples Optimization of the Implementation Verification 2.3.6 Solution 6: Checksum (★★✩✩✩) Examples Verification 2.3.7 Solution 7: Roman Numbers (★★★★✩) Solution 7a: Roman Numbers ➤ Decimal Numbers (★★★✩✩) Examples Solution 7b: Decimal Numbers ➤ Roman Numbers (★★★★✩) Verification 2.3.8 Solution 8: Combinatorics (★★✩✩✩) Solution 8a: Computation of a2 + b2 = c2 Bonus: Reduce the Running Time of O(n3) to O(n2) (★★★✩✩) Verification Solution 8b: Computation of a2 + b2 = c2 + d2 Bonus: Reduce the Running Time of O(n 4) to O(n 3) (★★★✩✩) Verification 2.3.9 Solution 9: Armstrong Numbers (★★✩✩✩) Examples Verification Bonus (★★★✩✩) Verification 2.3.10 Solution 10: Max Change Calculator (★★★★✩) Examples Verification 2.3.11 Solution 11: Related Numbers (★★✩✩✩) Examples Verification 2.3.12 Solution 12: Prime Factorization (★★★✩✩) Examples Verification 2.4 Summary: What You Learned Chapter 3: Recursion 3.1 Introduction 3.1.1 Mathematical Examples Example 1: Factorial Example 2: Calculation of the Sum of Numbers Up to n Example 3: Fibonacci Numbers 3.1.2 Algorithmic Examples Example 1: Palindrome—Recursive Variant Example 1: Palindrome—Iterative Variant Example 2: Fractal Generation 3.1.3 Steps When Multiplying the Digits of a Number 3.1.4 Typical Problems: Endless Calls and RecursionError 3.2 Exercises 3.2.1 Exercise 1: Fibonacci (★★✩✩✩) Exercise 1a: Fibonacci Recursive (★✩✩✩✩) Example Exercise 1b: Fibonacci Iterative (★★✩✩✩) 3.2.2 Exercise 2: Process Digits (★★✩✩✩) Exercise 2a: Count Digits (★★✩✩✩) Exercise 2b: Cross Sum (★★✩✩✩) Examples 3.2.3 Exercise 3: GCD (★★✩✩✩) Exercise 3a: GCD Recursive (★✩✩✩✩) Examples Exercise 3b: GCD Iterative (★★✩✩✩) Exercise 3c: LCM (★✩✩✩✩) Examples 3.2.4 Exercise 4: Reverse String (★★✩✩✩) Examples 3.2.5 Exercise 5: List Sum (★★✩✩✩) Examples 3.2.6 Exercise 6: List Min (★★✩✩✩) Examples 3.2.7 Exercise 7: Conversions (★★✩✩✩) Exercise 7a: Binary (★★✩✩✩) Examples Exercise 7b: Octal and Hexadecimal Numbers (★★✩✩✩) Examples 3.2.8 Exercise 8: Exponential Function (★★✩✩✩) Exercise 8a: Power of Two (★★✩✩✩) Examples Exercise 8b: Exponentiation Recursive (★★✩✩✩) Exercise 8c: Exponentiation Iterative (★★✩✩✩) Examples 3.2.9 Exercise 9: Pascal’s Triangle (★★✩✩✩) 3.2.10 Exercise 10: Number Palindromes (★★★★✩) Examples 3.2.11 Exercise 11: Permutations (★★★✩✩) Examples 3.2.12 Exercise 12: Count Substrings (★★✩✩✩) Examples 3.2.13 Exercise 13: Ruler (★★✩✩✩) Example 3.3 Solutions 3.3.1 Solution 1: Fibonacci (★★✩✩✩) Solution 1a: Fibonacci Recursive (★✩✩✩✩) Example Solution 1b: Fibonacci Iterative (★★✩✩✩) Verification 3.3.2 Solution 2: Process Digits (★★✩✩✩) Solution 2a: Count Digits (★★✩✩✩) Examples Solution 2b: Cross Sum (★★✩✩✩) Verification 3.3.3 Solution 3: GCD (★★✩✩✩) Solution 3a: GCD Recursive (★✩✩✩✩) Examples Solution 3b: GCD Iterative (★★✩✩✩) Verification Solution 3c: LCM (★✩✩✩✩) Examples Verification 3.3.4 Solution 4: Reverse String (★★✩✩✩) Examples Verification 3.3.5 Solution 5: List Sum (★★✩✩✩) Examples Verification 3.3.6 Solution 6: List Min (★★✩✩✩) Examples Verification 3.3.7 Solution 7: Conversions (★★✩✩✩) Solution 7a: Binary (★★✩✩✩) Examples Solution 7b: Octal and Hexadecimal Numbers (★★✩✩✩) Examples Verification 3.3.8 Solution 8: Exponential Function (★★✩✩✩) Solution 8a: Power of Two (★★✩✩✩) Examples Solution 8b: Exponentiation Recursive (★★✩✩✩) Solution 8c: Exponentiation Iterative (★★✩✩✩) Examples Verification 3.3.9 Solution 9: Pascal’s Triangle (★★✩✩✩) Verification 3.3.10 Solution 10: Number Palindromes (★★★★✩) Examples Verification 3.3.11 Solution 11: Permutations (★★★✩✩) Examples Verification 3.3.12 Solution 12: Count Substrings (★★✩✩✩) Examples Verification 3.3.13 Solution 13: Ruler (★★✩✩✩) Example Verification 3.4 Summary: What You Learned Chapter 4: Strings 4.1 Introduction 4.1.1 Practically Relevant Functions 4.1.2 Example Conversions and Extractions 4.1.3 Equality 4.1.4 Slicing—Access to Individual Characters and Substrings 4.1.5 Converting a String into a List of Characters 4.1.6 Iteration 4.1.7 Formatted Output 4.1.8 Character Processing 4.1.9 Example: String Processing 4.2 Exercises 4.2.1 Exercise 1: Number Conversions (★★✩✩✩) Examples Exercise 1a (★✩✩✩✩) Exercise 1b (★★✩✩✩) Exercise 1c (★★✩✩✩) 4.2.2 Exercise 2: Joiner (★✩✩✩✩) Example 4.2.3 Exercise 3: Reverse String (★★✩✩✩) Examples 4.2.4 Exercise 4: Palindrome (★★★✩✩) Exercise 4a (★★✩✩✩) Examples Exercise 4b (★★★✩✩) 4.2.5 Exercise 5: No Duplicate Chars (★★★✩✩) Examples 4.2.6 Exercise 6: Remove Duplicate Letters (★★★✩✩) Examples 4.2.7 Exercise 7: Capitalize (★★✩✩✩) Exercise 7a (★★✩✩✩) Examples Exercise 7b: Modification (★★✩✩✩) Exercise 7c: Special treatment (★★✩✩✩) Example 4.2.8 Exercise 8: Rotation (★★✩✩✩) Examples 4.2.9 Exercise 9: Well Formed Braces (★★✩✩✩) Examples 4.2.10 Exercise 10: Anagram (★★✩✩✩) Examples 4.2.11 Exercise 11: Morse Code (★★✩✩✩) Examples 4.2.12 Exercise 12: Pattern Checker (★★★✩✩) Examples 4.2.13 Exercise 13: Tennis Score (★★★✩✩) Examples 4.2.14 Exercise 14: Version Numbers (★★✩✩✩) Examples 4.2.15 Exercise 15: Conversion str_to_number (★★✩✩✩) Examples 4.2.16 Exercise 16: Print Tower (★★★✩✩) Example 4.2.17 Exercise 17: Filled Frame (★★✩✩✩) Examples 4.2.18 Exercise 18: Guessing Vowels (★★✩✩✩) 4.3 Solutions 4.3.1 Solution 1: Number Conversions (★★✩✩✩) Examples Solution 1a (★✩✩✩✩) Solution 1b (★★✩✩✩) Solution 1c (★★✩✩✩) Verification 4.3.2 Solution 2: Joiner (★✩✩✩✩) Example Verification 4.3.3 Solution 3: Reverse String (★★✩✩✩) Examples Verification 4.3.4 Solution 4: Palindrome (★★★✩✩) Solution 4a (★★✩✩✩) Examples Solution 4b (★★★✩✩) Verification 4.3.5 Solution 5: No Duplicate Chars (★★★✩✩) Examples Verification 4.3.6 Solution 6: Remove Duplicate Letters (★★★✩✩) Examples Verification 4.3.7 Solution 7: Capitalize (★★✩✩✩) Exercise 7a (★★✩✩✩) Examples Exercise 7b: Modification (★★✩✩✩) Exercise 7c: Special treatment (★★✩✩✩) Example Verification 4.3.8 Solution 8: Rotation (★★✩✩✩) Examples Verification 4.3.9 Solution 9: Well Formed Braces (★★✩✩✩) Examples Verification 4.3.10 Solution 10: Anagram (★★✩✩✩) Examples Verification 4.3.11 Solution 11: Morse Code (★★✩✩✩) Examples Bonus Verification 4.3.12 Solution 12: Pattern Checker (★★★✩✩) Examples Verification 4.3.13 Solution 13: Tennis Score (★★★✩✩) Examples Verification 4.3.14 Solution 14: Version Numbers (★★✩✩✩) Examples Verification 4.3.15 Solution 15: Conversion str_to_number (★★✩✩✩) Examples Verification Bonus: Enable the Parsing of Octal Numbers Verification 4.3.16 Solution 16: Print Tower (★★★✩✩) Example Verification 4.3.17 Solution 17: Filled Frame (★★✩✩✩) Examples Verification 4.3.18 Solution 18: Guessing Vowels (★★✩✩✩) Verification 4.4 Summary: What You Learned Chapter 5: Basic Data Structures: Lists, Sets, and Dictionaries 5.1 Introduction 5.1.1 Sequential Data Types Example 5.1.2 Lists Example List Comprehension Example: Custom Implementation of remove_all() Example: Custom Implementation of collect_all() Check Implementations 5.1.3 Sets Example 5.1.4 Key-Value Mappings (Dictionaries) Example Example: Filtering Elements of a Dictionary in a General Way 5.1.5 The Stack as a LIFO Data Structure Example 5.1.6 The Queue as a FIFO Data Structure Implementation Example 5.2 Exercises 5.2.1 Exercise 1: Common Elements (★★✩✩✩) Examples 5.2.2 Exercise 2: Your Own Stack (★★✩✩✩) 5.2.3 Exercise 3: List Reverse (★★✩✩✩) Exercise 3a: List Reverse (★✩✩✩✩) Examples Exercise 3b: List Reverse Inplace (★★✩✩✩) Exercise 3c: List Reverse Without Performant Index Access (★★✩✩✩) 5.2.4 Exercise 4: Remove Duplicates (★★✩✩✩) Examples 5.2.5 Exercise 5: Maximum Profit (★★★✩✩) Examples 5.2.6 Exercise 6: Longest Sequence (★★★✩✩) Examples 5.2.7 Exercise 7: Well-Formed Braces (★★✩✩✩) Examples 5.2.8 Exercise 8: Pascal’s Triangle (★★★✩✩) Example 5.2.9 Exercise 9: Check Magic Triangle (★★★✩✩) Examples 5.2.10 Exercise 10: Most Frequent Elements (★★✩✩✩) Examples 5.2.11 Exercise 11: Addition of Digits (★★★✩✩) Exercise 11a: Addition (★★★✩✩) Examples Exercise 11b: Addition Inverse (★★★✩✩) Examples 5.2.12 Exercise 12: List Merge (★★✩✩✩) Examples 5.2.13 Exercise 13: Excel Magic Select (★★✩✩✩) Examples 5.2.14 Exercise 14: Stack-Based Queue (★★✩✩✩) Example 5.3 Solutions 5.3.1 Solution 1: Common Elements (★★✩✩✩) Examples Verification 5.3.2 Solution 2: Your Own Stack (★★✩✩✩) Verification 5.3.3 Solution 3: List Reverse (★★✩✩✩) Solution 3a: List Reverse (★✩✩✩✩) Examples Solution 3b: List Reverse Inplace (★★✩✩✩) Solution 3c: List Reverse Without Performant Index Access (★★✩✩✩) Verification 5.3.4 Solution 4: Remove Duplicates (★★✩✩✩) Examples Verification 5.3.5 Solution 5: Maximum Profit (★★★✩✩) Examples Verification 5.3.6 Solution 6: Longest Sequence (★★★✩✩) Examples Verification 5.3.7 Solution 7: Well-Formed Braces (★★✩✩✩) Examples Verification Bonus Verification 5.3.8 Solution 8: Pascal’s Triangle (★★★✩✩) Example Verification 5.3.9 Solution 9: Check Magic Triangle (★★★✩✩) Examples Verification Verification 5.3.10 Solution 10: Most Frequent Elements (★★✩✩✩) Examples Verification 5.3.11 Solution 11: Addition of Digits (★★★✩✩) Solution 11a: Addition (★★★✩✩) Examples Verification Solution 11b: Addition Inverse (★★★✩✩) Examples Verification 5.3.12 Solution 12: List Merge (★★✩✩✩) Examples Verification 5.3.13 Solution 13: Excel Magic Select (★★✩✩✩) Examples Verification 5.3.14 Solution 14: Stack-Based Queue (★★✩✩✩) Example Verification 5.4 Summary: What You Learned Chapter 6: Arrays 6.1 Introduction 6.1.1 One-Dimensional Arrays Textual Output Example 1: Swapping Elements Example 2: Basic Functionality for Arrays Example 3: Remove Duplicates Example 4: Rotation by One or More Positions 6.1.2 Multidimensional Arrays Introductory Example Modeling Directions 6.1.3 Typical Errors 6.1.4 Special Features Special Treatment for Generalizations 6.1.5 Recapitulation: NumPy Creating NumPy Arrays Based on Lists Creating NumPy Arrays with Particular Values Other Functionalities of NumPy Arrays Advantages of NumPy Memory Consumption Performance Comparison 6.2 Exercises 6.2.1 Exercise 1: Even Before Odd Numbers (★★✩✩✩) Examples 6.2.2 Exercise 2: Flip (★★✩✩✩) Examples 6.2.3 Exercise 3: Palindrome (★★✩✩✩) Examples 6.2.4 Exercise 4: Inplace Rotate (★★★✩✩) Exercise 4a: Iterative (★★★✩✩) Example Exercise 4b: Recursive (★★★✩✩) 6.2.5 Exercise 5: Jewels Board Init (★★★✩✩) Exercise 5a: Initialize (★★★✩✩) Example Exercise 5b: Validity Check (★★★✩✩) Example 6.2.6 Exercise 6: Jewels Board Erase Diamonds (★★★★✩) Exercise 6a: Erase (★★★★✩) Examples Exercise 6b: Falling Down (★★★✩✩) Example 6.2.7 Exercise 7: Spiral Traversal (★★★★✩) Example 6.2.8 Exercise 8: Add One to an Array as a Number (★★✩✩✩) Examples 6.2.9 Exercise 9: Sudoku Checker (★★★✩✩) Example Example 6.2.10 Exercise 10: Flood Fill (★★✩✩✩) Exercise 10a (★★✩✩✩) Example Exercise 10b (★★✩✩✩) Example 6.2.11 Exercise 11: Array Min and Max (★★✩✩✩) Exercise 11a: Min and Max (★✩✩✩✩) Example Exercise 11b: Min und Max Pos (★★✩✩✩) Examples 6.2.12 Exercise 12: Array Split (★★★✩✩) Examples Exercise 12a: Array Split (★★✩✩✩) Exercise 12b: Array Split Inplace (★★★✩✩) Exercise 12c: Array Split Quick Sort Partition (★★★✩✩) Examples 6.2.13 Exercise 13: Minesweeper Board (★★★✩✩) Solution 13a (★★✩✩✩) Example Exercise 13b (★★★✩✩) Examples Exercise 13c (★★✩✩✩) Example 6.3 Solutions 6.3.1 Solution 1: Even Before Odd Numbers (★★✩✩✩) Examples Optimized Algorithm: Improved Running Time Optimized Algorithm: Less Copying Verification 6.3.2 Solution 2: Flip (★★✩✩✩) Examples Verification 6.3.3 Solution 3: Palindrome (★★✩✩✩) Examples Verification 6.3.4 Solution 4: Inplace Rotate (★★★✩✩) Solution 4a: Iterative (★★★✩✩) Example Solution 4b: Recursive (★★★✩✩) Verification 6.3.5 Solution 5: Jewels Board Init (★★★✩✩) Solution 5a: Initialize (★★★✩✩) Example Solution to the Bonus Task: Checking Diagonals (★★★✩✩) Verification Solution 5b: Validity Check (★★★✩✩) Example Verification 6.3.6 Solution 6: Jewels Board Erase Diamonds (★★★★✩) Solution 6a: Erase (★★★★✩) Examples Verification Solution 6b: Falling Down (★★★✩✩) Example Verification Overall Verification 6.3.7 Solution 7: Spiral Traversal (★★★★✩) Example Verification 6.3.8 Solution 8: Add One to an Array as a Number (★★✩✩✩) Examples Verification 6.3.9 Solution 9: Sudoku Checker (★★★✩✩) Example Verification Bonus Example Verification 6.3.10 Solution 10: Flood Fill (★★✩✩✩) Exercise 10a (★★✩✩✩) Example Verification Solution 10b (★★✩✩✩) Example Verification 6.3.11 Solution 11: Array Min and Max (★★✩✩✩) Solution 11a: Min and Max (★✩✩✩✩) Example Solution 11b: Min und Max Pos (★★✩✩✩) Examples Verification 6.3.12 Solution 12: Array Split (★★★✩✩) Examples Solution 12a: Array Split (★★✩✩✩) Solution 12b: Array Split Inplace (★★★✩✩) Solution 12c: Array Split Quick Sort Partition (★★★✩✩) Examples Verification 6.3.13 Solution 13: Minesweeper Board (★★★✩✩) Solution 13a (★★✩✩✩) Example Verification Solution 13b (★★★✩✩) Examples Verification Solution 13c (★★✩✩✩) Example Verification Summary: What You Learned Part II: More Advanced and Tricky Topics Chapter 7: Advanced Recursion 7.1 Memoization 7.1.1 Memoization for Fibonacci Numbers 7.1.2 Memoization for Pascal’s Triangle Conclusion 7.1.3 Memoization with Python On-Board Tools Memoization with a Decorator Built-in Memoization with lru_cache from the functools Module 7.2 Backtracking 7.2.1 The n-Queens Problem Algorithm What Is Still Missing in the Implementation? What Is the Next Step? 7.3 Exercises 7.3.1 Exercise 1: Towers of Hanoi (★★★✩✩) Example 7.3.2 Exercise 2: Edit Distance (★★★★✩) Examples 7.3.3 Exercise 3: Longest Common Subsequence (★★★✩✩) Examples 7.3.4 Exercise 4: Way Out of a Labyrinth (★★★✩✩) Example 7.3.5 Exercise 5: Sudoku Solver (★★★★✩) Example 7.3.6 Exercise 6: Math Operator Checker (★★★★✩) Examples 7.3.7 Exercise 7: Water Jug Problem (★★★✩✩) Examples 7.3.8 Exercise 8: All Palindrome Substrings (★★★★✩) Examples 7.3.9 Exercise 9: The n-Queens Problem (★★★✩✩) Example 7.4 Solutions 7.4.1 Solution 1: Towers of Hanoi (★★★✩✩) Bonus: Create a Console-Based Graphical Format Verification 7.4.2 Solution 2: Edit Distance (★★★★✩) Examples Verification Bonus: Optimize Edit Distance with Memoization (★★★✩✩) 7.4.3 Solution 3: Longest Common Subsequence (★★★✩✩) Examples Verification Bonus: Use Memoization for Longest Common Subsequence 7.4.4 Solution 4: Way Out of a Labyrinth (★★★✩✩) Example Verification Alternative 7.4.5 Solution 5: Sudoku Solver (★★★★✩) Example Verification Reasonable Optimizations 7.4.6 Solution 6: Math Operator Checker (★★★★✩) Examples Verification 7.4.7 Solution 7: Water Jug Problem (★★★✩✩) Examples Verification 7.4.8 Exercise 8: All Palindrome Substrings (★★★★✩) Examples Verification Bonus: Find the Longest of All Palindrome Substrings Verification 7.4.9 Solution 9: The n-Queens Problem (★★★✩✩) Example Verification Alternative Solution Approach Verification 7.5 Summary: What You Learned Chapter 8: Binary Trees 8.1 Introduction 8.1.1 Structure, Terminology, and Examples of Use 8.1.2 Binary Trees 8.1.3 Binary Trees with Order: Binary Search Trees 8.1.4 Traversals Breadth-First/Level Order Depth-First Searches 8.1.5 Balanced Trees and Other Properties The Properties Level and Height The Properties Completeness and Perfectness 8.1.6 Trees for the Examples and Exercises Tree with Letters and Numbers Trees with Textual and Real Digits 8.2 Exercises 8.2.1 Exercise 1: Tree Traversal (★★✩✩✩) Example 8.2.2 Exercise 2: Inorder, Preorder, and Postorder Iterative (★★★★✩) Example 8.2.3 Exercise 3: Tree Height (★★✩✩✩) Example 8.2.4 Exercise 4: Lowest Common Ancestor (★★★✩✩) Example 8.2.5 Exercise 5: Breadth-First (★★★✩✩) Examples 8.2.6 Exercise 6: Level Sum (★★★★✩) Example 8.2.7 Exercise 7: Tree Rotate (★★★✩✩) Example 8.2.8 Exercise 8: Reconstruction (★★★✩✩) Exercise 8a: Reconstruction from a List (★★✩✩✩) Example Exercise 8b: Reconstruction from Inorder/Preorder (★★★✩✩) Example 8.2.9 Exercise 9: Math Evaluation (★★✩✩✩) Example 8.2.10 Exercise 10: Symmetry (★★✩✩✩) Examples Example 8.2.11 Exercise 11: Check Binary Search Tree (★★✩✩✩) Example 8.2.12 Exercise 12: Completeness (★★★★★) Exercise 12a: Number of Nodes (★✩✩✩✩) Example Exercise 12b: Check for Full/Perfect (★★✩✩✩) Example Exercise 12c: Completeness (★★★★✩) Example Exercise 12d: Completeness Recursive (★★★★★) Example 8.2.13 Exercise 13: Tree Printer (★★★★★) Example Exercise 13a: Width of a Subtree (★★✩✩✩) Examples Exercise 13b: Draw Node (★★✩✩✩) Example Exercise 13c: Draw Connection Lines (★★✩✩✩) Example Exercise 13d: Tree Representation (★★★★★) Example 8.3 Solutions 8.3.1 Solution 1: Tree Traversal (★★✩✩✩) Bonus: Fill up a Tree into a List Example Verification 8.3.2 Solution 2: Inorder, Preorder, and Postorder Iterative (★★★★✩) Example Verification Surprise Algorithm 8.3.3 Solution 3: Tree Height (★★✩✩✩) Example Verification 8.3.4 Solution 4: Lowest Common Ancestor (★★★✩✩) Example Verification 8.3.5 Solution 5: Breadth-First (★★★✩✩) Examples Verification 8.3.6 Solution 6: Level Sum (★★★★✩) Example Verification 8.3.7 Solution 7: Tree Rotate (★★★✩✩) Example Verification 8.3.8 Solution 8: Reconstruction (★★★✩✩) Solution 8a: Reconstruction from a List (★★✩✩✩) Example Verification Solution 8b: Reconstruction from Inorder/Preorder (★★★✩✩) Example Verification 8.3.9 Solution 9: Math Evaluation (★★✩✩✩) Example Verification 8.3.10 Solution 10: Symmetry (★★✩✩✩) Examples Verification Bonus: Mirror Tree Example Verification 8.3.11 Solution 11: Check Binary Search Tree (★★✩✩✩) Example Verification 8.3.12 Solution 12: Completeness (★★★★★) Solution 12a: Number of Nodes (★✩✩✩✩) Example Solution 12b: Check for Full/Perfect (★★✩✩✩) Example Verification Solution 12c: Completeness (★★★★✩) Example Verification Solution 12d: Completeness Recursive (★★★★★) Example Verification 8.3.13 Solution 13: Tree Printer (★★★★★) Example Solution 13a: Width of a Subtree (★★✩✩✩) Examples Solution 13b: Draw Node (★★✩✩✩) Example Solution 13c: Draw Connection Lines (★★✩✩✩) Example Solution 13d: Tree Representation (★★★★★) Example Verification 8.4 Summary: What You Learned Chapter 9: Searching and Sorting 9.1 Introduction Search 9.1.1 Search with in(), index(), and count() 9.1.2 Search with rindex() and rfind() 9.1.3 Binary Search 9.2 Introduction Sort 9.2.1 Insertion Sort Determine Insertion Position Implementation of Insertion Sort 9.2.2 Selection Sort 9.2.3 Merge Sort 9.2.4 Quick Sort Inplace Implementation 9.2.5 Bucket Sort 9.2.6 Final Thoughts 9.3 Exercises 9.3.1 Exercise 1: Contains All (★★✩✩✩) Examples 9.3.2 Exercise 2: Partitioning (★★★★✩) Examples Exercise 2a: Partitioning Two Letters (★★★✩✩) Exercise 2b: Partitioning Three Letters (★★★★✩) 9.3.3 Exercise 3: Binary Search (★★✩✩✩) Exercise 3a: Binary Search Recursive (★★✩✩✩) Examples Exercise 3b: Binary Search Iterative (★★✩✩✩) Examples 9.3.4 Exercise 4: Insertion Sort (★★✩✩✩) Example 9.3.5 Exercise 5: Selection Sort (★★✩✩✩) Example 9.3.6 Exercise 6: Quick Sort (★★★✩✩) Examples 9.3.7 Exercise 7: Bucket Sort (★★✩✩✩) Example 9.3.8 Exercise 8: Search in Rotated Data (★★★★✩) Exercise 8a: Flank Change Efficient (★★★★✩) Examples Exercise 8b: Binary Search in Rotated Data (★★★★✩) Examples 9.4 Solutions 9.4.1 Solution 1: Contains All (★★✩✩✩) Examples Verification 9.4.2 Solution 2: Partitioning (★★★★✩) Examples Solution 2a: Partitioning Two Letters (★★★✩✩) Solution 2b: Partitioning Three Letters (★★★★✩) Verification 9.4.3 Solution 3: Binary Search (★★✩✩✩) Solution 3a: Binary Search Recursive (★★✩✩✩) Examples Solution 3b: Binary Search Iterative (★★✩✩✩) Examples Verification 9.4.4 Solution 4: Insertion Sort (★★✩✩✩) Example Verification 9.4.5 Solution 5: Selection Sort (★★✩✩✩) Example Verification 9.4.6 Solution 6: Quick Sort (★★★✩✩) Examples Verification 9.4.7 Solution 7: Bucket Sort (★★✩✩✩) Example Verification 9.4.8 Solution 8: Search in Rotated Data (★★★★✩) Solution 8a: Flank Change Efficient (★★★★✩) Examples Verification Solution 8b: Binary Search in Rotated Data (★★★★✩) Examples Verification 9.5 Summary: What You Learned Chapter 10: Conclusion and Supplementary Literature 10.1 Conclusion 10.1.1 Lessons Learned Per Chapter 10.1.2 Noteworthy Thoughts on Maintainability Thoughts on Performance Advantages of Unit Tests 10.2 Logic Puzzles 10.2.1 Gold Bags–Detect the Fake Solution 10.2.2 Horse Race–Determine Fastest Three Horses Solution 10.3 Supplementary Literature 10.3.1 Introduction to Algorithms and Data Structures 10.3.2 Basic Books 10.3.3 Specializing in Interview Questions 10.3.4 Supplements for Job Interviews at Top Companies Part III: Appendix Appendix A: Short Introduction to pytest A.1 Writing and Executing Tests A.1.1 Installing pytest A.1.2 First Unit Test A.1.3 Executing Tests Executing Tests on the Console Executing Tests from the IDE A.1.4 Handling Expected Exceptions A.1.5 Parameterized Tests with pytest Introduction to Parameterized Tests Other Possibilities in Parameterized Tests A.2 Further Reading on pytest Appendix B: Short Introduction to Decorators B.1 Argument Checks by Decorator B.2 Syntactic Sugar for Decorators B.3 Checking Multiple Parameters B.4 Logging Function Calls and Parameter Passing B.5 Improvement with wraps from the functools Module Appendix C: Quick Start O-Notation C.1 Estimations with O-Notation C.1.1 Complexity Classes C.1.2 Complexity and Program Running Time Appendix D: Short Introduction to Python 3.10 D.1 Error Messages D.1.1 Assignment Error Messages Python 3.9.x Improvement with Python 3.10 D.1.2 Error Messages for Incomplete Strings Python 3.9.x Improvement with Python 3.10 D.2 Case Distinctions with match D.2.1 Python 3.9.x Improvement with Python 3.10 Combination of Values More Complex Matching I More Complex Matching II D.3 Miscellaneous D.3.1 Improvements in Context Managers Improvement with Python 3.10 D.3.2 Performance Improvements D.3.3 Extension at zip() Python 3.9.x Improvement with Python 3.10 D.3.4 Typechecking Improvements Python 3.9.x Improvement with Python 3.10 Bibliography Index Augment your knowledge of Python with this entertaining learning guide, which features 100 exercises and programming puzzles and solutions. __Python Challenges__ will help prepare you for your next exam or a job interview, and covers numerous practical topics such as strings, data structures, recursion, arrays, and more. \*\* Each topic is addressed in its own separate chapter, starting with an introduction to the basics and followed by 10 to 15 exercises of various degrees of difficulty, helping you to improve your programming skills effectively. Detailed sample solutions, including the algorithms used for all tasks, are included to maximize your understanding of each area. Author **Michael Inden** also describes alternative solutions and analyzes possible pitfalls and typical errors. Three appendices round out the book: the first covers the Python command line interpreter, which is often helpful for trying out the code snippets and examples in the book, followed by an overview of Pytest for unit testing and checking the solutions. The last explains the O notation for estimating performance. After reading this book, you'll be prepared to take the next step in your career or tackle your next personal project. All source code is freely available for download via the Apress website. What You Will Learn Improve your Python knowledge by solving enjoyable but challenging programming puzzles \* Solve mathematical problems, recursions, strings, arrays and more \* Manage data processing and data structures like lists, sets, maps \* Handle advanced recursion as well as binary trees, sorting and searching \* Gamify key fundamentals for fun and easier reinforcement Who this book is for: Programmers, software developers who are either professionals or makers, as well as students and teachers. At least some prior experience with the Python programming is recommended.