interactive-coding-challenges ============

120+ continually updated, interactive, and test-driven coding challenges, with Anki flashcards.

Challenges focus on algorithms and data structures found in coding interviews.

Each challenge has one or more reference solutions that are:

• Fully functional
• Unit tested
• Easy-to-understand

Challenges will soon provide on-demand incremental hints to help you arrive at the optimal solution.

Notebooks also detail:

• Constraints
• Test cases
• Algorithms
• Big-O time and space complexities

Also included are unit tested reference implementations of various data structures and algorithms.

Challenge Solutions

Anki Flashcards: Coding and Design

The provided Anki flashcard deck uses spaced repetition to help you retain key concepts.

• Coding deck

Great for use while on-the-go.

Design Resource: The System Design Primer

Looking for resources to help you prep for the System Design and Object-Oriented Design interviews?

Check out the sister repo The System Design Primer, which contains additional Anki decks:

• System design deck
• System design exercises deck
• Object oriented design exercises deck

Notebook Structure

Each challenge has two notebooks, a challenge notebook with unit tests for you to solve and a solution notebook for reference.

Problem Statement

• States the problem to solve.

Constraints

• Describes any constraints or assumptions.

Test Cases

• Describes the general and edge test cases that will be evaluated in the unit test.

Algorithm

• [Challenge Notebook] Empty, refer to the solution notebook algorithm section if you need a hint.
• [Solution Notebook] One or more algorithm solution discussions, with Big-O time and space complexities.

Hints

• [Challenge Notebook] Provides on-demand incremental hints to help you arrive at the optimal solution. Coming soon!

Code (Challenge: Implement Me!)

• [Challenge Notebook] Skeleton code for you to implement.
• [Solution Notebook] One or more reference solutions.

Unit Test

• [Challenge Notebook] Unit test for your code. Expected to fail until you solve the challenge.
• [Solution Notebook] Unit test for the reference solution(s).

Index

Challenges Categories

Format: Challenge Category - Number of Challenges

• Arrays and Strings - 10
• Linked Lists - 8
• Stacks and Queues - 8
• Graphs and Trees - 21
• Sorting - 10
• Recursion and Dynamic Programming - 17
• Mathematics and Probability - 6
• Bit Manipulation - 8
• Online Judges - 16
• System Design - 8
• Object Oriented Design - 8

Total number of challenges: 120

Reference Implementations: Data Structures

Unit tested, fully functional implementations of the following data structures:

• Linked List
• Stack
• Queue
• Binary Search Tree
• Graph
• Min Heap
• Trie
• Priority Queue
• Hash Map

Reference Implementations: Algorithms

Unit tested, fully functional implementations of the following algorithms:

• Selection Sort
• Insertion Sort
• Quick Sort
• Merge Sort
• Radix Sort
• Topological Sort
• Tree Depth-First Search (Pre-, In-, Post-Order)
• Tree Breadth-First Search
• Graph Depth-First Search
• Graph Breadth-First Search
• Dijkstra's Shortest Path
• Unweighted Graph Shortest Path
• Knapsack 0/1
• Knapsack Unbounded
• Sieve of Eratosthenes

Reference Implementations: TODO

A

• Bellman-Ford
• Bloom Filter
• Convex Hull
• Fisher-Yates Shuffle
• Kruskal's
• Max Flow
• Prim's
• Rabin-Karp
• Traveling Salesman
• Union Find
• Contribute

Installing and Running Challenges

• Repo Structure
• Notebook Installation
• Running Challenges

Misc

• Contributing
• Credits
• Contact Info
• License

Challenges

Image Credits

Arrays and Strings

| Challenge | Static Notebook | |--------------------------------------------------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------------| | Determine if a string contains unique characters | Challenge │ Solution | | Determine if a string is a permutation of another | Challenge │ Solution | | Determine if a string is a rotation of another | Challenge │ Solution | | Compress a string | Challenge │ Solution | | Reverse characters in a string | Challenge │ Solution | | Given two strings, find the single different char | Challenge │ Solution | | Find two indices that sum to a specific value | Challenge │ Solution | | Implement a hash table | Challenge │ Solution | | Implement fizz buzz | Challenge │ Solution | | Find the first non-repeated character in a string | Contribute │ Contribute | | Remove specified characters in a string | Contribute │ Contribute | | Reverse words in a string | Contribute │ Contribute | | Convert a string to an integer | Contribute │ Contribute | | Convert an integer to a string | Contribute │ Contribute | | Add a challenge | Contribute │ Contribute |

Linked Lists

| Challenge | Static Notebook | |--------------------------------------------------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------------| | Remove duplicates from a linked list | Challenge │ Solution | | Find the kth to last element of a linked list | Challenge │ Solution | | Delete a node in the middle of a linked list | Challenge │ Solution | | Partition a linked list around a given value | Challenge │ Solution | | Add two numbers whose digits are stored in a linked list | Challenge │ Solution | | Find the start of a linked list loop | Challenge │ Solution | | Determine if a linked list is a palindrome | Challenge │ Solution | | Implement a linked list | Challenge │ Solution | | Determine if a list is cyclic or acyclic | Contribute │ Contribute | | Add a challenge | Contribute │ Contribute |

Stacks and Queues

| Challenge | Static Notebook | |--------------------------------------------------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------------| | Implement n stacks using a single array | Challenge │ Solution | | Implement a stack that keeps track of its minimum element | Challenge │ Solution | | Implement a set of stacks class that wraps a list of capacity-bounded stacks | Challenge │ Solution | | Implement a queue using two stacks | Challenge │ Solution | | Sort a stack using another stack as a buffer | Challenge │ Solution | | Implement a stack | Challenge │ Solution | | Implement a queue | Challenge │ Solution | | Implement a priority queue backed by an array | Challenge │ Solution | | Add a challenge | Contribute │ Contribute |

Graphs and Trees

| Challenge | Static Notebooks | |--------------------------------------------------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------------| | Implement depth-first search (pre-, in-, post-order) on a tree | Challenge │ Solution | | Implement breadth-first search on a tree | Challenge │ Solution | | Determine the height of a tree | Challenge │ Solution | | Create a binary search tree with minimal height from a sorted array | Challenge │ Solution | | Create a linked list for each level of a binary tree | Challenge │ Solution | | Check if a binary tree is balanced | Challenge │ Solution | | Determine if a tree is a valid binary search tree | Challenge │ Solution | | Find the in-order successor of a given node in a binary search tree | Challenge │ Solution | | Find the second largest node in a binary search tree | Challenge │ Solution | | Find the lowest common ancestor | Challenge │ Solution | | Invert a binary tree | Challenge │ Solution | | Implement a binary search tree | Challenge │ Solution | | Implement a min heap | Challenge │ Solution | | Implement a trie | Challenge │ Solution | | Implement depth-first search on a graph | Challenge │ Solution | | Implement breadth-first search on a graph | Challenge │ Solution | | Determine if there is a path between two nodes in a graph | Challenge │ Solution | | Implement a graph | Challenge │ Solution | | Find a build order given a list of projects and dependencies. | Challenge │ Solution | | Find the shortest path in a weighted graph. | Challenge │ Solution | | Find the shortest path in an unweighted graph. | Challenge │ Solution | | Add a challenge | Contribute │ Contribute |

Sorting

| Challenge | Static Notebooks | |--------------------------------------------------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------------| | Implement selection sort | Challenge │ Solution | | Implement insertion sort | Challenge │ Solution | | Implement quick sort | Challenge │ Solution | | Implement merge sort | Challenge │ Solution | | Implement radix sort | Challenge │ Solution | | Sort an array of strings so all anagrams are next to each other | Challenge │ Solution | | Find an item in a sorted, rotated array | Challenge │ Solution | | Search a sorted matrix for an item | Challenge │ Solution | | Find an int not in an input of n integers | Challenge │ Solution | | Given sorted arrays A, B, merge B into A in sorted order | Challenge │ Solution | | Implement a stable selection sort | Contribute │ Contribute | | Make an unstable sort stable | Contribute │ Contribute | | Implement an efficient, in-place version of quicksort | Contribute │ Contribute | | Given two sorted arrays, merge one into the other in sorted order | Contribute │ Contribute | | Find an element in a rotated and sorted array of integers | Contribute │ Contribute | | Add a challenge | Contribute │ Contribute |

Recursion and Dynamic Programming

| Challenge | Static Notebooks | |--------------------------------------------------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------------| | Implement fibonacci recursively, dynamically, and iteratively | Challenge │ Solution | | Maximize items placed in a knapsack | Challenge │ Solution | | Maximize unbounded items placed in a knapsack | Challenge │ Solution | | Find the longest common subsequence | Challenge │ Solution | | Find the longest increasing subsequence | Challenge │ Solution | | Minimize the cost of matrix multiplication | Challenge │ Solution | | Maximize stock prices given k transactions | Challenge │ Solution | | Find the minimum number of ways to represent n cents given an array of coins | Challenge │ Solution | | Find the unique number of ways to represent n cents given an array of coins | Challenge │ Solution | | Print all valid combinations of n-pairs of parentheses | Challenge │ Solution | | Navigate a maze | Challenge │ Solution | | Print all subsets of a set | Challenge │ Solution | | Print all permutations of a string | Challenge │ Solution | | Find the magic index in an array | Challenge │ Solution | | Find the number of ways to run up n steps | Challenge │ Solution | | Implement the Towers of Hanoi with 3 towers and N disks | Challenge │ Solution | | Implement factorial recursively, dynamically, and iteratively | Contribute │ Contribute | | Perform a binary search on a sorted array of integers | Contribute │ Contribute | | Print all combinations of a string | Contribute │ Contribute | | Implement a paint fill function | Contribute │ Contribute | | Find all permutations to represent n cents, given 1, 5, 10, 25 cent coins | Contribute │ Contribute | | Add a challenge | Contribute │ Contribute |

Mathematics and Probability

| Challenge | Static Notebooks | |--------------------------------------------------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------------| | Generate a list of primes | Challenge │ Solution | | Find the digital root | Challenge │ Solution | | Create a class supporting insert, max, min, mean, mode in O(1) | Challenge │ Solution | | Determine if a number is a power of two | Challenge │ Solution | | Add two numbers without the + or - sign | Challenge │ Solution | | Subtract two numbers without the + or - sign | Challenge │ Solution | | Check if a number is prime | Contribute │ Contribute | | Determine if two lines on a Cartesian plane intersect | Contribute │ Contribute | | Using only add, implement multiply, subtract, and divide for ints | Contribute │ Contribute | | Find the kth number such that the only prime factors are 3, 5, and 7 | Contribute │ Contribute | | Add a challenge | Contribute │ Contribute |

Bit Manipulation

| Challenge | Static Notebooks | |--------------------------------------------------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------------| | Implement common bit manipulation operations | Challenge │ Solution | | Determine number of bits to flip to convert a into b | Challenge │ Solution | | Draw a line on a screen | Challenge │ Solution | | Flip a bit to maximize the longest sequence of 1s | Challenge │ Solution | | Get the next largest and next smallest numbers | Challenge │ Solution | | Merge two binary numbers | Challenge │ Solution | | Swap odd and even bits in an integer | Challenge │ Solution | | Print the binary representation of a number between 0 and 1 | Challenge │ Solution | | Determine the number of 1s in the binary representation of a given integer | Contribute │ Contribute | | Add a challenge | Contribute │ Contribute |

Online Judges

| Challenge | Static Notebooks | |--------------------------------------------------------------------------------------------------------------|--------------------------------------------------------------------------------------------------------------------------------------------| | Find the longest substring with at most k distinct chars | Challenge │ Solution | | Find the highest product of three numbers | Challenge │ Solution | | Maximize stocks profit from 1 buy and 1 sell | Challenge │ Solution | | Move all zeroes in a list to the end | Challenge │ Solution | | Find the products of every other int | Challenge │ Solution | | Given a list of entries and exits, find the busiest period | Challenge │ Solution | | Determine an island's perimeter | Challenge │ Solution | | Format license keys | Challenge │ Solution | | Find the longest absolute file path | Challenge │ Solution | | Merge tuple ranges | Challenge │ Solution | | Assign cookies | Challenge │ Solution | | Determine if you can win in Nim | Challenge │ Solution | | Check if a magazine could have been used to create a ransom note | Challenge │ Solution | | Find the number of times a sentence can fit on a screen | Challenge │ Solution | | Utopian tree | Challenge │ Solution | | Maximizing xor | Challenge │ Solution