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 ধারণা, চিত্র	key, value, collision ও expected cost
2	Contains Duplicate	আগের ID মনে রাখা
3	Two Sum	complement lookup এবং একই item দুইবার না-নেওয়া
4	Subarray Sum Equals K	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,
}

Repeated prefix হারালে কিছু batch গণনা হবে না

1. পরিষ্কার amount

   চিহ্নিত ঘর: 04

   চিহ্নিত ঘর: 1-1

   2-3

   34

   Target 3-এর batch [0,2): 4 − 1 = 3।

2. Prefix: 0, 4, 3, 0, 4

   চিহ্নিত ঘর: 00

   14

   23

   চিহ্নিত ঘর: 30

   44

   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 · Unit tests

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²) হতে পারে।