همیشه در حال تماشا (کتاب همیشه ۱)

Get in the game and learn essential computer algorithms by solving competitive programming problems, in the fully revised second edition of the bestselling original. (Still no math required!) Are you hitting a wall with data structures and algorithms? Whether you’re a student prepping for coding interviews or an independent learner, this book is your essential guide to efficient problem-solving in programming. UNLOCK THE POWER OF DATA STRUCTURES & ALGORITHMS: Learn the intricacies of hash tables, recursion, dynamic programming, trees, graphs, and heaps. Become proficient in choosing and implementing the best solutions for any coding challenge. REAL-WORLD, COMPETITION-PROVEN CODE EXAMPLES: The programs and challenges in this book aren’t just theoretical—they’re drawn from real programming competitions. Train with problems that have tested and honed the skills of coders around the world. GET INTERVIEW-READY: Prepare yourself for coding interviews with practice exercises that help you think algorithmically, weigh different solutions, and implement the best choices efficiently. WRITTEN IN C, USEFUL ACROSS LANGUAGES: The code examples are written in C and designed for clarity and accessibility to those familiar with languages like C++, Java, or Python. If you need help with the C code, no problem: We’ve got recommended reading, too. Algorithmic Thinking is the complete package, providing the solid foundation you need to elevate your coding skills to the next level. FOREWORD ACKNOWLEDGMENTS INTRODUCTION What We’ll Do New to the Second Edition Who This Book Is For Our Programming Language Why Use C? Static Keyword Include Files Freeing Memory Topic Selection Programming Judges Anatomy of a Problem Description Starter Problem: Food Lines The Problem Solving the Problem Online Resources Notes 1 HASH TABLES Problem 1: Unique Snowflakes The Problem Simplifying the Problem Solving the Core Problem Solution 1: Pairwise Comparisons Solution 2: Doing Less Work Hash Tables Hash Table Design Why Use Hash Tables? Problem 2: Login Mayhem The Problem Solution 1: Looking at All Passwords Solution 2: Using a Hash Table Problem 3: Spelling Check The Problem Thinking About Hash Tables An Ad Hoc Solution Summary Notes 2 TREES AND RECURSION Problem 1: Halloween Haul The Problem Binary Trees Solving the Sample Instance Representing Binary Trees Collecting All the Candy A Completely Different Solution Walking the Minimum Number of Streets Reading the Input Why Use Recursion? Problem 2: Descendant Distance The Problem Reading the Input Number of Descendants from One Node Number of Descendants from All Nodes Sorting Nodes Outputting the Information The main Function Summary Notes 3 MEMOIZATION AND DYNAMIC PROGRAMMING Problem 1: Burger Fervor The Problem Forming a Plan Characterizing Optimal Solutions Solution 1: Recursion Solution 2: Memoization Solution 3: Dynamic Programming Memoization and Dynamic Programming Step 1: Structure of Optimal Solutions Step 2: Recursive Solution Step 3: Memoization Step 4: Dynamic Programming Problem 2: Moneygrubbers The Problem Characterizing Optimal Solutions Solution 1: Recursion The main Function Solution 2: Memoization Problem 3: Hockey Rivalry The Problem About Rivalries Characterizing Optimal Solutions Solution 1: Recursion Solution 2: Memoization Solution 3: Dynamic Programming A Space Optimization Summary Notes 4 ADVANCED MEMOIZATION AND DYNAMIC PROGRAMMING Problem 1: The Jumper The Problem Working Through an Example Solution 1: Backward Formulation Solution 2: Forward Formulation Problem 2: Ways to Build The Problem Working Through an Example Solution 1: Using “Exactly” Subproblems Solution 2: Adding More Subproblems Summary Notes 5 GRAPHS AND BREADTH-FIRST SEARCH Problem 1: Knight Chase The Problem Moving Optimally Best Knight Outcome The Knight Flip-Flop A Time Optimization Graphs and BFS What Are Graphs? Graphs vs. Trees BFS on Graphs Graphs vs. Dynamic Programming Problem 2: Rope Climb The Problem Solution 1: Finding the Moves Solution 2: A Remodel Problem 3: Book Translation The Problem Reading the Language Names Building the Graph The BFS The Total Cost Summary Notes 6 SHORTEST PATHS IN WEIGHTED GRAPHS Problem 1: Mice Maze The Problem Moving On from BFS Finding Shortest Paths in Weighted Graphs Building the Graph Implementing Dijkstra’s Algorithm Two Optimizations Dijkstra’s Algorithm Runtime of Dijkstra’s Algorithm Negative-Weight Edges Problem 2: Grandma Planner The Problem Adjacency Matrix Building the Graph Working Through a Weird Test Case Task 1: Shortest Paths Task 2: Number of Shortest Paths Summary Notes 7 BINARY SEARCH Problem 1: Feeding Ants The Problem A New Flavor of Tree Problem Reading the Input Testing Feasibility Searching for a Solution Binary Search Runtime of Binary Search Determining Feasibility Searching a Sorted Array Problem 2: River Jump The Problem A Greedy Idea Testing Feasibility Searching for a Solution Reading the Input Problem 3: Living Quality The Problem Sorting Every Rectangle Using Binary Search Testing Feasibility A Quicker Way to Test Feasibility Problem 4: Cave Doors The Problem Solving a Subtask Using Linear Search Using Binary Search Summary Notes 8 HEAPS AND SEGMENT TREES Problem 1: Supermarket Promotion The Problem Solution 1: Maximum and Minimum in an Array Max-Heaps Min-Heaps Solution 2: Heaps Heaps Two More Applications Choosing a Data Structure Problem 2: Building Treaps The Problem Recursively Outputting Treaps Sorting by Label Solution 1: Recursion Range Maximum Queries Segment Trees Solution 2: Segment Trees Segment Trees Problem 3: Two Sum The Problem Filling the Segment Tree Querying the Segment Tree Updating the Segment Tree The main Function Summary Notes 9 UNION-FIND Problem 1: Social Network The Problem Modeling as a Graph Solution 1: BFS Union-Find Solution 2: Union-Find Optimization 1: Union by Size Optimization 2: Path Compression Union-Find Relationships: Three Requirements Choosing Union-Find Optimizations Problem 2: Friends and Enemies The Problem Augmenting Union-Find The main Function Find and Union SetFriends and SetEnemies AreFriends and AreEnemies Problem 3: Drawer Chore The Problem Equivalent Drawers The main Function Find and Union Summary Notes 10 RANDOMIZATION Problem 1: Yōkan The Problem Randomly Choosing a Piece Generating Random Numbers Determining Number of Pieces Guessing Flavors How Many Attempts Do We Need? Filling the Flavor Arrays The main Function Randomization Monte Carlo Algorithms Las Vegas Algorithms Deterministic vs. Randomized Algorithms Problem 2: Caps and Bottles The Problem Solving a Subtask Solution 1: Recursion Solution 2: Adding Randomization Quicksort Implementing Quicksort Worst-Case and Expected Runtime Summary Notes AFTERWORD A ALGORITHM RUNTIME The Case for Timing . . . and Something Else Big O Notation Linear Time Constant Time Another Example Quadratic Time Big O in This Book B BECAUSE I CAN’T RESIST Unique Snowflakes: Implicit Linked Lists Burger Fervor: Reconstructing a Solution Knight Chase: Encoding Moves Dijkstra’s Algorithm: Using a Heap Mice Maze: Tracing with Heaps Mice Maze: Implementation with Heaps Compressing Path Compression Step 1: No More Ternary If Step 2: Cleaner Assignment Operator Step 3: Understand the Recursion Caps and Bottles: In-Place Sorting C PROBLEM CREDITS INDEX