LinkedIn (Social Graph)

// ─── JAVA BLUEPRINT ──────────────────────────────────────────────────────────
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.*;

class User {
    private final String id;
    private final String name;
    private final Set<String> connectionIds = ConcurrentHashMap.newKeySet();
    private final Set<String> skills = ConcurrentHashMap.newKeySet();

    public User(String id, String name) {
        this.id = id;
        this.name = name;
    }

    public String getId() { return id; }
    public String getName() { return name; }
    public Set<String> getConnectionIds() { return connectionIds; }
    public Set<String> getSkills() { return skills; }

    public void addConnection(String userId) { connectionIds.add(userId); }
    public void addSkill(String skill) { skills.add(skill); }
}

interface GraphObserver {
    void onConnectionEstablished(User u1, User u2);
}

class NetworkNotifier implements GraphObserver {
    @Override
    public void onConnectionEstablished(User u1, User u2) {
        System.out.println(String.format("[Notification] %s and %s are now connected!", u1.getName(), u2.getName()));
    }
}

class ConnectionGraph {
    private final Map<String, User> users = new ConcurrentHashMap<>();
    private final List<GraphObserver> observers = new CopyOnWriteArrayList<>();
    private final ReentrantLock lock = new ReentrantLock();

    public void addUser(User u) { users.put(u.getId(), u); }
    public User getUser(String id) { return users.get(id); }
    public Collection<User> getAllUsers() { return users.values(); }
    public void addObserver(GraphObserver obs) { observers.add(obs); }

    public void addUndirectedConnection(String id1, String id2) {
        lock.lock();
        try {
            User u1 = users.get(id1);
            User u2 = users.get(id2);
            if (u1 != null && u2 != null) {
                u1.addConnection(id2);
                u2.addConnection(id1);
                for (GraphObserver obs : observers) {
                    obs.onConnectionEstablished(u1, u2);
                }
            }
        } finally {
            lock.unlock();
        }
    }
}

// ─── STRATEGY PATTERN (PROFILE RECOMMENDATION) ───────────────────────────────
interface RecommendationStrategy {
    List<User> recommend(String userId, ConnectionGraph graph);
}

class MutualConnectionsRecommendationStrategy implements RecommendationStrategy {
    @Override
    public List<User> recommend(String userId, ConnectionGraph graph) {
        User user = graph.getUser(userId);
        if (user == null) return Collections.emptyList();

        Map<String, Integer> mutualCounts = new HashMap<>();
        Set<String> directConnections = user.getConnectionIds();

        for (String connId : directConnections) {
            User friend = graph.getUser(connId);
            if (friend == null) continue;

            for (String secondDegreeId : friend.getConnectionIds()) {
                if (secondDegreeId.equals(userId) || directConnections.contains(secondDegreeId)) {
                    continue; // Skip self and direct connections
                }
                mutualCounts.put(secondDegreeId, mutualCounts.getOrDefault(secondDegreeId, 0) + 1);
            }
        }

        List<Map.Entry<String, Integer>> sorted = new ArrayList<>(mutualCounts.entrySet());
        sorted.sort((a, b) -> Integer.compare(b.getValue(), a.getValue()));

        List<User> recommendations = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : sorted) {
            User recUser = graph.getUser(entry.getKey());
            if (recUser != null) recommendations.add(recUser);
        }
        return recommendations;
    }
}

// ─── OPTIMIZED TRAVERSAL (BIDIRECTIONAL BFS) ──────────────────────────────────
class DegreeOfSeparationService {
    private final ConnectionGraph graph;

    public DegreeOfSeparationService(ConnectionGraph graph) {
        this.graph = graph;
    }

    public int getDegree(String startId, String targetId) {
        if (startId.equals(targetId)) return 0;

        Map<String, Integer> visitedStart = new HashMap<>();
        Map<String, Integer> visitedTarget = new HashMap<>();
        Queue<String> queueStart = new LinkedList<>();
        Queue<String> queueTarget = new LinkedList<>();

        queueStart.add(startId);
        visitedStart.put(startId, 0);

        queueTarget.add(targetId);
        visitedTarget.put(targetId, 0);

        while (!queueStart.isEmpty() && !queueTarget.isEmpty()) {
            int degree = searchLevel(queueStart, visitedStart, visitedTarget);
            if (degree != -1) return degree;

            degree = searchLevel(queueTarget, visitedTarget, visitedStart);
            if (degree != -1) return degree;
        }

        return -1;
    }

    private int searchLevel(Queue<String> queue, Map<String, Integer> selfVisited, Map<String, Integer> otherVisited) {
        int levelSize = queue.size();
        for (int i = 0; i < levelSize; i++) {
            String curr = queue.poll();
            int currDist = selfVisited.get(curr);

            User u = graph.getUser(curr);
            if (u == null) continue;

            for (String neighbor : u.getConnectionIds()) {
                if (otherVisited.containsKey(neighbor)) {
                    return currDist + 1 + otherVisited.get(neighbor);
                }
                if (!selfVisited.containsKey(neighbor)) {
                    selfVisited.put(neighbor, currDist + 1);
                    queue.add(neighbor);
                }
            }
        }
        return -1;
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("=== LinkedIn Social Graph ===");
        ConnectionGraph graph = new ConnectionGraph();
        graph.addObserver(new NetworkNotifier());

        User u1 = new User("1", "Alice");
        User u2 = new User("2", "Bob");
        User u3 = new User("3", "Charlie");
        User u4 = new User("4", "David");

        graph.addUser(u1);
        graph.addUser(u2);
        graph.addUser(u3);
        graph.addUser(u4);

        // Connections: Alice - Bob - Charlie - David
        graph.addUndirectedConnection("1", "2");
        graph.addUndirectedConnection("2", "3");
        graph.addUndirectedConnection("3", "4");

        // Degree of separation
        DegreeOfSeparationService degreeService = new DegreeOfSeparationService(graph);
        int degree = degreeService.getDegree("1", "4"); // Should be 3 (Alice -> Bob -> Charlie -> David)
        System.out.println("Degree of Separation (Alice to David): " + degree);

        // Mutual Connection Recommendations
        RecommendationStrategy recStrategy = new MutualConnectionsRecommendationStrategy();
        List<User> recommendations = recStrategy.recommend("1", graph);
        System.out.print("Recommendations for Alice: ");
        for (User u : recommendations) {
            System.out.print(u.getName() + " ");
        }
        System.out.println();
    }
}