Another java solution


  • 0
    F

    First, create two class named BoundedStack and BoundedPriorityQueue which can stores at most 10 elements:

    class BoundedStack<E> extends LinkedList<E> {
        public static final int SIZE = 10;
    
        @Override
        public void push(E e) {
            if (size() == SIZE) {
                removeLast();
                super.push(e);
            } else {
                super.push(e);
            }
        }
    }
    
    class BoundedPriorityQueue<E> extends PriorityQueue<E> {
        public static final int SIZE = 10;
    
        public BoundedPriorityQueue(Comparator<? super E> comparator) {
            super(comparator);
        }
    
        @Override
        public boolean offer(E e) {
            if (size() == SIZE) {
                if (comparator().compare(peek(), e) < 0) {
                    poll();
                    return super.offer(e);
                } else {
                    return true;
                }
            } else {
                return super.offer(e);
            }
        }
    }
    

    Next, create a class named Tweet which contains a timestamp:

    class Tweet {
        public static final Comparator<Tweet> comparator = (o1, o2) -> Long.compare(o1.timestamp, o2.timestamp);
        private static long counter = Long.MIN_VALUE;
        private final long timestamp = counter++;
        private int tweetId;
    
        public Tweet(int tweetId) {
            this.tweetId = tweetId;
        }
    
        public int getTweetId() {
            return tweetId;
        }
    }
    

    Finally, implements Twitter, one thing to notice is that you cannot follow or unfollow yourself:

    public class Twitter {
        Map<Integer, Set<Integer>> users;
        Map<Integer, BoundedStack<Tweet>> tweets;
        Function<Integer, Set<Integer>> function = key -> {
            HashSet<Integer> hashSet = new HashSet<>();
            hashSet.add(key);
            return hashSet;
        };
    
        public Twitter() {
            users = new HashMap<>();
            tweets = new HashMap<>();
        }
    
        public void postTweet(int userId, int tweetId) {
            tweets.computeIfAbsent(userId, key -> new BoundedStack<>()).push(new Tweet(tweetId));
        }
    
        public List<Integer> getNewsFeed(int userId) {
            Set<Integer> set = users.computeIfAbsent(userId, function);
            BoundedPriorityQueue<Tweet> priorityQueue = new BoundedPriorityQueue<>(Tweet.comparator);
            set.stream().filter(tweets::containsKey).forEach(integer -> tweets.get(integer).forEach(priorityQueue::offer));
            LinkedList<Integer> result = new LinkedList<>();
            while (!priorityQueue.isEmpty()) {
                result.push(priorityQueue.poll().getTweetId());
            }
            return result;
        }
    
        public void follow(int followerId, int followeeId) {
            if (followerId == followeeId) {
                return;
            }
            users.computeIfAbsent(followerId, function).add(followeeId);
        }
    
        public void unfollow(int followerId, int followeeId) {
            if (followerId == followeeId) {
                return;
            }
            if (users.containsKey(followerId)) {
                users.get(followerId).remove(followeeId);
            }
        }
    }
    

  • 0
    V
    set.stream().filter(integer -> tweets.containsKey(integer)).forEach(integer -> tweets.get(integer).forEach(priorityQueue::offer));
    

    How to calculate the time complexity?


  • 0
    F

    @VectorChange sorry, I do not know the details of java stream, but it is very slow to use stream, one reason to use stream is that it can make my code short and easy to understand, but I believe that the efficiency will be improved in the later jdk versions. besides java stream, I use priorityQueue to get the top k elements, as detailed implementation information in the api:

    • Implementation note: this implementation provides O(log(n)) time for the enqueuing and dequeuing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

    so its time comlexity is O(nlog(n))


  • 0
    V

    @fhqplzj Thanks for your explanation.


Log in to reply
 

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