This is a repository where I keep all interesting algorithms and data structures I came across either in work or learning.
Lack of a well-trained background in computer science always pushed me back in taking time to catch up in algorithms and data structures. But that is indeed the area where a programmer shines and aligns the thinking process with his beloved machine. Behind the general software engineering principles, it's the carefully designed algorithms and data structures in vaiours code snippets that make the overall product performant and wonderful.
Java 8 is required so as to support the functional interface and Lambda expressions used.
Each package contains an interesting algorithmic question with solution provided.
- Run it as a Java application in a common IDE like Eclipse (make sure Java 8 is supported). This provides flexibility to modify code.
- Key function calls will be provided with roughly estimated running time so as to cross check with the indicated time complexity.
- Integer Array
- Find the largest sub-array sum of a given integer array
- Find the largest absolute difference of two non-overlapping sub-arrays of a given integer array
- Find total number of reverse pairs in a given integer array
- Find the largest sum of a sub-array with size K in a given integer array
- Find the k'th smallest item from a given array of distinct integers
- Find number pairs each of which sums up to a fixed value from an integer array
- All hail Recursion! Find required add and subtract operations to produce a fixed sum
- Find the greatest common divisor of an array of integers
- Print numbers along matrix diagonals
- Print spiral numbers
- Bitwise operations
- Merge sorted integer arrays
- All hail Recursion! Find all subsets of an integer set
- Patch a given array to produce list of sums from 1 to N
- Binary search in a sorted array rotated at an unknown pivot
- All hail Recursion! Number permutation
- All hail Recursion! Number combination
- Random number with different entropies
- Binary search in matrix
- Multiple-Condition Check Insert intervals
- Reverse an integer number
- Recover a rotated sorted array
- NP Hard Bin packing problem
- Boyer–Moore Majority Vote Algorithm Find majority numbers
- Monkey crossing river
- Number of ways to sum up to a given number with consecutive positive integers
- Array based circular queue
- Linked List
- Dynamic Programming
- Fibonacci Numbers
- Binomial Coefficients
- Catalan Numbers Find all expressions of balanced n pairs of parentheses
- Coin change problems
- Number of possible combinations for given sum
- List of possible combinations for given sum
- Least number of coins needed for given sum
- Number arrangements to get a fixed sum
- Maximum sub-array sum
- Ugly Numbers
- Maximum stock profit
- Digit sequence decoder
- Longest common subsequence
- Longest common substring
- Longest increasing subsequence
- Edit distance algorithm
- Set partition for minimum sum difference
- Distance and steps
- Longest path in matrix
- NP-Complete Subset of fixed sum
- Optimal coin game strategy
- Minimum insertions for palindrome
- NP-Complete 0-1 Knapsack problem
- Wildcard pattern match check
- Beware of integer overflow! Boolean parenthesization
- DP Enhancement Find required add and subtract operations to produce a fixed sum
- Shortest common supersequence
- Least arithmetic operations for matrix chain multiplication
equalsandhashCodemethod override Rod cutting for maximum gain- Resolve a string with dictionary words
- Rope cutting for maximum length product
- Dice rolling for fixed sum
- Egg dropping puzzle
- K non-overlapping subarrays of maximum sum
- LEGO part assembler
- NP-Complete Minimum time for fixed sum of points
- String
- Remove duplicates in string
- Remove alternate duplicates in string
- Remove adjacent duplicates in string
- Remove consecutive duplicates in string
- Longest valid parentheses substring
- Parentheses checker
- In-place string rotator
- Backtracking String permutation
- KMP Algorithm Search for patterns in string
- DP Check interleaved string
- Minimum window substring
- IPv4 address regex matcher
- Functional Programming Credit card number Luhn check
- String to int converter
- Longest palindromic substring
- Binary Tree
- Plain Binary Tree implementation with linked nodes
- Pre-order Traversal
- Post-order Traversal
- Level-order Traversal
- Clone via pre-order traversal
- Serialization/de-serialization
- Plain Binary Search Tree implementation with linked nodes
- Parse a BST from its pre-order traversal
- Parse a BST from its post-order traversal
- Parse a BST from its level-order traversal
- Convert a BT to a BST with tree structure maintained
- Divide and Conquer Search range in BST
- Sum up greater keys with each node in BST
- Sum up greater keys for each node in BST
- Convert integer array to BST
- Convert integer linked list to BST
- All possible BSTs from 1 to N Catalan Numbers
- Convert BST to min heap
- Convert BT to doubly linked list
- Convert complete BST to conditional min heap where left sub-tree smaller than right sub-tree
- Binary tree mirror image
- Plain Binary Tree implementation with linked nodes
- Binary Heap
- Graph
- Plain Directed Graph implementation with adjacency list
- Breadth First Search
- Depth First Search
- Linear paths from source to destination
- Plain Directed Graph implementation with adjacency list
- Backtracking Technique
This all started with a day when I accidentally picked a book my university professor passed me when I graduated.
Data Structures & Algorithm Analysis in Java by Weiss, Mark Allen (ISBN 0-201-35754-2). It's a textbook for first-year graduate student in computer science so it should be a good starting point.
Well eventually it turned out that reading book is rather slow and solving problems can be more challenging and rewarding. Hence eventually this repository became a place where I keep my practice and notes. Each question comes with a detailed explanation in code comments. When I do coding practice on LintCode, LeetCode or Geeks For Geeks and encounter certain typical and interesting problems, I will add them to the list here.
Author: Ruifeng Ma
Email: [email protected]
- Fork the repository on Github
- Create a named feature branch (like
add_component_x) - Write your change
- Write tests for your change (if applicable)
- Run the tests, ensuring they all pass
- Submit a Pull Request using Github