IsFollowing Implementation

Uber social features may need to answer whether a user followed another user at a particular historical snapshot. Each snapshot is represented as a node in a persistent history: it stores one follow or unfollow change and a pointer to the previous snapshot.

Implement is_following(followerId, followeeId, snapId) to return whether followerId follows followeeId in the state represented by snapId. The newest change for a relationship determines its state. If no change for the pair exists in the snapshot's history, return False.

Formal Specification

• followerId and followeeId are integers.
• snapId is either None, representing an empty snapshot, or a dictionary with:
  • id: an integer snapshot identifier
  • change: a dictionary containing followerId, followeeId, and action, where action is either "follow" or "unfollow"
  • parent: the previous snapshot node or None
• Return a boolean.
• Snapshot nodes form a finite singly linked chain ending at None.

Walk from the requested snapshot toward its ancestors. The first matching relationship change is authoritative.