Cracking The Coding Interview Together – Problem 10.10: Rank from Stream

Picture this: You are building a real-time analytics dashboard for a massive multiplayer online game. As players score points, you continuously ingest an incoming stream of integer scores. Periodically, product management asks you a deceptively simple question: "Given a score x, how many players have a score less than or equal to x?"

At first glance, it sounds trivial. Just dump everything into a list, right? But as you scale to millions of concurrent events, your latency spikes, and your CPU pegs at 100%. We have hit a classic data structure bottleneck. Today, we are going to look under the hood of streaming analytics and solve Problem 10.10: Rank from Stream. By the end of this post, you will know how to design an augmented data structure that turns a sluggish search problem into an elegant logarithmic-time masterpiece.

Problem Statement

We need to implement a data structure that supports two primary operations:

• track(int x): Called when a new integer appears in the stream.
• getRankOfNumber(int x): Returns the number of values less than or equal to x (not including x itself, or including it depending on definition—traditionally, the count of elements $\le x$). Let's follow the standard definition from the prompt: the number of values less than or equal to x.

Our operational goals are straightforward: minimize the time complexity of both ingestion and rank lookup while keeping our space footprint reasonable.

Analyze the Problem Together

Let's break down the constraints and naive approaches before jumping into code.

Approach 1: Array or List. If we store incoming numbers in a simple array or list, tracking takes $O(1)$ time (just append). However, finding the rank requires iterating through the entire collection to count elements less than or equal to x, resulting in an $O(n)$ time complexity per query. If we keep the array sorted to use binary search, tracking drops to $O(n)$ due to shifting elements.

Approach 2: Self-Balancing Binary Search Tree (BST). A standard BST gives us $O(\log n)$ average time for both insertion and search. But how do we find the rank? A standard BST node only knows its value, left child, and right child. To find how many elements are less than or equal to x, we would still need to traverse subtrees, which degrades to $O(n)$ in the worst case.

The Aha! Conflict: What if we augment our BST nodes? If every node stores the size of its left subtree (or the total count of nodes in its subtrees), we can accumulate counts as we navigate the tree. This is the exact architectural insight we need.

Questions for the Interviewer

Before writing a single line of code, a senior engineer clarifies edge cases by asking:

1. "Can the stream contain duplicate numbers? If so, how should duplicates affect our rank calculation?"
2. "What is the expected ratio of track() calls to getRankOfNumber() calls? Do we need to optimize for heavy reads or heavy writes?"
3. "Can we assume the dataset fits comfortably in memory, or should we design with disk-based persistence in mind?"
4. "What is the upper bound on the number of elements we expect to ingest?"

Think About the Solution

We will design a custom Binary Search Tree where each node contains:

• val: The integer value.
• leftSize: The number of nodes in the left subtree (plus duplicates, if we handle them via counts).
• left and right child references.

When tracking a new number x:

• If x is less than the current node's value, we increment the current node's leftSize and recurse left.
• If x is greater than or equal to the current node's value, we recurse right.

When querying getRankOfNumber(x):

• If x matches the current node's value, we return the current node's leftSize plus 1 (to account for the node itself, or adjust based on exact definitions).
• If x is less than the current node's value, we search the left subtree.
• If x is greater than the current node's value, our rank includes the current node, its left subtree, and whatever we find in the right subtree.

Write Code and Explain

Here is our production-ready Java implementation:

public class RankTracker {
    
    private static class TreeNode {
        int val;
        int leftSize = 0;
        TreeNode left;
        TreeNode right;
        
        public TreeNode(int val) {
            this.val = val;
        }
        
        public void insert(int x) {
            if (x <= val) {
                leftSize++;
                if (left == null) {
                    left = new TreeNode(x);
                } else {
                    left.insert(x);
                }
            } else {
                if (right == null) {
                    right = new TreeNode(x);
                } else {
                    right.insert(x);
                }
            }
        }
        
        public int getRank(int x) {
            if (x == val) {
                return leftSize;
            }
            if (x < val) {
                if (left == null) return 0;
                return left.getRank(x);
            } else {
                int rightRank = (right == null) ? 0 : right.getRank(x);
                return leftSize + 1 + rightRank;
            }
        }
    }
    
    private TreeNode root = null;
    
    public void track(int x) {
        if (root == null) {
            root = new TreeNode(x);
        } else {
            root.insert(x);
        }
    }
    
    public int getRankOfNumber(int x) {
        if (root == null) return 0;
        return root.getRank(x);
    }
}

Step-by-Step Walkthrough:

1. Node Augmentation: We track leftSize dynamically during insertion. Every time we move left because our new value is smaller than or equal to the current node, leftSize goes up by one.
2. Rank Accumulation: When querying rank, matching x == val immediately gives us all elements in the left subtree (leftSize). If x > val, we know the current node and its entire left subtree are smaller than or equal to x, so we add leftSize + 1 to our running tally before querying the right subtree.

Time & Space Complexity

• Time Complexity:
  • track(int x): $O(\log n)$ on average (balanced tree), $O(n)$ in the worst-case if the tree degrades into a linked list.
  • getRankOfNumber(int x): $O(\log n)$ on average, $O(n)$ in the worst case.
• Space Complexity: $O(n)$ to store n elements in our tree nodes.

Pro-Tip: In a production system, you would want to use a self-balancing tree variant like an AVL tree or Red-Black tree augmented with subtree sizes to guarantee $O(\log n)$ worst-case performance.

Why This Problem Matters (The Senior Perspective)

Augmented data structures are a hallmark of senior-level system design. You will encounter this pattern frequently in database indexing (like B-Trees tracking child pointers and key counts) and metrics aggregation systems (like calculating percentiles in Prometheus or Datadog). Understanding how to inject metadata directly into node structures without breaking invariant properties separates engineers who write code that merely works from engineers who build scalable systems.

Final Thoughts

Problem 10.10 teaches us that standard data structures are often just starting points. By thoughtfully augmenting nodes with aggregate state, we can solve complex range-query problems efficiently. Take some time to implement a self-balancing version of this tree as an exercise. Keep practicing, keep building, and I will see you in the next post!