Algorithms & Data Structures

A collection of algorithms & data structures implemented in Java.

Table of Contents

• Algorithms
  • QuickSelect
  • Shuffle
• Data Structures
  • WildcardMap
• Prerequisites
• Build
  • NVD API Key
• Code Quality
  • IDE Setup
• Contributing
• License

Algorithms

QuickSelect

Finds the k-th smallest element in an unordered array using the QuickSelect algorithm with Lomuto partitioning.

• Time complexity: O(n) average, O(n^2) worst case (mitigated by initial random shuffle)
• Space complexity: O(n) for the shuffled copy (original array is not modified)

Example:

Integer[] array = {3, 1, 4, 1, 5, 9, 2, 6};

// Find the 0th smallest (minimum)
Integer min = QuickSelect.quickSelect(array, 0);  // 1

// Find the 4th smallest element (zero-based)
Integer element = QuickSelect.quickSelect(array, 4);  // 4

Shuffle

Fisher-Yates shuffle implementations providing three variants:

• shuffle - Inside-out variant that returns a shuffled copy without modifying the original array
• shuffleForward - In-place forward variant, iterating first to last
• shuffleReverse - In-place Durstenfeld/Knuth variant, iterating last to first

Example:

Integer[] array = {1, 2, 3, 4, 5};

// Shuffled copy (original unchanged)
Integer[] shuffled = Shuffle.shuffle(array);

// In-place shuffle
Shuffle.shuffleForward(array);
Shuffle.shuffleReverse(array);

Data Structures

WildcardMap

A thread-safe map that supports wildcard queries on composite keys. Values are indexed by three string keys, and retrieval supports wildcards (null/empty/blank) for any key component.

Features:

• O(1) wildcard lookups
• Thread-safe using ConcurrentHashMap
• Automatic key trimming

Example:

WildcardMap map = new WildcardMap();
map.put("Honda", "Civic", "Blue", "VIN123");
map.put("Honda", "Accord", "Red", "VIN456");

map.get("Honda", "Civic", "Blue");  // ["VIN123"]
map.get("Honda", null, null);       // ["VIN123", "VIN456"] - wildcard query

Prerequisites

• JDK 25+
• Maven 3.9.12+

Build

./mvnw compile         # compile sources
./mvnw test            # run tests
./mvnw verify          # full build with all quality checks
./mvnw verify -Ppitest # full build with mutation testing

NVD API Key

OWASP Dependency-Check requires an NVD API key for fast vulnerability database updates. You can pass it via command line:

./mvnw verify -Dnvd.api.key=YOUR_KEY

Or configure it permanently in ~/.m2/settings.xml:

<settings>
  <profiles>
    <profile>
      <id>security-profile</id>
      <activation>
        <activeByDefault>true</activeByDefault>
      </activation>
      <properties>
        <nvd.api.key>YOUR_KEY</nvd.api.key>
      </properties>
    </profile>
  </profiles>
</settings>

Code Quality

All checks run automatically via GitHub Actions on every push and pull request. Mutation testing runs only on pull requests.

Tool	Purpose	Phase
Checkstyle	Google Java Style enforcement	validate
Maven Enforcer	Build constraints (Java/Maven versions, dependency rules)	validate
Sortpom	POM formatting and ordering	validate
Error Prone	Compile-time bug detection	compile
JaCoCo	Code coverage (80% line, 75% branch minimum)	verify
Maven Dependency	Unused/undeclared dependency analysis	verify
Maven Javadoc	Javadoc validation and completeness	verify
Modernizer	Legacy API detection	verify
OWASP Dependency-Check	CVE vulnerability scanning (CVSS >= 7 fails build)	verify
PMD	Static code analysis (unused code, dead code, complexity)	verify
Pitest	Mutation testing (80% threshold, profile: -Ppitest)	verify
SpotBugs	Static bug detection	verify

Dependabot is enabled for automated Maven and GitHub Actions dependency updates.

Coverage reports are uploaded to Codecov.

Reproducible builds are enabled via project.build.outputTimestamp.

IDE Setup

The project uses google-java-format for formatting. VSCode will recommend the extension automatically via .vscode/extensions.json.

Contributing

See CONTRIBUTING.md for setup instructions, including verified commit signing.

License

MIT