Algorithms and Data Structures implemented in Java

Overview

Java : Algorithms and Data Structure alt tag

The algorithms and data structures are implemented in Java.

This is a collection of algorithms and data structures I've implemented in my academic and professional life. The code isn't optimized but is written to be correct and readable. The algorithms and data structures are tested and, unless noted, believed to be correct.

Created by Justin Wetherell

Support me with a donation

Donate to this project

What's been implemented:

Table of Contents

Data Structures

Mathematics

Numbers

  • Integers
    • to binary String
      • using divide and modulus
      • using right shift and modulus
      • using BigDecimal
      • using divide and double
    • is a power of 2
      • using a loop
      • using recursion
      • using logarithm
      • using bits
    • to English (e.g. 1 would return "one")
  • Longs
    • to binary String
      • using divide and modulus
      • using right shift and modulus
      • using BigDecimal
  • Complex
    • addition
    • subtraction
    • multiplication
    • absolute value
    • polar value

Graphs

Search

Sequences

Sorts

String Functions

String Functions

  • Reverse characters in a string
    • using additional storage (a String or StringBuilder)
    • using in-place swaps
    • using in-place XOR
  • Reverse words in a string
    • using char swaps and additional storage (a StringBuilder)
    • using StringTokenizer and additional (a String)
    • using split() method and additional storage (a StringBuilder and String[])
    • using in-place swaps
  • Is Palindrome
    • using additional storage (a StringBuilder)
    • using in-place symetric element compares
  • Subsets of characters in a String
  • Edit (Levenshtein) Distance of two Strings (Recursive, Iterative)

Manacher's algorithm (Find the longest Palindrome)

KMP (Knuth–Morris–Pratt) Algorithm - Length of maximal prefix-suffix for each prefix

String rotations

  • Find in lexicographically minimal string rotation
  • Find in lexicographically maximal string rotation
Comments
  • Inconsistent equals/hashCode methods

    Inconsistent equals/hashCode methods

    For instance, the class Graph.CostPathPair is not correct:

    import java.util.HashSet;
    import org.junit.Test;
    import com.jwetherell.algorithms.data_structures.Graph;
    import com.jwetherell.algorithms.data_structures.Graph.*;
    
    public class GraphTest {
        @Test
        public void testCostVertexPair() {
            HashSet<Edge<Integer>> s1 = new HashSet<Graph.Edge<Integer>>();
            s1.add(new Edge<Integer>(1, new Vertex<Integer>(10), new Vertex<Integer>(20)));
            s1.add(new Edge<Integer>(2, new Vertex<Integer>(20), new Vertex<Integer>(30)));
            Graph.CostPathPair<Integer> p1 = new Graph.CostPathPair<Integer>(1, s1);
    
            HashSet<Edge<Integer>> s2 = new HashSet<Graph.Edge<Integer>>();
            s2.add(new Edge<Integer>(2, new Vertex<Integer>(10), new Vertex<Integer>(20)));
            s2.add(new Edge<Integer>(1, new Vertex<Integer>(20), new Vertex<Integer>(30)));
            Graph.CostPathPair<Integer> p2 = new Graph.CostPathPair<Integer>(1, s2);
    
            System.err.println(p1.equals(p2)); // => false
            System.err.println(p2.equals(p1)); // => false
            System.err.println(p1.hashCode()); // 62
            System.err.println(p2.hashCode()); // 62
        }
    }
    

    (question arising while testing: Shouldn't the class Graph be moved in the graph package?)

    opened by jolkdarr 9
  • Added PR template in repo

    Added PR template in repo

    Issue fixing #40 @phishman3579 Please review it and come back. Do you like it? What are the suggestions? Is it worth? I think you got the structure if you want to implement then go for it.

    I do have a suggestion can we remove default folder created by IDE because its little bit confused and also giving path code take too much string.

    opened by jitendra3109 6
  • Incorrect results for Fibonacci sequences

    Incorrect results for Fibonacci sequences

    Incorrect value is returrned for "big" n values (n > 92) because of the encoding limitation of the used primary type (long). Either an IllegalArgumentException should be raised or a zero value returned for all algorithms.

    Fibonacci sequence tests

    algorithm: FibonacciSequenceUsingLoop

    f(25) =                75025 [    4.157 µs]
    f(26) =               121393 [    5.207 µs]
    f(27) =               196418 [    5.023 µs]
    ...
    f(90) =  2880067194370816120 [   18.408 µs]
    f(91) =  4660046610375530309 [   18.718 µs]
    f(92) =  7540113804746346429 [   18.741 µs]
    f(93) = -6246583658587674878 [   19.363 µs] KO
    f(94) =  1293530146158671551 [   18.479 µs] KO
    f(95) = -4953053512429003327 [   19.053 µs] KO
    

    algorithm: FibonacciSequenceUsingRecursion

    f(25) =                75025 [    1.581 ms]
    f(26) =               121393 [    2.671 ms]
    f(27) =               196418 [    4.328 ms]
    f(28) =               317811 [    7.032 ms]
    f(29) =               514229 [    9.708 ms]
    f(30) =               832040 [   15.432 ms]
    f(31) =              1346269 [   24.880 ms]
    f(32) =              2178309     time out
    

    algorithm: FibonacciSequenceUsingMatrixMultiplication

    f(25) =                75025 [   23.856 µs]
    f(26) =               121393 [   29.692 µs]
    f(27) =               196418 [   30.164 µs]
    ...
    f(90) =  2880067194370816120 [   88.054 µs]
    f(91) =  4660046610375530309 [   88.248 µs]
    f(92) =  7540113804746346429 [   89.123 µs]
    f(93) = -6246583658587674878 [  114.994 µs] KO
    f(94) =  1293530146158671551 [   91.361 µs] KO
    f(95) = -4953053512429003327 [   92.010 µs] KO
    

    algorithm: FibonacciSequenceUsingBinetsFormula

    f(25) =                75025 [    5.359 µs]
    f(26) =               121393 [    4.295 µs]
    f(27) =               196418 [    4.476 µs]
    ...
    f(90) =  2880067194370825216 [    3.210 µs]
    f(91) =  4660046610375544832 [    3.850 µs]
    f(92) =  7540113804746369024 [    3.288 µs]
    f(93) =  9223372036854775807 [    3.637 µs] KO
    f(94) =  9223372036854775807 [    3.654 µs] KO
    f(95) =  9223372036854775807 [    3.752 µs] KO
    
    opened by jolkdarr 5
  • BinaryHeapArray::clear function is broken

    BinaryHeapArray::clear function is broken

    Here's a custom test case written:

    BinaryHeap.BinaryHeapArray<Integer> aHeapMax = new BinaryHeap.BinaryHeapArray<Integer>(BinaryHeap.Type.MAX);
    aHeapMax.add(10);
    aHeapMax.add(11);
    aHeapMax.clear();
    assertNull(aHeapMax.getHeadValue()); // we expect null here
    

    We expect that the head of BinaryHeapArray becomes null on clear, but it does not, and BinaryHeapArray::getHeadValue and BinaryHeapArray::toString functions return the first value of the heap array despite asking for a clear.

    opened by lkn2993 3
  • Adding cheat-sheet of Intellij

    Adding cheat-sheet of Intellij

    By submitting this pull request I confirm I've read and complied with the below requirements.

    • [X] I have read the Contribution guidelines and I am confident that my PR reflects them.
    • [X] I have followed the coding guidelines for this project.
    • [X] My code follows the skeleton code structure.
    • [X] This pull request has a descriptive title. For example, Added {Algorithm/DS name} [{Language}], not Update README.md or Added new code.
    opened by jitendra3109 3
  • Readme.md file need to more better structure

    Readme.md file need to more better structure

    Hi!, I'm seeing here in readme file it has very good content but needs to more organize way. Likes :

             1. Contents list
            2.  Add relative link to direct code in readme.md
           3. Remove extra folder from repo
           4. Add contribute.md file
           5. Add PULL_REQUEST_TEMPLETE.md
           6. Add License 
    

    Would you like to help ? Yes! :)

    opened by jitendra3109 3
  • Added multiply using loop with string input.

    Added multiply using loop with string input.

    I added a new method to multiply two numbers with String input to Multiplication class which uses loop to multiply . This method uses the Chinese multiplication method of multiplying each number and then adding diagonals. Please merge my changes . If any change is needed just message me.

    opened by codechefamit 3
  • Adding a recursive range query method to the KdTree class.

    Adding a recursive range query method to the KdTree class.

    Adding a recursive range query. Two methods were added: searchNodeRangeRecursive and rangeRecursive. Given a node and a range (eps), the method range recursive executes searchNodeRangeRecursive, that returns all the nodes within an eps distance.

    opened by antoniocavalcante 3
  • Fix functions getHeadValue and toString to return null when size is 0 in binaryheap.java

    Fix functions getHeadValue and toString to return null when size is 0 in binaryheap.java

    Edited functions getHeadValue and toString in binaryHeapArray in file binaryheap.java to return null when size is 0

    EDIT: Also added corresponding test cases. Related to #102 , alternative proposal.

    • [x] I have read the Contribution guidelines and I am confident that my PR reflects them.
    • [x] I have followed the coding guidelines for this project.
    • [x] My code follows the skeleton code structure.
    • [x] This pull request has a descriptive title. For example, Added {Algorithm/DS name} [{Language}], not Update README.md or Added new code.
    opened by lkn2993 2
  • Bug in finding the

    Bug in finding the "Longest Increasing Subsequence"

    Last Testcase gets fail : 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 a longest increasing subsequence is 0, 2, 6, 9, 11, 15. or 0, 4, 6, 9, 11, 15 or 0, 2, 6, 9, 13, 15 or 0, 4, 6, 9, 13, 15

    But it return wrong answer: 0, 1, 3, 7, 11, 15

    opened by Markandayan1518 2
  • Fixed problem with inserting element to arraylist on large index

    Fixed problem with inserting element to arraylist on large index

    Inserting element on position larger then size was causing exception - IMO it's counter intuitive because if we can insert element on position larger then size of list (list size + 1) then probably we should be able to insert it on any position.

    opened by SzymonStankiewicz 2
  • Report on possible code improvements applying design patterns

    Report on possible code improvements applying design patterns

    Hi, due to academic issues I have reviewed your code and I have detected possible design patterns that can be implemented in order to improve the appearance of the code.

    Strategy Pattern A new interface called "WithOrigin" is created which refers to methods specific to shortest path algorithms of a graph considering an initial vertex and an end. The Dijkstra and Bellman-Ford classes represent concrete classes that implement the interface described above. Each class will perform its own implementation of the methods provided by the interface. In addition, the pattern gives rise to a new class called "ShortestWay" that will represent a handler for these algorithms. It communicates directly with the client and provides it with a kind of facade (not considering the pattern) that allows to choose the algorithm of interest. image image image image

    The class diagram would be as follows:

    image

    Decorator Pattern For this solution an interface called Node was created that will be joined with the abstract class LinkedList with a composition relation of multiplicity 2. The concrete classes called SinglyNode and DoublyNode will implement the Node interface. It should be emphasized that with this solution the List file, original of the analyzed code is segregated into other classes. Thus, in order to provide greater modularity. image image image The ArrayList and LinkedList classes, including the latter's child classes, are separated into separate files. image image image LinkedList child classes. image image

    The class diagram would be as follows:

    image

    Iterator Pattern For this solution, an extra operation is added to the IGraph interface called createIterator() that will allow choosing the type of path of interest. An Iterator interface is added with the operations used by the traversal algorithms. The concrete classes BreadthFirst and DepthFirst implement this interface. image image Iterator interface. image Concrete classes that implement the interface. image image

    The class diagram would be as follows:

    image

    opened by santi0ne 0
  • Add files via upload

    Add files via upload

    By submitting this pull request I confirm I've read and complied with the below requirements.

    • [x] I have read the Contribution guidelines and I am confident that my PR reflects them.
    • [x] I have followed the coding guidelines for this project.
    • [x] My code follows the skeleton code structure.
    • [x] This pull request has a descriptive title. For example, Added {Algorithm/DS name} [{Language}], not Update README.md or Added new code.
    opened by Manas-Chamola 1
  • SYSC5807F_Assignment_AbhijeetsinhJadeja

    SYSC5807F_Assignment_AbhijeetsinhJadeja

    By submitting this pull request I confirm I've read and complied with the below requirements.

    • [x] I have read the Contribution guidelines and I am confident that my PR reflects them.
    • [x] I have followed the coding guidelines for this project.
    • [x] My code follows the skeleton code structure.
    • [x] This pull request has a descriptive title. For example, Added {Algorithm/DS name} [{Language}], not Update README.md or Added new code.
    opened by AbhijeetJadeja 0
  • 5807F Assignment

    5807F Assignment

    By submitting this pull request I confirm I've read and complied with the below requirements.

    • [ ] I have read the Contribution guidelines and I am confident that my PR reflects them.
    • [ ] I have followed the coding guidelines for this project.
    • [ ] My code follows the skeleton code structure.
    • [ ] This pull request has a descriptive title. For example, Added {Algorithm/DS name} [{Language}], not Update README.md or Added new code.
    opened by deep15499 0
  • Pull request Akhil_SYSC5807

    Pull request Akhil_SYSC5807

    By submitting this pull request I confirm I've read and complied with the below requirements.

    • [ x] I have read the Contribution guidelines and I am confident that my PR reflects them.
    • [x ] I have followed the coding guidelines for this project.
    • [x ] My code follows the skeleton code structure.
    • [ x] This pull request has a descriptive title. For example, Added {Algorithm/DS name} [{Language}], not Update README.md or Added new code.
    opened by akhilyengal 1
  • Feature/gargi

    Feature/gargi

    Gargi Sysc 5807

    By submitting this pull request I confirm I've read and complied with the below requirements.

    • [ ] I have read the Contribution guidelines and I am confident that my PR reflects them.
    • [ ] I have followed the coding guidelines for this project.
    • [ ] My code follows the skeleton code structure.
    • [ .] This pull request has a descriptive title. For example, Added {Algorithm/DS name} [{Language}], not Update README.md or Added new code.
    opened by gargi29 0
Owner
Justin Wetherell
Justin Wetherell
Design patterns implemented in Java

Design patterns implemented in Java Read in different language : CN, KR, FR, TR, AR Introduction Design patterns are the best formalized practices a p

Ilkka Seppälä 79k Jan 2, 2023
Castled is an open source reverse ETL solution that helps you to periodically sync the data in your warehouses and databases to sales, marketing, support or custom apps without any help from engineering teams

Open source reverse-ETL platform to operationalize your data warehouse Introduction Castled is a Reverse ETL solution which enables you to make the va

Castled 314 May 2, 2022
Spring Data Example Projects

Spring Data Examples This repository contains example projects for the different Spring Data modules to showcase the API and how to use the features p

Spring 4.7k Jan 4, 2023
MCQs and coding questions solutions of Object-Oriented Programming java of coding ninjas

cn-java-sols (⌐■_■) Link to This repository Other similar repository of my friend Link ?? enjoy having full marks ?? ?? now answers avaible up to Stri

Sanyam Mahajan 11 Dec 27, 2022
Repository for Bryn and Ethan's Java with MicroServices Batch

210607-FeederProgram This repository houses examples and environment setup for the Revature feeder program beginning on 6/7/2021 Environment Setup Gui

Bryn Portella 17 May 22, 2022
http://kodlama.io "Java & React Bootcamp" up to date Lectures and Homeworks.

Java & React Bootcamp (https://kodlama.io/) Lectures Lecture 1 intro Lecture 2 oopIntro homework Lecture 3 oopIntro2 inheritance inheritance2 homework

Karcan Ozbal 237 Dec 29, 2022
Modern Java - A Guide to Java 8

Modern Java - A Guide to Java 8 This article was originally posted on my blog. You should also read my Java 11 Tutorial (including new language and AP

Benjamin Winterberg 16.1k Dec 29, 2022
Fast and stable sort algorithm that uses O(1) memory. Public domain.

WikiSort WikiSort is an implementation of "block merge sort", which is a stable merge sort based on the work described in "Ratio based stable in-place

Mike McFadden 1.2k Jan 1, 2023
The quickstarts demonstrate JBoss EAP, Jakarta EE 8 and a few additional technologies. They provide small, specific, working examples that can be used as a reference for your own project.

shared-doc/attributes.adoc WildFly Quickstarts The quickstarts demonstrate Jakarta EE 8 and a few additional technologies from the WildFly stack. They

JBoss Developer 792 Dec 16, 2022
VnV Bootcamp for ITJuana documentation and other tools

From Zero to Hero VnV Bootcamp VnV Bootcamp for ITJuana pre-work, documentation and other tools Code created during bootcamp will be uploaded here so

null 3 Sep 6, 2021
100 Days of Code Learning program to keep a habit of coding daily and learn things at your own pace with help from our remote community.

100 Days of Code Learning program to keep a habit of coding daily and learn things at your own pace with help from our remote community.

Git Commit Show by Invide 41 Dec 30, 2022
Java EE 7 Samples

Java EE 7 Samples This workspace consists of Java EE 7 Samples and unit tests. They are categorized in different directories, one for each Technology/

JavaEE Samples 2.5k Dec 20, 2022
Solutions for some common algorithm problems written in Java.

Algorithms This repository contains my solution for common algorithms. I've created this repository to learn about algorithms and improve solutions to

Pedro Vicente Gómez Sánchez 2.8k Dec 30, 2022
Rework of html-java-dsl to work with newer Javas

java-html-dsl Example DSL for writing html in Java. Rework of benjiman/java-html-dsl to work with newer versions of Java This String doc = html(

Benji Weber 19 Jan 25, 2022
A toolchain for Minecraft: Java Edition that builds a workspace to interact with the game using the official mappings provided to the public by Mojang Studios.

VanillaGradle is a toolchain for Minecraft: Java Edition that provides a workspace to interact with the game using official mappings provided by Mojan

SpongePowered 75 Nov 22, 2022
Amazing Ruby's "Enumerable" ported to Java

Overview How to use? .all .any .none .select .map .count .reject .find How to contribute? Contributors Overview enumerable4j is a Ruby's well known En

Yurii Dubinka 30 Oct 28, 2022
Java 16 Features

Java 16 Features. Features are separated by package name.

Rahman Usta 9 Jan 7, 2022
Java Kampında derslerde yazılan projeler

nLayeredDemo JavaCampDay5Lesson https://www.youtube.com/watch?v=yaBPeS65vwM&ab_channel=EnginDemiro%C4%9F linkteki derste yapılan proje. Nortwind JavaC

Zeyneb Eda YILMAZ 10 Dec 14, 2021
Engin DEMIROG yotube java kamp HW

JavaBootCamp https://www.kodlama.io/courses/enrolled/1332369 Engin DEMIROG yotube javaBootCamp HW ve projeler Java & React Bootcamp (https://kodlama.i

Melik KARACA 8 Nov 13, 2022