Algorithms & Interview Questions

This repository contains:

• Common Algorithms that were implemented using Java
• Solutions to a lot of interview questions

Graph Algorithms & Solutions:

• Kruskal's Minimum Spanning Tree algorithm
• Prim's Minimum Spanning Tree algorithm
• Dijkstra's shortest path algorithm for directed graphs with non-negative weights
• Algorithm that solves the max-spacing k clustering problem: "Given a distance measure d and k, compute the k-clustering with maximum spacing"
• Algorithm that solves the interview question: "Design an efficient algorithm that takes as input a collection of equality and inequality constraints and decides whether the constraints can be satisfied simultaneously."
• Algorithm based on DFS that allows to iterate over a directed graph in different orders (preorder, postorder, reverse postorder)
• Algorithm based on DFS to determine whether a directed graph contains a cycle. It also returns the entire path from source vertex to the cycle end
• Algorithm to compute the topological ordering of a directed graph that is also a DAG
• Algorithm that solves the "All-Pair-Shortest Path Problem"

Sorting:

• Mergesort (with multiple improvements)
• Quicksort (with multiple improvements)
• Calculating the number of inversions
• Merging k sorted arrays in an efficient manner.

Stacks:

• An implementation to translate infix to postfix expressions
• An algorithm that checks whether a given string contains properly nested and balanced parentheses
• An algorithm that reverses a stack without using additional data structures. Interview question: "Reverse a stack without using extra space (recursion can be used)."
• Stack Sorter. Interview question "Sort a stack of numbers in descending order"

Some general algorithms and/or solutions:

• Knapsack problem
• Finding a missing integer. Interview question: "Given an input file with four billion non-negative integers, provide an algorithm to generate an integer which is not contained in the file.
  Assume that you have 1GB of memory available for this task."
• Computing largest sums
• Two-Sum and Three-Sum solver
• Levenshtein Distance
• An algorithm that checks whether a string is a palindrome
• An algorithm that computes the square root based on the binary search approach
• Different algorithms and approaches were implemented to generate all permutations of a given string
• and many more...

Searching:

• Different solutions to interview questions that relate to searching, such as
• Algorithm to find the first occurrence that is larger than k
• Algorithm to search a sorted array where A[i] = i
• Algorithm to search a sorted array of unknown length

Data Structures:

• A basic hash map that uses chaining for collision resolution
• A connected component finder
• Edge-weighted graph
• Graph
• Directed Graph
• Least-recently-used cache (LRU cache)
• MinHeap (MinPriorityQueue)
• MaxHeap (MaxPriorityQueue)
• Trie
• The union-find data structure
• A fenwick tree that supports point-queries and range updates in O(log n)
• A Segment tree that allows sum and update queries for a given range (class SegmentTreeForRangeSum).
• A Segment tree that allows max queries for a given range. It is also allowed to update a particular index position or it allows to update values within a given range (class SegmentTreeForRangeMax).
• A Segment tree that allows range updates and range max queries with lazy propagation (class SegmentTreeForRangeMaxLazyPropagation).
• A very simple Interval tree without rebalancing capabilities

Dynamic Programming

• Rod Cutting
• Subset Sum
• Min Coins
• Coin Change
• Binomial Coefficient
• Edit Distance
• Longest Increasing Subsequence
• Longest Common Subsequence