Top-N queries in Redis - Time & Space Complexity

Time Complexity: Top-N queries

O(N)

Understanding Time Complexity

When we ask for the top N items in Redis, we want to know how the time to get those items changes as the data grows.

We want to understand how fast Redis can find the top scores or values as the list gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

# Add scores to a sorted set
ZADD leaderboard 100 "Alice"
ZADD leaderboard 200 "Bob"
ZADD leaderboard 150 "Carol"

# Get top 2 players by score descending
ZREVRANGE leaderboard 0 1 WITHSCORES
    

This code adds players with scores to a sorted set and then retrieves the top 2 players with the highest scores.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Retrieving the top N elements from the sorted set.
• How many times: The operation scans or accesses elements up to N times to return the top N results.

How Execution Grows With Input

Getting the top N items takes time mostly based on N, not the total size of the set.

Input Size (n)	Approx. Operations
10	About 10 operations to get top 10
100	About 10 operations to get top 10
1000	About 10 operations to get top 10

Pattern observation: The time depends on how many top items you want, not on how many total items are in the set.

Final Time Complexity

Time Complexity: O(N)

This means the time to get the top N items grows linearly with N, regardless of the total data size.

Common Mistake

[X] Wrong: "Getting top N items takes longer as the whole set grows bigger."

[OK] Correct: Redis uses a sorted set structure that lets it jump directly to the top scores, so the total size does not slow down fetching the top N.

Interview Connect

Understanding how Redis handles top-N queries shows you know how to work with efficient data structures and can explain performance clearly.

Self-Check

"What if we asked for the bottom N items instead of the top N? How would the time complexity change?"

Practice

1. What Redis command is used to get the top N highest scores from a sorted set?

easy

A. ZRANGE

B. ZREVRANGE

C. ZADD

D. ZREM

Solution

1. Step 1: Understand sorted set ordering

   Redis sorted sets store elements with scores. To get highest scores, we want descending order.

2. Step 2: Identify the correct command

   ZREVRANGE returns elements in descending order by score, perfect for top N queries.

3. Final Answer:

   ZREVRANGE -> Option B

4. Quick Check:

   Top N highest = ZREVRANGE [OK]

Hint: Use ZREVRANGE for top scores in descending order [OK]

Common Mistakes:

• Using ZRANGE which returns lowest scores first
• Confusing ZADD (adds elements) with query commands
• Using ZREM which removes elements

2. Which of the following is the correct syntax to get the top 3 highest scoring members from sorted set players?

easy

A. ZREVRANGE players 1 3

B. ZRANGE players 0 2

C. ZREVRANGE players 0 2

D. ZRANGE players -3 -1

Solution

1. Step 1: Understand index ranges in ZREVRANGE

   Indexes start at 0. To get top 3, use 0 to 2 inclusive.

2. Step 2: Choose correct command and range

   ZREVRANGE returns highest scores first. So ZREVRANGE players 0 2 gets top 3.

3. Final Answer:

   ZREVRANGE players 0 2 -> Option C

4. Quick Check:

   Top 3 highest = ZREVRANGE players 0 2 [OK]

Hint: Use 0 to N-1 indexes with ZREVRANGE for top N [OK]

Common Mistakes:

• Using ZRANGE which returns lowest scores
• Starting index at 1 instead of 0
• Using negative indexes incorrectly

3. Given a sorted set scores with members and scores: {"alice": 50, "bob": 70, "carol": 60}, what is the result of ZREVRANGE scores 0 1 WITHSCORES?

medium

A. ["carol", "60", "alice", "50"]

B. ["alice", "50", "carol", "60"]

C. ["bob", "70", "alice", "50"]

D. ["bob", "70", "carol", "60"]

Solution

1. Step 1: Order members by descending score

   Scores descending: bob(70), carol(60), alice(50).

2. Step 2: Select top 2 with scores

   ZREVRANGE 0 1 returns first two: bob and carol with their scores.

3. Final Answer:

   ["bob", "70", "carol", "60"] -> Option D

4. Quick Check:

   Top 2 with scores = bob(70), carol(60) [OK]

Hint: ZREVRANGE 0 N-1 gets top N in descending order [OK]

Common Mistakes:

• Mixing ascending and descending order
• Forgetting WITHSCORES returns pairs
• Selecting wrong index range

4. You run ZREVRANGE leaderboard 0 4 but get an empty list. What is the most likely cause?

medium

A. The sorted set leaderboard does not exist or is empty

B. The command syntax is incorrect

C. ZREVRANGE only works with hashes, not sorted sets

D. The indexes 0 to 4 are out of range for the sorted set

Solution

1. Step 1: Check command syntax validity

   ZREVRANGE syntax is correct for sorted sets, so syntax is not the issue.

2. Step 2: Understand empty result causes

   If the sorted set does not exist or is empty, ZREVRANGE returns an empty list.

3. Final Answer:

   The sorted set leaderboard does not exist or is empty -> Option A

4. Quick Check:

   Empty result means no data in sorted set [OK]

Hint: Empty list means sorted set missing or empty [OK]

Common Mistakes:

• Assuming syntax error without checking data
• Thinking ZREVRANGE works on hashes
• Believing index out of range causes error instead of empty list

5. You want to get the top 5 players with the lowest scores from a sorted set game_scores. Which command should you use?

hard

A. ZRANGE game_scores 0 4

B. ZRANGE game_scores -5 -1

C. ZREVRANGE game_scores -5 -1

D. ZREVRANGE game_scores 0 4

Solution

1. Step 1: Identify order for lowest scores

   ZRANGE returns elements in ascending order by score, so lowest scores first.

2. Step 2: Select correct range for top 5

   Indexes 0 to 4 select first 5 elements, which are lowest scores.

3. Final Answer:

   ZRANGE game_scores 0 4 -> Option A

4. Quick Check:

   Lowest 5 scores = ZRANGE 0 4 [OK]

Hint: Use ZRANGE 0 N-1 for lowest N scores [OK]

Common Mistakes:

• Using ZREVRANGE which returns highest scores
• Using negative indexes incorrectly
• Confusing ascending and descending order