Algorithms & Data structures

anagram.rb

def find_most_anagram
    words = File.open('/usr/share/dict/words').read

    hash = Hash.new { [] }

    words.each_line do |word|
        word = word.strip.downcase
        signature = word.split('').sort.join('')

        hash[signature] <<= word
    end

    gets

    return hash.sort_by { |k, v| v.size }.reverse

end

index.rb

# linear, O(n) = n

def find_index(numbers, number)
    numbers.each_with_index do |n, i|
        if n == number
            return i
        end
    end

    return nil
end



# [ 3, 6, 200, 250, 251, 1000, 1000000, 1000001 ]

# O(n) = log n

def find_index_sorted(numbers, number)

    middle = numbers.size / 2
    first = 0
    last = numbers.size - 1

    while middle != last && middle != first

        if numbers[middle] == number
            return middle
        end

        puts "middle is #{middle}"
        puts "first is #{first}"
        puts "last is #{last}"
        gets

        if number > numbers[middle]
            first = middle
            middle += (last - middle) / 2
        else
            last = middle
            middle = middle / 2
        end
    end

    return nil
end

sum_pairs.rb

# Runtime O(n) = n^2
# Memory O(n) = 0

def find_sum_pairs(numbers, sum)
    numbers.each_with_index do |n, i|
        numbers.each_with_index do |m, j|
            if i != j && n + m == sum
                return i, j
            end
        end
    end

    return nil
end


# Runtime O(n) = n
# Memory O(n) = n

def find_sum_pairs_optimized(numbers, sum)
    hash = {}
    numbers.each do |n|
        target = sum - n
        hash[target] = n
    end

    numbers.each do |n|
        if hash.has_key?(n)
            return n, hash[n]
        end
    end
end