Skip to content

nastra/algorithms-java

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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

About

Common Algorithms written in Java

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages