Stack Overflow: questions and answers

Design a question-and-answer site. Users ask questions with tags, post answers and comments, vote once per post, earn reputation by clear rules, accept an answer, and search questions by tag.

Design the core of a Stack Overflow style site. Users ask questions and tag them, other users answer and comment, anyone can upvote or downvote a question or an answer once, the asker can accept one answer, and reputation changes by fixed rules. Users must be able to find questions by tag.

Questions to ask first

  • What can be voted on? Assume questions and answers, one vote per user per post, up or down. Comments take no votes.
  • Can a user vote on their own post? Assume no. The call is refused.
  • How does reputation change? Assume a fixed table. An upvote on a question gives its author 5, and on an answer 10. A downvote takes 2 from the author and 1 from the voter. An accepted answer gives its author 15 and the asker 2.
  • Can reputation go negative? Assume no. It never goes below 1.
  • How many answers can be accepted? Assume one per question, chosen by the asker, and it cannot be changed. Changing it is an extension.
  • How are tags matched? Assume case does not matter, a question has 1 to 3 tags, and results show the highest score first.

Requirements

  • Register users. Each user has a reputation that starts at 1.
  • Ask a question with a title and 1 to 3 tags. Post answers to it, and comments on a question or an answer.
  • Upvote or downvote a question or an answer. A user can vote once per post and never on their own post.
  • Change reputation by the stated rules, with a floor of 1.
  • Let the asker accept one answer, and show the accepted answer first.
  • Search questions by tag, best score first.

Out of scope

  • Login, profiles, badges and bounties.
  • Editing or deleting posts, and a vote history.
  • Full text search, closing duplicates and moderation.

Entities

  • User: name, reputation -> change(points)
  • Post: author, votes, comments -> addVote(user, direction), score(), addComment()
  • Question (a Post): title, tags, answers, accepted answer -> addAnswer(), accept()
  • Answer (a Post): the question it belongs to
  • Comment: author, text
  • ReputationEvent: QUESTION_UPVOTED, ANSWER_UPVOTED, POST_DOWNVOTED, ANSWER_ACCEPTED
  • ReputationPolicy: the points table -> forAuthor(event), forActor(event)
  • TagIndex: tag to questions -> add(question), find(tag)
  • QaService: the entry point -> ask(), answer(), comment(), vote(), accept(), searchByTag()

Classes in the model design

  • User (class)
  • Post (abstract)
  • Question (class)
  • Answer (class)
  • Comment (class)
  • ReputationEvent (enum)
  • ReputationPolicy (interface)
  • DefaultReputationPolicy (class)
  • TagIndex (class)
  • QaService (class)

The main use case, step by step

  1. Ravi has answered Asha's question, and Kabir upvotes the answer. The client calls `QaService.vote("kabir", "A1", 1)`.
  2. The service looks up the user and the post. A missing one returns NO_USER or NO_POST. A direction other than +1 or -1 returns INVALID. A vote on your own post returns OWN_POST.
  3. It calls `post.addVote(kabir, 1)`. The post keeps one entry per voter, so a second vote by Kabir on this post is refused and the service returns ALREADY_VOTED. Nothing else has changed yet.
  4. The vote was accepted, so the service asks the answer for its event. An `Answer` returns ANSWER_UPVOTED. A `Question` returns QUESTION_UPVOTED, and a downvote always uses POST_DOWNVOTED.
  5. The service asks the `ReputationPolicy` for the points. For ANSWER_UPVOTED, the author gets 10 and the voter gets 0. It calls `change()` on each user.
  6. `User.change` adds the points and raises the result to 1 if it fell below 1. Ravi goes from 1 to 11.
  7. Later, Asha accepts the answer. The service checks that Asha asked the question and that no answer is accepted yet. It stores the answer on the question, and the policy gives Ravi 15 and Asha 2.

Patterns used

  • Inheritance for shared behaviour: Question and Answer extend Post. Post holds the author, the votes and the comments.. Questions and answers are voted on and commented on in the same way. The code is written once in Post. Each subclass adds only what is its own: a title and tags, or a link to its question.
  • Strategy: ReputationPolicy with DefaultReputationPolicy, a table of points per ReputationEvent.. Reputation rules change often, and a site may want different rules for a different community. The service asks the policy for numbers and never contains them.
  • Index: TagIndex keeps a map from a lower-case tag to its questions.. A search by tag reads one map entry. Scanning every question would get slower as the site grows.

Key code

Posts, votes and the one-vote guard

public abstract class Post {
    private final String id;
    private final User author;
    private final Map<User, Integer> votes = new HashMap<>();    // voter -> +1 or -1
    private final List<Comment> comments = new ArrayList<>();

    protected Post(String id, User author) { this.id = id; this.author = author; }

    public User author() { return author; }
    public int score() { return votes.values().stream().mapToInt(Integer::intValue).sum(); }
    public void addComment(Comment c) { comments.add(c); }

    /** One vote per user per post. A second vote, up or down, is refused. */
    public boolean addVote(User voter, int direction) {
        return votes.putIfAbsent(voter, direction) == null;
    }

    public abstract ReputationEvent upvoteEvent();
}

public final class Question extends Post {
    private final List<Answer> answers = new ArrayList<>();
    private Answer accepted;

    public Question(String id, User author, String title, List<String> tags) { super(id, author); /* store title and tags */ }

    public Answer accepted() { return accepted; }
    public void accept(Answer a) { accepted = a; }
    public void addAnswer(Answer a) { answers.add(a); }

    @Override public ReputationEvent upvoteEvent() { return ReputationEvent.QUESTION_UPVOTED; }
}

public final class Answer extends Post {
    private final Question question;

    public Answer(String id, User author, Question question) { super(id, author); this.question = question; }

    public Question question() { return question; }

    @Override public ReputationEvent upvoteEvent() { return ReputationEvent.ANSWER_UPVOTED; }
}

The reputation policy and the floor

public enum ReputationEvent { QUESTION_UPVOTED, ANSWER_UPVOTED, POST_DOWNVOTED, ANSWER_ACCEPTED }

public interface ReputationPolicy {
    /** Points for the post's author (for ANSWER_ACCEPTED: the answer's author). */
    int forAuthor(ReputationEvent event);

    /** Points for whoever acted: the voter, or for ANSWER_ACCEPTED the asker. */
    int forActor(ReputationEvent event);
}

public final class DefaultReputationPolicy implements ReputationPolicy {
    @Override public int forAuthor(ReputationEvent event) {
        switch (event) {
            case QUESTION_UPVOTED: return 5;
            case ANSWER_UPVOTED: return 10;
            case POST_DOWNVOTED: return -2;
            default: return 15;
        }
    }

    @Override public int forActor(ReputationEvent event) {
        switch (event) {
            case POST_DOWNVOTED: return -1;
            case ANSWER_ACCEPTED: return 2;
            default: return 0;
        }
    }
}

public final class User {
    private int reputation = 1;

    /** Reputation never goes below 1. */
    public void change(int points) { reputation = Math.max(1, reputation + points); }
    public int reputation() { return reputation; }
}

Voting and accepting in the service

public class QaService {
    public synchronized String vote(String userName, String postId, int direction) {
        User voter = users.get(userName);
        if (voter == null) return "NO_USER";
        Post post = posts.get(postId);
        if (post == null) return "NO_POST";
        if (direction != 1 && direction != -1) return "INVALID";
        if (post.author() == voter) return "OWN_POST";
        if (!post.addVote(voter, direction)) return "ALREADY_VOTED";

        ReputationEvent event = direction == 1 ? post.upvoteEvent() : ReputationEvent.POST_DOWNVOTED;
        post.author().change(policy.forAuthor(event));
        voter.change(policy.forActor(event));
        return "OK";
    }

    public synchronized String accept(String userName, String answerId) {
        User asker = users.get(userName);
        if (asker == null) return "NO_USER";
        if (!(posts.get(answerId) instanceof Answer)) return "NO_ANSWER";
        Answer answer = (Answer) posts.get(answerId);
        Question question = answer.question();
        if (question.author() != asker) return "NOT_ASKER";
        if (question.accepted() != null) return "ALREADY_ACCEPTED";
        question.accept(answer);
        if (answer.author() != asker) {                          // accepting your own answer earns nothing
            answer.author().change(policy.forAuthor(ReputationEvent.ANSWER_ACCEPTED));
            asker.change(policy.forActor(ReputationEvent.ANSWER_ACCEPTED));
        }
        return "OK";
    }
}

Deep dives

Allowing one vote per user

Weak: Disable the vote button in the screen and trust it. A second request from a script or a second tab still counts. Or keep a list of voters and scan it on every vote, which gets slower with each vote.

Good: Keep a Map<User, Integer> on the post, from voter to direction. putIfAbsent returns something only if the user had already voted, so the check and the insert are one step. The score is the sum of the values.

Great: Make the check the gate for everything else. The service changes reputation only when addVote says the vote is new, so a refused vote can never move any reputation. Run the service method under one lock, or use a ConcurrentHashMap on the post, so two simultaneous votes by the same user cannot both pass. Write a test with many threads.

Trade-off: Refusing a second vote is simple, but real sites let users change or withdraw a vote. That needs the old direction, and an undo of the earlier reputation change, which is why the policy and the votes should stay separate. Mention it as an extension.

Where the reputation rules live

Weak: Write the numbers inside vote() and accept(): author.reputation += 10. A change to a number means a code search. The floor of 1 is forgotten in one of the places, and a user reaches zero or less.

Good: Put the numbers in named constants in one class, and add the points through a User.change method that applies the floor. The rules are easy to find, and the floor lives in one method.

Great: Name the moments that matter as a ReputationEvent enum, and put the points for each in a ReputationPolicy. A post only says which event an upvote is, because a question and an answer are worth different points. The service asks the policy for the author's points and the actor's points. Rules change in one class, and a test can supply a different policy.

Trade-off: A policy interface adds a class and a level of indirection, which is more than a few constants need. It pays off when the rules differ by community or change often. If an interviewer says "keep it simple", say that constants plus change() is enough, and show how you would grow it.

Searching by tag

Weak: Loop over every question and check its tags on each search. It is correct for ten questions and slow for a million. Case also matters by accident: a search for Java misses java.

Good: Keep a Map<String, List<Question>> from tag to questions, filled when a question is asked. A search reads one entry. Make every tag lower case on the way in and on the way out so case never matters.

Great: Put the map in its own TagIndex class, so the service does not know how tags are stored. Sort the found questions when you return them, by score and then by age, with a comparator that uses the question number and not the id text, because "Q10" sorts before "Q2" as text. Reject a question with no tags or more than three.

Trade-off: Sorting at read time costs more as a tag grows, but scores change with every vote, so a stored order would go stale. For a small site, sort on read. For a large one, keep a top-N list per tag and refresh it in the background.

Now add one more feature

  • Now let the asker change the accepted answer. What changes? `Question.accept` replaces the old answer. The service reverses the 15 points of the old answer's author and gives them to the new one. The asker's 2 points are not given twice. The policy gives the numbers, so only the service method changes.
  • Now let a user change or withdraw a vote. What changes? `Post` stores the direction per voter, so `addVote` becomes `setVote` and returns the old direction. The service reverses the earlier reputation change and then applies the new one. This is why the points live in a policy and not in the post.
  • Now add badges, such as 'first answer' or 'reputation 100'. What changes? Publish an event after each reputation change, and let a `BadgeAwarder` listen to it. This is the Observer pattern, and the vote and accept code do not change.
  • Now add editing with a history. What changes? `Post` keeps a list of `Revision` objects, newest last. An edit adds a revision and never overwrites one, so the history stays complete.
  • Now add a rule that a user needs reputation to downvote. What changes? Add a method `canPerform(user, action)` to the policy, and call it in `vote()` before `addVote`. A refused downvote returns a new code and changes nothing.

What each level is expected to show

SDE-1: Users, questions, answers and comments, with Question and Answer sharing a Post class. One vote per user per post, the stated reputation rules, accepting an answer, and search by tag. Clear return codes for bad calls. A `main` that replays one question end to end is enough.

SDE-2: Everything at SDE-1, plus a reputation policy with a floor in one place, an index for tags, a guard that makes the vote check and the reputation change one atomic step, and correct ordering of results. Discuss changing votes, changing the accepted answer and badges as extensions.

Common mistakes

  • Writing the reputation numbers inside `vote()` and `accept()`, so a rule change means editing several methods.
  • Changing reputation before checking the vote guard, so a refused second vote still moves reputation.
  • Forgetting the floor, so reputation goes to zero or below for a user who is downvoted at 1.
  • Making separate vote logic for questions and for answers, instead of one Post class that both extend.
  • Searching tags by scanning every question and comparing text with case, so `Java` and `java` give different results.
  • Sorting ids as text, so "Q10" comes before "Q2".
  • Letting a user vote on their own post, or letting anyone but the asker accept an answer.

Lessons behind this answer