chiphuyen/coding-exercises

This repository contains my implementation of useful data structures, algorithms, games, as well as my solutions to programming puzzles.

Each item is marked with a difficulty level. 1 - easy 2 - medium 3 - hard

If a file name starts with 'lc', it's a problem from leetcode.com

Written in python3. Thanks Danijar Hafner (@danijar) for the inspiration.

Data structures

Linked lists

• List class (linked_list.py) - 1
• Remove duplicates (linked_list_algos.py)
• Find nth last element (linked_list_algos.py)
• Remove node given only its object (linked_list_algos.py)
• Sum linked lists with one digit per node (linked_list_algos.py)
• Find beginning of circle (linked_list_algos.py)

Trees

• Binary heap class (binary_heap.py) - 2

• Binary tree class (binary_tree.py) - 1

• Binary search tree class that allows duplicate values (binary_search_tree.py) - 2

  BST class inherits binary tree class
  

• Red black tree class (red_black_tree.py)

• B+ tree class (b_tree.py) - 3

• Trie class that allows word removal (trie.py) - 2

• Check if a binary tree is a binary search tree (binary_tree_algos.py) - 2

• Check if a binary tree is balanced (binary_tree_algos.py)

• Find first common ancestor of two nodes in a binary tree (binary_tree_algos.py)

• Get all nodes of depth n in a binary tree (binary_tree_algos.py)

• Given two large trees, check if the first is a subtree of the second (binary_tree_algos.py)

• Find all sub paths in a binary tree that sum up to x (binary_tree_algos.py)

• Create a balanced binary search tree from a sorted array (bst_algos.py)

Graphs

• Undirected graph class
• Directed graph class
• Breadth first search (search.py)
• Depth first search (search.py)
• A-star (search.py)

Stacks and queues

• Queue class (queue.py)
• Heap priority queue (priority_queue.py) - 1
• Stack class (stack.py)
• Stack that finds min in O(1) (min_stack.py)
• Solve Hanoi towers using stacks (stack_algos.py)
• Sort stack using only push, pop, peek and empty (stack_algos.py)
• Build a queue using two stacks (stack_algos.py)

Algorithms

Sorting

• Insertion sort (sort.py) - 1
• Selection sort (sort.py) - 1
• Merge sort (sort.py) - 2
• Heap sort (sort.py) - 2
• Quick sort (sort.py) - 2
• Counting sort (sort.py) - 2
• Radix sort (sort.py) - 2
• Bucket sort (sort.py) - 2

Dynamic Programming

• Computing a Fibonacci sequence
• Find the longest common subsequence between two strings

Recursion

• Find all permutations of a string
• Find all subsets of a set
• Find all proper combinations of n parentheses
• Bucket fill
• Check if it's possible to make a change with a set of coins
• Check if it's possible to weight two objects with a set of weights
• Eight queen

Programming Puzzles

String Manipulation

• Check if two strings are anagrams in O(n + m) time (anagrams.py) - 1
• Find the longest palindromic substring in O(n^2) time (lc_longest_palindrome.py) - 2
• Check if a string has balanced delimiters in O(n) time (delim_balanced.py) - 2
• Reverse words while maintaining spaces and tabs in O(n) time (reverse_words.py) - 2
• Longest substring without repeating characters in O(n) time (lc_longest_nonrepeat_substring.py) - 2
• Longest contiguous substring of 2 distinct characters in O(n) time (substring_two_chars.py) - 2
• Remove duplicate chars in a string
• Encode and decode Caesar cipher (caesar.py)
• Check if a string is a rotation of another

Mathematical

• Reverse integers (lc_reverse_int.py) - 1

• Sieve of Eratosthenes (sieve_prime.py) - 1

• Two sum in O(n) time (lc_two_sum.py) - 1

  Given an array of integers, return indices of the two numbers 
  such that they add up to a specific target.
  

• Year with maximum population (year_max_pop.py) - 1

  Given a list of people with their years of birth and death, 
  find the year with max population
  

• FizzBuzz (fizzbuzz.py) - 1

• ZigZag conversion (lc_zigzag_convert.py) - 2

• Find sum of all subarrays of an array (subarray_sum.py) - 2

• Add two numbers, each represented by a reverse linked list (lc_add_number_reverse.py) - 2

• Find the median of two sorted arrays in O(log(m+n)) time (lc_median_arrays.py) - 3

• Find nth smallest number that can be created using a list of prime factors

• Count occurences of given digit in all numbers up to n

• Rotate N x N matrix in place

Games

• Game of ghost (ghost.py) - 3

  Ghost is a word game in which players take turns adding letters to a
  growing word fragment, trying not to be the one to complete a valid word.
  
  This implementation uses minimax with alpha-beta pruning to make sure the computer always wins.
  It uses a Trie to keep track of the dictionary.