Solve pair-counting and account-merging problems
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem A — Count qualifying products
You are given two integer arrays `A` and `B`, and an integer `T`.
For each element `a` in `A`, count how many elements `b` in `B` satisfy:
\[
a \times b \ge T
\]
Return an array `ans` of length `len(A)` where `ans[i]` is the count for `A[i]`.
### Input/Output
- **Input:** integers arrays `A`, `B`, integer `T` (all non-negative).
- **Output:** integer array `ans`.
### Constraints (typical interview scale)
- `1 <= len(A), len(B) <= 1e5`
- `0 <= A[i], B[i] <= 1e5`
- `0 <= T <= 1e10`
---
## Problem B — Merge user accounts by shared identifiers
You are given a list of accounts. Each account is a list of strings:
- The first string is a **user name**.
- The remaining strings are **identifiers** (e.g., emails).
Two accounts belong to the same real user if they share **at least one identifier** (directly or transitively). Merge all accounts that belong to the same user.
### Output format
Return the merged accounts as a list where each merged account is:
- `[name, id1, id2, ...]`
- Identifiers must be **unique** and **sorted lexicographically**.
- You may output merged accounts in any order.
### Notes
- If multiple accounts with different names get connected via identifiers, assume the name for the merged result can be taken from any one of the connected accounts (state your choice).
### Constraints (typical interview scale)
- `1 <= number_of_accounts <= 1e4`
- Total number of identifiers across all accounts `<= 1e5`
Quick Answer: This question evaluates proficiency in algorithmic problem-solving for pair counting and entity consolidation, focusing on efficient array processing, threshold-based counting, and merging records by shared identifiers, and it falls under the Coding & Algorithms domain.
Count Products Meeting a Threshold
For each a in A, count how many b in B satisfy a * b >= T. Inputs are non-negative integers.
Constraints
- len(A), len(B) can be up to 1e5
- Values are non-negative
Examples
Input: ([2, 4, 0], [1, 3, 5], 10)
Expected Output: [1, 2, 0]
Input: ([0, 1], [0, 2], 0)
Expected Output: [2, 2]
Input: ([5], [], 3)
Expected Output: [0]
Hints
- Sort B and binary-search the smallest b that works for each a.
Merge Accounts by Shared Identifiers
Each account is [name, id1, id2, ...]. Merge accounts connected by shared identifiers. Identifiers in each merged account are unique and sorted. If connected accounts have different names, choose the lexicographically smallest name; sort merged accounts deterministically by name and identifiers.
Examples
Input: ([['John', 'a@mail', 'b@mail'], ['John', 'b@mail', 'c@mail'], ['Mary', 'z@mail']],)
Expected Output: [['John', 'a@mail', 'b@mail', 'c@mail'], ['Mary', 'z@mail']]
Input: ([['B', 'x'], ['A', 'x', 'y'], ['C', 'q']],)
Expected Output: [['A', 'x', 'y'], ['C', 'q']]
Input: ([['Solo'], ['Solo2']],)
Expected Output: [['Solo'], ['Solo2']]
Hints
- Use union-find on identifiers.
- Sort the final identifiers to make output deterministic.