Just some practice for interviews and whatnot.

practice.rb

#!/usr/bin/env ruby
# Just some practice for interviews and whatnot.
require 'set'


class Array
  # Shift each element in the array by N positions.
  # Use a negative N to rotate left.
  def rotate_by n
    len = length
    n  %= len
    n   = len + n if n < 0
    n   = len - n
    fst = slice n, len
    snd = slice 0, n
    return fst + snd
  end


  # If the array contains only sub-arrays of
  # equivalent length then convert the array to
  # a hash. Returns nil otherwise.
  def to_hash
    raise ArgumentError unless map(&:length).reduce(true) do |memo, len|
      memo && 2 == len
    end
    return reduce({}) do |result, field|
      key, value = field
      result[key] = value
      result
    end
  end


  # Find the smallest element of a ciruclar array in O(n).
  def circ_min
    len = length
    0.upto(len) do |i|
      j = i + 1
      j = 0 if j >= len
      return self[j] if self[i] > self[j]
    end
    return self[0]
  end


  # Given an array of integers, compute the sub-
  # array with the largest sum.
  def lsum
    len = length
    subsets = Set.new
    0.upto(len) do |i|
      i.upto(len) do |j|
        subsets.add slice(i, j - i + 1)
      end
    end
    
    largest_sum   = -1.0/0
    subset_of_sum = nil
    subsets.map do |subset|
      if subset.length > 0
        sum = subset.reduce(:+)
        if sum > largest_sum
          largest_sum = sum
          subset_of_sum = subset
        end
      end
    end
    return subset_of_sum
  end
end



# Generate a multiplication table with
# N > 0 rows and M > 0 columns.
def multiplication_table n, m
  result = []
  len    = (n*m).to_s.length
  1.upto(n) do |i|
    row = 1.upto(m).map { |j| i * j }
    result << " " + row.map do |x|
      x.to_s.center len
    end.join(" | ") + " "
  end
  return result.join("\n" + ("-" * ((len + 3) * m - 1)) + "\n")
end



# Find the Nth Fibonacci number.
class Fib
  attr_reader :value
  @@memo = { 1 => 1, 2 => 1 }

  def initialize n
    raise ArgumentError if n < 0
    if @@memo.include? n ; @value = @@memo[n]
    else
      @value    = Fib.new(n-1).value + Fib.new(n-2).value
      @@length  = n + 1
      @@memo[n] = @value
    end
  end
end

def nfib n ; Fib.new(n).value ; end



class String
  # Find the index of the first occurence of
  # STR in a string. Return nil on failure.
  def substr str
    len = str.length
    0.upto(length) do |i|
      return i if slice(i, len) == str
    end
    return nil
  end

  # Return the original string with all the
  # characters not in STR removed.
  def filter_with str
    chars = Set.new str.split('')
    return self.split('').keep_if do |c|
      !chars.include?(c)
    end.join('')
  end
end



# Efficiently find all routes from SRC to DST
# given a map of SRCs and DSTs (as a Ruby hash).
def find_routes map, src, dst, visited=Set.new
  return Set.new if src == dst
  return Set.new if visited.include? src
  nxt = map[src] rescue nil
  return Set.new if nxt.nil? or nxt.empty?
  visited.add src

  routes = Set.new
  routes.add([src, dst]) if nxt.include? dst
  partial_routes = nxt.map do |nxt_src|
    nxt_routes = find_routes(map, nxt_src, dst, visited.dup)
    nxt_routes
  end.reduce(:+)

  return routes | partial_routes.map do |partial_route|
    [src] + partial_route
  end
end



class BinaryTree
  attr_reader :value, :left, :right, :is_search_tree

  def initialize value, left=nil, right=nil
    @value = value
    @left  = left
    @right = right
  end

  # Decide whether a binary tree is also a search tree.
  def is_search_tree?
    return is_search_tree unless is_search_tree.nil?
    left_okay, right_okay = false

    if left.nil?
      left_okay = true
    elsif left.left.nil?
      left_okay = left.value < value
    else
      left_okay = left.is_search_tree?
    end

    if right.nil?
      right_okay = true
    elsif right.right.nil?
      right_okay = right.value > value
    else
      right_okay = right.is_search_tree?
    end

    is_search_tree = left_okay && right_okay
  end

  # Binary search algorithm.
  def search term
    raise ArgumentError unless is_search_tree?
    return self if term == value
    if term < value and not left.nil?
      return left.search(term)
    elsif not right.nil?
      return right.search(term)
    end
    return nil
  end
end



class Factorization
  @@memo = {}

  attr_reader :value, :factors, :prime

  def prime? ; prime.nil? ? @prime = factors.length <= 2 : prime ; end

  def initialize n
    raise ArgumentError unless n > 0
    @value = n

    unless @@memo.has_key? n
      candidates = (2..Math.sqrt(n).floor).to_a
      candidates.select! { |c| n % c == 0 }

      if candidates.empty? ; candidates = [1, n]
      else
        left  = Factorization.new(candidates.first).factors
        right = Factorization.new(n / candidates.first).factors
        candidates = (left + right).uniq.select do |m|
          Factorization.new(m).prime?
        end
      end

      @@memo[n] = candidates
    end

    @factors = @@memo[n]
  end

  def to_s ; @factors.inspect ; end
end



class SearchTree
  attr_reader :term, :value, :children

  def initialize term, value=nil, children=Set.new
    @term     = term
    @value    = value
    @children = children
  end

  def insert child
    SearchTree.new(@term, @value, @children.add(child))
  end

  # Depth-first search.
  def dfs term
    return self.value if term == @term
    children.each do |child|
      result = child.dfs(term)
      return result unless result.nil?
    end ; return nil
  end

  # Breadth-first search.
  def bfs term
    queue = [self]
    until queue.empty?
      st = queue.shift
      return st.value if st.term == term
      st.children.map { |c| queue.push c }
    end ; return nil
  end
end



class Array
  # Swap a binary array if the first element is smaller.
  def bswap
    x, y = self
    x, y = y, x if x > y
    [x, y]
  end

  # Merge a sorted array with another sorted array.
  def merge b
    a = self
    result = []
    until a.empty? || b.empty?
      x = a.shift
      y = b.shift
      if x < y
        result << x
        b.unshift(y)
      else
        result << y
        a.unshift(x)
      end
    end

    result.concat(a).concat(b)
  end


  def swap_sort
    len = length
    result = self
    (len-1).times do |i|
      (len-1).times do |j|
        if result[j] > result[j+1]
          result[j], result[j+1] = result[j+1], result[j]
        end
      end
    end
    return result
  end


  def merge_sort
    len   = length
    idx   = (len / 2).floor
    left  = slice(0, idx)
    right = slice(idx, len)
    if left.length == 2    ; left  = left.bswap
    elsif left.length > 1  ; left  = left.merge_sort
    end
    if right.length == 2   ; right = right.bswap
    elsif right.length > 1 ; right = right.merge_sort
    end
    return left.merge(right)
  end


  def quick_sort
    len = self.length
    return self if len <= 1
    return self.bswap if len == 2

    pidx  = rand(len - 2) + 1
    left  = slice 0, pidx
    pivot = slice(pidx, 1).first
    right = slice(pidx + 1, len)

    less, greater = [], []
    left.concat(right).each do |m|
      if m <= pivot ; less << m
      else ; greater << m
      end
    end

    less    = less.quick_sort
    greater = greater.quick_sort
    return less.push(pivot).concat(greater)
  end
end



# Pascal's Triangle
def prows n
  raise ArgumentError if n < 1
  return [[1], [1,1]] if n == 1
  rows = prows(n-1)
  lrow = rows.last
  res  = []
  (lrow.length - 1).times do |i|
    res << lrow[i] + lrow[i+1]
  end
  return rows << res.unshift(1).push(1)
end


def pascals_triangle n
  rows    = prows n
  max     = rows.last.max
  nwidth  = max.to_s.length + 2
  nwidth += 1 unless nwidth % 2
  rows.map! do |row|
    row.map { |m| m.to_s.center nwidth }.join
  end
  lwidth = rows.last.length
  return rows.map { |row| row.center lwidth }.join("\n")
end



################################################
#      I don't always test, but when I do      #
#       I usually use a lot of printfs.        #
################################################

l, s = [1,2,3,4,5,6], -2

puts "%s.rotate_by(%d) => %s" % [l, s, l.rotate_by(s).inspect]

l = [['a', [1,2,3]], ['b', 2], ['c', nil], ['d', "hey there!"]]

puts "%s.to_hash =>\n  %s" % [l, l.to_hash]

l = [5, 10, -1, 3, 4]

puts "%s.circ_min => %d" % [l, l.circ_min]

s = 101

puts 'nfib(%d) => %d' % [s, nfib(s)]

s, t = 6, 6

puts "multiplication_table(%d,%d) =>\n%s" % [s, t, multiplication_table(s,t)]

l = [1,-2,4,-2,3,-1,2]

puts "%s.lsum => %s" % [l, l.lsum.inspect]

s, t = "asadface", "fa"

puts '"%s".substr("%s") => %d' % [s, t, s.substr(t)]

s, t = "hello, world!", "lam"

puts '"%s".filter_with("%s") => "%s"' % \
  [s, t, s.filter_with(t)]

s, t = 'Seattle', 'Florida'

puts "find_routes('%s', '%s') =>\n  %s" % [s, t,
  find_routes({
    'Seattle' => ['LA', 'Florida'],
    'LA'      => ['Florida', 'Maine'],
    'Florida' => ['Seattle', 'LA'],
    'Maine'   => ['Seattle', 'Florida']
  }, s, t).to_a.inspect]

leftLR = BinaryTree.new(0)
leftL  = BinaryTree.new(-1, nil, leftLR)
leftR  = BinaryTree.new(7)
left   = BinaryTree.new(5, leftL, leftR)
rightL = BinaryTree.new(13)
rightR = BinaryTree.new(17)
right  = BinaryTree.new(15, rightL, rightR)
root   = BinaryTree.new(10, left, right)

s, t = -1, -10
puts "binary_search(%d) =>\n  %s" % [s, root.search(s).inspect]
puts "binary_search(%d) => %s" % [t, root.search(t).inspect]

s = 43
puts "factor(%d) => %s" % [nfib(s), Factorization.new(nfib(s))]

hey = SearchTree.new('hey', 1)
ho  = SearchTree.new('ho',  2)
hi  = SearchTree.new('hi',  3)
foo = SearchTree.new('foo', 4)
bar = SearchTree.new('bar', 5)
ho  = ho.insert(foo)
hi  = hi.insert(bar)
hey = hey.insert(ho)
hey = hey.insert(hi)

s, t = 'bar', 'baz'
puts "bfs('%s') => %s" % [s, hey.bfs(s).inspect]
puts "bfs('%s') => %s" % [t, hey.bfs(t).inspect]

s, t = 'foo', 'fum'
puts "dfs('%s') => %s" % [s, hey.dfs(s).inspect]
puts "dfs('%s') => %s" % [t, hey.dfs(t).inspect]

l = 5.downto(-5).to_a

puts "swap_sort(%s)  => %s" % [l, l.swap_sort]

puts "merge_sort(%s) => %s" % [l, l.merge_sort]

puts "quick_sort(%s) => %s" % [l, l.quick_sort]

s = 10
puts "pascals_triangle(%d) =>\n%s" % [s, pascals_triangle(s)]