Java Challenges: 100+ Proven Tasks that Will Prepare You for Anything

Table of Contents
About the Author
About the Technical Reviewer
Preface
Practice Makes Perfect
Why This Book?
Who Is This Book Aimed At?
What Does This Book Teach?
Practical Tips and Advice
Difficulty Level at a Glance
Structure of This Book
Conventions and Executable Programs
Character Sets Used
Abbreviations Used
Java Version(s) Used
Classes Used from the JDK
Downloads, Source Code, and Executables
Acknowledgements (English Book)
Acknowledgements (German Book)
Suggestions and Criticism
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 Eclipse Project
1.3 Basic Framework for Unit Tests
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 Thoughts on final and var
1.4.5 Notes on Method Visibility
1.4.6 Block Comments in Listings
1.4.7 Thoughts on Formatting
1.5 Trying Out the Examples and Solutions
1.6 Let’s Go: Discovering Java 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
2.1.5 Rules
2.1.6 Examples
2.1.7 Noteworthy
2.1.8 Number Games
2.1.9 Perfect Numbers
2.1.10 Armstrong Numbers
2.1.11 Algorithm for a Simple Checksum
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 a 2 + b 2 = c 2 + d 2
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
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(n4) to O(n3) (★★★✩✩)
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
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 as an Example
3.1.3 Steps When Multiplying the Digits of a Number
3.1.4 Typical Problems
Endless Calls and StackOverflowError
Unexpected Parameter Values
3.2 Exercises
3.2.1 Exercise 1: Fibonacci (★★✩✩✩)
Exercise 1a: Fibonacci Recursive (★✩✩✩✩)
Exercise 1b: Fibonacci Iterative (★★✩✩✩)
3.2.2 Exercise 2: Process Digits (★★✩✩✩)
Exercise 2a: Count Digits (★★✩✩✩)
Examples
Exercise 2b: Cross Sum (★★✩✩✩)
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: Array Sum (★★✩✩✩)
Examples
3.2.6 Exercise 6: Array 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 (★★✩✩✩)
3.3 Solutions
3.3.1 Solution 1: Fibonacci (★★✩✩✩)
Solution 1a: Fibonacci Recursive (★✩✩✩✩)
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: Array Sum (★★✩✩✩)
Examples
Verification
3.3.6 Solution 6: Array 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 (★★✩✩✩)
Verification
Chapter 4: Strings
4.1 Introduction
4.1.1 The Interface CharSequence
4.1.2 The Class String
Methods Relevant to Practice
4.1.3 The Classes StringBuffer and StringBuilder
Additional Functionality and Comparison with the Class String
4.1.4 The Class Character
Example
4.1.5 Examples Related to Character and String
Homemade Conversions with Character
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 (★✩✩✩✩)
Exercise 2a (★✩✩✩✩)
Exercise 2b (★✩✩✩✩)
Examples
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 strToLong (★★✩✩✩)
Examples
4.2.16 Exercise 16: Print Tower (★★★✩✩)
4.3 Solutions
4.3.1 Solution 1: Number Conversions (★★✩✩✩)
Examples
Solution 1a (★✩✩✩✩)
Solution 1b (★★✩✩✩)
Solution 1c (★★✩✩✩)
Verification
4.3.2 Solution 2: Joiner (★✩✩✩✩)
Solution 2a (★✩✩✩✩)
Examples
Solution 2b (★✩✩✩✩)
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 (★★✩✩✩)
Solution 7a (★★✩✩✩)
Examples
Solution 7b: Modification (★★✩✩✩)
Solution 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
Bonus
4.3.15 Solution 15: Conversion strToLong (★★✩✩✩)
Examples
Verification
Bonus: Enable the Parsing of Octal Numbers
Verification
4.3.16 Solution 16: Print Tower (★★★✩✩)
Verification
Chapter 5: Arrays
5.1 Introduction
5.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
5.1.2 Multidimensional Arrays
Introductory Example
Modeling Directions
5.1.3 Typical Errors
5.2 Exercises
5.2.1 Exercise 1: Even Before Odd Numbers (★★✩✩✩)
Examples
5.2.2 Exercise 2: Flip (★★✩✩✩)
Examples
5.2.3 Exercise 3: Palindrome (★★✩✩✩)
Examples
5.2.4 Exercise 4: Inplace Rotate (★★★✩✩)
Exercise 4a: Iterative (★★★✩✩)
Example
Exercise 4b: Recursive (★★★✩✩)
5.2.5 Exercise 5: Jewels Board Init (★★★✩✩)
Exercise 5a: Initialize (★★★✩✩)
Example
Exercise 5b: Validity Check (★★★✩✩)
Example
5.2.6 Exercise 6: Jewels Board Erase Diamonds (★★★★✩)
Exercise 6a: Erase (★★★★✩)
Examples
Exercise 6b: Falling Down (★★★✩✩)
Example
5.2.7 Exercise 7: Spiral Traversal (★★★★✩)
Example
5.2.8 Exercise 8: Add One to Array as Number (★★✩✩✩)
Examples
5.2.9 Exercise 9: Sudoku Checker (★★★✩✩)
Example
Example
5.2.10 Exercise 10: Flood Fill (★★✩✩✩)
Exercise 10a (★★✩✩✩)
Example
Exercise 10b (★★✩✩✩)
Example
5.2.11 Exercise 11: Array Merge (★★✩✩✩)
Examples
5.2.12 Exercise 12: Array Min and Max (★★✩✩✩)
Exercise 12a: Min and Max (★✩✩✩✩)
Example
Exercise 12b: Min and Max Pos (★★✩✩✩)
Examples
5.2.13 Exercise 13: Array Split (★★★✩✩)
Examples
Exercise 13a: Array Split (★★✩✩✩)
Exercise 13b: Array Split Inplace (★★★✩✩)
Exercise 13c: Array Split Quick Sort Partition (★★★✩✩)
Examples
5.2.14 Exercise 14: Minesweeper Board (★★★✩✩)
Exercise 14a (★★✩✩✩)
Example
Exercise 14b (★★★✩✩)
Examples
Exercise 14c (★★✩✩✩)
Example
5.3 Solutions
5.3.1 Solution 1: Even Before Odd Numbers (★★✩✩✩)
Examples
Optimized Algorithm: Improved Running Time
Optimized Algorithm: Less Copying
Verification
5.3.2 Solution 2: Flip (★★✩✩✩)
Examples
Verification
5.3.3 Solution 3: Palindrome (★★✩✩✩)
Examples
Verification
5.3.4 Solution 4: Inplace Rotate (★★★✩✩)
Solution 4a: Iterative (★★★✩✩)
Example
Solution 4b: Recursive (★★★✩✩)
Verification
5.3.5 Solution 5: Jewels Board Init (★★★✩✩)
Solution 5a: Initialize (★★★✩✩)
Example
Solution to the Bonus Task: Diagonal Check (★★★✩✩)
Verification
Solution 5b: Validity Check (★★★✩✩)
Example
Verification
5.3.6 Solution 6: Jewels Board Erase Diamonds (★★★★✩)
Solution 6a: Erase (★★★★✩)
Examples
Verification
Solution 6b: Falling Down (★★★✩✩)
Example
Verification
Overall Verification
5.3.7 Solution 7: Spiral Traversal (★★★★✩)
Example
Verification
5.3.8 Solution 8: Add One to Array as Number (★★✩✩✩)
Examples
Verification
5.3.9 Solution 9: Sudoku Checker (★★★✩✩)
Example
Verification
Bonus
Example
Verification
5.3.10 Solution 10: Flood Fill (★★✩✩✩)
Solution 10a (★★✩✩✩)
Example
Verification
Solution 10b (★★✩✩✩)
Example
Verification
5.3.11 Solution 11: Array Merge (★★✩✩✩)
Examples
Verification
5.3.12 Solution 12: Array Min and Max (★★✩✩✩)
Solution 12a: Min and Max (★✩✩✩✩)
Examples
Solution 12b: Min and Max Pos (★★✩✩✩)
Examples
Verification
5.3.13 Solution 13: Array Split (★★★✩✩)
Examples
Solution 13a: Array Split (★★✩✩✩)
Solution 13b: Array Split Inplace (★★★✩✩)
Solution 13c: Array Split Quick Sort Partition (★★★✩✩)
Examples
Verification
5.3.14 Solution 14: Minesweeper Board (★★★✩✩)
Solution 14a (★★✩✩✩)
Example
Verification
Solution 14b (★★★✩✩)
Examples
Verification
Solution 14c (★★✩✩✩)
Example
Verification
Chapter 6: Date Processing
6.1 Introduction
6.1.1 The Enumerations DayOfWeek and Month
6.1.2 The Classes LocalDate, LocalTime, and LocalDateTime
Extensions in the LocalDate Class with Java 9
6.1.3 The Class ZonedDateTime
6.1.4 The class ZoneId
6.1.5 The Class Duration
6.1.6 The Class Period
6.1.7 Date Arithmetic
Predefined TemporalAdjusters
More Specific Predefined TemporalAdjusters
Example
Example: Define TemporalAdjuster Yourself
6.1.8 Formatting and Parsing
6.2 Exercises
6.2.1 Exercise 1: Leap Years (★✩✩✩✩)
Examples
6.2.2 Exercise 2: Basic Knowledge Date-API (★★✩✩✩)
Exercise 2a: Creation (★✩✩✩✩)
Exercise 2b: Time Durations (★★✩✩✩)
6.2.3 Exercise 3: Length of Month (★★✩✩✩)
Exercise 3a: Calculations (★✩✩✩✩)
Exercise 3b: Length of Month (★★✩✩✩)
6.2.4 Exercise 4: Time Zones (★★✩✩✩)
Example
6.2.5 Exercise 5: Time Zone Calculation (★★✩✩✩)
Example
6.2.6 Exercise 6: Calculations with LocalDate
Exercise 6a: Friday the 13th (★★✩✩✩)
Example
Exercise 6b: Several Occurrences of Friday the 13th (★★✩✩✩)
Examples
6.2.7 Exercise 7: Calendar Output (★★★✩✩)
Example
6.2.8 Exercise 8: Weekdays (★✩✩✩✩)
Exercise 8a: Weekdays (★✩✩✩✩)
Examples
Exercise 8b: Date (★✩✩✩✩)
Example
Exercise 8c: Day in Month or Year (★✩✩✩✩)
Examples
6.2.9 Exercise 9: Sundays and Leap Years (★★✩✩✩)
Exercise 9a: Sundays
Examples
Exercise 9b: Leap Years
Examples
6.2.10 Exercise 10: TemporalAdjuster (★★★✩✩)
Examples
6.2.11 Exercise 11: NthWeekdayAdjuster (★★★✩✩)
Examples
6.2.12 Exercise 12: Payday TemporalAdjuster (★★★✩✩)
Example
6.2.13 Exercise 13: Formatting and Parsing (★★✩✩✩)
Examples
6.2.14 Exercise 14: Fault-Tolerant Parsing (★★✩✩✩)
Examples
6.3 Solutions
6.3.1 Solution 1: Leap Years (★✩✩✩✩)
Examples
Verification
6.3.2 Solution 2: Basic Knowledge Date-API (★★✩✩✩)
Solution 2a: Creation (★✩✩✩✩)
Solution 2b: Time Durations (★★✩✩✩)
6.3.3 Solution 3: Length of Month (★★✩✩✩)
Solution 3a: Calcu lations (★✩✩✩✩)
Solution 3b: Length of Month (★★✩✩✩)
Verification
6.3.4 Solution 4: Time Zones (★★✩✩✩)
Example
Verification
6.3.5 Solution 5: Time Zone Calculation (★★✩✩✩)
Example
Verification
6.3.6 Solution 6: Calculations With LocalDate
Exercise 6a: Friday the 13th (★★✩✩✩)
Example
Solution 6b: Several Occurrences of Friday the 13th (★★✩✩✩)
Examples
Verification
6.3.7 Solution 7: Calendar Output (★★★✩✩)
Example
Verification
6.3.8 Solution 8: Weekdays (★✩✩✩✩)
Solution 8a: Weekdays (★✩✩✩✩)
Examples
Verification
Solution 8b: Date (★✩✩✩✩)
Example
Verification
Solution 8c: Day in Month or Year (★✩✩✩✩)
Examples
Verification
6.3.9 Solution 9: Sundays and Leap Years (★★✩✩✩)
Solution 9a: Sundays
Examples
Verification
Solution 9b: Leap Years
Examples
Verification
6.3.10 Solution 10: TemporalAdjuster (★★★✩✩)
Examples
Verification
6.3.11 Solution 11: NthWeekdayAdjuster (★★★✩✩)
Examples
Verification
6.3.12 Solution 12: Payday TemporalAdjuster (★★★✩✩)
Example
Verification
6.3.13 Solution 13: Formatting and Parsing (★★✩✩✩)
Examples
Verification
6.3.14 Solution 14: Fault-Tolerant Parsing (★★✩✩✩)
Examples
Verification
Chapter 7: Basic Data Structures: Lists, Sets, and Maps
7.1 Introduction
7.1.1 The Interface Collection
7.1.2 Lists and the Interface List
The Interface List
7.1.3 Sets and the Interface Set
The Interface Set
7.1.4 Key-Value Mappings and the Interface Map
The Interface Map
7.1.5 The Stack as a LIFO Data Structure
Example
7.1.6 The Queue as a FIFO Data Structure
Example
7.2 Exercises
7.2.1 Exercise 1: Set Operations (★★✩✩✩)
Exercise 1a: Common Elements (★★✩✩✩)
Examples
Exercise 1b: Set Operations (★★✩✩✩)
Examples
7.2.2 Exercise 2: List Reverse (★★✩✩✩)
Exercise 2a: List Reverse (★★✩✩✩)
Examples
Exercise 2b: List Reverse Inplace (★★✩✩✩)
Exercise 2c: List Reverse Without Performant Index Access (★★✩✩✩)
7.2.3 Exercise 3: Remove Duplicates (★★✩✩✩)
Examples
7.2.4 Exercise 4: Maximum Profit (★★★✩✩)
Examples
7.2.5 Exercise 5: Longest Sequence (★★★✩✩)
Examples
7.2.6 Exercise 6: Own Stack (★★✩✩✩)
7.2.7 Exercise 7: Well-Formed Braces (★★✩✩✩)
Examples
7.2.8 Exercise 8: Check a Magic Triangle (★★★✩✩)
Examples
7.2.9 Exercise 9: Pascal’s Triangle (★★★✩✩)
Example
7.2.10 Exercise 10: Most Frequent Elements (★★✩✩✩)
Examples
7.2.11 Exercise 11: Addition of Digits (★★★✩✩)
Exercise 11a: Addition (★★★✩✩)
Examples
Exercise 11b: Addition Inverse (★★★✩✩)
Examples
7.2.12 Exercise 12: Compound Key (★★✩✩✩)
Examples
7.2.13 Exercise 13: List Merge (★★✩✩✩)
Examples
7.2.14 Exercise 14: Excel Magic Select (★★✩✩✩)
Examples
7.3 Solutions
7.3.1 Solution 1: Set Operations (★★✩✩✩)
Solution 1a: Common Elements (★★✩✩✩)
Examples
Verification
Solution 1b: Set Operations (★★✩✩✩)
Examples
Verification
7.3.2 Solution 2: List Reverse (★★✩✩✩)
Solution 2a: List Reverse (★★✩✩✩)
Examples
Solution 2b: List Reverse Inplace (★★✩✩✩)
Solution 2c: List Reverse Without Performant Index Access (★★✩✩✩)
Verification
7.3.3 Solution 3: Remove Duplicates (★★✩✩✩)
Examples
Verification
7.3.4 Solution 4: Maximum Profit (★★★✩✩)
Examples
Verification
7.3.5 Solution 5: Longest Sequence (★★★✩✩)
Examples
Verification
7.3.6 Solution 6: Own Stack (★★✩✩✩)
Verification
7.3.7 Solution 7: Well-Formed Braces (★★✩✩✩)
Examples
Verification
Bonus
7.3.8 Solution 8: Check a Magic Triangle (★★★✩✩)
Examples
Verification
Verification
7.3.9 Solution 9: Pascal’s Triangle (★★★✩✩)
Example
Verification
7.3.10 Solution 10: Most Frequent Elements (★★✩✩✩)
Examples
Verification
7.3.11 Solution 11: Addition of Digits (★★★✩✩)
Solution 11a: Addition (★★★✩✩)
Examples
Verification
Solution 11b: Addition Inverse (★★★✩✩)
Examples
Verification
7.3.12 Solution 12: Compound Key (★★✩✩✩)
Examples
Verification
7.3.13 Solution 13: List Merge (★★✩✩✩)
Examples
Verification
7.3.14 Solution 14: Excel Magic Select (★★✩✩✩)
Examples
Verification
Part II: More Advanced and Tricky Topics
Chapter 8: Recursion Advanced
8.1 Memoization
8.1.1 Memoization for Fibonacci Numbers
8.1.2 Memoization for Pascal’s Triangle
Conclusion
8.2 Backtracking
8.2.1 n-Queens Problem
Algorithm
What Is Still Missing in the Implementation? What is the Next Step?
8.3 Exercises
8.3.1 Exercise 1: Towers of Hanoi (★★★✩✩)
Example
8.3.2 Exercise 2: Edit Distance (★★★★✩)
Examples
8.3.3 Exercise 3: Longest Common Subsequence (★★★✩✩)
Examples
8.3.4 Exercise 4: Way Out of a Labyrinth (★★★✩✩)
Example
8.3.5 Exercise 5: Sudoku Solver (★★★★✩)
Example
8.3.6 Exercise 6: Math Operator Checker (★★★★✩)
Examples
8.3.7 Exercise 7: Water Jug Problem (★★★✩✩)
Examples
8.3.8 Exercise 8: All Palindrome Substrings (★★★★✩)
Examples
8.3.9 Exercise 9: n-Queens Problem (★★★✩✩)
Example
8.4 Solutions
8.4.1 Solution 1: Towers of Hanoi (★★★✩✩)
Example
Bonus: Create a Console-Based Graphical Format
Verification
8.4.2 Solution 2: Edit Distance (★★★★✩)
Examples
Verification
Verification
Bonus: Optimize Edit Distance with Memoization (★★★✩✩)
8.4.3 Solution 3: Longest Common Subsequence (★★★✩✩)
Examples
Verification
Bonus: Use Memoization for Longest Common Subsequence
8.4.4 Solution 4: Way Out of a Labyrinth (★★★✩✩)
Example
Verification
Alternative
8.4.5 Solution 5: Sudoku Solver (★★★★✩)
Example
Verification
Reasonable Optimizations
8.4.6 Solution 6: Math Operator Checker (★★★★✩)
Examples
Variant with Streams
Variant as of Java 15
Verification
8.4.7 Solution 7: Water Jug Problem (★★★✩✩)
Examples
Verification
8.4.8 Solution 8: All Palindrome Substrings (★★★★✩)
Examples
Bonus: Find the Longest of All Palindrome Substrings
Verification
8.4.9 Solution 9: n-Queens Problem (★★★✩✩)
Example
Verification
Alternative Solution Approach
Verification
Chapter 9: Binary Trees
9.1 Introduction
9.1.1 Structure, Terminology, and Examples of Use
9.1.2 Binary Trees
9.1.3 Binary Trees with Order: Binary Search Trees
9.1.4 Traversals
Breadth-First/Level-Order
Depth-First Searches
9.1.5 Balanced Trees and Other Properties
The Properties Level and Height
The Properties Completeness and Perfectness
9.1.6 Trees for the Examples and Exercises
Tree with Letters and Numbers
Trees with Textual and Real Digits
9.2 Exercises
9.2.1 Exercise 1: Tree Traversal (★★✩✩✩)
9.2.2 Exercise 2: Preorder, Inorder, and Postorder Iteratives (★★★★✩)
Example
9.2.3 Exercise 3: Tree Height (★★✩✩✩)
Example
9.2.4 Exercise 4: Lowest Common Ancestor (★★★✩✩)
Example
9.2.5 Exercise 5: Breadth-First (★★★✩✩)
Examples
9.2.6 Exercise 6: Level Sum (★★★★✩)
Example
9.2.7 Exercise 7: Tree Rotate (★★★✩✩)
Example
9.2.8 Exercise 8: Reconstruction (★★★✩✩)
Exercise 8a: Reconstruction from an Array (★★✩✩✩)
Example
Exercise 8b: Reconstruction from Preorder/Inorder (★★★✩✩)
Example
9.2.9 Exercise 9: Math Evaluation (★★✩✩✩)
Example
9.2.10 Exercise 10: Symmetry (★★✩✩✩)
Examples
Example
9.2.11 Exercise 11: Check Binary Search Tree (★★✩✩✩)
Example
9.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
9.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
9.3 Solutions
9.3.1 Solution 1: Tree Traversal (★★✩✩✩)
Bonus: Fill Up a Tree into a List
Verification
9.3.2 Solution 2: Preorder, Inorder, and Postorder Iteratives (★★★★✩)
Example
Verification
Surprise Algorithm
9.3.3 Solution 3: Tree Height (★★✩✩✩)
Example
Verification
9.3.4 Solution 4: Lowest Common Ancestor (★★★✩✩)
Example
Verification
9.3.5 Solution 5: Breadth-First (★★★✩✩)
Examples
Verification
9.3.6 Solution 6: Level Sum (★★★★✩)
Example
Verification
9.3.7 Solution 7: Tree Rotate (★★★✩✩)
Example
Verification
9.3.8 Solution 8: Reconstruction (★★★✩✩)
Solution 8a: Reconstruction from an Array (★★✩✩✩)
Example
Verification
Solution 8b: Reconstruction from Preorder/Inorder (★★★✩✩)
Example
Verification
9.3.9 Solution 9: Math Evaluation (★★✩✩✩)
Example
Verification
9.3.10 Solution 10: Symmetry (★★✩✩✩)
Examples
Verification
Bonus: Mirror Tree
Example
Verification
9.3.11 Solution 11: Check Binary Search Tree (★★✩✩✩)
Example
Verification
9.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
9.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
Chapter 10: Searching and Sorting
10.1 Introduction Search
10.1.1 Searching in Collections and Arrays
Searching with contains()
Searching with indexOf() and lastIndexOf()
Programming Searches in Arrays Yourself
10.1.2 Binary Search with binarySearch()
10.2 Introduction Sort
10.2.1 Insertion Sort
Determine Insertion Position
Implementation of Insertion Sort
10.2.2 Selection Sort
10.2.3 Merge Sort
10.2.4 Quick Sort
Inplace Implementation for Arrays
10.2.5 Bucket Sort
10.2.6 Final Thoughts
10.3 Exercises
10.3.1 Exercise 1: Contains All (★★✩✩✩)
Examples
10.3.2 Exercise 2: Partitioning (★★★★✩)
Examples
Exercise 2a: Partitioning Two Letters (★★★✩✩)
Exercise 2b: Partitioning Three Letters (★★★★✩)
10.3.3 Exercise 3: Binary Search (★★✩✩✩)
Exercise 3a: Binary Search Recursive (★★✩✩✩)
Examples
Exercise 3b: Binary Search Iterative (★★✩✩✩)
Examples
10.3.4 Exercise 4: Insertion Sort (★★✩✩✩)
Example
10.3.5 Exercise 5: Selection Sort (★★✩✩✩)
Example
10.3.6 Exercise 6: Quick Sort (★★★✩✩)
Examples
10.3.7 Exercise 7: Bucket Sort (★★✩✩✩)
Example
10.3.8 Exercise 8: Search in Rotated Data (★★★★✩)
Exercise 8a: Flank Change Efficient (★★★★✩)
Examples
Exercise 8b: Binary Search in Rotated Data (★★★★✩)
Examples
10.4 Solutions
10.4.1 Solution 1: Contains All (★★✩✩✩)
Examples
Verification
10.4.2 Solution 2: Partitioning (★★★✩✩)
Examples
Solution 2a: Partitioning Two Letters (★★✩✩✩)
Solution 2b: Partitioning Three Letters (★★★✩✩)
Verification
10.4.3 Solution 3: Binary Search (★★✩✩✩)
Solution 3a: Binary Search Recursive (★★✩✩✩)
Examples
Solution 3b: Binary Search Iterative (★★✩✩✩)
Examples
Verification
10.4.4 Solution 4: Insertion Sort (★★✩✩✩)
Example
Verification
10.4.5 Solution 5: Selection Sort (★★✩✩✩)
Example
Verification
10.4.6 Solution 6: Quick Sort (★★★✩✩)
Examples
Verification
10.4.7 Solution 7: Bucket Sort (★★✩✩✩)
Example
Verification
10.4.8 Solution 8: Search in Rotated Data (★★★★✩)
Solution 8a: Flank Change Efficient (★★★★✩)
Examples
Verification
Solution 8b: Binary Search in Rotated Data (★★★★✩)
Examples
Verification
Chapter 11: Conclusion and Supplementary Literature
11.1 Conclusion
11.1.1 Lessons Learned per Chapter
11.1.2 Noteworthy
Thoughts on Maintainability
Thoughts on Performance
Advantages of Unit Tests
11.2 Puzzles
11.2.1 Gold Bags: Detect the Fake
Solution
11.2.2 Horse Race: Determine Fastest Three Horses
Solution
11.3 Supplementary Literature
11.3.1 Introduction to Algorithms and Data Structures
11.3.2 Basic Books
11.3.3 Specializing in Interview Questions
11.3.4 Supplements for Job Interviews at Top Companies
Part III: Appendices
Appendix A: Quick Start for JShell
A.1 Java + REPL => jshell
A.1.1 Introductory Example
A.1.2 More Commands and Possibilities
A.1.3 Using Syntactic Specialties and Modern Java Features
A.1.4 More Complex Actions
A.1.5 Exiting the JShell
Appendix B: Short Introduction to JUnit 5
B.1 Writing and Running Tests
B.1.1 Example: A First Unit Test
B.1.2 Fundamentals of Writing and Running Tests
Testing Multiple Assertions with assertAll()
Test Execution
Eclipse plugin MoreUnit
B.1.3 Handling Expected Exceptions with assertThrows()
B.2 Parameterized Tests with JUnit 5
B.2.1 Introduction to Parameterized Tests with JUnit 5
B.2.2 More Practical Parameterized Tests
B.2.3 JUnit Parameterized Tests with @MethodSource
Appendix C: Quick Start for O-notation
C.1 Estimations with O-notation
C.1.1 Complexity Classes
C.1.2 Complexity and Program Running Time
Bibliography
Index