How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Google during technical interviews.

Match payments to invoices by memo or amount

Quick Overview

This Coding & Algorithms question for a Data Scientist evaluates string parsing and pattern matching, keyed and numeric record matching, date-based tie-breaking, and algorithmic complexity analysis, and is commonly asked to test handling of messy input formats and deterministic reconciliation rules.

You are building a small payment-to-invoice matching utility.

Data

You are given:

invoices : a list of invoice records with:
- invoice_id (string)
- amount_cents (integer)
- due_date (string, ISO-8601 date like YYYY-MM-DD )
payments : a list of payment records with:
- payment_id (string)
- amount_cents (integer)
- memo (string; may contain extra whitespace)

Assume invoice_id is unique in invoices.

Part 1 (Memo → invoice_id matching)

A payment memo may contain a standardized invoice reference in the form:

"Paying off: <INVOICE_ID>"

where <INVOICE_ID> is the invoice id you should match to.

Write a function that, for each payment, extracts the target invoice_id from the memo (if present), finds the corresponding invoice in invoices, and outputs a matched result.

Output requirement (per payment):

If a match is found: output the payment_id , extracted invoice_id , and the matched invoice details.
If no match is found (or memo cannot be parsed): output a clear "not found" result for that payment.

Handle edge cases such as extra spaces in the memo, missing/empty memo, or malformed standardized strings.

Part 2 (Hybrid matching: memo-based OR amount-based)

Extend the logic:

If memo contains the standardized prefix "Paying off:" , use Part 1 memo → invoice_id matching.
Otherwise, match by amount:
- Find invoices where invoice.amount_cents == payment.amount_cents .
- If there are multiple candidates, choose the invoice with the earliest due_date .
- If there is no candidate, output: "cannot find matching invoice for amount <amount_cents>" (or equivalent).

State the time and space complexity of your approach and justify it.

Quick Overview

You are building a small payment-to-invoice matching utility.

Data

You are given:

invoices : a list of invoice records with:
- invoice_id (string)
- amount_cents (integer)
- due_date (string, ISO-8601 date like YYYY-MM-DD )
payments : a list of payment records with:
- payment_id (string)
- amount_cents (integer)
- memo (string; may contain extra whitespace)

Assume invoice_id is unique in invoices.

Part 1 (Memo → invoice_id matching)

A payment memo may contain a standardized invoice reference in the form:

"Paying off: <INVOICE_ID>"

where <INVOICE_ID> is the invoice id you should match to.

Write a function that, for each payment, extracts the target invoice_id from the memo (if present), finds the corresponding invoice in invoices, and outputs a matched result.

Output requirement (per payment):

If a match is found: output the payment_id , extracted invoice_id , and the matched invoice details.
If no match is found (or memo cannot be parsed): output a clear "not found" result for that payment.

Handle edge cases such as extra spaces in the memo, missing/empty memo, or malformed standardized strings.

Part 2 (Hybrid matching: memo-based OR amount-based)

Extend the logic:

If memo contains the standardized prefix "Paying off:" , use Part 1 memo → invoice_id matching.
Otherwise, match by amount:
- Find invoices where invoice.amount_cents == payment.amount_cents .
- If there are multiple candidates, choose the invoice with the earliest due_date .
- If there is no candidate, output: "cannot find matching invoice for amount <amount_cents>" (or equivalent).

State the time and space complexity of your approach and justify it.

Match payments to invoices by memo or amount

Quick Overview

Data

Part 1 (Memo → invoice_id matching)

Part 2 (Hybrid matching: memo-based OR amount-based)

Submit Your Answer to Earn 20XP

Match payments to invoices by memo or amount

Quick Overview

Data

Part 1 (Memo → invoice_id matching)

Part 2 (Hybrid matching: memo-based OR amount-based)

Submit Your Answer to Earn 20XP