Mastering Unique Elements and Anagram Detection with Ruby Set

Welcome to our focused exploration of Ruby's Set and its remarkable applications in solving algorithmic challenges. In this lesson, "Mastering Unique Elements and Anagram Detection with Ruby Set", we'll delve into how this efficient data structure can be leveraged to address and solve various problems commonly encountered in technical interviews.

Picture this: you're given a vast list of words, and you must identify the final word that stands proudly solitary — the last word that is not repeated. Imagine sorting through a database of unique identifiers and finding one identifier towards the end of the list that is unlike any other.

The straightforward approach would be to examine each word in reverse, comparing it to every other word for uniqueness. This brute-force method would result in poor time complexity, O(n^2), which is less than ideal for large datasets.

Here is the naive approach in Ruby:

def find_last_unique_word_naive(words)
  words.reverse_each do |word|
    if words.count(word) == 1
      return word
    end
  end
  nil # In case no unique word is found
end

We can utilize two Set instances: words_set to maintain unique words and duplicates_set to keep track of duplicate words. By the end, we can remove all duplicated words from words_set to achieve our goal.

Create a Set instance to store unique words:

require 'set'
words_set = Set.new

Initialize another Set to monitor duplicates:

duplicates_set = Set.new

Iterate through the word array, filling words_set and duplicates_set:

words.each do |word|
  if words_set.include?(word)
    duplicates_set.add(word)
  else
    words_set.add(word)
  end
end

Use the subtract method from the Set API to remove all duplicated words from words_set:

words_set.subtract(duplicates_set)

Now, words_set only contains unique words. Find the last unique word by iterating through the original word list from the end:

last_unique_word = nil
words.reverse_each do |word|
  if words_set.include?(word)
    last_unique_word = word
    break
  end
end

And finally, return the last unique word:

def find_last_unique_word_efficient(words)
  require 'set'
  words_set = Set.new
  duplicates_set = Set.new

  words.each do |word|
    if words_set.include?(word)
      duplicates_set.add(word)
    else
      words_set.add(word)
    end
  end

  words_set.subtract(duplicates_set)

  last_unique_word = nil
  words.reverse_each do |word|
    if words_set.include?(word)
      last_unique_word = word
      break
    end
  end

  last_unique_word
end

This efficient approach, with a time complexity close to O(n), is far superior to the naive method and showcases your proficiency in solving algorithmic problems with Ruby's Set.