# Mixed Interview Lab — Incident report তৈরি করুন

একটি service-এর support ticket stream এসেছে। একই ticket পুনরায় আসতে পারে, পুরোনো ticket সাম্প্রতিক dashboard থেকে বাদ পড়ে, আর একটি incident বোঝার জন্য কয়েক ধরনের ticket পাশাপাশি দেখতে হয়। একটি report বানান যা duplicate বাদ দেবে, recent workload দেখাবে এবং investigation-এর জন্য সবচেয়ে ছোট প্রাসঙ্গিক ticket sequence খুঁজবে।

**Microsoft কোর্সের সংযোগ:** Module 4-এর hashing ও problem-solving, Module 5-এর priority queue ও optimization-এর সঙ্গে এই practice মেলে। এটি একটি নিজস্ব সমন্বিত অনুশীলন; কোনো Microsoft interview question বা course assessment-এর অনুলিপি নয়।

## ১. আগে পড়া ও problem-এর ক্রম

| ক্রম | প্রস্তুতি | যে ধারণাটি কাজে লাগবে |
|---|---|---|
| ১ | [Arrays/strings-এর পরিচয়](../02-arrays-and-strings/README.md), [Hashing ধারণা](../05-hashing/concept.md) | Stream order, set ও frequency map |
| ২ | [Stack/queue ধারণা](../04-stack-and-queue/concept.md) | পুরোনো event FIFO order-এ সরানো |
| ৩ | [Top K Frequent](../13-interview-master-problems/problems/013-top-k-frequent.md) | Frequency থেকে priority বানানো |
| ৪ | [Longest substring without repeat](../13-interview-master-problems/problems/015-longest-substring-no-repeat.md) | Sliding window-এর দুই pointer |
| ৫ | [Minimum Window Substring](../13-interview-master-problems/problems/023-minimum-window-substring.md) | সব required category পাওয়ার পরে window ছোট করা |
| ৬ | [Interview শেখার পথ](../13-interview-master-problems/learning-guide.md) | আগে contract ও example, পরে code ও complexity |

৩ ও ৫ নম্বর problem আলাদাভাবে হাতে trace করুন। Lab-এ দুটি ভিন্ন window থাকবে: সময়ের window এবং required category cover করার window। তাদের উদ্দেশ্য এক নয়।

## ২. সুনির্দিষ্ট সমস্যা

`incident_brief(events, window, k, required)` লিখুন। Event হলো `(ticket_id, timestamp, category)`।

1. Input timestamp nondecreasing। একই ID বারবার এলে **প্রথম event** গ্রহণ করুন; পরেরগুলো duplicate। পরে category বদলালেও প্রথমটির তথ্য থাকবে।
2. প্রতিটি input event-এর timestamp-এ clock এগোবে, এমনকি সেটি duplicate হলেও। সময় `t`-তে recent ticket interval **`(t-window, t]`**; বাম boundary-তে থাকা event বাদ।
3. Final clock-এ recent accepted ticket-এর count এবং top `k` category দিন। বেশি frequency আগে; সমান হলে category string-এর lexical order।
4. সম্পূর্ণ accepted history থেকে একটি **contiguous slice** খুঁজুন, যেখানে `required`-এর প্রতিটি distinct category অন্তত একবার আছে। Ticket count সবচেয়ে কম হবে; সমান হলে আগে শুরু হওয়া slice। Returned list-এ ওই slice-এর সব ticket ID থাকবে, মাঝখানের irrelevant category-সহ।
5. Empty required হলে minimum cover `[]`; কোনো required category না পাওয়া গেলে `None`।

**সীমা:** `0 ≤ event_count ≤ 100,000`, timestamp পূর্ণসংখ্যা `0..10⁹`, `1 ≤ window ≤ 10⁹`, `0 ≤ k ≤ 100,000`; ID ও category nonempty string। Required category repeat হলে একবার ধরুন। Negative/unsorted timestamp, nonpositive window বা negative `k`-তে `ValueError`। Input বদলাবেন না।

এই cover-এর উদ্দেশ্য সবচেয়ে কম **ticket**, সবচেয়ে কম elapsed seconds নয়। Recent dashboard-এর বাইরে থাকা পুরোনো ticket-ও investigation cover-এ থাকতে পারে।

```python
events = [
    ("a", 0, "login"), ("b", 1, "payment"), ("a", 2, "login"),
    ("c", 3, "login"), ("d", 6, "search"), ("e", 7, "payment"),
]
incident_brief(events, window=5, k=2, required=["login", "payment"])
```

```python
{
    "accepted": ["a", "b", "c", "d", "e"],
    "duplicates": 1,
    "active_count": 3,
    "top": [("login", 1), ("payment", 1)],
    "minimum_cover": ["a", "b"],
}
```

Final clock `7`; recent interval `(2,7]`-এ `c,d,e` আছে। তিন category-র count `1`, তাই lexical tie-break-এ `login,payment` top two। Complete accepted history-তে `[a,b]`-ই দুই required category-র earliest shortest cover।

```mermaid
flowchart TD
    input["Timestamp-ordered event"] --> clock["Clock এগোন\nমেয়াদোত্তীর্ণ ticket সরান"]
    clock --> seen{"ID আগে দেখা?"}
    seen -->|হ্যাঁ| skip["Duplicate count বাড়ান"]
    seen -->|না| accepted["Accepted history + recent queue"]
    accepted --> count["Recent frequency map"]
    count --> heap["Priority queue → top categories"]
    accepted --> cover["Sliding window → minimum cover"]
    heap --> report["Investigation brief"]
    cover --> report
```

## ৩. Guided milestones

### A — Contract থেকে deduplication

Seen ID set এবং accepted event list রাখুন। ID প্রথমবার এলে গ্রহণ করুন; duplicate হলে count বাড়ান। Category frequency-তে duplicate যোগ করবেন না।

**Invariant:** accepted list-এ ID unique, কিন্তু timestamp ও category repeat করতে পারে। **Checkpoint:** example-এর ছয় event থেকে পাঁচটি accepted; দ্বিতীয় `a` নেই।

### B — সময়ের queue ও counts

প্রতিটি event-এর timestamp-এ আগে queue-এর front থেকে `time ≤ now-window` event বের করুন। তার category count কমান; count zero হলে map থেকে key মুছুন। এরপর event নতুন হলে queue-তে ঢোকান।

**Hint:** Duplicate বলে clock update skip করবেন না। `("a",0,"login")`, পরে একই ID time `10`, window `5` হলে recent count `0`; পুরোনো `a` revive হয় না।

**Invariant:** queue-তে কেবল active accepted ticket, সময়ক্রমে সাজানো; frequency map তাদের ঠিক count রাখে। **Checkpoint:** example-এর final queue `c,d,e`।

### C — Category priority queue

প্রতি active category-র জন্য `(-count, category)` tuple min-heap-এ দিন। সর্বোচ্চ `k` বার pop করে `(category, count)` ফেরত দিন। Zero count-এর category আগের ধাপেই মুছে গেছে।

**Checkpoint:** count `login=3, payment=2, search=2` হলে `k=2`-তে `login`, তারপর `payment`। Tie rule input insertion order-এর ওপর নির্ভর করবে না।

### D — Investigation-এর minimum cover

Accepted history-তে left/right pointer চালান। Right বাড়িয়ে required category count আপডেট করুন। সব distinct category present হলে candidate record করুন এবং left বাড়িয়ে window ছোট করুন; কোনো category হারালে আবার right বাড়ান।

**Invariant:** `formed` হলো positive count থাকা required category-র সংখ্যা, ticket count নয়। Irrelevant category window-তে থাকতে পারে কিন্তু formed বাড়ায় না।

**Checkpoint:** `[login, other, payment, login]` history-তে শেষের `[payment, login]` ছোট cover; প্রথম তিন ticket ধরে থেমে গেলে ভুল হবে। Equal length candidate দিয়ে পুরোনো best overwrite করবেন না।

## ৪. সমাধানের যুক্তি

??? success "কেন একটি ticket সীমিতবার কাজ করে"

    Set প্রতিটি ticket-এর প্রথম occurrence আলাদা করে। Timestamp nondecreasing হওয়ায় expired event কেবল queue-এর front-এ থাকে; প্রতিটি accepted ticket একবার ঢোকে ও সর্বোচ্চ একবার বের হয়। Recent frequency তার সঙ্গে চলায় heap final workload সঠিকভাবে rank করে।

    Cover window-তে right প্রতিটি accepted ticket একবার যোগ করে, left সর্বোচ্চ একবার সরায়। সব category থাকলে left না সরিয়ে রাখলে ছোট answer মিস হতে পারে; category হারানোর পরে আরও ছোট করলে cover ফেরত আসবে না, তাই right বাড়াতে হয়।

    [সম্পূর্ণ Python solution](../practice/interview_lab.py){ download } · [unit test](../practice/test_interview_lab.py){ download }।

## ৫. Unit test ও interview checkpoint

Repository root থেকে চালান; download করলে দুই ফাইল `practice/`-এ রাখুন।

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

৮টি test method worked example, empty input, exact window boundary, clock-advancing duplicate, later shorter cover, missing category, `k=0` ও invalid input দেখে। ১৫০টি seeded stream-এ আলাদা brute-force implementation সব contiguous slice পরীক্ষা করে পুরো result মেলায়।

নিজেকে interview-এ এই চারটি প্রশ্ন করুন:

1. একই ID নতুন timestamp-এ এলে clock কেন বদলাবে কিন্তু accepted record বদলাবে না?
2. Recent time window আর minimum cover window-র মধ্যে কোন data shared, কোন state আলাদা?
3. কেন frequency map-এ zero count মুছতে হবে?
4. Required category-এর multiplicity চাইলে current contract ও algorithm কোথায় বদলাবে?

`N` input event, `U` final active category, `R` distinct required category হলে expected hashing cost-সহ time `O(N + R + U + min(k,U) log(U+1))`; heapify `O(U)`। Space `O(N + R + U)`। সব input/accepted history রাখা এই learning implementation-এর অংশ; infinite stream-এর storage policy আলাদা design problem।

## ৬. Coverage ও বাকি practice

| এখানে ব্যবহার | আলাদা করে করবেন |
|---|---|
| Set, frequency map, deduplication | Custom hash table ও collision handling |
| FIFO deque, time-based eviction | [LRU cache](../13-interview-master-problems/problems/021-lru-cache.md): recent access order লাগে |
| Heap ranking ও deterministic tie | Streaming top-k-তে frequency বদলালে heap update |
| Two-pointer minimum cover | Required multiplicity ও Unicode normalization |
| একাধিক invariant-সহ report | Tree, DSU, graph shortest path ও DP capstone |

[সব mixed interview problem](../13-interview-master-problems/problems/README.md)-এ ফিরে পৃথক pattern যাচাই করুন। এই report project-এ সব ২৯টি problem-এর algorithm জোর করে বসানো হয়নি।