Top-K IP Addresses from File Records
Updated
Problem statement
You are given a large file with one IP address per line. Your function gets those lines as the array addresses. Every line is a valid IPv4 address in standard form.
Return the k addresses that appear most often, from most to least frequent. If two addresses appear the same number of times, compare them as strings and put the smaller string first. The answer must be exact. An approximate answer (a "heavy hitters" estimate) is not accepted.
Follow-up: a file of several gigabytes
Here the lines are already loaded into addresses so your code can be tested. In the original question, the file is too large for memory. For that case, you may read the file several times from start to end. You may also write temporary partition files to disk, where each address always goes to the same file based on its hash. The goal is to keep in memory only the counts for one partition, plus O(k) space to track the top k. Temporary files on disk do not count as memory. Use enough partitions that the counts for the different addresses in one partition fit in the memory you have.
Function
topKIpAddresses(addresses: String[], k: int) → String[]Examples
Example 1
addresses = ["10.0.0.1","10.0.0.2","10.0.0.1","192.168.1.1","10.0.0.2","10.0.0.1"]k = 2return = ["10.0.0.1","10.0.0.2"]10.0.0.1 appears three times, 10.0.0.2 appears twice, and 192.168.1.1 appears once. The two most frequent addresses are the answer, most frequent first.
Example 2
addresses = ["2.0.0.1","1.0.0.1","3.0.0.1","2.0.0.1","1.0.0.1"]k = 2return = ["1.0.0.1","2.0.0.1"]1.0.0.1 and 2.0.0.1 each appear twice. That is a tie, so they are compared as strings, and the smaller string comes first.
Constraints
1 <= addresses.length <= 200000in the tests.- Every element of
addressesis an IPv4 address: four numbers from0to255joined by dots. A number with more than one digit never starts with a zero. 1 <= k <=the number of different addresses.- The answer has exactly
kaddresses. - In the large-file follow-up, the answer must still be exact. You may read the file several times and write temporary partition files.
More Google Onsite Interview questions
- Evaluate a Nested Math ExpressionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Distinct Subset SumsONSITE INTERVIEW · Seen Nov 2026
- Playlist With No Same Artist in a RowONSITE INTERVIEW · Seen Nov 2026
- Route Pattern MatcherPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Delete Nodes and Return Forest RootsONSITE INTERVIEW · Seen Nov 2026
- Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- First and Last Target Position in a Mountain ArrayONSITE INTERVIEW · Seen Nov 2026
- Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
- Batched Subsequence Word MatchesONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Mutual-Friend RecommendationsMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
- Top K Frequent ElementsAmazon · OA · PHONE SCREEN
- Top K Frequent WordsBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Worst-Performing Ads by CTR in a Campaign TreeUber · PHONE SCREENUber interview questions
- Time-Aware Search AutocompleteRoblox · PHONE SCREENRoblox interview questions
- Top-K Values per Key in MapReduceDatabricks · PHONE SCREENDatabricks interview questions
- Top K Frequent ElementsCapgemini · ONSITE INTERVIEWCapgemini interview questions
- Top-K IP Addresses Across Log FilesRender · PHONE SCREEN
- Top K Frequent Values Across Key-Partitioned ShardsJP Morgan Chase · PHONE SCREENJP Morgan Chase interview questions
- Top K Frequent Elements with Larger-Value Tie BreakOracle · ONSITE INTERVIEWOracle interview questions