Group_by for categorization in Ruby - Time & Space Complexity

Time Complexity: Group_by for categorization

O(n)

Understanding Time Complexity

We want to understand how the time needed to group items changes as the list gets bigger.

How does the work grow when we categorize many items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

numbers = [1, 2, 3, 4, 5, 6]
groups = numbers.group_by { |num| num.even? }
# groups will be {true => [2, 4, 6], false => [1, 3, 5]}

This code groups numbers into two categories: even and odd.

Identify Repeating Operations

• Primary operation: Going through each number once to check if it is even or odd.
• How many times: Exactly once for each number in the list.

How Execution Grows With Input

As the list gets bigger, the time to group grows in a straight line with the number of items.

Input Size (n)	Approx. Operations
10	About 10 checks
100	About 100 checks
1000	About 1000 checks

Pattern observation: Doubling the list size roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to group items grows directly with the number of items.

Common Mistake

[X] Wrong: "Grouping takes more time because it creates many groups inside the loop."

[OK] Correct: Actually, grouping just checks each item once and adds it to a group. The number of groups does not multiply the work for each item.

Interview Connect

Knowing how grouping scales helps you explain how your code handles bigger data smoothly and shows you understand efficient data organization.

Self-Check

"What if we nested group_by calls to group items by two conditions? How would the time complexity change?"

Practice

1. What does the Ruby method group_by do when called on an array?

easy

A. It converts the array into a string.

B. It groups elements into a hash based on a given condition.

C. It removes duplicate elements from the array.

D. It sorts the array in ascending order.

Solution

1. Step 1: Understand the purpose of group_by

   The group_by method organizes elements by a condition and returns a hash.

2. Step 2: Compare with other array methods

   Sorting, removing duplicates, or converting to string are different methods like sort, uniq, or join.

3. Final Answer:

   It groups elements into a hash based on a given condition. -> Option B

4. Quick Check:

   group_by = groups hash [OK]

Hint: Remember: group_by returns a hash of grouped elements [OK]

Common Mistakes:

• Confusing group_by with sort or uniq
• Expecting an array instead of a hash
• Thinking it changes element order only

2. Which of the following is the correct syntax to group an array nums by even or odd using group_by?

easy

A. nums.group_by(n % 2 == 0)

B. nums.group_by do n % 2 == 0 end

C. nums.group_by { |n| n % 2 == 0 }

D. nums.group_by ->(n) { n % 2 == 0 }

Solution

1. Step 1: Recall block syntax for group_by

   The method requires a block with curly braces or do-end and a block variable.

2. Step 2: Check each option's syntax

   nums.group_by { |n| n % 2 == 0 } uses correct block with { |n| ... }. nums.group_by(n % 2 == 0) misses block. nums.group_by do n % 2 == 0 end lacks block variable. nums.group_by ->(n) { n % 2 == 0 } uses lambda incorrectly.

3. Final Answer:

   nums.group_by { |n| n % 2 == 0 } -> Option C

4. Quick Check:

   Correct block syntax = nums.group_by { |n| n % 2 == 0 } [OK]

Hint: Use curly braces with block variable for group_by [OK]

Common Mistakes:

• Omitting block variable in block
• Passing condition as argument instead of block
• Using lambda syntax incorrectly

3. What is the output of this Ruby code?

words = ['apple', 'banana', 'avocado', 'blueberry']
groups = words.group_by { |w| w[0] }
puts groups

medium

A. [["a", ["apple", "avocado"]], ["b", ["banana", "blueberry"]]]

B. ["apple", "avocado", "banana", "blueberry"]

C. {"apple"=>"a", "banana"=>"b"}

D. {"a"=>["apple", "avocado"], "b"=>["banana", "blueberry"]}

Solution

1. Step 1: Understand group_by with first letter

   The block groups words by their first character, so keys are 'a' and 'b'.

2. Step 2: Check output format of group_by

   It returns a hash with keys as letters and values as arrays of words starting with that letter.

3. Final Answer:

   {"a"=>["apple", "avocado"], "b"=>["banana", "blueberry"]} -> Option D

4. Quick Check:

   group_by first char = hash with arrays [OK]

Hint: group_by returns a hash, not an array or string [OK]

Common Mistakes:

• Expecting an array instead of a hash
• Confusing keys and values in output
• Misreading output as string instead of hash

4. Identify the error in this Ruby code snippet:

numbers = [1, 2, 3, 4]
groups = numbers.group_by do n
  n.even?
end
puts groups

medium

A. Missing block variable in the do-end block.

B. group_by cannot be used with do-end blocks.

C. The method even? does not exist for integers.

D. The array must be sorted before using group_by.

Solution

1. Step 1: Check block syntax for group_by

   The block must have a variable to represent each element, like do |n| ... end.

2. Step 2: Identify the missing block variable

   The code uses do n without vertical bars, so n is treated as a local variable, causing error.

3. Final Answer:

   Missing block variable in the do-end block. -> Option A

4. Quick Check:

   Block variable required in do-end [OK]

Hint: Always use |variable| in do-end blocks [OK]

Common Mistakes:

• Omitting vertical bars around block variable
• Thinking even? is undefined for integers
• Believing group_by needs sorted array

5. Given an array of hashes representing people:

people = [
  {name: 'Alice', age: 30},
  {name: 'Bob', age: 20},
  {name: 'Carol', age: 30},
  {name: 'Dave', age: 20}
]

Which code correctly groups people by their age using group_by?

hard

A. people.group_by { |person| person[:age] }

B. people.group_by { |person| person.name }

C. people.group_by { |person| person['age'] }

D. people.group_by { |person| person.age }

Solution

1. Step 1: Understand data structure and access

   Each element is a hash with symbol keys like :age, so access with person[:age].

2. Step 2: Check each option's key access

   people.group_by { |person| person[:age] } uses correct symbol key access. people.group_by { |person| person.name } and D use dot notation which doesn't work on hashes. people.group_by { |person| person['age'] } uses string key which is incorrect here.

3. Final Answer:

   people.group_by { |person| person[:age] } -> Option A

4. Quick Check:

   Hash keys accessed by symbols = people.group_by { |person| person[:age] } [OK]

Hint: Use symbol keys with [:key] to access hash values [OK]

Common Mistakes:

• Using dot notation on hashes
• Using string keys instead of symbols
• Confusing array of hashes with objects