Continually updated, interactive and test-driven coding challenges.
Challenges focus on algorithms and data structures that are typically found in coding interviews or coding competitions.
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
Each challenge has two notebooks, a challenge notebook for you to solve and a solution notebook for reference.
- States the problem to solve.
- Describes any constraints or assumptions.
- Describes the general and edge test cases that will be evaluated in the unit test.
- [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.
- [Challenge Notebook] Provides on-demand incremental hints to help you arrive at the optimal solution. Coming soon!
- [Challenge Notebook] Skeleton code for you to implement.
- [Solution Notebook] One or more reference solutions.
- [Challenge Notebook] Unit test for your code. Expected to fail until you solve the challenge.
- [Solution Notebook] Unit test for the reference solution(s).
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.4), but can be extended to include 44 supported languages
- Repo will be continually updated with new solutions and challenges
- Contributions are welcome!
- Arrays and Strings
- Linked Lists
- Stacks and Queues
- Sorting
- Graphs and Trees
- Recursion and Dynamic Programming
- Bit Manipulation
- Scalability and Memory Limits
- Concurrency
- Online Judges
| 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 |
| Implement a hash table | 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 |
| 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 |
| 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 |
| Add a challenge | Contribute│Contribute |
| Challenge | Static Notebooks |
|---|---|
| Implement selection sort | Challenge│Solution |
| Implement insertion sort | Challenge│Solution |
| Implement quick sort | Challenge│Solution |
| Implement merge sort | 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 |
| Sort an array of strings so all anagrams are next to each other | Contribute│Contribute |
| Find an element in a rotated and sorted array of integers | Contribute│Contribute |
| Add a challenge | Contribute│Contribute |
| 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 |
| Implement a binary search tree | 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 |
| Print a tree using pre-order traversal without recursion | Contribute│Contribute |
| Determine the lowest common ancestor of two nodes | Contribute│Contribute |
| Transform a binary tree into a heap | Contribute│Contribute |
| Implement a right and left rotation on a tree | Contribute│Contribute |
| Check if a binary tree is binary search tree | Contribute│Contribute |
| Add a challenge | Contribute│Contribute |
| Challenge | Static Notebooks |
|---|---|
| Implement fibonacci recursively, dynamically, and iteratively | Challenge│Solution |
| Implement the Towers of Hanoi with 3 towers and N disks | Challenge│Solution |
| Find the 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 |
| Implement factorial recursively, dynamically, and iteratively | Contribute│Contribute |
| Perform a binary search on a sorted array of integers | Contribute│Contribute |
| Print all subsets of a set | Contribute│Contribute |
| Print all permutations of a string | 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 |
| Challenge | Static Notebooks |
|---|---|
| Check if a number is prime | Contribute│Contribute |
| Generate a list of primes | 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 |
| Challenge | Static Notebooks |
|---|---|
| Given a number between 0 and 1, print the binary representation | Contribute│Contribute |
| Determine the number of bits required to convert integer A to integer B | Contribute│Contribute |
| Swap odd and even bits in an integer with as few instructions as possible | Contribute│Contribute |
| Determine the number of 1 bits in the binary representation of a given integer | Contribute│Contribute |
| Add a challenge | Contribute│Contribute |
| Challenge | Static Notebooks |
|---|---|
| Utopian tree | Challenge│Solution |
| Maximizing xor | Challenge│Solution |
| Add a challenge | Contribute│Contribute |
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 (.pynb) read/write the associated unit test (.py) file.
Challenges are provided in the form of IPython/Jupyter Notebooks and have been tested with Python 2.7 and Python 3.4.
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 notebook
This 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.
Unit tests are provided in the form of Nose tests.
If you need to install Nose, see the Nose Installation section.
If you already have Python installed and are familiar with installing packages, you can get IPython Notebook with pip:
pip install "ipython[notebook]"
If you run into an issue about pyzmq, refer to the following Stack Overflow post and run:
pip uninstall ipython
pip install "ipython[all]"
As an alternative, you can also use the provided requirements.txt file:
pip install -r requirements.txt
For 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.
Install nose using setuptools/distribute:
easy_install nose
or
pip install nose
More information on Nose can be found here.
Contributions are welcome!
Review the Contributing Guidelines for details on how to:
- Submit issues
- Add solutions to existing challenges
- Add new challenges
- Cracking the Coding Interview | GitHub Solutions
- Elements of Programming Interviews | GitHub Solutions
- Programming Interviews Exposed
- The Algorithm Design Manual | Solutions
- CareerCup
- Quora
- HackerRank
- TopCoder
- Arrays and Strings: nltk.org
- Linked Lists: wikipedia.org
- Stacks: wikipedia.org
- Queues: wikipedia.org
- Sorting: wikipedia.org
- Recursion and Dynamic Programming: wikipedia.org
- Graphs and Trees: wikipedia.org
- Mathematics and Probability: wikipedia.org
- Bit Manipulation: wikipedia.org
- Online Judges: topcoder.com
Feel free to contact me to discuss any issues, questions, or comments.
- Email: donne.martin@gmail.com
- Twitter: @donne_martin
- GitHub: donnemartin
- LinkedIn: donnemartin
- Website: donnemartin.com
Copyright 2015 Donne Martin
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.