Introduction

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.

Problem 1: Unique Echo

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.

Naive Approach

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:

Ruby
1def find_last_unique_word_naive(words) 2 words.reverse_each do |word| 3 if words.count(word) == 1 4 return word 5 end 6 end 7 nil # In case no unique word is found 8end
Efficient Approach

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:

Ruby
1require 'set' 2words_set = Set.new

Initialize another Set to monitor duplicates:

Ruby
1duplicates_set = Set.new

Iterate through the word array, filling words_set and duplicates_set:

Ruby
1words.each do |word| 2 if words_set.include?(word) 3 duplicates_set.add(word) 4 else 5 words_set.add(word) 6 end 7end

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

Ruby
1words_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:

Ruby
1last_unique_word = nil 2words.reverse_each do |word| 3 if words_set.include?(word) 4 last_unique_word = word 5 break 6 end 7end

And finally, return the last unique word:

Ruby
1def find_last_unique_word_efficient(words) 2 require 'set' 3 words_set = Set.new 4 duplicates_set = Set.new 5 6 words.each do |word| 7 if words_set.include?(word) 8 duplicates_set.add(word) 9 else 10 words_set.add(word) 11 end 12 end 13 14 words_set.subtract(duplicates_set) 15 16 last_unique_word = nil 17 words.reverse_each do |word| 18 if words_set.include?(word) 19 last_unique_word = word 20 break 21 end 22 end 23 24 last_unique_word 25end

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.

Problem 2: Anagram Matcher

Now, imagine a different scenario in which you have two arrays of strings, and your task is to find all the unique words from the first array that have an anagram in the second array. An anagram is a word or phrase formed by rearranging the letters of another word or phrase, such as forming "listen" from "silent".

Naive Approach

A basic approach would involve checking every word in the first array against every word in the second array by generating and comparing their sorted character strings. This results in an O(n^2) time complexity due to the pairwise comparison of words.

Here is the naive approach in Ruby:

Ruby
1def find_anagrams_naive(array1, array2) 2 result = [] 3 4 array1.each do |word1| 5 array2.each do |word2| 6 if word1.chars.sort == word2.chars.sort 7 result << word1 8 break 9 end 10 end 11 end 12 13 result.uniq # Ensure unique matches 14end
Efficient Approach

We'll create a unique signature for each word by sorting its characters and then compare these signatures for matches. We'll use a Set to store signatures for efficient access.

Construct a method to create sorted character signatures from the input string:

Ruby
1def sort_characters(word) 2 word.chars.sort.join 3end

Store these sorted characters from array2 in a Set for fast lookup:

Ruby
1sorted_words_in_array2 = Set.new 2array2.each do |word| 3 sorted_words_in_array2.add(sort_characters(word)) 4end

For each word in array1, check for its sorted signature in the Set and track the found anagrams:

Ruby
1anagrams_matched = Set.new 2result = [] 3array1.each do |word| 4 if sorted_words_in_array2.include?(sort_characters(word)) && !anagrams_matched.include?(word) 5 result << word 6 anagrams_matched.add(word) 7 end 8end

Our final step is to return the list of anagrams found:

Ruby
1def find_anagrams_efficient(array1, array2) 2 require 'set' 3 sorted_words_in_array2 = Set.new 4 array2.each do |word| 5 sorted_words_in_array2.add(sort_characters(word)) 6 end 7 8 anagrams_matched = Set.new 9 result = [] 10 array1.each do |word| 11 if sorted_words_in_array2.include?(sort_characters(word)) && !anagrams_matched.include?(word) 12 result << word 13 anagrams_matched.add(word) 14 end 15 end 16 17 result 18end

By utilizing Set in this manner, we achieve efficient anagram checking with reduced complexity, considering both the O(m log m) character sorting for each word and the O(n) comparison for n words.

Lesson Summary

In this lesson, we have utilized Ruby's Set to improve the efficiency of solving the "Unique Echo" and "Anagram Matcher" problems. These strategies help us manage complexity by leveraging the efficient operations of Set and maintaining the ability to efficiently manage unique collections. This steers us away from less efficient methods and aligns with the standards expected in technical interviews. Through nuanced algorithmic practice with Set, you'll refine your skills and deepen your understanding of their computational benefits.

Sign up
Join the 1M+ learners on CodeSignal
Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal