# Familiar Faces > The same signals keep coming back. Count how often they meet. Canonical URL: Domain: Python · Difficulty: easy · Seniority: L3 ## Problem We're auditing a production log with millions of integer event codes, and we need to know how often the same code recurs across it. Return the number of position pairs that hold the same code. ## Worked solution and explanation ### What this problem really is This is a frequency-to-combinatorics conversion wearing an event-log costume. The real question: can you count equal-value pairs without comparing every position to every other? Two shortcuts tempt you and both are wrong. The brute-force double loop over every (i, j) is correct but O(n^2), and it never finishes on a log with millions of codes. And the tidy 'add one for each repeat' tally undercounts the instant a value shows up three or more times: three copies make three pairs, not two. The fix is to count how many times each code occurs and turn each frequency k into k*(k-1)/2 pairs, in a single linear pass. > **Trick to solving** > > Count how many times each value occurs, then for a value seen k times add `k * (k - 1) // 2`. That is 'k choose 2': the number of ways to pick two of the k positions. Sum it across the distinct values and you never touch a single index pair. > **The same count, incrementally** > > You don't even need the closed form. Scan once, keeping a running count per code; before you increment a code's count, add its current count to the total. Over k copies that adds 0 + 1 + ... + (k - 1), which is exactly k*(k-1)/2. Same O(n), same answer: the two are the same idea written two ways. --- ### Getting there #### Step 1: Tally each value's frequency Walk the list once and tally each value into a dictionary. This is the only pass over the data; everything after works on the tally, not the raw list. #### Step 2: Turn each frequency into a pair count A value seen k times has k*(k-1)//2 unordered pairs among its positions. Integer-divide so the result stays an int. A value seen once contributes 0, which falls out of the formula for free. #### Step 3: Sum across the distinct values Add the per-value pair counts together. That sum is the answer; there is nothing to sort or dedup. --- ### The solution **Frequency tally plus k-choose-2** ```python from collections import Counter def count_good_pairs(nums: list) -> int: total_pairs = 0 for k in Counter(nums).values(): total_pairs += k * (k - 1) // 2 return total_pairs ``` *One pass to tally, one pass over the distinct values to sum the combinations. O(n) overall.* > **Time and space** > > **Time:** O(n) to tally the frequencies plus O(d) to sum over the d distinct values, so O(n) overall. > > **Space:** O(d) for the frequency map, one entry per distinct value. **Brute force (rejected for scale)** Two nested loops over all i < j, incrementing when nums[i] == nums[j]. Correct, but O(n^2): a log with a million entries is 5*10^11 comparisons and never returns inside the time limit. **Frequency + nC2** Tally once, then one term per distinct value. O(n) time, and the combination formula handles a value appearing 2, 3, or 3000 times with the same single line. > **Interviewers watch for** > > Whether you reach for a linear frequency pass or start writing a nested loop, and whether you get three-of-a-kind right (3 pairs, not 2). Naming why the double loop won't scale, and why the per-repeat tally undercounts, is the tell that you understand the count rather than pattern-matching to a brute force. > **Common pitfall** > > Counting a repeated value once per extra copy instead of combinatorially. It looks fine on pairs and doubles, then silently undercounts every value that appears three or more times: five copies give 4 instead of 10. The formula k*(k-1)//2 (or the running-count accumulation) is the guard against it. --- ## Common follow-up questions - What if you needed pairs that sum to a target instead of equal pairs? _(Tests the two-sum hash map approach.)_ - What if the input were a stream and you needed a running pair count? _(Tests incrementally updating the count as each new element arrives (the running-count idea taken online).)_ - What if you needed the actual pairs, not just the count? _(Tests that enumerating pairs is inherently O(n^2) in the worst case.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/familiar_faces) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.