Rocket - Think it. Type it. Launch it.
Mini toolsdonnemartin / interactive-coding-challenges
120+ interactive Python coding interview challenges (algorithms and data structures). Includes Anki flashcards.
README
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.
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:
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:
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
Misc
Challenges
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 |
| Add a challenge | Contribute │ Contribute |
Repo Structure
interactive-coding-challenges # Repo
├─ arrays_strings # Category of challenges
│ ├─ rotation # Challenge folder
│ │ ├─ rotation_challenge.ipynb # Challenge notebook
│ │ ├─ rotation_solution.ipynb # Solution notebook
│ │ ├─ test_rotation.py # Unit test*
│ ├─ compress
│ │ ├─ compress_challenge.ipynb
│ │ ├─ compress_solution.ipynb
│ │ ├─ test_compress.py
│ ├─ ...
├─ linked_lists
│ ├─ palindrome
│ │ └─ ...
│ ├─ ...
├─ ...*The notebooks (.ipynb) read/write the associated unit test (.py) file.
Notebook Installation
Zero Install
This README contains links to Binder , which hosts dynamic notebooks of the repo's contents online with no installation needed.
Jupyter Notebook
Run:
pip install jupyterFor detailed instructions, scripts, and tools to more optimally set up your development environment, check out the dev-setup repo.
For more details on notebook installation, follow the directions here.
More information on IPython/Jupyter Notebooks can be found here.
Running Challenges
Notebooks
Challenges are provided in the form of IPython/Jupyter Notebooks and have been tested with Python 2.7 and Python 3.x.
If you need to install IPython/Jupyter Notebook, see the Notebook Installation section.
- This README contains links to nbviewer, which hosts static notebooks of the repo's contents
- To interact with or to modify elements within the dynamic notebooks, refer to the instructions below
Run the notebook of challenges:
$ git clone https://github.com/donnemartin/interactive-coding-challenges.git
$ cd interactive-coding-challenges
$ jupyter notebookThis will launch your web browser with the list of challenge categories:
- Navigate to the Challenge Notebook you wish to solve
- Run the cells within the challenge notebook (Cell->Run All)
- This will result in an expected unit test error
- Solve the challenge and verify it passes the unit test
- Check out the accompanying Solution Notebook for further discussion
To debug your solution with pdb, refer to the following ticket.
Note: If your solution is different from those listed in the Solution Notebook, consider submitting a pull request so others can benefit from your work. Review the Contributing Guidelines for details.
Future Development
Challenges, solutions, and unit tests are presented in the form of IPython/Jupyter Notebooks.
- Notebooks currently contain mostly Python solutions (tested on both Python 2.7 and Python 3.x), but can be extended to include 40+ supported languages
- Repo will be continually updated with new solutions and challenges
- Contributions are welcome!
Contributing
Contributions are welcome!
Review the Contributing Guidelines for details on how to:
- Submit issues
- Add solutions to existing challenges
- Add new challenges
