My implementation of useful data structures, algorithms, as well as my solutions to programming puzzles.
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.
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)
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
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.