# Free book – for #datascience interviews - Guide to competitive programming Competitive programming strategies are useful for many data science interviews and they help to improve your maths foundations.  There are not many books on this subject (although there are many good websites and YouTube resources).

So, I hope you find this book useful

From the book

• Competitive programming combines two topics: the design of algorithms and the implementation of algorithms.
• Design of Algorithms The core of competitive programming is about inventing efficient algorithms that solve well-defined computational problems.
• The design of algorithms requires problem solving and mathematical skills. Often a solution to a problem is a combination of well-known methods and new insights.
• Mathematics plays an important role in competitive programming. Actually, there are no clear boundaries between algorithm design and mathematics.
• The most common language for the implementation of competitive algorithms is C++

The book contents are

Programming Techniques

Language Features

Input and Output

Working with Numbers

Shortening Code

Recursive Algorithms

Generating Subsets

Generating Permutations

Backtracking

Bit Manipulation

Bit Operations

Representing Sets

Efficiency

Time Complexity

Calculation Rules

Common Time Complexities

Estimating Efficiency

Formal Definitions

Examples

Maximum Subarray Sum

Two Queens Problem

Sorting and Searching

Sorting Algorithms

Bubble Sort

vii

Merge Sort

Sorting Lower Bound

Counting Sort

Sorting in Practice

Solving Problems by Sorting

Sweep Line Algorithms

Scheduling Events

Binary Search

Implementing the Search

Finding Optimal Solutions

Data Structures

Dynamic Arrays

Vectors

Iterators and Ranges

Other Structures

Set Structures

Sets and Multisets

Maps

Priority Queues

Policy-Based Sets

Experiments

Set Versus Sorting

Map Versus Array

Priority Queue Versus Multiset

Dynamic Programming

Basic Concepts

When Greedy Fails

Finding an Optimal Solution

Counting Solutions

Further Examples

Longest Increasing Subsequence

Paths in a Grid

Knapsack Problems

From Permutations to Subsets

Counting Tilings

Graph Algorithms

Basics of Graphs

Graph Terminology

Graph Representation

Graph Traversal

Depth-First Search

viii Contents

Applications

Shortest Paths

Bellman–Ford Algorithm

Dijkstra’s Algorithm

Floyd–Warshall Algorithm

Directed Acyclic Graphs

Topological Sorting

Dynamic Programming

Successor Graphs

Finding Successors

Cycle Detection

Minimum Spanning Trees

Kruskal’s Algorithm

Union-Find Structure

Prim’s Algorithm

Algorithm Design Topics

Bit-Parallel Algorithms

Hamming Distances

Counting Subgrids

Reachability in Graphs

Amortized Analysis

Two Pointers Method

Nearest Smaller Elements

Sliding Window Minimum

Finding Minimum Values

Ternary Search

Convex Functions

Minimizing Sums

Range Queries

Queries on Static Arrays

Sum Queries

Minimum Queries

Tree Structures

Binary Indexed Trees

Segment Trees

Tree Algorithms

Basic Techniques

Tree Traversal

Calculating Diameters

All Longest Paths

Contents ix

Tree Queries

Finding Ancestors

Subtrees and Paths

Lowest Common Ancestors

Merging Data Structures

Centroid Decomposition

Heavy-Light Decomposition

Mathematics

Number Theory

Primes and Factors

Sieve of Eratosthenes

Euclid’s Algorithm

Modular Exponentiation

Euler’s Theorem

Solving Equations

Combinatorics

Binomial Coefficients

Catalan Numbers

Inclusion-Exclusion

Burnside’s Lemma

Cayley’s Formula

Matrices

Matrix Operations

Linear Recurrences

Graphs and Matrices

Gaussian Elimination

Probability

Working with Events

Random Variables

Markov Chains

Randomized Algorithms

Game Theory

Game States

Nim Game

Sprague–Grundy Theorem

Strong Connectivity

Kosaraju’s Algorithm

SAT Problem

Complete Paths

Eulerian Paths

x Contents

Hamiltonian Paths

Applications

Maximum Flows

Ford–Fulkerson Algorithm

Disjoint Paths

Maximum Matchings

Path Covers

Depth-First Search Trees

Biconnectivity

Eulerian Subgraphs

Geometry

Geometric Techniques

Complex Numbers

Points and Lines

Polygon Area

Distance Functions

Sweep Line Algorithms

Intersection Points

Closest Pair Problem

Convex Hull Problem

String Algorithms

Basic Topics

Trie Structure

Dynamic Programming

String Hashing

Polynomial Hashing

Applications

Collisions and Parameters

Z-Algorithm

Constructing the Z-Array

Applications

Suffix Arrays

Prefix Doubling Method

Finding Patterns

LCP Arrays

Square Root Techniques

Data Structures

Subalgorithms

Integer Partitions

Mo’s Algorithm

Contents xi

Segment Trees Revisited

Lazy Propagation

Dynamic Trees

Data Structures in Nodes

Two-Dimensional Trees

Treaps

Splitting and Merging

Implementation

Dynamic Programming Optimization

Convex Hull Trick

Divide and Conquer Optimization

Knuth’s Optimization

Miscellaneous

Meet in the Middle

Counting Subsets

Parallel Binary Search

Dynamic Connectivity

Appendix A: Mathematical Background

Views: 4313