dsa-ruby

Data structures for coding interviews in Ruby. Provides the missing structures that Ruby's stdlib doesn't include but are essential for technical interviews.

Installation

gem "dsa-ruby"

Or install directly:

gem install dsa-ruby

Usage

require "dsa-ruby"

MinHeap / MaxHeap

heap = DSA::MinHeap.new
heap.push(5, 3, 7, 1)
heap.pop   # => 1
heap.peek  # => 3

max_heap = DSA::MaxHeap.new([5, 3, 7, 1])
max_heap.pop  # => 7

PriorityQueue

pq = DSA::PriorityQueue.new(type: :min)
pq.push("task_a", 3)
pq.push("task_b", 1)
pq.push("task_c", 2)

pq.pop  # => "task_b" (lowest priority first)

pq = DSA::PriorityQueue.new(type: :max)
pq.push("task_a", 3)
pq.push("task_b", 1)
pq.pop  # => "task_a" (highest priority first)

Deque

dq = DSA::Deque.new
dq.push_front(1).push_back(2)
dq.pop_front   # => 1
dq.pop_back    # => 2

# Enumerable support
dq.push_back(1, 2, 3)
dq.map { |x| x * 2 }  # => [2, 4, 6]

Trie

trie = DSA::Trie.new
trie.insert("apple")
trie.search("apple")     # => true
trie.search("app")       # => false
trie.starts_with("app")  # => true
trie.delete("apple")

UnionFind

uf = DSA::UnionFind.new(10)
uf.union(1, 2)
uf.union(2, 3)
uf.connected?(1, 3)  # => true
uf.count              # => 8 (started with 10, merged 2 pairs)

LinkedList

# Singly Linked List
list = DSA::LinkedList::Singly.new
list.push(1).push(2).push(3)
list.pop        # => 3
list.to_a       # => [2, 1]
list.reverse!
list.to_a       # => [1, 2]

# Doubly Linked List
dll = DSA::LinkedList::Doubly.new
dll.push_back(1).push_back(2).push_back(3)
dll.pop_front   # => 1
dll.pop_back    # => 3
dll.to_a        # => [2]

Stack

stack = DSA::Stack.new
stack.push(1).push(2).push(3)
stack.pop    # => 3
stack.peek   # => 2

Queue

queue = DSA::Queue.new
queue.enqueue("a").enqueue("b").enqueue("c")
queue.dequeue  # => "a"
queue.peek     # => "b"

BinarySearchTree

bst = DSA::BinarySearchTree.new
bst.insert(5).insert(3).insert(7).insert(1).insert(4)
bst.search(3)       # => true
bst.min             # => 1
bst.max             # => 7
bst.inorder         # => [1, 3, 4, 5, 7]
bst.preorder        # => [5, 3, 1, 4, 7]
bst.postorder       # => [1, 4, 3, 7, 5]
bst.delete(3)

API Reference

Stack

  • #push(val) — add to top (O(1))
  • #pop — remove and return top (O(1))
  • #peek — return top without removing (O(1))

Queue

  • #enqueue(val) — add to back
  • #dequeue — remove and return front
  • #peek — return front without removing

BinarySearchTree

  • #insert(val) — insert value (O(log n) avg)
  • #search(val) — check if value exists (boolean)
  • #delete(val) — remove value, returns true if deleted
  • #min / #max — return minimum/maximum value
  • #inorder / #preorder / #postorder — traversal arrays

Common Methods

All structures support:

  • #size — number of elements
  • #empty? — whether the structure is empty
  • #to_a — returns a defensive copy as an array

Heap (MinHeap, MaxHeap)

  • #push(val) — insert element (O(log n))
  • #pop — remove and return extremum (O(log n))
  • #peek — return extremum without removing (O(1))

PriorityQueue

  • #push(item, priority) — insert with priority
  • #pop — remove and return highest/lowest priority item
  • #peek — return top item without removing
  • #priority_peek — return top item's priority value

Deque

  • #push_front(val) / #push_back(val) — insert at either end
  • #pop_front / #pop_back — remove from either end
  • #front / #back — peek at either end
  • Includes Enumerable

Trie

  • #insert(word) — insert a word
  • #search(word) — exact word lookup
  • #starts_with(prefix) — prefix lookup
  • #delete(word) — remove a word

UnionFind

  • #find(x) — find root with path compression
  • #union(x, y) — merge sets, returns true if merged
  • #connected?(x, y) — check if in same set
  • #count — number of disjoint sets

LinkedList (Singly / Doubly)

  • #push(val) / #push_front(val) / #push_back(val) — insert
  • #pop / #pop_front / #pop_back — remove
  • #delete(val) — remove by value
  • #find(val) — find node by value
  • #peek / #front / #back — peek
  • #reverse! — reverse in-place (Singly only)
  • Includes Enumerable

Development

bundle install
bundle exec rspec

Release

Bump version, build gem, push to RubyGems, and create GitHub Release:

./release.sh patch   # 0.1.0 -> 0.1.1
./release.sh minor   # 0.1.0 -> 0.2.0
./release.sh major   # 0.1.0 -> 1.0.0

Requires: gh CLI authenticated, GEM_HOST_API_KEY environment variable set.

Using Makefile

make build      # Build the gem
make test       # Run tests
make install    # Build and install locally
make publish    # Build and push to rubygems.org
make release    # Full release workflow
make help       # Show all commands

License

MIT