SADD and SREM for membership in Redis - Time & Space Complexity

Time Complexity: SADD and SREM for membership

O(1)

Understanding Time Complexity

When working with Redis sets, it is important to know how the time to add or remove members changes as the set grows.

We want to understand how the cost of adding or removing items scales with the number of items in the set.

Scenario Under Consideration

Analyze the time complexity of the following Redis commands.

SADD myset member1
SADD myset member2
SREM myset member1
SREM myset member3
    

This code adds members to a set and removes members from it, checking membership as needed.

Identify Repeating Operations

Look at what happens when adding or removing members.

• Primary operation: Checking if a member exists and then adding or removing it.
• How many times: Each command works on one member at a time, so operations happen once per command.

How Execution Grows With Input

Adding or removing a member takes about the same time no matter how many members are in the set.

Input Size (n)	Approx. Operations
10	1 operation per add or remove
100	1 operation per add or remove
1000	1 operation per add or remove

Pattern observation: The time to add or remove a member stays about the same even as the set grows.

Final Time Complexity

Time Complexity: O(1)

This means adding or removing a member takes constant time, no matter how big the set is.

Common Mistake

[X] Wrong: "Adding or removing members gets slower as the set grows because it has to check all members."

[OK] Correct: Redis uses efficient data structures for sets that let it find and update members quickly without scanning the whole set.

Interview Connect

Knowing that Redis set operations like SADD and SREM run in constant time helps you understand how Redis handles data efficiently, a useful skill for real-world projects and interviews.

Self-Check

"What if we used a Redis list instead of a set for membership? How would the time complexity of adding and removing change?"

Practice

1. What does the Redis command SADD myset member1 do?

easy

A. Adds 'member1' to the set 'myset' if it is not already present.

B. Removes 'member1' from the set 'myset'.

C. Returns all members of the set 'myset'.

D. Deletes the set 'myset' entirely.

Solution

1. Step 1: Understand the SADD command

   SADD adds one or more unique members to a Redis set.

2. Step 2: Apply to the example

   Using SADD with 'myset' and 'member1' adds 'member1' if not already in 'myset'.

3. Final Answer:

   Adds 'member1' to the set 'myset' if it is not already present. -> Option A

4. Quick Check:

   SADD adds unique members [OK]

Hint: SADD adds unique items; SREM removes them [OK]

Common Mistakes:

• Confusing SADD with SREM
• Thinking SADD deletes sets
• Assuming SADD returns all members

2. Which of the following is the correct syntax to remove 'member2' from a Redis set named 'myset'?

easy

A. REMOVE myset member2

B. SADD myset member2

C. SREM myset member2

D. DEL myset member2

Solution

1. Step 1: Identify the command to remove members

   SREM is the Redis command used to remove members from a set.

2. Step 2: Check syntax correctness

   The correct syntax is SREM followed by the set name and the member to remove.

3. Final Answer:

   SREM myset member2 -> Option C

4. Quick Check:

   SREM removes members correctly [OK]

Hint: Use SREM to remove members, not DEL or REMOVE [OK]

Common Mistakes:

• Using SADD instead of SREM to remove
• Using DEL which deletes keys, not members
• Using non-existent REMOVE command

3. Given the following Redis commands executed in order:
SADD fruits apple banana orange
SREM fruits banana
What will the command SMEMBERS fruits return?

medium

A. apple, orange

B. banana, orange

C. apple, banana, orange

D. apple, banana

Solution

1. Step 1: Add members to the set 'fruits'

   SADD adds 'apple', 'banana', and 'orange' to the set 'fruits'.

2. Step 2: Remove 'banana' from the set

   SREM removes 'banana' from 'fruits', leaving 'apple' and 'orange'.

3. Step 3: Retrieve members with SMEMBERS

   SMEMBERS returns all current members: 'apple' and 'orange'.

4. Final Answer:

   apple, orange -> Option A

5. Quick Check:

   Removed banana, so only apple and orange remain [OK]

Hint: SREM removes members; SMEMBERS shows current set [OK]

Common Mistakes:

• Assuming removed members still appear
• Confusing SREM with DEL
• Expecting order in SMEMBERS output

4. You run the command SREM myset memberX but get no error and the member still appears in SMEMBERS myset. What is the most likely reason?

medium

A. SREM command syntax is incorrect.

B. Redis server is down.

C. 'myset' is not a set but a string key.

D. 'memberX' was never in 'myset' to begin with.

Solution

1. Step 1: Understand SREM behavior when member absent

   SREM does not error if the member is not in the set; it simply does nothing.

2. Step 2: Check if member exists in the set

   If 'memberX' still appears in SMEMBERS output, it means it was never removed or was never absent.

3. Step 3: Consider other options

   Syntax errors cause errors; wrong key type causes errors; server down causes no response.

4. Final Answer:

   'memberX' was never in 'myset' to begin with. -> Option D

5. Quick Check:

   SREM silently ignores missing members [OK]

Hint: SREM ignores missing members without error [OK]

Common Mistakes:

• Expecting error if member not present
• Confusing key type errors with SREM behavior
• Assuming server down causes silent no-op

5. You want to maintain a Redis set 'online_users' that tracks currently logged-in users. Which sequence of commands correctly updates the set when user 'alice' logs in and then logs out?

hard

A. SREM online_users aliceSADD online_users alice

B. SADD online_users aliceSREM online_users alice

C. DEL online_users aliceSADD online_users alice

D. SADD online_users aliceDEL online_users alice

Solution

1. Step 1: Add user on login

   Use SADD to add 'alice' to 'online_users' when she logs in.

2. Step 2: Remove user on logout

   Use SREM to remove 'alice' from 'online_users' when she logs out.

3. Step 3: Evaluate other options

   DEL deletes the entire set, which is not desired for single user updates.

4. Final Answer:

   SADD online_users alice
   SREM online_users alice -> Option B

5. Quick Check:

   Add with SADD, remove with SREM for membership [OK]

Hint: Add with SADD, remove with SREM; avoid DEL for single members [OK]

Common Mistakes:

• Using DEL which deletes whole set
• Removing before adding user
• Confusing SADD and SREM order