Merge and update methods in Ruby - Time & Space Complexity

Time Complexity: Merge and update methods

O(m + n)

Understanding Time Complexity

When we use merge or update methods in Ruby hashes, we want to know how the time it takes changes as the hashes get bigger.

We ask: How does the work grow when we combine or change hashes? Let m be the size of the first hash, n the size of the second.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

hash1 = { a: 1, b: 2, c: 3 }
hash2 = { b: 4, d: 5 }

result = hash1.merge(hash2) do |key, old_val, new_val|
  old_val + new_val
end

# result is { a: 1, b: 6, c: 3, d: 5 }

This code merges two hashes, combining values for keys that appear in both.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operations: 1. Duplicating all key-value pairs from the first hash (O(m)). 2. Iterating over each key-value pair in the second hash, with lookups and updates (O(n) total).
• How many times: Duplication once per element in first (m times), iteration once per element in second (n times).

How Execution Grows With Input

As either hash gets bigger, the method does more work proportionally.

Sizes (m, n)	Approx. Operations
(10, 10)	About 20
(100, 100)	About 200
(1000, 1000)	About 2000

Pattern observation: The work grows linearly with the combined size of both hashes.

Final Time Complexity

Time Complexity: O(m + n)

This means the time to merge grows linearly with the sizes of both hashes.

Common Mistake

[X] Wrong: "Merging two hashes takes time based only on the second hash."

[OK] Correct: Ruby's merge method first duplicates the first hash (O(m)), then loops over the second (O(n)). Time depends on both.

Interview Connect

Understanding how merge and update methods scale helps you write efficient code when combining data, a common task in many programs. Note merge! is O(n) as it modifies in place without duplication.

Self-Check

"What if we used merge! instead of merge? How would the time complexity change?"

Answer: It becomes O(n), since no duplication of the first hash; only iterates over the second.

Practice

1.

Which Ruby method returns a new hash by combining two hashes without changing the original?

easy

A. merge

B. merge!

C. update

D. replace

Solution

1. Step 1: Understand merge behavior

   merge returns a new hash combining two hashes without modifying the original.

2. Step 2: Compare with merge! and update

   Both merge! and update modify the original hash, so they don't return a new one.

3. Final Answer:

   merge -> Option A

4. Quick Check:

   merge returns new hash [OK]

Hint: Remember: merge returns new hash, merge! updates original [OK]

Common Mistakes:

• Confusing merge and merge! methods
• Thinking update returns a new hash
• Assuming replace merges hashes

2.

Which of the following is the correct syntax to update hash a with hash b in Ruby?

a = {x: 1}

b = {y: 2}

easy

A. a + b

B. a.merge!b

C. a.merge b

D. a.update(b)

Solution

1. Step 1: Check syntax for updating hash

   update is a method that modifies the original hash and takes another hash as argument with parentheses.

2. Step 2: Compare with other options

   merge! also updates but usually called with ! and parentheses are optional but update(b) is the most explicit and correct syntax here.

3. Final Answer:

   a.update(b) -> Option D

4. Quick Check:

   Use update() to modify original hash [OK]

Hint: Use update(hash) to change original hash [OK]

Common Mistakes:

• Using + operator to combine hashes (not valid)
• Forgetting parentheses in method call
• Confusing merge and update syntax

3.

What is the output of this Ruby code?

a = {a: 1, b: 2}

b = {b: 3, c: 4}

c = a.merge(b)

puts c

medium

A. {:a=>1, :b=>2, :c=>4}

B. {:a=>1, :b=>3}

C. {:a=>1, :b=>3, :c=>4}

D. {:b=>3, :c=>4}

Solution

1. Step 1: Understand merge behavior with overlapping keys

   merge returns a new hash combining keys; overlapping keys get values from the second hash.

2. Step 2: Apply to given hashes

   Key :b is in both hashes; value from b (3) replaces value from a (2). Keys :a and :c are included as is.

3. Final Answer:

   {:a=>1, :b=>3, :c=>4} -> Option C

4. Quick Check:

   Overlapping keys replaced by second hash [OK]

Hint: Overlapping keys take second hash's value in merge [OK]

Common Mistakes:

• Assuming original hash is changed by merge
• Not replacing overlapping key values
• Missing keys from either hash

4.

Identify the error in this Ruby code snippet:

a = {x: 10}

b = {y: 20}

a.merge! b

puts a

medium

A. Output will be empty hash

B. No error; code works correctly

C. Runtime error because merge! cannot be used with variables

D. Syntax error due to missing parentheses in merge!

Solution

1. Step 1: Check syntax of merge! method call

   merge! can be called without parentheses in Ruby, so a.merge! b is valid syntax.

2. Step 2: Verify runtime behavior

   merge! updates a with keys and values from b, so a becomes {x: 10, y: 20}. No errors occur.

3. Final Answer:

   No error; code works correctly -> Option B

4. Quick Check:

   merge! updates original hash without error [OK]

Hint: merge! can be called without parentheses [OK]

Common Mistakes:

• Thinking parentheses are mandatory
• Assuming merge! returns a new hash
• Expecting runtime error with variable argument

5.

You have two hashes:

h1 = {a: 1, b: 2, c: 3}

h2 = {b: 20, d: 4}

You want to update h1 with h2 but only keep keys from h2 that have values greater than 10. Which code correctly does this?

hard

A. h1.update(h2.select { |k, v| v > 10 })

B. h1.update(h2.reject { |k, v| v > 10 })

C. h1.merge(h2.select { |k, v| v > 10 })

D. h1.replace(h2.select { |k, v| v > 10 })

Solution

1. Step 1: Filter h2 keys with values > 10

   Use select { |k, v| v > 10 } to keep only keys with values greater than 10.

2. Step 2: Update h1 with filtered h2

   Use update to modify h1 in place with the filtered hash.

3. Step 3: Check other options

   merge! also updates but update is clearer; merge returns new hash and does not modify h1.

4. Final Answer:

   h1.update(h2.select { |k, v| v > 10 }) -> Option A

5. Quick Check:

   Filter then update original hash [OK]

Hint: Filter with select, then update original hash [OK]

Common Mistakes:

• Using merge instead of update (does not modify original)
• Not filtering keys before update
• Using reject incorrectly