Data Structures in Ruby

# Ruby arrays are dynamic, but can simulate fixed-size
nums = [10, 20, 30, 40, 50].freeze  # immutable reference

copy = nums.dup
copy[0] = 99                 # O(1) - direct index access
val = copy[2]                # O(1) - read by index

# Search
idx = copy.index(30)         # O(n) - linear search
has = copy.include?(40)      # O(n) - linear scan

# Sort
sorted = copy.sort           # O(n log n)
copy.sort!                   # O(n log n) - in-place

names = ["Alice", "Bob", "Charlie"]

names.push("Diana")             # O(1) amortized - append
names.insert(1, "Eve")          # O(n) - shifts elements
names.pop                       # O(1) - remove last
names.shift                     # O(n) - remove first

has = names.include?("Bob")     # O(n)
idx = names.index("Bob")        # O(n)

names.sort!                     # O(n log n) - in-place
squares = (0...10).map { |x| x * x }  # O(n) - functional transform

# Use Array as stack
stack = []

stack.push(10)            # O(1)
stack.push(20)
stack.push(30)

top = stack.last           # O(1) - peek -> 30
val = stack.pop            # O(1) - pop -> 30

# Interview pattern: valid parentheses
def valid?(s)
  pairs = { "(" => ")", "[" => "]", "{" => "}" }
  st = []
  s.each_char do |c|
    if pairs.key?(c) then st.push(pairs[c])
    elsif st.empty? || st.pop != c then return false
    end
  end
  st.empty?
end

require "thread"

# Thread::Queue for thread-safe queue
q = Thread::Queue.new
q.push("Task A")           # O(1) - enqueue
q.push("Task B")
q.push("Task C")

val = q.pop                # O(1) - dequeue (blocks if empty)
q.empty?                   # check if empty

# Interview pattern: BFS using Array
def bfs(root)
  queue = [root]
  until queue.empty?
    node = queue.shift                   # O(n) - dequeue
    print "#{node.val} "
    queue.push(node.left) if node.left
    queue.push(node.right) if node.right
  end
end

prices = { "apple" => 3, "banana" => 5 }

prices["cherry"] = 2                 # O(1) - add
prices["apple"] = 10                 # O(1) - update
has = prices.key?("banana")          # O(1)
prices.delete("cherry")              # O(1)

count = prices.fetch("mango", 0)    # O(1) - safe lookup with default

# Interview pattern: Two Sum
def two_sum(nums, target)
  seen = {}
  nums.each_with_index do |num, i|
    need = target - num
    return [seen[need], i] if seen.key?(need)  # O(1)
    seen[num] = i                               # O(1)
  end
  []
end

require "set"

s = Set[1, 2, 3, 4, 5]

s.add(6)                   # O(1)
s.delete(1)                # O(1)
has = s.include?(4)        # O(1) -> true

# Set operations
other = Set[4, 5, 6, 7]
s & other                  # intersection -> Set[4, 5, 6]
s | other                  # union
s - other                  # difference

# Interview pattern: contains duplicate
def contains_duplicate?(nums)
  nums.length != nums.to_set.length
end

# Ruby has no built-in linked list - manual implementation
ListNode = Struct.new(:val, :next)

head = ListNode.new(1, ListNode.new(2, ListNode.new(3)))

# Traverse - O(n)
curr = head
while curr
  print "#{curr.val} "
  curr = curr.next
end

# Interview pattern: reverse a linked list
def reverse(head)
  prev = nil
  curr = head
  while curr
    nxt = curr.next         # save
    curr.next = prev        # reverse link
    prev = curr; curr = nxt
  end
  prev  # O(n) time, O(1) space
end

require "set"

# SortedSet was removed in Ruby 3.0 - use sorted array pattern
sorted = [5, 3, 8, 1, 9].sort    # [1, 3, 5, 8, 9]

# Insert maintaining order - O(log n) search + O(n) shift
idx = sorted.bsearch_index { |x| x >= 4 } || sorted.length
sorted.insert(idx, 4)            # [1, 3, 4, 5, 8, 9]

sorted.delete(3)                 # O(n) - remove

min_val = sorted.first           # O(1) -> 1
max_val = sorted.last            # O(1) -> 9

# Range query
between = sorted.select { |x| x >= 4 && x <= 8 }  # [4, 5, 8]

# Ruby Hash preserves insertion order but not sorted order
sd = { "banana" => 2, "apple" => 5, "cherry" => 1 }

sd["date"] = 3                   # O(1) insert
val = sd["apple"]                # O(1) -> 5
sd.delete("cherry")              # O(1)

# Iterate in sorted key order - O(n log n)
sd.sort_by { |k, _| k }.each do |key, value|
  puts "#{key}: #{value}"
end
# apple: 5, banana: 2, date: 3

first_key = sd.keys.sort.first   # "apple"
last_key  = sd.keys.sort.last    # "date"

# No built-in heap - manual min-heap implementation
class MinHeap
  def initialize = @items = []

  def push(val)                        # O(log n)
    @items << val; sift_up(@items.size - 1)
  end

  def pop                              # O(log n)
    return nil if @items.empty?
    @items[0], @items[-1] = @items[-1], @items[0]
    min = @items.pop; sift_down(0)
    min
  end

  def peek = @items.first              # O(1)

  private

  def sift_up(i)
    while i > 0 && @items[i] < @items[(i - 1) / 2]
      @items[i], @items[(i - 1) / 2] = @items[(i - 1) / 2], @items[i]
      i = (i - 1) / 2
    end
  end

  def sift_down(i) = nil # heapify down
end

# gem install concurrent-ruby
require "concurrent-ruby"

cache = Concurrent::Map.new

cache["counter"] = 0                    # O(1) - thread-safe write
val = cache["counter"]                  # O(1) - thread-safe read

# Atomic compute-if-absent
cache.compute_if_absent("sessions") { 0 }  # factory called once

# Atomic update
cache.compute("counter") { |v| v + 1 }     # thread-safe increment

# Merge - update or insert
cache.merge_pair("hits", 1) { |old| old + 1 }

# Safe iteration (snapshot semantics)
cache.each_pair { |k, v| puts "#{k}: #{v}" }

# String slicing - returns a new string (copy)
data = "Hello, World!"
chunk = data[7, 5]              # "World" - O(k) copy
data[7, 5] = "Earth"           # mutate in place
puts data                       # "Hello, Earth!"

# Array slicing - returns a new array (copy)
nums = [10, 20, 30, 40, 50]
slice = nums[1, 3]             # [20, 30, 40] - O(k) copy

# String#byteslice for byte-level slicing
raw = "binary\x00data"
header = raw.byteslice(0, 6)   # O(k) - "binary"
body   = raw.byteslice(7..)    # O(k) - "data"

# IO::Buffer (Ruby 3.2+) for zero-copy memory views
buf = IO::Buffer.for(raw)      # wraps existing string memory