ZRANK and ZREVRANK for position in Redis - Time & Space Complexity

Time Complexity: ZRANK and ZREVRANK for position

O(log n)

Understanding Time Complexity

When using Redis commands like ZRANK and ZREVRANK, it's important to know how the time to find an element's position changes as the sorted set grows.

We want to understand how the work Redis does grows when the number of elements increases.

Scenario Under Consideration

Analyze the time complexity of the following Redis commands.

# Find the rank of member "user42" in sorted set "scores"
ZRANK scores user42

# Find the reverse rank of member "user42" in sorted set "scores"
ZREVRANK scores user42
    

These commands return the position of a member in a sorted set, counting from the lowest or highest score.

Identify Repeating Operations

Look at what Redis does internally to find the member's rank.

• Primary operation: Searching through the sorted set's internal data structure to locate the member.
• How many times: The search depends on the size of the sorted set, as Redis may need to check multiple elements.

How Execution Grows With Input

As the sorted set grows, finding a member's rank takes more steps, but not one for each element.

Input Size (n)	Approx. Operations
10	About 4 steps
100	About 7 steps
1000	About 10 steps

Pattern observation: The steps grow slowly as the set gets bigger, roughly adding one step each time the size multiplies by about 2.

Final Time Complexity

Time Complexity: O(log n)

This means the time to find a member's rank grows slowly and predictably as the sorted set gets larger.

Common Mistake

[X] Wrong: "Finding a member's rank takes the same time no matter how big the sorted set is."

[OK] Correct: Actually, Redis uses a data structure that lets it find members faster than checking every element, but it still takes more steps as the set grows.

Interview Connect

Understanding how Redis commands scale helps you explain your choices clearly and shows you know how data size affects performance.

Self-Check

"What if the sorted set used a different internal structure, like a simple list? How would the time complexity of ZRANK change?"

Practice

1. What does the Redis command ZRANK return when used on a sorted set?

easy

A. The total number of members in the sorted set

B. The zero-based rank of a member with scores in ascending order

C. The score of the member in the sorted set

D. The member with the highest score

Solution

1. Step 1: Understand what ZRANK does

   ZRANK returns the position of a member in a sorted set ordered by score from lowest to highest.

2. Step 2: Identify the rank type

   The rank is zero-based, meaning the lowest score member has rank 0.

3. Final Answer:

   The zero-based rank of a member with scores in ascending order -> Option B

4. Quick Check:

   ZRANK = ascending zero-based rank [OK]

Hint: ZRANK ranks ascending, starting at zero [OK]

Common Mistakes:

• Confusing rank with score
• Thinking rank starts at 1
• Mixing ZRANK with ZREVRANK

2. Which of the following is the correct syntax to get the rank of member 'user1' in sorted set 'scores' using ZREVRANK?

easy

A. ZRANK user1 scores

B. ZREVRANK user1 scores

C. ZRANK scores user1

D. ZREVRANK scores user1

Solution

1. Step 1: Recall ZREVRANK command syntax

   The syntax is: ZREVRANK key member

2. Step 2: Apply to given example

   Here, key is 'scores' and member is 'user1', so command is ZREVRANK scores user1

3. Final Answer:

   ZREVRANK scores user1 -> Option D

4. Quick Check:

   ZREVRANK key member syntax [OK]

Hint: Command syntax: ZREVRANK key member [OK]

Common Mistakes:

• Swapping key and member order
• Using ZRANK instead of ZREVRANK
• Adding extra parameters

3. Given a sorted set 'players' with members and scores: {"alice": 50, "bob": 70, "carol": 60}, what is the result of ZRANK players bob?

medium

A. 2

B. 1

C. 0

D. None (member not found)

Solution

1. Step 1: Sort members by ascending score

   Sorted by score ascending: alice(50), carol(60), bob(70)

2. Step 2: Find zero-based rank of 'bob'

   bob is third in order, so rank is 2 (0-based)

3. Final Answer:

   2 -> Option A

4. Quick Check:

   ZRANK ascending order rank = 2 [OK]

Hint: ZRANK counts from lowest score, zero-based [OK]

Common Mistakes:

• Assuming rank is score
• Confusing ascending with descending order
• Using ZREVRANK result instead

4. You run ZREVRANK leaderboard "playerX" but get a null reply. What is the most likely reason?

medium

A. "playerX" is not a member of the sorted set "leaderboard"

B. The command syntax is incorrect

C. The sorted set "leaderboard" is empty

D. ZREVRANK only works on lists, not sorted sets

Solution

1. Step 1: Understand ZREVRANK null reply meaning

   Null reply means the member does not exist in the sorted set.

2. Step 2: Check other options

   Syntax is correct, empty set would also return null but question implies member missing, and ZREVRANK works only on sorted sets.

3. Final Answer:

   "playerX" is not a member of the sorted set "leaderboard" -> Option A

4. Quick Check:

   Null reply means member missing [OK]

Hint: Null reply means member not in set [OK]

Common Mistakes:

• Thinking syntax error causes null
• Assuming empty set returns error
• Confusing data types for ZREVRANK

5. You have a sorted set 'scores' with members and scores: {"x": 10, "y": 20, "z": 30}. You want to find the rank of member 'y' counting from highest score first. Which command and expected result is correct?

hard

A. ZRANK scores y returns 1

B. ZREVRANK scores y returns 2

C. ZREVRANK scores y returns 1

D. ZRANK scores y returns 2

Solution

1. Step 1: Understand ZREVRANK ranks descending

   ZREVRANK ranks members from highest to lowest score, zero-based.

2. Step 2: Sort members descending and find 'y' rank

   Descending order: z(30), y(20), x(10). 'y' is second, so rank is 1.

3. Final Answer:

   ZREVRANK scores y returns 1 -> Option C

4. Quick Check:

   ZREVRANK descending zero-based rank = 1 [OK]

Hint: ZREVRANK ranks from highest score, zero-based [OK]

Common Mistakes:

• Mixing ZRANK and ZREVRANK results
• Counting rank starting at 1 instead of 0
• Confusing ascending and descending order