Find the second most frequent tag
Company: SoFi
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a list of strings in the following repeating order:
`[id1, name1, tag1, id2, name2, tag2, ...]`
So every 3 consecutive elements describe one record: `(id, name, tag)`.
Return the tag that is the **second most frequent** among all records’ tags.
Tie/edge-case rules:
1. If there is **no** “second most frequent” tag because **all tags have the same count** (i.e., there is only one distinct frequency), return `"notag"`.
2. If there are **multiple** tags tied for second most frequent, return the one whose **first appearance in the input list** occurs earliest.
Constraints/expectations:
- Run time should be O(n).
- You may assume the input length is a multiple of 3.
Example:
Input: `["1","A","x","2","B","y","3","C","y","4","D","x","5","E","z"]`
Counts: `x=2, y=2, z=1` → second most frequent is `z` → return `"z"`.
Write a function to compute the required tag.
Quick Answer: This question evaluates a candidate's ability to perform frequency analysis and stable tie-breaking on a linear sequence, exercising skills in hashing, counting, and handling edge cases such as equal frequencies.
You are given a flat list of strings in repeating groups of 3:
[id1, name1, tag1, id2, name2, tag2, ...]
Each group represents one record: (id, name, tag).
Return the tag that is the second most frequent among all record tags.
Important rules:
1. "Second most frequent" means the second highest distinct frequency. For example, if counts are x=2, y=2, z=1, then the highest frequency is 2 and the second highest distinct frequency is 1, so the answer is z.
2. If there is no second most frequent tag because all tags have the same count, return "notag".
3. If multiple tags are tied for the second most frequent count, return the one whose first appearance in the input list is earliest.
You may ignore ids and names when solving the problem.
Constraints
- 0 <= len(data) <= 3 * 10^5
- len(data) % 3 == 0
- All elements of data are strings
- Expected time complexity: O(n), where n is the length of data
Examples
Input: (['1','A','x','2','B','y','3','C','y','4','D','x','5','E','z'],)
Expected Output: 'z'
Explanation: The tag counts are x=2, y=2, z=1. The distinct frequencies are 2 and 1, so the second most frequent count is 1. Therefore the answer is 'z'.
Input: (['1','A','red','2','B','blue','3','C','red','4','D','blue'],)
Expected Output: 'notag'
Explanation: The counts are red=2 and blue=2. All tags have the same frequency, so there is no second most frequent tag.
Hints
- You only need to inspect elements at indices 2, 5, 8, ... because those are the tags.
- Use one hash map for counts and another for each tag's first position, then find the top two distinct frequencies without sorting all tags.