Familiar Faces

An easy Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
easy
Seniority
L3
Asked in
Citadel

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.

The same signals keep coming back. Count how often they meet.

Example 1

Input:

nums = [1,2,3,1,1,3]

Output:

4

Example 2

Input:

nums = [1,1,1,1]

Output:

6

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.

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
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.

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.

Common follow-up questions