Mastering Algorithmic Problem Solving with Ruby's Hash Structure

Introduction to the Lesson

Welcome back! Today, we're sharpening our algorithmic problem-solving skills, focusing on Ruby's Hash . Imagine Hash as the backbone of a social network app, ensuring that each user's data remains unique and instantly accessible. By the close of this lesson, you will be equipped to use Ruby's Hash to efficiently solve problems that might otherwise seem daunting due to their complexity or data size.

Problem 1: Majority Element Finder

Our journey begins with the Majority Element Finder. You're handed an array of integers, and your mission is simple yet intriguing: determine whether this array has a celebrity element. This integer appears more frequently than all others combined. More formally, we are looking for an element appearing more than n/2 times. Why does this matter? Well, consider analyzing sales data to determine the most sold product in an online marketplace — knowing the majority of products could streamline marketing strategies and inventory management. That's the real-world relevance of the majority element problem. Now, let's be savvy about this. Enter the Hash : your sophisticated voting tally system. With it, you can keep a running total of each product's sales as you go through the transaction list once rather than reviewing the entire list for each product. It grants us the speed of an experienced cashier who knows customers' habits by heart.

Problem 1: Solution Building

Let's dissect the process in our election analogy step by step: Ruby count_map = Hash.new(0) majority_threshold = arr.length / 2 Here, we're preparing our Hash, akin to setting up our ballot boxes and establishing the majority threshold — the number of votes needed to win the election by a landslide. Ruby arr.each do |num| count_map[num] += 1 We're recording every vote cast in our Hash ledger. Each key is a unique product, and the value is the current total of received votes. Ruby if count_map[num] > majority_threshold return num end end Once a product's vote count exceeds the threshold, signaling a majority, our search concludes, akin to declaring a winner! Ruby def find_majority_element(arr) count_map = Hash.new(0) majority_threshold = arr.length / 2 arr.each do |num| count_map[num] += 1 if count_map[num] > majority_threshold return num end end -1 end If the polling ends with no majority victor, we return -1, signifying a contested market where no single product dominates.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Problem 2: Keyword Index Creator

Imagine you are building a search feature for an app, and you need a function that quickly retrieves all documents where a certain keyword is present. If you have ever searched for something using your browser's Ctrl+F or Command+F function, you have utilized such an index! Our task is to create a hash that behaves like an index, mapping a keyword to all the documents where it can be found.

This capability is the cornerstone of search engines or reference databases — offering instant results when you look up a word or phrase. Indexing is an unsung hero in big data, where speed is invaluable.

Our Hash steps in as our digital librarian, capable of cataloging every word and its locations at a fantastic clip. It's the magic behind the fast search results we often take for granted.

Let's delve into our code, assembling our digital index:

Ruby

index = Hash.new { |hash, key| hash[key] = [] }

index = Hash.new { |hash, key| hash[key] = [] }

This line can be likened to opening a new spreadsheet where each row represents a distinct word, and the columns list the document numbers where the word appears.

Ruby

docs.each_with_index do |doc, i|
    words = doc.split(' ')
    words.each do |word|

docs.each_with_index do |doc, i|
    words = doc.split(' ')
    words.each do |word|

Here, we're flipping through each document and dissecting it into individual words. It's parallel to scanning each page of our metaphorical book.

Ruby

        unless word.empty?
            index[word] << i
        end
    end
end

        unless word.empty?
            index[word] << i
        end
    end
end

For every word we encounter, we pinpoint its listing or create one if it's new. Then, we're cross-referencing the document index, much like jotting down on which page a topic is discussed.

Ruby

def create_keyword_index(docs)
    index = Hash.new { |hash, key| hash[key] = [] }

    docs.each_with_index do |doc, i|
        words = doc.split(' ')
        words.each do |word|
            unless word.empty?
                index[word] << i
            end
        end
    end

    index
end

def create_keyword_index(docs)
    index = Hash.new { |hash, key| hash[key] = [] }

    docs.each_with_index do |doc, i|
        words = doc.split(' ')
        words.each do |word|
            unless word.empty?
                index[word] << i
            end
        end
    end

    index
end

And with that, our index is complete, a feat many times quicker than doing so manually and without the risk of paper cuts!

Mastering Algorithmic Problem Solving with Ruby's Hash Structure

Introduction to the Lesson

Problem 1: Majority Element Finder

Problem 1: Solution Building

Join the 1M+ learners on CodeSignal

Problem 2: Keyword Index Creator

Lesson Summary