This repository contains various algorithm and data structure implementations in Java 8.
For any given problem follow the steps bellow as you would do in professional settings:
- Examples: Ask for examples
- Clarify: Ask questions to clarify input-output and constraints
- First Solution: Find a brute-force solution and estimate time/space complexity
- Iterate: Iterate to find improvements and their time/space complexity
- Approval: Ask if the solution is OK to proceed with
- Test cases: Think about test cases: Edge cases, Base cases and Regular cases
- Code: Write the solution. Feel free to add comments in the code. Make it as neat and clean as possible.
- Verify: verify your code using the tests cases.
Here is the list of algorithm problems and implementations:
- Clone even numbers in the array
- Find a pair that equals to the given sum in a sorted array
- Rearrange all zeros (or num) at the start
- Rearrange all zeros (num) at the end
- Swap two numbers in an array without temporary variable
- Arrange numbers in three groups based on pivot (Dutch Flag)
- Reverse words in a sentence
- Find longest unique substring
- Find a pair that equals to the given sum in an unsorted array
- Find a subarray with maximum sum
- Find a subarray that equals to the sum
- Prefix sum: Given an array of integers, find the contiguous subarray that sums to 0.
- Find an item (number, object) in a sorted array (Generic Binary Search)
- Given a sorted array that can contain duplicates, find the first occurrence of a target element T
- Given a sorted array that can contain duplicates, find the last occurrence of a target element T
- Given a sorted array A and a target T. Return the first index where it would be placed if inserted in order
- Given a sorted array A and a target T. Return the last index where it would be placed if inserted in order
- Given a sorted array A and a target T, find the target. If the target is not in the array, find the smallest number closest to the target
- Given a sorted array A and a target T, find the target. If the target is not in the array, find the largest number in the order closest to the target
- Given a sorted array A that has been rotated in a cycle, find the smallest element of the array in O(log(n)) time
- Given a sorted array A that has been rotated in a cycle, find the largest element of the array in O(log(n)) time
- Given a sorted array whose length is not known, perform binary search for a target T. Do the search in O(log(n)) time
- Find the square root of an integer X. For example, squareRoot(4) = 2. It is ok to find the integer floor of the square root. So squareRoot(5) or squareRoot(8) can also return 2. squareRoot(9) will return 3.
- Find the peak: A peak element in array A is an A[i] where its adjacent elements are less than A[i]. So, A[i - 1] < A[i] and A[i + 1] < A[i].
- Memoization
- Auxiliary Buffers
- Backtracking
- Append function
- Find the median of a sorted linked list
- Delete nodes
- Linked Hash Table
- Stacks as restriction
- Stack with max
- Expression and evaluation
- Sliding window
- Queue with Max
- Dynamic Programming
- Max diff
- 2D arrays
- Add/Multiply
- Special Tricks
- Hash Table and Hash
- Hash functions
- String search
- Depth first search
- Breadth first search
- Topological sort recursive
- Topological sort iterative
- Least number of semesters required to complete a list of courses with prerequisites
- Diameter of a directed graph, or the longest path of a directed graph
- Skyline problem
- Selection algorithm
- Merge sort
- Quick sort
- Stability and large data
- Special tricks
- Find even occurrences in an array with odd numbers
- Detecting cycles
- Bipartite Graph
- Connected Components
- In-order traversal
- Pre-order traversal
- Post-order traversal
- In-order traversal without recursion
- Height of a binary tree (Top to Bottom Approach)
- Height of a binary tree (Bottom to Top Approach)
- Check if a binary tree is balanced or not
- Find the diameter of a binary tree
- LCA in a binary tree with parent pointers
- LCA in a binary tree without parent pointers
- Given a binary tree find all paths to children from root node
- Build binary tree from in-order and pre-order traversals
- Build binary tree from in-order and post-order traversals
- Given a Binary Tree, determine if it is a Binary Search Tree (BST)
- Implement add operation in a BST
- Implement operations to find a node in a BST
- Implement the Delete operation in a BST
- First occurrence of the number X in in-order traversal of BST.
- Successor of a node in BST
- LCA in a binary search tree
- Building Balanced BST from a sorted array
- Building Balanced BST from a sorted linked list
- Trie
- Search n/2 majority
- Search n/k majority