# Hashing — replay-safe transaction reconciliation

একটি ledger service network retry-এর কারণে একই transaction একাধিকবার পায়। আগে replay বাদ দিয়ে সঠিক arrival order রাখতে হবে। তারপর account-এর balance, নির্দিষ্ট target-এর দুই transaction, এবং target sum-এর টানা transaction batch গণনা করতে হবে। একই ledger থেকে চার ধরনের hash-based উত্তর তৈরি হবে।

**কোর্স-সংযোগ:** Microsoft Module 4-এর hashing-এর সম্পর্কিত অনুশীলন। এটি শেখার জন্য বানানো ledger; production financial system-এর পূর্ণ নকশা নয়, এবং official course assignment-ও নয়।

## ১. শুরু করার আগে

| ক্রম | নোট | যে ধারণা দরকার |
| --- | --- | --- |
| 1 | [Hashing ধারণা](../05-hashing/concept.md), [চিত্র](../05-hashing/visual-explanation.md) | key, value, collision ও expected cost |
| 2 | [Contains Duplicate](../05-hashing/problems/002-contains-duplicate.md) | আগের ID মনে রাখা |
| 3 | [Two Sum](../05-hashing/problems/001-two-sum.md) | complement lookup এবং একই item দুইবার না-নেওয়া |
| 4 | [Subarray Sum Equals K](../05-hashing/problems/013-subarray-sum-equals-k.md) | repeated prefix-এর frequency কেন দরকার |

## ২. সমস্যার চুক্তি

`audit_ledger(records, target=0)` বানাও। record হলো `(transaction_id, account, amount)`। ID ও account খালি নয় এমন string; amount signed integer। পরিমাণ integer ক্ষুদ্রতম unit-এ দেওয়া—floating point ব্যবহার করতে হবে না। `0 ≤ n ≤ 100000`।

1. একই ID ও একই data আবার এলে replay; শুধু প্রথমটি রাখো। একই ID-তে account বা amount বদলে এলে `ValueError`। একই amount কিন্তু ভিন্ন ID হলে আলাদা transaction।
2. `balances`: deduplicated সব record-এর account অনুযায়ী amount-এর যোগফল। zero balance হলেও account রাখো।
3. `pair`: target sum-এর **দুটি আলাদা** transaction ID। আগে পাওয়া second index জিতবে; তার মধ্যে আগে পাওয়া first index। না থাকলে `None`।
4. `batch_count`: deduplicated arrival order-এ target sum-এর খালি নয় এমন contiguous subarray-এর সংখ্যা। batch account পার হতে পারে—এটি global audit, per-account audit নয়।

প্রথমে deduplication শেষ করতে হবে; raw stream-এ sum করলে replay balance বাড়িয়ে দেবে। original input বদলাবে না।

### উদাহরণ ও সঠিক output

```python
records = [
    ("t1", "A", 4), ("t2", "B", -1), ("t1", "A", 4),
    ("t3", "A", -3), ("t4", "B", 4),
]
```

তৃতীয় record replay। পরিষ্কার amount sequence `[4,-1,-3,4]`; A balance `4-3=1`, B balance `-1+4=3`। target 3 হলে প্রথম pair `t1,t2`; target-এর একমাত্র contiguous batch `[4,-1]`।

```python
{
    "records": [("t1", "A", 4), ("t2", "B", -1), ("t3", "A", -3), ("t4", "B", 4)],
    "balances": {"A": 1, "B": 3},
    "pair": ("t1", "t2"),
    "batch_count": 1,
}
```

```dsa
kind: array
title: "Repeated prefix হারালে কিছু batch গণনা হবে না"
steps:
  - label: "পরিষ্কার amount"
    values: [4, -1, -3, 4]
    active: [0, 1]
    note: "Target 3-এর batch [0,2): 4 − 1 = 3।"
  - label: "Prefix: 0, 4, 3, 0, 4"
    values: [0, 4, 3, 0, 4]
    active: [0, 3]
    note: "Prefix 0 দুইবার এসেছে। Set শুধু উপস্থিতি রাখে; frequency map দুটো সম্ভাব্য start-ই রাখে।"
```

## ৩. চারটি guided milestone

### ধাপ A — ID অনুযায়ী replay বাদ

`deduplicate(records)`-এ `seen[id] = পূর্ণ record` রাখো। ID প্রথমবার হলে output-এ append। আগে থাকলে আগের পূর্ণ record-এর সঙ্গে তুলনা করো।

**Invariant:** seen-এর প্রতিটি ID output-এ একবার আছে, এবং output প্রথম arrival-এর ক্রমে। Hint: শুধু ID set দিয়ে conflicting replay শনাক্ত করা যায় না।

**Checkpoint:** `("x","A",1)` দুবার এলে এক record; দ্বিতীয়টি `("x","A",2)` হলে error। `("x","A",1)` ও `("y","A",1)` দুটিই থাকবে।

### ধাপ B — account aggregation

`account_balances(records)` লিখো: প্রতিটি amount সংশ্লিষ্ট account-এর চলতি balance-এ যোগ হবে। absent key-এর initial value 0।

**Invariant:** প্রথম `i` record পড়ার পরে dictionary-তে ঠিক সেই prefix-এর per-account total আছে।

**Checkpoint:** sample-এ `{"A":1,"B":3}`। `+2,-2`-এর account-ও output-এ value 0 নিয়ে থাকবে।

### ধাপ C — earliest target pair

`first_target_pair(records, target)`-এ `amount → প্রথম transaction ID` map রাখো। বর্তমান amount `x` হলে আগে `target-x` খোঁজো; পাওয়া গেলে pair ফেরাও। তারপরই বর্তমান amount map-এ রাখো; প্রথম occurrence overwrite করবে না।

**Invariant:** lookup-এর সময় map-এ কেবল আগের record আছে; তাই নিজেকে pair বানানো অসম্ভব। earliest-second tie স্বয়ংক্রিয়ভাবে scan order থেকে মেলে।

**Checkpoint:** শুধু amount 2 ও target 4 থাকলে `None`; দুটি আলাদা ID-তে 2 থাকলে বৈধ pair।

### ধাপ D — সব target batch গণনা

`count_target_batches(records, target)`-এ চলতি prefix `s` রাখো। আগের prefix `p` হলে মাঝের sum `s-p`; target পেতে চাই `p = s-target`। `frequencies = {0:1}` দিয়ে শুরু করো।

```python
prefix += amount
count += frequencies.get(prefix - target, 0)
frequencies[prefix] = frequencies.get(prefix, 0) + 1
```

**Invariant:** lookup-এর সময় frequency-তে শুধু বর্তমান অবস্থানের আগের prefix আছে। update আগে করলে target 0-তে খালি batch-ও গুনে ফেলবে। negative amount থাকায় সাধারণ positive-only sliding window এখানে ঠিক নয়।

**Checkpoint:** চারটি zero-এর target 0 batch সংখ্যা `4+3+2+1=10`; 4 নয়। এবার deduplicated list তিন helper-কে দিয়ে final report বানাও।

## ৪. Unit test ও reference

[Python implementation](../practice/hashing_lab.py) · [Unit tests](../practice/test_hashing_lab.py)

```bash
python -m unittest discover -s practice -p 'test_hashing_lab.py' -v
```

১০টি test-এ replay conflict, same-amount distinct ID, self-pair, zero/negative input, tie rule ও sample আছে। ১৮০ random ledger-এ সব pair ও সব contiguous batch brute-force করে hash solution-এর সঙ্গে মেলানো হয়।

Reference পড়ার সময় তিনটি dictionary-র **value-এর অর্থ** তুলনা করো: `seen`-এ পূর্ণ record, `first_amount`-এ earliest ID, `frequencies`-এ count। key একই ধরনের হলেও problem অনুযায়ী value বদলে যায়।

## ৫. Coverage ও সীমা

| Technique | এই report-এ কাজ |
| --- | --- |
| Hash map deduplication | replay ও conflicting ID |
| Group-by aggregation | account balance |
| Complement lookup | earliest target pair |
| Prefix frequency map | negative/zero-সহ target batch count |
| আলাদা অনুশীলন | anagram signatures, rolling hash, minimum window, top-k এবং custom hash table implementation |

Python dictionary-র সাধারণ expected-cost মডেলে সময় `O(n)`, অতিরিক্ত memory `O(n)`। এটি worst-case collision guarantee নয়। output batch **সংখ্যা** দেয়; সব batch-এর index list চাইলে output নিজেই `O(n²)` হতে পারে।