LinkedIn

Professional Networking Platform

Design the core of a professional network: profiles, connection requests, degrees of separation, visibility by degree, a job board with tracked applications, and a feed.

Overview

A professional network has profiles, a graph of accepted connections, a job board and a feed. The interviewer picks this problem because everyone knows the product, so the hour goes to your design: how the graph is stored, how a request becomes a connection without a race, how far a search may walk the graph, and how one rule table decides what a viewer may see. This is a design exercise. It does not describe how any real company builds its system.

The problem tests four things. First, a request has a life cycle (pending, accepted, ignored, withdrawn) and two people can invite each other at the same moment. Second, the degree of separation between two people is a shortest-path question, and a search that walks the whole graph is too slow, so you must bound it. Third, visibility depends on that degree, and it should be one table, not a chain of if statements. Fourth, a job application only moves forward through its statuses, which is a small state machine.

A strong answer names the entities in the first minutes, puts the request and the graph behind one lock, explains bidirectional search capped at three steps, and writes a program a test can drive.

Scoping the problem

Ask these before you draw anything. Each answer changes the design.

Are connections mutual, or can I follow someone one way? — Mutual connections make an undirected graph; follows add a directed edge — Connections are mutual; companies are followed
How far do degrees go? — Bounds the search; beyond the bound the person is out of network — 1st, 2nd and 3rd degree
What does each degree see on a profile? — A visibility rule table — Closer sees more
Who may endorse a skill? — A permission check on the graph — 1st-degree connections only
Can a person apply to the same job twice? — A uniqueness rule with a race — No; one application per person per job
Which application status moves are legal? — A state machine — Forward only; hired and rejected are final
What is in the feed? — Which authors are pulled and how they are ordered — Posts by connections and followed companies, newest first
Must anything survive a restart? — Adds a store; not the core — A follow-up

Core entities

The graph is one object with one lock. Everything that depends on 'how are these two people related' calls it. That keeps the answer to that question in one place, which matters for both correctness and later caching.

A request becomes a connection

A request is a row keyed by (sender, receiver). Accepting it deletes the row and adds the edge in both directions. Ignoring and withdrawing delete the row and record why.

The interesting case is two people inviting each other at the same moment. Without care you end with two pending rows, or with the edge added twice. The code treats the second request as an accept of the first, and does the check and the write under the same lock.

The demo runs this race 50 times with two threads and asserts that x and y are connected and no request is pending.

Degrees of separation

The degree between two people is the length of the shortest path between them in the connection graph. A plain breadth-first search from one side visits every person within three steps. A bidirectional search grows a frontier from each side and stops when they meet, so each side only walks about half the distance: for a cap of three, one side takes two steps and the other takes one.

Plain BFS to depth 3 — b × b × b — about 1,000,000
Bidirectional BFS, two steps from one side and one from the other — b × b + 2 × b — about 10,000

These are order-of-magnitude estimates: real networks are uneven, and friends of friends overlap. The code stops when the two depths add up to three and reports None, which the profile service treats as out of network.

The demo checks the bidirectional answer against a plain BFS for every pair in a random graph of 14 people, so the shortcut is tested, not trusted.

Visibility is a table

What a viewer sees depends only on the degree. That is a dictionary from degree to field names; the profile service looks the degree up and returns those fields.

Yourself, or 1st — name, headline, summary, experience, skills
2nd — name, headline, summary, experience
3rd — name, headline, experience
Out of network (None) — name, headline

Adding a new field or a new rule is one edit to the table. The public help page for LinkedIn defines 1st-degree connections as people who accepted each other's invitation, 2nd-degree as connections of your 1st-degree connections, and 3rd-degree as connections of your 2nd-degree connections. The fields per degree above are this exercise's choice, not the product's.

Applications move forward only

An application is a small state machine. The legal moves live in one dictionary, and advance refuses anything else.

One person may apply once per job. The same person pressing apply twice at once is a check-then-act race on the applications table: both calls can see no application and both insert. So apply holds the board's lock across the check and the insert. The demo runs 20 different people at once and keeps all 20, then one person from 10 threads at once and keeps exactly one.

The feed

The feed for a person is the posts by their 1st-degree connections and the companies they follow, newest first. The code computes it on read: collect the authors, gather their posts, sort by time.

Authors — connections(user) plus follows[user] — one set union
Gather — every post by every author — grows with posts per author
Order — sort by created_at descending, then by id — n log n on the gathered posts

Computing on read is the right first answer. The key questions cover when to precompute instead.

What you will be able to do

Draw the entities and say which one owns the graph and its lock.
Explain the request life cycle and the mutual-invitation race, and show the lock that removes it.
Describe bidirectional BFS capped at three steps and estimate why it is cheaper.
Turn visibility and status rules into tables that the code looks up.
Drive the whole design from a test, including the duplicate-application failure case.

Functional requirements

Profiles with headline, summary, experience and skills; 1st-degree connections may endorse a skill
send_request, accept, ignore and withdraw; a request is one row keyed by (sender, receiver)
degree(a, b) returns 0 to 3, or None when the two are out of network
view(viewer, user_id) returns only the fields the viewer's degree allows
Companies post jobs; people search by title, location and skill, and see jobs ranked by skill overlap
apply(user_id, job_id) once per person per job; statuses move forward only
A feed of posts by connections and followed companies, newest first

Non-functional requirements

Mutual invitations at the same moment connect the pair once and leave nothing pending
Degree queries stop after three steps and walk from both ends, so cost does not grow with the whole network
Visibility and status rules are data tables, so a new rule is an edit, not a new branch
Duplicate applications are refused even when the same person applies from several threads at once
Time is injected, so feed order is exact in tests

Interview questions

Two people invite each other at the same moment. What goes wrong, and how does your code prevent it?
Why bidirectional BFS, and why stop at three steps?
How would you make the graph fast at scale, and keep degree queries fast?
How does visibility stay consistent as rules grow, for example a recruiter view or an open profile?
How would you rank jobs for a person, and how do you keep the ranking swappable?