/interactive-coding-challenges

Continually updated, interactive, test-driven Python coding interview challenges (algorithms and data structures).

Primary LanguagePythonOtherNOASSERTION


interactive-coding-challenges

Continually updated, interactive and test-driven coding challenges.

Challenges focus on algorithms and data structures that are typically 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

Challenge Solutions



Notebook Structure

Each challenge has two notebooks, a challenge notebook 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).

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.4), but can be extended to include 44 supported languages
  • Repo will be continually updated with new solutions and challenges
  • Contributions are welcome!

Index

Challenges Categories

Installing and Running Challenges

Misc

Challenges

Image Credits



Arrays and Strings

Challenge Static Notebook
Determine if a string contains unique characters ChallengeSolution
Determine if a string is a permutation of another ChallengeSolution
Determine if a string is a rotation of another ChallengeSolution
Compress a string ChallengeSolution
Reverse characters in a string ChallengeSolution
Implement a hash table ChallengeSolution
Find the first non-repeated character in a string ContributeContribute
Remove specified characters in a string ContributeContribute
Reverse words in a string ContributeContribute
Convert a string to an integer ContributeContribute
Convert an integer to a string ContributeContribute
Add a challenge ContributeContribute


Linked Lists

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


Stacks and Queues

Challenge Static Notebook
Implement n stacks using a single array ChallengeSolution
Implement a stack that keeps track of its minimum element ChallengeSolution
Implement a set of stacks class that wraps a list of capacity-bounded stacks ChallengeSolution
Implement a queue using two stacks ChallengeSolution
Sort a stack using another stack as a buffer ChallengeSolution
Implement a stack ChallengeSolution
Implement a queue ChallengeSolution
Add a challenge ContributeContribute


Graphs and Trees

Challenge Static Notebooks
Implement depth-first search (pre-, in-, post-order) on a tree ChallengeSolution
Implement breadth-first search on a tree ChallengeSolution
Determine the height of a tree ChallengeSolution
Create a binary search tree with minimal height from a sorted array ChallengeSolution
Create a linked list for each level of a binary tree ChallengeSolution
Check if a binary tree is balanced ChallengeSolution
Determine if a tree is a valid binary search tree ChallengeSolution
Find the in-order successor of a given node in a binary search tree ChallengeSolution
Implement a binary search tree ChallengeSolution
Implement depth-first search on a graph ChallengeSolution
Implement breadth-first search on a graph ChallengeSolution
Determine if there is a path between two nodes in a graph ChallengeSolution
Implement a graph ChallengeSolution
Print a tree using pre-order traversal without recursion ContributeContribute
Determine the lowest common ancestor of two nodes ContributeContribute
Transform a binary tree into a heap ContributeContribute
Implement a right and left rotation on a tree ContributeContribute
Check if a binary tree is binary search tree ContributeContribute
Add a challenge ContributeContribute


Sorting

Challenge Static Notebooks
Implement selection sort ChallengeSolution
Implement insertion sort ChallengeSolution
Implement quick sort ChallengeSolution
Implement merge sort ChallengeSolution
Implement a stable selection sort ContributeContribute
Make an unstable sort stable ContributeContribute
Implement an efficient, in-place version of quicksort ContributeContribute
Given two sorted arrays, merge one into the other in sorted order ContributeContribute
Sort an array of strings so all anagrams are next to each other ContributeContribute
Find an element in a rotated and sorted array of integers ContributeContribute
Add a challenge ContributeContribute


Recursion and Dynamic Programming

Challenge Static Notebooks
Implement fibonacci recursively, dynamically, and iteratively ChallengeSolution
Implement the Towers of Hanoi with 3 towers and N disks ChallengeSolution
Find the number of ways to represent n cents given an array of coins ChallengeSolution
Print all valid combinations of n-pairs of parentheses ChallengeSolution
Implement factorial recursively, dynamically, and iteratively ContributeContribute
Perform a binary search on a sorted array of integers ContributeContribute
Print all subsets of a set ContributeContribute
Print all permutations of a string ContributeContribute
Print all combinations of a string ContributeContribute
Implement a paint fill function ContributeContribute
Find all permutations to represent n cents, given 1, 5, 10, 25 cent coins ContributeContribute
Add a challenge ContributeContribute


Mathematics and Probability

Challenge Static Notebooks
Check if a number is prime ContributeContribute
Generate a list of primes ContributeContribute
Determine if two lines on a Cartesian plane intersect ContributeContribute
Using only add, implement multiply, subtract, and divide for ints ContributeContribute
Find the kth number such that the only prime factors are 3, 5, and 7 ContributeContribute
Add a challenge ContributeContribute


Bit Manipulation

Challenge Static Notebooks
Given a number between 0 and 1, print the binary representation ContributeContribute
Determine the number of bits required to convert integer A to integer B ContributeContribute
Swap odd and even bits in an integer with as few instructions as possible ContributeContribute
Determine the number of 1 bits in the binary representation of a given integer ContributeContribute
Add a challenge ContributeContribute


Online Judges

Challenge Static Notebooks
Utopian tree ChallengeSolution
Maximizing xor ChallengeSolution
Add a challenge ContributeContribute

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 (.pynb) read/write the associated unit test (.py) file.

Notebook Installation

IPython Notebook

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.

Nose Tests

Install nose using setuptools/distribute:

easy_install nose

or

pip install nose

More information on Nose 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.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.

Contributing

Contributions are welcome!

Review the Contributing Guidelines for details on how to:

  • Submit issues
  • Add solutions to existing challenges
  • Add new challenges

Credits

Resources

Images

Contact Info

Feel free to contact me to discuss any issues, questions, or comments.

My contact info can be found on my GitHub page.

License

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.