Algorithms and Data structures

find_number.rb

# complexity O(log N)


def find_number(numbers, find_number)

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

    loop do
        puts "#{first}, #{middle}, #{last}"
        if find_number == numbers[middle]
            return middle
        elsif find_number < numbers[middle]
            last = middle
            middle = (last + first) / 2
        elsif find_number > numbers[middle]
            first = middle
            middle = (last + first) / 2
        elsif numbers[last] == numbers[first]
            return nil
        end

    end

    return nil
end

find_pairs.rb

# complexity O(N^2)
# memory O(1)

def find_pairs(numbers, sum)
    results = []

    numbers.each do |number1|
        numbers.each do |number2|
            if number1 + number2 == sum
                results << [number1, number2]
            end
        end
    end

    results
end



# complexity O(N)
# memory O(N)

def find_pairs(numbers, sum)
    results = []

    hash = Hash.new { false }
    numbers.each do |number|
        hash[number] = true
    end

    numbers.each do |number|
        if hash[sum-number] == true
            results << [number, sum-number]
        end
    end


    results
end

palindrome.rb

# finds all palindromes within a word
# complexity O(N^2)

def find_palindromes(word)

    pals = []
    word.chars.each_with_index do |letter, x|

        if word[x - 1] == word[x]
            i = x - 1
            j = x
        elsif word[x - 1] == word[x+1]
            i = x - 1
            j = x + 1
        else
            puts "#{x}"
            next
        end
        puts "#{i}, #{j}"

        while word[i] == word[j]
            i -= 1
            j += 1
        end
        pals << word[i+1..j-1]
    end
    pals
end

rhyme.rb

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

    rhymes = Hash.new { [] }
    most_common = ''

    words.each_line do |word|
        word = word.strip
        rhyme = word[-2..-1]
        rhymes[rhyme] <<= word

        if rhymes[rhyme].size > rhymes[most_common].size
            most_common = rhyme
        end
    end

    return [most_common, rhymes[most_common]]
end