Default values for missing keys in Ruby - Time & Space Complexity

Time Complexity: Default values for missing keys

O(n)

Understanding Time Complexity

When we use default values for missing keys in a hash, we want to know how this choice affects how long the program takes to run.

We ask: How does the time to find or set a default value change as the hash grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

hash = Hash.new(0)
keys = ["a", "b", "c", "d", "e"]

keys.each do |key|
  hash[key] += 1
end

value = hash["z"]
    

This code creates a hash with a default value of 0, counts keys, and accesses a missing key.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping over the keys array and accessing/updating the hash.
• How many times: Once for each key in the array (5 times here).

How Execution Grows With Input

Each key is processed once, and each hash access is quick regardless of size.

Input Size (n)	Approx. Operations
10	About 10 hash accesses and updates
100	About 100 hash accesses and updates
1000	About 1000 hash accesses and updates

Pattern observation: The time grows directly with the number of keys processed.

Final Time Complexity

Time Complexity: O(n)

This means the time to process keys grows in a straight line with the number of keys.

Common Mistake

[X] Wrong: "Setting a default value makes hash lookups slower as the hash grows."

[OK] Correct: Hash lookups stay fast because Ruby hashes use efficient methods internally, so default values do not slow down access noticeably.

Interview Connect

Understanding how default values affect hash access time helps you explain how data structures work efficiently in real programs.

Self-Check

"What if we changed the default value from a fixed number to a block that computes a value? How would the time complexity change?"

Practice

1. What does setting a default value for a Ruby hash do when you access a key that does not exist?
h = Hash.new(0)

easy

A. Returns the default value instead of nil for missing keys

B. Raises an error for missing keys

C. Adds the missing key with nil value to the hash

D. Returns nil for missing keys as usual

Solution

1. Step 1: Understand default value behavior

   When a hash is created with Hash.new(0), it sets 0 as the default value for any missing key.

2. Step 2: Accessing a missing key

   Accessing a key not present in the hash returns the default value 0 instead of nil.

3. Final Answer:

   Returns the default value instead of nil for missing keys -> Option A

4. Quick Check:

   Default value = 0 returned for missing keys [OK]

Hint: Default value replaces nil for missing keys [OK]

Common Mistakes:

• Thinking missing keys raise errors
• Assuming missing keys return nil always
• Believing missing keys get added automatically

2. Which of the following is the correct syntax to create a Ruby hash with a default value of an empty array for missing keys?

easy

A. h = Hash.new { |key| [] }

B. h = Hash.new { [] }

C. h = Hash.new([])

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

Solution

1. Step 1: Understand default block usage

   Using a block with Hash.new allows dynamic default values. To assign a new array to each missing key, the block must assign it to the hash.

2. Step 2: Identify correct block syntax

   The block receives hash and key parameters and assigns [] to hash[key]. This ensures each missing key gets its own array.

3. Final Answer:

   h = Hash.new { |hash, key| hash[key] = [] } -> Option D

4. Quick Check:

   Block assigns new array to missing keys [OK]

Hint: Use block with two params to assign default arrays [OK]

Common Mistakes:

• Using Hash.new([]) shares one array for all keys
• Using block without assigning to hash[key]
• Using wrong block parameters

3. What is the output of the following Ruby code?

h = Hash.new { |hash, key| hash[key] = [] }
h[:a] << 1
h[:b] << 2
p h

medium

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

B. {:a=>[1], :b=>[2], nil=>[]}

C. {:a=>[1], :b=>[2]}

D. {}

Solution

1. Step 1: Understand default block behavior

   The hash is created with a block that assigns an empty array to missing keys when accessed.

2. Step 2: Modify arrays for keys :a and :b

   Appending 1 to h[:a] creates :a => [1]. Similarly, appending 2 to h[:b] creates :b => [2].

3. Step 3: Print the hash

   Only keys :a and :b have values. No other keys exist.

4. Final Answer:

   {:a=>[1], :b=>[2]} -> Option C

5. Quick Check:

   Default arrays assigned and modified correctly [OK]

Hint: Default block assigns new array per missing key [OK]

Common Mistakes:

• Expecting keys not accessed to appear
• Confusing default value with nil
• Thinking default array is shared

4. Identify the error in this Ruby code that tries to set a default value of 0 for missing keys:

h = Hash.new
h.default = 0
puts h[:missing]

medium

A. h.default=0 sets default but does not affect missing keys

B. No error; code works and prints 0

C. h.default=0 should be h.default = 0 (space required)

D. Syntax error in setting default value

Solution

1. Step 1: Check default value assignment

   Using h.default = 0 correctly sets the default value for missing keys after hash creation.

2. Step 2: Access missing key

   Accessing h[:missing] returns 0 as expected, no error occurs.

3. Final Answer:

   No error; code works and prints 0 -> Option B

4. Quick Check:

   Setting default after creation works [OK]

Hint: Use h.default = value to set default after creation [OK]

Common Mistakes:

• Thinking default= is a syntax error
• Confusing default= with default_proc
• Expecting missing keys to raise errors

5. You want a Ruby hash that counts how many times each word appears in an array. Which code correctly uses default values to do this?

words = ['apple', 'banana', 'apple', 'orange', 'banana', 'apple']
counter = ???
words.each { |w| counter[w] += 1 }
puts counter

hard

A. counter = Hash.new(0)

B. counter = Hash.new { |h, k| [] }

C. counter = Hash.new([])

D. counter = {}

Solution

1. Step 1: Understand counting with default values

   To count words, missing keys must return 0 so counter[w] += 1 works. The += reads the default 0, increments to 1, and assigns back, storing the key.

2. Step 2: Compare options

   Hash.new(0) returns 0 for missing keys (no store); += 1 stores the result. Perfect for counting.
   Hash.new { |h, k| [] } returns []; [] += 1 TypeError.
   Hash.new([]) returns shared []; TypeError.
   {} returns nil; error.

3. Final Answer:

   counter = Hash.new(0) -> Option A

4. Quick Check:

   Hash.new(0) enables counter[w] += 1 [OK]

Hint: Hash.new(0) for numeric counting [OK]

Common Mistakes:

• Using block or Hash.new([]) returns array; TypeError on += 1
• Using {} with no default; nil error
• Wrong block parameters or no assignment