DataEngineer DataEngineer - 4 years ago 176
Ruby Question

Implement a method for ordered_vowel_words

I've been going over some of the many coding interview questions. I was wondering about implementing an ordered_vowel words method. I'm working on algorithm question to implement this method for purposes of the understanding algorithm. I have the below:

This method takes a string of lowercase words and returns a string with just the words containing all their vowels (excluding "y") in alphabetical order. Vowels may be repeated (

"afoot"
is an ordered vowel word)

def ordered_vowel_words(str)
words = str.split(" ")

ordered_vowel_words = words.select do |word|
ordered_vowel_word?(word)
end

ordered_vowel_words.join(" ")
end

def ordered_vowel_word?(word)
vowels = ["a", "e", "i", "o", "u"]

letters_arr = word.split("")
vowels_arr = letters_arr.select { |l| vowels.include?(l) }

(0...(vowels_arr.length - 1)).all? do |i|
vowels_arr[i] <= vowels_arr[i + 1]
end
end


I added the following test cases:

puts("\nTests for #ordered_vowel_words")
puts("===============================================")
puts "ordered_vowel_words(\"amends\") == \"amends\": " + (ordered_vowel_words("amends") == "amends").to_s
puts "ordered_vowel_words(\"complicated\") == \"\": " + (ordered_vowel_words("complicated") == "").to_s
puts "ordered_vowel_words(\"afoot\") == \"afoot\": " + (ordered_vowel_words("afoot") == "afoot").to_s
puts "ordered_vowel_words(\"ham\") == \"ham\": " + (ordered_vowel_words("ham") == "ham").to_s
puts "ordered_vowel_words(\"crypt\") == \"crypt\": " + (ordered_vowel_words("crypt") == "crypt").to_s
puts "ordered_vowel_words(\"o\") == \"o\": " + (ordered_vowel_words("o") == "o").to_s
puts "ordered_vowel_words(\"tamely\") == \"tamely\": " + (ordered_vowel_words("tamely") == "tamely").to_s


What is the runtime analysis for this one?

Why is it true that we can get O(m)O(m) runtime for mm function calls.

I appreciate your explanation for this. thank you.

Answer Source

This method is short and should be reasonably readable :

def ordered_vowel_words(str)
  str.split(" ").select{|w| ordered_vowel_word?(w) }.join(" ")
end

def ordered_vowel_word?(word)
  vowels = word.scan(/[aeiou]/)
  vowels == vowels.sort
end

It might not be very efficient to sort an array just to check it's already sorted, so here's an alternative :

def ordered_vowel_word?(word)
  word.scan(/[aeiou]/).each_cons(2).all?{ |vowel1, vowel2| vowel1 <= vowel2 }
end

With this method, the whole complexity should be O(n), n being the number of characters in str.

Complexity cannot be any better, because the whole string needs to be parsed at least once to find the vowels. There might be faster implementations, though.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download