Implement a method for order_vowel_words

Question

I go over some of the many coding related issues. I was wondering how to implement the order_vowel words method. I am working on an algorithmic issue to implement this method for understanding the algorithm. I have the following:

This method takes a string of lowercase words and returns a string containing only words containing all their vowels (excluding "y") in alphabetical order. Vowels can be repeated ( "afoot" is an ordered vowel)

 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 runtime analysis for this?

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

I appreciate your explanation for this. thanks.

Answer 1

This method is short and should be readable enough:

 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 may not be very efficient to sort the array to test it already sorted, so here is an alternative:

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

Using this method, all complexity should be O(n) , n is the number of characters in str .

Complexity could not be better, because the entire line must be analyzed at least once to find vowels. However, there may be faster implementations.

Answer 2

It seems you are just using the solution provided by App Academy for this question. In preparing for these interview questions, it is important that you try to solve them all yourself - they will not ask you these exact questions, but variants of the same logic (breaking down data structures, applying some methods to them and comparing results or creating new answers to basis of input.)

So, if you are serious about the application, do not look at the solutions. I also recommend finding a mentor.

Now, to your question.

 require 'benchmark' 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 puts Benchmark.measure {ordered_vowel_words("amends")} puts Benchmark.measure {ordered_vowel_words("complicated")} puts Benchmark.measure {ordered_vowel_words("afoot")} puts Benchmark.measure {ordered_vowel_words("ham")} puts Benchmark.measure {ordered_vowel_words("crypt")} puts Benchmark.measure {ordered_vowel_words("o")} puts Benchmark.measure {ordered_vowel_words("tamely")} 

See here a few simple tools for comparison: https://ruby-doc.org/stdlib-1.9.3/libdoc/benchmark/rdoc/Benchmark.html