Skip to content

Instantly share code, notes, and snippets.

@mayfer
Created February 21, 2014 20:29
Show Gist options
  • Save mayfer/9142794 to your computer and use it in GitHub Desktop.
Save mayfer/9142794 to your computer and use it in GitHub Desktop.
Problem solving and runtime complexity exercises
# given an array of integers, find the largest value
def find_largest(numbers)
# initialize our "largest number" to the first number in the array
# because it is the largest so far
largest = numbers[0]
# looping over each number once
numbers.each do |i|
if i > largest
# overwriting the largest if it's bigger as we go
largest = i
end
end
# now that we have checked each number, the variable "largest" will indeed
# contain the largest number
largest
end
# given a word, find the number of doubled up letters
def find_num_doubles(word)
# initializing to nil guarantees that no letter will equal "last_letter" at first
last_letter = nil
# initialize our number of doubles to zero for obvious reasons
double_count = 0
# iterate over each character in the word
word.chars.each do |x|
# if the previous letter equals the current one, we have a double.
if last_letter == x
double_count += 1
end
# set our current letter to the last_letter, such that the next iteration
# of the loop can check it for equality
last_letter = x
end
double_count
end
# find the most frequently occuring letter in the text
def find_most_frequent(text)
# initialize a hash table where the default value of keys that are
# not created yet will be zero
letter_hash = Hash.new(0)
# iterate over each letter
text.chars.each do |letter|
# the key in the hash is our letter.
# we know that the counts will start at zero, so we can safely increment by 1
letter_hash[letter] += 1
end
# some ruby magic to return the key (letter) that has the largest value
letter_hash.max_by{|k,v| v}[0]
end
# find all pairs that add up to 100 - TAKE 1
# complexity O(n^2) where n is the number of integers in our input array
def find_pairs(numbers, sum)
pairs = []
numbers.each_with_index do |number, index|
numbers.each_with_index do |number2, index2|
if index != index2 && number + number2 == 100
pairs << [number, number2]
end
end
end
pairs
end
# find all pairs that add up to 100 - TAKE 2
# complexity O(n) where n is the size of input - More optimal
def find_pairs(numbers)
num_pairs = 0
pairs_hash = {}
pears = [] # hhehehe
numbers.each do |number|
# if the current number is the pair of a previous number that was iterated over,
# we know that this is the second value of a valid pair that exists.
if pairs_hash.has_key?(number)
pears << [number, 100-number]
end
# for the current number, we can KNOW what the pair should be by subtracting it
# from our sum. we then set this value as a key in a hash, so we can later
# check to see if the pair we're looking for exists earlier in the array
pairs_hash[sum-number] = number
end
pears
end
# find the word with most number of anagrams in the english dictionary
def find_word_with_most_anagrams
# open text file
words = File.open('/usr/share/dict/words').read
# just an empty hash. missing keys default to nil.
hashes = {}
# just in case there are no anagrams at all
most_signature = ''
# this keeps track of the most number of anagrams we have seen so far
most = 0
# each line in text file is an individual word
words.each_line do |word|
# remove whitespace from beginning and end of word (spaces/newlines)
word = word.strip.downcase
# make a signature of the word by sorting its letters
# all anagrams will have matching signatures
signature = word.chars.sort.join('')
# initialize our place in the hash to an empty array
if hashes[signature] == nil
hashes[signature] = []
end
# add our current word into the array of anagrams we have for this signature
hashes[signature] << word
# if this word has more anagrams than the largest number we've come accross so far,
# keep track of which anagram it is
if hashes[signature].length >= most
most_signature = signature
most = hashes[signature].length
end
end
# donesies
return hashes[most_signature]
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment