Filter and map operations in Kafka - Time & Space Complexity

Time Complexity: Filter and map operations

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run filter and map operations changes as the data grows.

How does the number of items affect the work done by these operations?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

val numbers = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
val evenNumbers = numbers.filter(n => n % 2 == 0)
val doubled = evenNumbers.map(n => n * 2)

This code filters even numbers from a list and then doubles each filtered number.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Traversing the list twice: once for filter, once for map.
• How many times: Each operation goes through all items in the list once.

How Execution Grows With Input

As the list gets bigger, the work grows because each item is checked and then processed.

Input Size (n)	Approx. Operations
10	About 20 (10 for filter + 10 for map)
100	About 200 (100 for filter + 100 for map)
1000	About 2000 (1000 for filter + 1000 for map)

Pattern observation: The total work grows roughly twice as fast as the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to run filter and map grows in a straight line with the number of items.

Common Mistake

[X] Wrong: "Filter and map together make the time complexity O(n²) because they are two steps."

[OK] Correct: Each step goes through the list once, so the total work adds up, not multiplies. This keeps it linear, not squared.

Interview Connect

Understanding how filter and map scale helps you explain how data processing pipelines work efficiently in real projects.

Self-Check

"What if we combined filter and map into one step? How would the time complexity change?"

Practice

1. What does the filter operation do in Kafka Streams?

easy

A. Deletes all messages in the stream

B. Changes messages to a new form

C. Keeps only messages that meet a condition

D. Sends messages to a different topic

Solution

1. Step 1: Understand filter purpose

   The filter operation selects messages that satisfy a given condition, removing others.

2. Step 2: Compare with other operations

   Unlike map, which changes message content, filter only keeps or drops messages.

3. Final Answer:

   Keeps only messages that meet a condition -> Option C

4. Quick Check:

   Filter = Keep messages by condition [OK]

Hint: Filter keeps or drops messages based on a rule [OK]

Common Mistakes:

• Confusing filter with map operation
• Thinking filter changes message content
• Assuming filter deletes all messages

2. Which of the following is the correct syntax to apply a map operation on a Kafka stream named stream to convert messages to uppercase?

easy

A. stream.map(value.toUpperCase)

B. stream.filter(value -> value.toUpperCase())

C. stream.map(value => value.toUpperCase())

D. stream.map(value -> value.toUpperCase())

Solution

1. Step 1: Identify correct lambda syntax in Kafka Streams

   Kafka Streams in Java uses map(value -> ...) syntax for mapping values.

2. Step 2: Check method call correctness

   value.toUpperCase() correctly converts string to uppercase.

3. Final Answer:

   stream.map(value -> value.toUpperCase()) -> Option D

4. Quick Check:

   Correct lambda and method call = stream.map(value -> value.toUpperCase()) [OK]

Hint: Use arrow -> for lambda in Kafka Streams Java [OK]

Common Mistakes:

• Using filter instead of map
• Using JavaScript arrow => instead of Java ->
• Missing parentheses in method call

3. Given the following Kafka Streams code, what will be the output messages after processing?

stream.filter(value -> value.length() > 3)
      .map(value -> value.substring(0, 3))

Input messages: ["apple", "cat", "banana", "dog"]

medium

A. ["cat", "dog"]

B. ["app", "ban"]

C. ["apple", "banana"]

D. ["app", "cat", "ban", "dog"]

Solution

1. Step 1: Apply filter condition

   Keep messages with length > 3: "apple" (5), "banana" (6). "cat" and "dog" are dropped.

2. Step 2: Apply map operation

   Take first 3 characters: "apple" -> "app", "banana" -> "ban".

3. Final Answer:

   ["app", "ban"] -> Option B

4. Quick Check:

   Filter then map = ["app", "ban"] [OK]

Hint: Filter first, then map to transform filtered messages [OK]

Common Mistakes:

• Not filtering before mapping
• Mapping before filtering
• Including messages with length ≤ 3

4. Identify the error in this Kafka Streams code snippet:

stream.filter(value -> value.startsWith("a"))
      .map(value -> value.toUpperCase())
      .filter(value -> value.length() > 5)

medium

A. No error; code is correct

B. Using two filter operations is not allowed

C. The second filter uses the mapped uppercase value correctly

D. The lambda syntax is incorrect

Solution

1. Step 1: Check filter and map chaining

   Chaining multiple filters and maps is allowed in Kafka Streams.

2. Step 2: Verify lambda syntax and logic

   Lambdas use correct syntax and logic: first filter checks start, map uppercases, second filter checks length.

3. Final Answer:

   No error; code is correct -> Option A

4. Quick Check:

   Multiple filters and maps allowed = No error; code is correct [OK]

Hint: Multiple filters and maps can be chained without error [OK]

Common Mistakes:

• Thinking multiple filters are disallowed
• Confusing lambda syntax with other languages
• Assuming map changes variable type incorrectly

5. You want to process a Kafka stream of user names to keep only those starting with 'J' and convert them to lowercase. Which code snippet correctly does this?

hard

A. stream.filter(name -> name.startsWith("J"))
.map(name -> name.toLowerCase())

B. stream.map(name -> name.toLowerCase())
.filter(name -> name.startsWith("J"))

C. stream.filter(name -> name.toLowerCase().startsWith("j"))
.map(name -> name.toUpperCase())

D. stream.map(name -> name.startsWith("J"))
.filter(name -> name.toLowerCase())

Solution

1. Step 1: Filter names starting with 'J'

   Use filter(name -> name.startsWith("J")) to keep only names starting with uppercase 'J'.

2. Step 2: Map filtered names to lowercase

   Apply map(name -> name.toLowerCase()) to convert names to lowercase.

3. Final Answer:

   stream.filter(name -> name.startsWith("J")) .map(name -> name.toLowerCase()) -> Option A

4. Quick Check:

   Filter first, then map to lowercase [OK]

Hint: Filter first by condition, then map to transform [OK]

Common Mistakes:

• Mapping before filtering causing wrong results
• Using incorrect lambda syntax
• Filtering after changing case causing misses