My ACC solution using link list and priority queue n-way merge


  • 0

    My solution storing users feeds as a link list, then using a priority queue to merge on request. O(1) post, O(1 * follower) feed generation.

    public class Twitter {
        static class Feed {
            static class Link {
                Integer value;
                Integer timestamp;
                Link next;
                Link previous;
                Link(Integer value, Integer timestamp) {
                    this.value = value;
                    this.timestamp = timestamp;
                }
                
                Link addNext(Link link) {
                    if (this.next != null) {
                        this.next.previous = link;
                        link.next = this.next;
                    }
                    
                    this.next = link;
                    link.previous = this;
                    
                    return link;
                }
                
                void unlink() {
                    if (this.next != null) 
                        this.next.previous = this.previous;
                    if (this.previous != null) 
                        this.previous.next = this.next;
                        
                    this.next = null;
                    this.previous = null;
                }
            }
            
            Link head = new Link(null, null);
            Link tail = head.addNext(new Link(null, null));
            
            int size = 0;
            void add(int id, int timestamp) {
                head.addNext(new Link(id, timestamp));
                if (++size > 10) {
                    tail.previous.unlink();
                    size--;
                }
            }
            
            boolean isEmpty() {
                return size == 0;
            }
        }
        
        class User {
            Set<Integer> following = new HashSet<>();
            Feed myFeed = new Feed();
            
            void post(int tweet, int timestamp) {
                myFeed.add(tweet, timestamp);
            }
        
            void follow(int followee) {
                this.following.add(followee);
            }
            
            void unfollow(int followee) {
                this.following.remove(followee);
            }
            
            List<Feed.Link> feedHeads() {
                List<Feed.Link> feeds = new ArrayList<>();
                
                if (!myFeed.isEmpty()) feeds.add(myFeed.head.next);
                for (int person : following) {
                    User user = getUser(person);
                    if (!user.myFeed.isEmpty()) {
                        feeds.add(user.myFeed.head.next);
                    }
                }
                
                return feeds;
            }
        }
        
        Map<Integer, User> users = new HashMap<>();
    
        /** Initialize your data structure here. */
        public Twitter() {
            
        }
        
        User getUser(int userId) {
            if (!users.containsKey(userId)) {
                users.put(userId, new User());
            }
            
            return users.get(userId);
        }
        
        /** Compose a new tweet. */
        int timestamp = 0;
        public void postTweet(int userId, int tweetId) {
            getUser(userId).post(tweetId, timestamp++);
        }
        
        
        
        /** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
        public List<Integer> getNewsFeed(int userId) {
            List<Integer> items = new ArrayList<>();
            PriorityQueue<Feed.Link> queue = new PriorityQueue<>((lhs, rhs) -> rhs.timestamp - lhs.timestamp);
            for (Feed.Link link : getUser(userId).feedHeads()) {
                queue.add(link);
            }
            
            while (!queue.isEmpty() && items.size() < 10) {
                Feed.Link link = queue.poll();
                items.add(link.value);
                
                if (link.next.value != null) {
                    queue.add(link.next);
                }
            }
            
            return items;
        }
        
        /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
        public void follow(int followerId, int followeeId) {
            if (followerId != followeeId) {
                getUser(followerId).follow(followeeId);
            }
        }
        
        /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
        public void unfollow(int followerId, int followeeId) {
            getUser(followerId).unfollow(followeeId);
        }
    }

  • 0
    X

    The time complexity of getNewsFeed() is O(nlogn) instead of O(n), where n is the number of the user followed by current user, because you need O(nlogn) to establish the priority queue.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.