Google 24秋招phone interview

Google Phone Interview 面经分享 在最近的 Google 电话面试中，我被要求解决一个有趣的算法问题。以下是这次面试中遇到的问题和解决方案，帮助大家更好地准备 Google 的技术面试。

问题: Top Talkative Users 描述: 给定一个日志文件，找出对话最多的前 N 个用户。 样例输入:

10:00 <john> hi!
10:01 <maria> hello!
10:07 <john> can you link the design?

输出

john: 6 words
maria: 1 word

class UserWordCount {
    String username;
    int wordCount;
}

public List<UserWordCount> parseLog(String filepath) {
    // Implemented for you
}

public List<String> getTopNTalkativeUsers(String filepath, int N) {
    List<UserWordCount> parsedCounts = parseLog(filepath);
    Map<String, Integer> userWordCounts = new HashMap<>();
    for (UserWordCount count : parsedCounts) {
        userWordCounts.put(count.username, userWordCounts.getOrDefault(count.username, 0) + count.wordCount);
    }
    
    PriorityQueue<UserWordCount> userHeap = new PriorityQueue<>((user1, user2) -> {
        if (user1.wordCount == user2.wordCount) {
            return user1.username.compareTo(user2.username);
        }
        return user2.wordCount - user1.wordCount;
    });

    for (Map.Entry<String, Integer> entry : userWordCounts.entrySet()) {
        userHeap.offer(new UserWordCount(entry.getKey(), entry.getValue()));
        if (userHeap.size() > N) {
            userHeap.poll();
        }
    }

    List<String> result = new ArrayList<>();
    while (!userHeap.isEmpty()) {
        result.add(userHeap.poll().username);
    }

    Collections.reverse(result);
    return result;
}