Reject for inverse filtering in Ruby - Time & Space Complexity

Time Complexity: Reject for inverse filtering

O(n)

Understanding Time Complexity

We want to understand how the time needed to run the reject for inverse filtering method changes as the input size grows.

Specifically, how does the number of operations increase when we process more data?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def reject_inverse_filtering(data, threshold)
  result = []
  data.each do |value|
    inverse = 1.0 / value
    if inverse > threshold
      result << value
    end
  end
  result
end

This code goes through each number in the data, calculates its inverse, and keeps the original number if the inverse is bigger than a threshold.

Identify Repeating Operations

• Primary operation: Looping through each element in the data array.
• How many times: Once for every element in the input data.

How Execution Grows With Input

As the input data gets bigger, the code does more work by checking each new element once.

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

Pattern observation: The work grows directly in proportion to the number of items.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line with the number of items to check.

Common Mistake

[X] Wrong: "Calculating the inverse inside the loop makes the code slower than linear time."

[OK] Correct: Each inverse calculation is a simple step done once per item, so it still grows linearly with input size.

Interview Connect

Understanding how loops affect time helps you explain your code clearly and shows you can think about efficiency in real tasks.

Self-Check

"What if we added a nested loop inside the existing loop? How would the time complexity change?"

Practice

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

easy

A. It sorts the array in reverse order.

B. It modifies the original array to keep only elements matching the condition.

C. It returns the first element that matches the condition.

D. It returns a new array excluding elements that match the given condition.

Solution

1. Step 1: Understand the purpose of reject

   The reject method filters elements by removing those that satisfy the condition.

2. Step 2: Compare with other methods

   Unlike select, which keeps matching elements, reject excludes them and returns a new array.

3. Final Answer:

   It returns a new array excluding elements that match the given condition. -> Option D

4. Quick Check:

   reject excludes matching elements = A [OK]

Hint: Reject removes items matching condition, returning a new array [OK]

Common Mistakes:

• Thinking reject modifies the original array
• Confusing reject with select
• Assuming reject returns a single element

2. Which of the following is the correct syntax to use reject on an array nums to remove even numbers?

easy

A. nums.reject { |n| n % 2 == 0 }

B. nums.reject(n % 2 == 0)

C. nums.reject => n { n % 2 == 0 }

D. nums.reject do n; n % 2 == 0 end

Solution

1. Step 1: Identify correct block syntax for reject

   The reject method requires a block with { |var| condition } or do |var| ... end.

2. Step 2: Check each option's syntax

   nums.reject { |n| n % 2 == 0 } uses correct block syntax with braces and block variable. nums.reject(n % 2 == 0) misses block. nums.reject => n { n % 2 == 0 } uses invalid syntax. nums.reject do n; n % 2 == 0 end misses block variable in do syntax.

3. Final Answer:

   nums.reject { |n| n % 2 == 0 } -> Option A

4. Quick Check:

   Correct block syntax with |var| = D [OK]

Hint: Use braces with |var| for reject blocks [OK]

Common Mistakes:

• Omitting block variable in block
• Passing condition as method argument
• Using incorrect block syntax

3. What is the output of this Ruby code?

arr = [1, 2, 3, 4, 5]
result = arr.reject { |x| x > 3 }
puts result.inspect

medium

A. [1, 2, 3]

B. [4, 5]

C. [1, 2, 3, 4, 5]

D. []

Solution

1. Step 1: Understand the reject condition

   The block removes elements where x > 3 is true, so numbers 4 and 5 are removed.

2. Step 2: Determine remaining elements

   Elements 1, 2, and 3 remain because they do not satisfy the condition.

3. Final Answer:

   [1, 2, 3] -> Option A

4. Quick Check:

   reject removes >3, so [1,2,3] remain = A [OK]

Hint: Reject removes matching items, so keep others [OK]

Common Mistakes:

• Confusing reject with select
• Expecting removed elements as output
• Ignoring block condition logic

4. The following code is intended to remove all nil values from the array data. What is the error?

data = [1, nil, 2, nil, 3]
clean = data.reject do |x|
  x = nil
end
puts clean.inspect

medium

A. The block variable is missing in the block.

B. The reject method cannot remove nil values.

C. The block uses assignment (=) instead of comparison (==).

D. The code should use select instead of reject.

Solution

1. Step 1: Identify the block logic error

   The block uses x = nil which assigns nil to x instead of checking if x equals nil.

2. Step 2: Correct the comparison operator

   It should use x == nil to test if x is nil for rejection.

3. Final Answer:

   The block uses assignment (=) instead of comparison (==). -> Option C

4. Quick Check:

   Use == for comparison inside reject blocks [OK]

Hint: Use == for comparison inside reject blocks [OK]

Common Mistakes:

• Using = instead of == in block condition
• Thinking reject modifies original array
• Confusing reject with select

5. Given a hash scores = { alice: 90, bob: 55, carol: 75, dave: 40 }, how can you use reject to create a new hash excluding all entries with scores below 60?

hard

A. scores.reject { |name| name < 60 }

B. scores.reject { |name, score| score < 60 }

C. scores.reject { |score| score < 60 }

D. scores.reject { |name, score| name < 60 }

Solution

1. Step 1: Understand hash reject block parameters

   When rejecting from a hash, the block receives two parameters: key and value.

2. Step 2: Apply condition on values

   We want to reject entries where the score (value) is less than 60, so the block should check score < 60.

3. Step 3: Verify options

   scores.reject { |name, score| score < 60 } correctly uses both key and value parameters and checks the score. The other options either use only one block parameter or check the key instead of the value.

4. Final Answer:

   scores.reject { |name, score| score < 60 } -> Option B

5. Quick Check:

   Reject hash entries by value condition = B [OK]

Hint: Use two block params for hash reject: |key, value| [OK]

Common Mistakes:

• Using only one block parameter for hash reject
• Checking key instead of value
• Confusing reject with select for filtering