Algorithms in Java

This repository contains various algorithm and data structure implementations in Java 8.

Steps

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:

Arrays and Strings I

• 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

Subarray Problems

• 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.

Binary Search

• 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].

Recursion & Backtracking

• Memoization
• Auxiliary Buffers
• Backtracking

Linked List

• Append function
• Find the median of a sorted linked list
• Delete nodes
• Linked Hash Table

Stack

• Stacks as restriction
• Stack with max
• Expression and evaluation

Queue

• Sliding window
• Queue with Max
• Dynamic Programming

Arrays and Strings II

• Max diff
• 2D arrays

Arrays and Strings III

• Add/Multiply
• Special Tricks

Hashtable

• Hash Table and Hash
• Hash functions
• String search

Graph I

• 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

Linesweep

• Skyline problem

Heaps

Sorting

• Selection algorithm
• Merge sort
• Quick sort
• Stability and large data
• Special tricks

Bit manipulation

• Find even occurrences in an array with odd numbers

Graph II

• Detecting cycles
• Bipartite Graph
• Connected Components

Binary Trees

• 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

Binary Search Tree

• 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

Majority Search

• Search n/2 majority
• Search n/k majority