Build a Trust-Aware BIN Database
Company: Square
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Build a Trust-Aware BIN Database
Implement `process_bin_operations(operations)` for an in-memory database of card-number prefixes. A prefix identifies attributes such as card brand and card type. The function returns the result of every lookup operation, in order.
Each operation is one of:
- `("store", prefix, source, trust, brand, card_type)`
- `("lookup", card_number)`
`prefix`, `source`, `brand`, and `card_type` are strings. For a store, at least one of `brand` or `card_type` is not `None`; the other may be `None`. `trust` is an integer. Every store is a new write, even when its source and values repeat.
For a lookup, resolve `brand` and `card_type` independently:
1. Consider every stored prefix that is a prefix of `card_number` and that supplied the requested field.
2. Prefer the longest matching prefix.
3. Among writes at that prefix, prefer the highest trust.
4. If trust ties, prefer the most recent write.
A write that omits a field must not erase an older value for that field. Return each lookup as `(brand, card_type)`, using `None` for a field with no matching write.
## Constraints
- `1 <= len(operations) <= 200,000`
- Prefixes and card numbers contain only decimal digits.
- `1 <= len(prefix) <= 32`; `len(card_number) <= 64`
- `source` is retained as write metadata; different sources may report the same values.
- Inputs are valid; no format-validation code is required.
## Example behavior
If a six-digit prefix supplies a high-trust brand but no type, and a more specific eight-digit prefix supplies only a type, a matching card number combines the six-digit brand with the eight-digit type. A later equal-trust write wins only for the field it supplies.
## Candidate clarifications
Confirm field-by-field merging, longest-prefix precedence over trust, tie-breaking, whether duplicate values are allowed, and the required complexity for heavy lookup traffic.
Quick Answer: Build an in-memory card-prefix database that resolves brand and card type independently across overlapping writes. Practice combining longest-prefix matching with trust and recency rules while preserving omitted fields and supporting heavy lookup traffic.
Implement process_bin_operations using six parallel operation arrays. A store row supplies a nonempty digit prefix, source, signed-32 trust, and at least one nonempty brand or card_type. The empty string is reserved as the omission sentinel and cannot be a stored brand or card type. A lookup row uses keys[i] as the card number. Resolve brand and type independently by longest matching prefix, then highest trust at that prefix, then most recent equal-trust write. Return [brand, card_type] pairs for lookups, using the reserved empty string for a missing field.
Constraints
- All six operation arrays have equal length from 1 through 200,000; operation_types contains only store or lookup.
- Every stored prefix is a nonempty decimal-digit string of length at most 32; every lookup card number is a possibly empty decimal-digit string of length at most 64.
- -2,147,483,648 <= trust <= 2,147,483,647 for every store row.
- A store supplies at least one nonempty field. Empty brand and card_type strings are reserved for omission and missing lookup output.
- Sources, brands, and card types are compared as exact strings.
Examples
Input: (["lookup"], ["411111"], [""], [0], [""], [""])
Expected Output: [["", ""]]
Explanation: A lookup with no stored prefix has two missing fields.
Input: (["store","lookup"], ["4111","41112222"], ["s",""] , [5,0], ["Visa",""], ["credit",""])
Expected Output: [["Visa", "credit"]]
Explanation: Both fields can come from one matching write.
Hints
- Maintain the trusted winner separately for each field and exact prefix.
- During lookup, search prefix lengths from longest to shortest for each unresolved field.