কনটেন্টে যান

Linked List — delivery manifest ও crate loading

দুই warehouse থেকে batch ID অনুযায়ী সাজানো parcel list এসেছে। বাতিল batch-এর parcel বাদ দিতে হবে। তারপর পূর্ণ crate-এ একসঙ্গে kটি parcel উল্টো ক্রমে load হবে; শেষের অসম্পূর্ণ crate আগের ক্রমেই থাকবে। Array বানিয়ে sort/reverse না করে একই node-এর link বদলে final manifest তৈরি করো।

কোর্স-সংযোগ: Microsoft Module 1-এর linked list, traversal ও operation cost-এর সম্পর্কিত অনুশীলন। এটি সাইটের নিজস্ব guided problem।

১. আগে যা পড়বে

ক্রম নোট বোঝার লক্ষ্য
1 Linked list ধারণা, pointer-এর চিত্র node-এর identity ও value কেন এক নয়
2 Cycle detection fast/slow pointer কখন মিলবে
3 Merge Two Sorted Lists dummy head দিয়ে প্রথম node-এর বিশেষ case সরানো
4 Remove Elements বাদ দেওয়ার সময় previous কেন একই থাকে
5 Reverse Linked List, Reverse k-Group next হারানোর আগেই বাঁচিয়ে রাখা

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

build_manifest(left, right, cancelled, group_size) একটি Node head ফেরাবে। প্রতিটি node-এ integer value ও next থাকবে। value হলো batch ID; একই batch-এর একাধিক parcel থাকতে পারে। cancelled-এ ID থাকলে সেই ID-এর সব parcel বাদ যাবে।

  • দুই list nondecreasing order-এ থাকবে, cycle থাকবে না, এবং তারা কোনো node share করবে না। মোট 0 ≤ n ≤ 100000।
  • group_size = k ≥ 1 integer। অবশিষ্ট node-এর মধ্যে প্রতি পূর্ণ k-group reverse হবে; ছোট শেষ group অপরিবর্তিত।
  • সমান ID-এর merge-এ left list-এর node আগে আসে। কোনো নতুন parcel node তৈরি করবে না; temporary dummy node ব্যবহার করা যাবে।
  • Input consume হবে: original head ধরে আগের list আবার ব্যবহার করবে না। Node-এর link বদলানোই কাজটির অংশ।
  • cycle, shared tail, unsorted input বা invalid k পেলে link বদলানোর আগেই ValueError। খালি list বৈধ।

উদাহরণ

Python
left = from_values([1, 4, 7])
right = from_values([2, 3, 6, 8])
result = build_manifest(left, right, cancelled={3, 7}, group_size=2)
assert to_values(result) == [2, 1, 6, 4, 8]
Merge → বাতিল বাদ → পূর্ণ crate reverse

  1. দুই sorted manifest merge

    1
    →
    2
    →
    চিহ্নিত ঘর: 3
    →
    4
    →
    6
    →
    চিহ্নিত ঘর: 7
    →
    8

    Batch 3 ও 7 বাতিল।

  2. বাতিলের node bypass

    1
    →
    2
    →
    4
    →
    6
    →
    8

    দুটি পূর্ণ crate: [1,2] ও [4,6]; শেষ [8] অসম্পূর্ণ।

  3. প্রতি পূর্ণ crate উল্টো

    চিহ্নিত ঘর: 2
    →
    চিহ্নিত ঘর: 1
    →
    চিহ্নিত ঘর: 6
    →
    চিহ্নিত ঘর: 4
    →
    8

    শেষ 8-এর অবস্থান অপরিবর্তিত; value কপি নয়, link বদলেছে।

৩. চারটি guided milestone

ধাপ A — নিরাপদে list পড়া

প্রথমে assert_acyclic(head) লিখো। slow এক ধাপ, fast দুই ধাপ। identity দিয়ে মিলবে: slow is fast; একই value থাকলেই cycle নয়। এরপর sorted order যাচাই করে প্রতিটি list-এর শেষ node মনে রাখো।

কেন শেষ node যথেষ্ট: দুটি acyclic singly linked list কোনো node share করলে সেই node-এর পরের পুরো পথই shared; তাই তাদের tail একই হবে। দুই nonempty list-এর tail একই হলে reject করো।

Checkpoint: self-loop reject হবে; 1 → shared5 এবং 2 → shared5-ও reject হবে। একই value-সহ আলাদা node বৈধ। এই ধাপের আগে কোনো next বদলাবে না।

ধাপ B — existing node merge

merge_sorted(left, right)-এ dummy ও tail রাখো। ছোট head-কে tail.next করো, সেই input head এগিয়ে নাও, তারপর tail এগোবে।

Invariant: dummy-র পরের অংশ sorted এবং tail তার শেষ node। Hint: তুলনায় <= দিলে equal-ID parcel-এর স্থির ক্রম থাকে। শেষের অবশিষ্ট chain একবার link করলেই হবে।

Checkpoint: দুই input-এর সব node identity output-এ আছে; sample-এর merge হলো [1,2,3,4,6,7,8]।

ধাপ C — cancelled parcel bypass

remove_cancelled(head, cancelled)-এ dummy-কে previous করো। previous.next.value বাতিল হলে previous.next = previous.next.next। অন্যথায় previous এগোবে।

Invariant: previous পর্যন্ত রাখা প্রতিটি node বৈধ। Hint: node বাদ দিলে previous এগিয়ো না; পরেরটিও বাতিল হতে পারে। cancelled আগে set করলে membership সাধারণত O(1)।

Checkpoint: প্রথম node বাতিল, পরপর দুই node বাতিল, এবং সব node বাতিল—তিনটিই পরীক্ষা করো। সব বাদ গেলে head হবে None।

ধাপ D — পূর্ণ group-ই reverse

reverse_complete_groups(head, k)-এ before হলো group-এর আগের node। আগে k ধাপ হেঁটে দেখো group পূর্ণ কি না। পূর্ণ না হলে কাজ শেষ; কোনো pointer বদলাবে না।

পূর্ণ হলে তিনটি anchor রাখো: first, last, after = last.next। reverse করার শুরুতে previous = after রাখো; এতে পুরনো first শেষে গিয়েই পরের group-এর সঙ্গে যুক্ত হয়। reverse শেষে before.next = last, তারপর নতুন before হবে পুরনো first।

Invariant: before-এর আগের group-গুলো final; after-এর পরের chain এখনো untouched। next বদলানোর আগে following = current.next রাখতে হবে।

Checkpoint: [1,2,3,4,5], k=2 → [2,1,4,3,5]; k=1-এ আগের ক্রম। k বড় হলে পুরো ছোট list অপরিবর্তিত।

৪. Unit test ও solution পড়ার নিয়ম

Python reference implementation · Unit tests

Bash
python -m unittest discover -s practice -p 'test_linked_list_lab.py' -v

১০টি test-এ sample, duplicates, empty/all-cancelled, অসম্পূর্ণ group, invalid input এবং node identity বজায় থাকা যাচাই হয়। আরও ১৫০ random case-এ একটি সহজ array model-এর সঙ্গে final order মেলানো হয়। শুধু value মিললে pointer solution সঠিক প্রমাণিত হয় না; cycle বা নতুন parcel node তৈরি হওয়াও ধরা চাই।

Reference পড়ার সময় প্রথমে build_manifest-এর pipeline দেখো। তারপর group reversal-এর following, previous, current তিন pointer কাগজে trace করো। এই তিনটির অর্থ মুখে বলতে না পারলে code মুখস্থ করে এগিয়ো না।

৫. Coverage ও খরচ

Pattern কোথায় কাজে লাগল
Fast/slow pointer invalid cycle ধরা
Shared-tail reasoning input lists disjoint কি না
Dummy node + sorted merge এক manifest তৈরি
Previous/current deletion cancelled parcel বাদ
In-place reversal পূর্ণ crate-এর order বদল
আলাদা অনুশীলন random pointer copy, palindrome check, digit addition, LRU cache এখানে নেই

মোট সময় expected O(n + c), যেখানে c cancelled ID-এর সংখ্যা। cancellation set O(c) memory নেয়; pointer transformation নিজে O(1) অতিরিক্ত memory। to_values শুধু output দেখা/test-এর জন্য O(n) array বানায়; মূল algorithm সেটি ব্যবহার করে না।