সরাসরি পর্বে যান
পর্ব ৮৫ · ৮৫-এর মধ্যে · মডিউল ১৪

ইন্টারভিউ আর প্রতিযোগিতায় গণনার তত্ত্ব — regex, parsing আর complexity

Theory of Computation in Interviews and Contests — Safe Regex and ReDoS, State-Machine Design, Tokenizers and Recursive-Descent Parsers, Recognising NP-Hardness, Choosing Exact, Approximate, Heuristic or Solver Methods, Halting-Style Trick Questions and DP over Automata

Taught in Bangla, this practice page covers theory of computation in software interviews and contests with 35 questions in nine parts: regex and ReDoS, state-machine design, tokenizers and recursive-descent parsers, recognising NP-hardness, choosing exact, approximate, heuristic or solver methods, pseudo-polynomial reasoning, halting-style trick questions and DP over automata. Eleven in-page Python (Pyodide) checkers test each claim by brute force; all examples are fictional, not real company questions.

এই পর্বে যা পাবেন

  • দুর্বল regex চেনা, দ্ব্যর্থহীন করে আবার লেখা আর language বদলায়নি তা brute force-এ দেখানো
  • OTP আর চেকআউটের state machine নকশা, BFS দিয়ে deadlock আর নিরাপত্তার ফাঁক খোঁজা
  • জায়গায় বসে tokenizer আর recursive-descent parser, error message আর গভীরতার সীমাসহ
  • ছদ্মবেশী NP-complete সমস্যা চেনা, reduction-এর দিক ঠিক রাখা আর exact, approximation, heuristic, SAT বা ILP বেছে নেওয়া
  • Pseudo-polynomial DP, input-এর encoding, timeout আর static analysis-এর সীমা নিয়ে ফাঁদের প্রশ্ন
  • Contest-এ Aho–Corasick automaton আর digit DP দিয়ে গোনা, আর তত্ত্ব সহজ ভাষায় বোঝানোর অভ্যাস

১ · ইন্টারভিউতে গণনার তত্ত্ব কোথায় লুকিয়ে থাকে, আর উত্তরের ছক

ইন্টারভিউতে কেউ সাধারণত জিজ্ঞেস করেন না “pumping lemma বলুন”. প্রশ্ন আসে কাজের ভাষায়: “এই regex-টা কেন সার্ভার আটকে দিল?”, “একটি calculator-এর expression পার্স করুন”, “ডেলিভারির রুট সবচেয়ে ছোট করার কোড লিখুন”, “সাবমিট করা কোড অসীম loop-এ পড়ে কি না ধরার function লিখুন”. প্রতিটির পেছনে এই কোর্সের একটি ফল আছে, আর সেটি চিনতে পারলে উত্তর অর্ধেক হয়ে যায়। রেলের টিকিট কাউন্টারে অভিজ্ঞ কর্মী যেমন প্রশ্ন শুনেই বোঝেন কোন ফর্ম লাগবে, তেমনি আপনার কাজ প্রশ্নের চেহারা দেখে মডেল চেনা। মডিউলের অন্য পাতাগুলো অন্য দিক দেখে: পর্ব ৮১-এ নকশার অনুশীলন, পর্ব ৮২-এ MCQ, পর্ব ৮৩-এ লিখিত ও মৌখিক প্রশ্ন, পর্ব ৮৪-এ প্রমাণ লেখা।

প্রশ্নের চেহারাপেছনের তত্ত্বভাগঝালিয়ে নিন
“Regex ধীর কেন?”, “এটা validate করুন”backtracking বনাম automaton, regular-এর সীমা২২১, ১৩
“লগইন বা অর্ডারের flow নকশা করুন”DFA, guard, reachability, deadlock৩২৪, ১২
“Expression বা query পার্স করুন”lexer, CFG, LL(1), precedence৪২২, ৩৮, ৪২
“দ্রুত algorithm দিন” (আসলে কঠিন)NP-completeness, reduction৫, ৬৬১, ৭৩
“O(n · W) কি polynomial?”encoding, pseudo-polynomial৭০৫, ৫৭
“অসীম loop ধরার tool লিখুন”halting problem, Rice৮৫১, ৫৩, ৫৫
“নিষিদ্ধ শব্দ ছাড়া কয়টি string?”KMP, Aho–Corasick, DFA-র ওপর DP৯২৩, ০৮
উত্তরের পাঁচ ধাপ

১. প্রশ্ন পরিষ্কার করুন। Input কত বড়, কোন alphabet (বাংলা অঙ্ক আসবে কি?), সংখ্যাগুলো কত বড়, input কি অবিশ্বস্ত ব্যবহারকারী থেকে আসে?

২. মডেল চিনুন। সসীম স্মৃতি যথেষ্ট (automaton)? Stack লাগে (grammar)? না অসীম অনুসন্ধান (Turing machine)? আর সময়ের দিকে: P-তে জানা, NP-hard, না undecidable?

৩. ছোট উদাহরণ জোরে চালান। তিন-চার অক্ষরের input, দুই-তিন state-এর যন্ত্র।

৪. Algorithm আর তার শর্তসহ জটিলতা বলুন। “O(n · t), কিন্তু t-এর মান বড় হলে এটি polynomial নয়” ধরনের সতর্কতা নম্বর বাড়ায়।

৫. যাচাইয়ের পরিকল্পনা। Brute force-এর সঙ্গে মেলানো, প্রান্তের input, দুষ্ট input আর সময়ের সীমা।

১.১(সহজ) বাজারঘরের একজন ডেভেলপার জানতে চান কোন যাচাই শুধু একটি formal regex (বা DFA) দিয়ে করা যায়: (ক) অর্ডার-কোড “BG-” আর ঠিক ৪টি অঙ্ক; (খ) query-তে বন্ধনী ঠিকমতো জোড়া; (গ) binary string-এর মান ৩ দিয়ে বিভাজ্য; (ঘ) string-এ a আর b সমান সংখ্যায়। প্রতিটির জন্য এক লাইনের কারণ দিন।
(a) yes : a finite language ; complete DFA with 8 states + dead = 9 (lesson 08)
(b) no  : brackets need a counter of unbounded depth -> CFG / stack (lessons 17, 25)
(c) yes : 3 states = value mod 3 (lesson 08)
(d) no  : {w : #a = #b} is not regular; a counter or a CFG is needed (lesson 17)

এক লাইনের যুক্তিটি সবসময় একই: যন্ত্রকে কতটুকু মনে রাখতে হয়? সসীম তথ্য (অবস্থান, ভাগশেষ) হলে regular; সীমাহীন গণনা (খোলা বন্ধনীর সংখ্যা, a-এর বাড়তি) হলে নয়। ইন্টারভিউতে “pumping lemma দিয়ে প্রমাণ করুন” এলে পর্ব ১৭-এর adversary ছক লিখুন: split বাছবেন না, প্রতিপক্ষ বাছে। আর বাস্তব regex engine-এর backreference বা recursion সুবিধা formal regex-এর বাইরে; সেগুলো regular-এর সীমা পেরোয়, কিন্তু দামে (ভাগ ২)।

২ · Regex ঠিকভাবে — catastrophic backtracking, রৈখিক engine আর input যাচাই

ঝালিয়ে নিন: পর্ব ২১ · বাস্তব regex engine, পর্ব ১৪ · Thompson construction, পর্ব ২০ · equivalence; নিরাপদ কোডিংয়ের বড় ছবি Cybersecurity কোর্সের পর্ব ৪৬-এ।

২.১(সহজ) Python-এর re-তে ^(a+)+$ pattern n টি a আর শেষে একটি b-এর input-এ এত ধীর কেন? কত ধীর, আর একই pattern RE2-ধাঁচের engine-এ কেমন চলে?

এটি catastrophic backtracking. Backtracking engine একবারে একটি পথ চেষ্টা করে। an-কে অশূন্য টুকরোয় ভাগ করার প্রতিটি উপায় একটি পথ, আর শেষের b মিল ভেঙে দেয় বলে engine সব পথ চেষ্টা করে: মোট 2n − 1 বার $ পরীক্ষা (পর্ব ২১-এর উপপাদ্য ৩.১, composition গুনে)। ফলে n দুই বাড়লে সময় প্রায় চার গুণ। সেই পর্বের ডেস্কটপ run-এ n = 28-এ Python re 6.8667 সেকেন্ড, google-re2 0.000048 সেকেন্ড। কারণ automaton engine পথ নয়, (state, অবস্থান) জোড়া গোনে: Thompson NFA-র state-সেট ধরে এগোলে সময় |R| · m-এর অনুপাতে। ইন্টারভিউতে এই বাক্যটিই মূল: “একই অংশ একাধিক উপায়ে মেলে আর শেষে মিল ব্যর্থ হয়, তাই পথের সংখ্যা exponential”.

২.২(মাঝারি) বাজারঘরের ডেলিভারি-ফর্মে জেলার তালিকা কমা দিয়ে লেখা হয়, যেমন dhaka,sylhet,khulna. কোডে আছে ^([a-z]+,?)+$. (ক) দুর্বলতা কোথায়, দুষ্ট input কেমন? (খ) একই language-এর নিরাপদ pattern দিন। (গ) কীভাবে দেখাবেন যে language বদলায়নি?
(a) ",?" may match nothing, so "aaaa" splits into groups in 2^3 = 8 ways
    -> same shape as (a+)+ ; evil input: "a" * n + "!"
(b) ^[a-z]+(,[a-z]+)*,?$     every new group must start with a comma:
                             the commas fix the split, one way per string
(c) brute force over alphabet {a, b, ,} up to length 8: 9841 strings, 0 differences
    (checker below) ; the stricter ^[a-z]+(,[a-z]+)*$ differs on 1034 strings,
    shortest "a,"  -> a product decision, not a silent change

পুরোনো pattern দিয়ে একজন ব্যবহারকারী ইচ্ছা করে সার্ভার ব্যস্ত রাখতে পারেন, যার নাম ReDoS. এখানে দুটি আলাদা সিদ্ধান্ত আছে, আর ভালো উত্তর সেগুলো আলাদা রাখে। নিরাপত্তার সংশোধন language বদলায় না; শেষের কমা বাদ দেওয়া নীতির প্রশ্ন, যা পণ্যের মালিকের সঙ্গে ঠিক করতে হয়। বাড়তি স্তর হিসেবে regex চালানোর আগেই দৈর্ঘ্যের সীমা দিন, আর regression test-এ একটি দুষ্ট input রাখুন। Python 3.11 থেকে re-তে atomic group (?>…) আর possessive quantifier আছে, যা একই কাজ করে, কিন্তু সব engine-এ নেই।

import re, time
from itertools import product
OLD = re.compile(r"^([a-z]+,?)+$")          # district list, as written in a hurry
NEW = re.compile(r"^[a-z]+(,[a-z]+)*,?$")   # same language, exactly one split
STRICT = re.compile(r"^[a-z]+(,[a-z]+)*$")  # also rejects a trailing comma
def diff(p, q, sigma="ab,", n=8):
    W = ["".join(t) for k in range(n + 1) for t in product(sigma, repeat=k)]
    bad = [w for w in W if bool(p.match(w)) != bool(q.match(w))]
    return f"{len(bad)} differences in {len(W)} strings, shortest: {bad[0] if bad else '-'}"
print("OLD vs NEW   :", diff(OLD, NEW))
print("OLD vs STRICT:", diff(OLD, STRICT))
for n in range(10, 31, 2):
    s = "a" * n + "!"
    t = time.perf_counter(); OLD.match(s); dt = time.perf_counter() - t
    print(f"OLD    n = {n:<6}  {dt:.4f} s")
    if dt > 0.1:
        print("stop: the next run would take about 4x longer"); break
s = "a" * 100000 + "!"
for name, p in (("NEW", NEW), ("STRICT", STRICT)):
    t = time.perf_counter(); p.match(s)
    print(f"{name:6} n = 100000  {time.perf_counter() - t:.4f} s")
print(r"\d+ on '১০০০':", bool(re.fullmatch(r"\d+", "১০০০")),
      "| [0-9]+:", bool(re.fullmatch(r"[0-9]+", "১০০০")),
      "| re.ASCII:", bool(re.fullmatch(r"\d+", "১০০০", re.ASCII)))

প্রথম দুই লাইন ২.২(গ): {a, b, কমা}-এর ওপর দৈর্ঘ্য ০ থেকে ৮-এর 9841টি string-এ নতুন pattern পুরোনোটির সঙ্গে হুবহু মেলে, আর কঠোর রূপ 1034টিতে আলাদা, সবচেয়ে ছোট a,. তারপর পুরোনো pattern-এর সময়: n দুই বাড়লে প্রায় চার গুণ, আর ০.১ সেকেন্ড ছাড়াতেই ব্লক নিজে থেমেছে, যাতে পাতা আটকে না যায়। দুই নিরাপদ pattern এক লাখ অক্ষরেও কয়েক মিলিসেকেন্ডে শেষ। শেষ লাইনটি পরের প্রশ্নের: \d বাংলা অঙ্ক “১০০০” মেলায়, [0-9] আর re.ASCII মেলায় না।

২.৩(মাঝারি) বাজারঘরের (কাল্পনিক) মোবাইল নম্বরের নিয়ম: “01”, তারপর 3 থেকে 9-এর একটি অঙ্ক, তারপর ঠিক ৮টি অঙ্ক। একজন লিখলেন re.match(r"01[3-9]\d{8}", s). কোন কোন ভুল ঢুকতে পারে?

তিনটি ফাঁদ। (১) re.match শুধু শুরু বাঁধে, শেষ নয়: “01712345678xyz” গৃহীত হবে। re.fullmatch বা \Z দিন; $-ও শেষে একটি newline ছেড়ে দেয়। (২) Python-এর \d Unicode অঙ্ক মেলায়, তাই “০১৭১২৩৪৫৬৭৮” বা মিশ্র লেখা ঢুকে পড়বে, অথচ পরের কোড হয়তো ASCII ধরে নেয় (পর্ব ২২-এর ফাঁদ)। [0-9] বা re.ASCII দিন, অথবা ইচ্ছা করে বাংলা অঙ্ক রূপান্তর করে নিন, কিন্তু সিদ্ধান্তটি লিখে রাখুন। (৩) Format ঠিক মানেই নম্বরটি আসল নয়; সেটি যাচাই হয় OTP দিয়ে (ভাগ ৩)। এই pattern-এ nested quantifier নেই, তাই ReDoS-এর ভয় নেই: language সসীম, আর সম্পূর্ণ DFA-তে ১৩টি state লাগে (পড়া অক্ষরের সংখ্যা ০ থেকে ১১, আর একটি dead state).

২.৪(মাঝারি) “Regex দিয়ে বাজারঘরের query-র বন্ধনী মিলেছে কি না যাচাই করুন।” কী উত্তর দেবেন? কিছু engine-এ তো recursion আছে বলে শোনা যায়।

Formal অর্থে অসম্ভব: বন্ধনীর ভাষা (Dyck language) regular নয়, কারণ যন্ত্রকে খোলা বন্ধনীর সংখ্যা মনে রাখতে হয়, আর (p)p-এ pumping lemma ভাঙে। কিছু backtracking engine-এ recursion-এর মতো সুবিধা আছে বলে তাদের নথিতে লেখা, তাই “একটি engine-এ কাজ করে” বলা যায়, কিন্তু তখন সেটি আর regular expression নয়, আর কার্যক্ষমতার নিশ্চয়তাও নেই। ভালো উত্তর: একটি counter বা stack দিয়ে এক পাসে O(n) যাচাই, আর query-র বাকি গঠনের জন্য একটি parser (ভাগ ৪)। এই দৃশ্যে counter-ই যথেষ্ট, কারণ একটিমাত্র বন্ধনীর ধরন; কয়েক রকম বন্ধনী হলে stack লাগে, যা একটি pushdown automaton.

২.৫(কঠিন) বাজারঘর বিক্রেতাদের নিজেদের regex দিয়ে পণ্যের নাম খোঁজার সুবিধা দিতে চায়। Pattern আর text দুটিই অবিশ্বস্ত। নকশা কী হবে, আর কোন তাত্ত্বিক ফল সিদ্ধান্তগুলো সমর্থন করে?
1. engine     : automaton-based (RE2-style): time ∝ |R| · m  (lesson 21, theorem 4.1)
2. features   : no backreferences, no lookaround (outside the linear guarantee)
3. limits     : max pattern length, max counted repetition, max text length
4. cost cap   : per-request CPU budget / timeout as a last layer
5. tests      : evil inputs in CI ; compare with a reference matcher on random strings

যুক্তিগুলো এক এক করে। Backreference-সহ pattern মেলানো সাধারণভাবে NP-complete বলে সাহিত্যে উল্লেখ আছে (পর্ব ২১-এর আলোচনা), তাই P ≠ NP হলে (যা খোলা প্রশ্ন) কোনো engine সব ক্ষেত্রে দ্রুত হতে পারবে না; সুবিধাটি বাদ দেওয়াই নিরাপদ। রৈখিক engine-এও |R| গুণক আছে, আর a{1000}-এর মতো গোনা পুনরাবৃত্তি NFA-কে বড় করে, তাই pattern-এর আকারেও সীমা। Lazy DFA cache-এর জন্য মেমরির সীমা (পর্ব ১০-এর state বিস্ফোরণ মনে রাখুন)। আর timeout শেষ স্তর, প্রথম নয়: ভাগ ৮-এ দেখবেন timeout একটি ভিন্ন প্রশ্নের উত্তর দেয়।

৩ · State machine নকশা — OTP, চেকআউট আর অর্ডারের flow

ঝালিয়ে নিন: পর্ব ২৪ · Software-এ state machine, পর্ব ০৭ · DFA, পর্ব ২০ · emptiness; test নকশা সফটওয়্যার টেস্টিং কোর্সের পর্ব ১০-এ।

ধরুন ইন্টারভিউয়ার বললেন: “বাজারঘরের লগইনে OTP যাচাইয়ের logic লিখুন। কোড পাঠানো হয়, ব্যবহারকারী কোড দেন, ভুল হলে আবার চেষ্টা, তিনবার ভুলে অ্যাকাউন্ট সাময়িক বন্ধ, কোডের মেয়াদ ফুরালে আবার পাঠানো যায়, কিন্তু দুবারের বেশি নয়।” এখানে if-এর জঙ্গল না লিখে প্রথমে state machine আঁকুন। অবস্থা (state) পাঁচটি, আর তার সঙ্গে দুটি গণনা: ভুলের সংখ্যা w আর পুনঃপ্রেরণের সংখ্যা r. পুরো অবস্থা তাই একটি configuration (state, w, r), যা পর্ব ২৪-এর extended FSM.

বাজারঘরের OTP যাচাই — পাঁচটি state

বন্ধনীর ভেতরে guard: w = এ পর্যন্ত ভুল, r = এ পর্যন্ত পুনঃপ্রেরণ। দুই দাগের বাক্স শেষ অবস্থা। না-আঁকা event প্রত্যাখ্যাত হয়, configuration বদলায় না।

OTP verification state machine IDLESENTVERIFIED EXPIREDLOCKED send right wrong [w<2] wrong[w=2] expire resend[r<2]
ছবি ৮৫.১ — EXPIRED থেকে বের হওয়ার একমাত্র তীরে guard r < 2. দুবার পুনঃপ্রেরণের পর মেয়াদ ফুরালে সেখান থেকে কোনো বৈধ event নেই, অথচ EXPIRED শেষ অবস্থা নয়: এটিই ৩.২-এর deadlock.
৩.১(মাঝারি) উপরের OTP নিয়মের transition table লিখুন: প্রতিটি সারিতে state, event, guard, নতুন configuration. ইন্টারভিউতে table-টি কোডে কীভাবে বসাবেন?
state    event   guard   next (state, w, r)
IDLE     send    -       (SENT, 0, 0)
SENT     right   -       (VERIFIED, w, r)
SENT     wrong   w < 2   (SENT, w + 1, r)
SENT     wrong   w = 2   (LOCKED, 3, r)
SENT     expire  -       (EXPIRED, w, r)
EXPIRED  resend  r < 2   (SENT, w, r + 1)      <- w is NOT reset
any other (state, event): rejected, configuration unchanged

কোডে একটি function step(config, event), যা table-এর একটি সারি খোঁজে আর নতুন configuration বা “প্রত্যাখ্যাত” ফেরত দেয়। সব নিয়ম এক জায়গায় থাকে, তাই নতুন নিয়ম মানে একটি সারি, আর test মানে প্রতিটি সারি আর প্রতিটি না-থাকা ঘর একবার চালানো। মনে রাখুন DFA-র রীতিতে না-থাকা তীর dead state-এ যায়, কিন্তু software সাধারণত প্রত্যাখ্যান করে আগের অবস্থায় থাকে; ইন্টারভিউতে কোনটি নিচ্ছেন, স্পষ্ট বলুন।

ধাপ ১শুরু
config (IDLE, 0, 0)
events: send wrong wrong
        expire resend wrong
ধাপ ২send
(IDLE,0,0) --send-->
(SENT, 0, 0)
ধাপ ৩দুটি ভুল
--wrong--> (SENT, 1, 0)
--wrong--> (SENT, 2, 0)
ধাপ ৪expire
--expire-->
(EXPIRED, 2, 0)
ধাপ ৫resend
fixed : (SENT, 2, 1)
buggy : (SENT, 0, 1)
ধাপ ৬তৃতীয় ভুল
fixed : (LOCKED, 3, 1)
buggy : (SENT, 1, 1)
  1. শুরু। নতুন লগইন, configuration (IDLE, 0, 0). নিচের ছয়টি event একজন আক্রমণকারী পাঠান, যিনি কোড জানেন না।
  2. Send. একমাত্র বৈধ event; কোড গেল, w = 0, r = 0.
  3. দুটি ভুল। প্রতিবার guard w < 2 সত্য, তাই SENT-এ থেকে w বাড়ে: 1, তারপর 2.
  4. মেয়াদ শেষ। আক্রমণকারী তৃতীয় চেষ্টা না করে কোডের মেয়াদ ফুরাতে দেন। EXPIRED-এ w = 2 মনে থাকে।
  5. Resend. r = 0 < 2, তাই বৈধ। ঠিক নকশায় w = 2 থেকে যায়; ভুল নকশায় resend গণনা মুছে w = 0 করে।
  6. তৃতীয় ভুল। ঠিক নকশায় w = 2 থেকে LOCKED: মোট তিনটি অনুমান। ভুল নকশায় w = 1, আক্রমণকারী আরও অনুমান চালিয়ে যেতে পারেন; চেকার দেখাবে মোট সাতটি পর্যন্ত।
৩.২(মাঝারি) “এই নকশা নিরাপদ কি না প্রমাণ করুন” প্রশ্নের জবাবে কোনো test-এর বদলে সব reachable configuration ঘুরে দেখান: (ক) একজন আক্রমণকারী সর্বোচ্চ কয়টি ভুল অনুমান করতে পারেন, resend গণনা মুছলে আর না মুছলে? (খ) কোথাও ব্যবহারকারী আটকে যান কি?
BFS over (configuration, wrong guesses so far), 5 events, guards as in 3.1
reset on resend : 31 configurations, max wrong guesses 7   (2 + 2 + 3)
keep counter    : 31 configurations, max wrong guesses 3
deadlocks (both): (EXPIRED, w, 2) for w = 0, 1, 2
fix: after the second resend, expire -> LOCKED (or a final EXPIRED_OUT with
     "start again later"), so every non-final configuration has a way out

এটি পর্ব ২৪-এর উপপাদ্য ৬.২: configuration সসীম হলে “খারাপ কিছু কখনো ঘটে না” প্রশ্নটি BFS দিয়ে decidable, আর এটি আসলে পর্ব ২০-এর emptiness. এখানে “অনুমানের সংখ্যা” configuration-এর সঙ্গে জুড়ে দেওয়ায় নিরাপত্তার শর্তটিও একটি reachability প্রশ্ন হয়েছে। ভুল নকশায় প্রতিটি দফায় দুটি করে ভুল, তারপর মেয়াদ ফুরানো, দুবার; শেষে তিনটি: 2 + 2 + 3 = 7. ছোট মনে হলেও ছয় অঙ্কের কোডে এটি সফল অনুমানের সম্ভাবনা দুই গুণের বেশি করে, আর সংখ্যাটি নকশা থেকে এসেছে, test থেকে নয়।

from collections import deque
EVENTS, FINAL = ("send", "right", "wrong", "expire", "resend"), {"VERIFIED", "LOCKED"}
def step(c, e, reset):                       # c = (state, wrong, resends)
    s, w, r = c
    if s == "IDLE" and e == "send": return ("SENT", 0, 0)
    if s == "SENT" and e == "right": return ("VERIFIED", w, r)
    if s == "SENT" and e == "wrong": return ("SENT", w + 1, r) if w < 2 else ("LOCKED", 3, r)
    if s == "SENT" and e == "expire": return ("EXPIRED", w, r)
    if s == "EXPIRED" and e == "resend" and r < 2: return ("SENT", 0 if reset else w, r + 1)
    return None                              # rejected: configuration unchanged
def explore(reset):
    start = (("IDLE", 0, 0), 0)              # (configuration, wrong guesses so far)
    seen, todo = {start}, deque([start])
    while todo:
        c, g = todo.popleft()
        for e in EVENTS:
            n = step(c, e, reset)
            if n and (n, g + (e == "wrong")) not in seen:
                seen.add((n, g + (e == "wrong"))); todo.append((n, g + (e == "wrong")))
    confs = {c for c, _ in seen}
    dead = sorted(c for c in confs
                  if c[0] not in FINAL and not any(step(c, e, reset) for e in EVENTS))
    return len(confs), max(g for _, g in seen), dead
for reset in (True, False):
    n, most, dead = explore(reset)
    print(f"resend resets counter = {reset}: {n} configurations, max wrong guesses {most}")
    print("   deadlocks:", dead)

দুই নকশাতেই পৌঁছানো configuration 31টি, কারণ গণনা মোছা বা না-মোছা configuration-এর আকার বদলায় না; বদলায় কোন পথে কতগুলো wrong জমে। তাই BFS-এর অবস্থায় “এ পর্যন্ত ভুল অনুমান” যোগ করা হয়েছে, আর তার সর্বোচ্চ মান 7 বনাম 3. দুই ক্ষেত্রেই deadlocks-এ তিনটি (EXPIRED, w, 2): দ্বিতীয় পুনঃপ্রেরণের পর মেয়াদ ফুরালে ব্যবহারকারীর কিছুই করার থাকে না। কোনো এলোমেলো test এটি পেত হয়তো, কিন্তু BFS নিশ্চিতভাবে পায়।

৩.৩(সহজ) একজন প্রার্থী চেকআউট বোতামের অবস্থা তিনটি boolean দিয়ে রাখলেন: loading, error, success. ইন্টারভিউয়ার জিজ্ঞেস করলেন, “এতে সমস্যা কী?” উত্তর দিন, আর double click-এর সমাধান বলুন।

তিনটি boolean মানে 23 = 8টি সম্ভাব্য সমন্বয়, অথচ বৈধ অবস্থা চারটি (idle, loading, success, error); বাকি চারটি, যেমন “error আর success একসঙ্গে”, কোডের কোনো ভুলে ঢুকে পড়তে পারে। পর্ব ২৪-এর JavaScript run-এ flag-এর কোড double click আর retry-তে তিনটি অনুরোধ পাঠিয়েছিল আর শেষে E = 1, S = 1; একই event-ক্রমে state machine দুটি অনুরোধ পাঠায়, কারণ (loading, click) ঘরটি খালি, তাই দ্বিতীয় click উপেক্ষিত। দেরিতে আসা পুরোনো উত্তর বাদ দিতে প্রতিটি অনুরোধের একটি id রাখুন। তবু UI একা যথেষ্ট নয়: server-এ idempotency key দিন, যাতে একই অনুরোধ দুবার এলে অর্ডার একবারই হয়।

৩.৪(কঠিন) “আপনার state machine-এর test কীভাবে লিখবেন, আর state অনেক হলে কী করবেন?”

তিন স্তরে বলুন। (১) Transition coverage: table-এর প্রতিটি সারি একবার, আর প্রতিটি খালি ঘরে একটি অবৈধ event, যাতে প্রত্যাখ্যান আর অপরিবর্তিত configuration দুটিই দেখা হয় (টেস্টিং কোর্সের পর্ব ১০)। (২) সম্পূর্ণ অনুসন্ধান: configuration সসীম আর ছোট হলে ৩.২-এর মতো BFS দিয়ে reachability, deadlock আর নিরাপত্তার শর্ত প্রমাণ। (৩) এলোমেলো stateful test: model আর আসল কোডে একই এলোমেলো event-ক্রম চালিয়ে ফল মেলানো (পর্ব ৫৮)। State বাড়লে configuration সংখ্যা গুণফলে বাড়ে (দুটি স্বাধীন অংশ মানে |S1| · |S2|), যাকে state explosion বলে; তখন symmetry বাদ দেওয়া, abstraction আর model checker-এর কৌশল লাগে (পর্ব ৭৭)। বাড়তি নম্বরের কথা: কিছু ভাষায় typestate দিয়ে অবৈধ transition compile error বানানো যায়।

৪ · জায়গায় বসে tokenizer আর recursive-descent parser

“একটি string-এ লেখা গাণিতিক expression-এর মান বের করুন, eval ছাড়া” কোডিং ইন্টারভিউর খুব চেনা প্রশ্ন। এটি আসলে দুটি প্রশ্ন: lexer (অক্ষর থেকে token) আর parser (token থেকে গাছ বা মান)। প্রথমে grammar লিখে নিন, কারণ precedence আর associativity grammar-এর স্তরেই ঠিক হয়:

E → E + T ∣ E − T ∣ T          (left recursive: fine for a CFG, fatal for recursive descent)
T → T ∗ U ∣ T / U ∣ U
U → − U ∣ NUM ∣ ( E )
after removing left recursion (lesson 30):  E → T { (+ ∣ −) T } ,  T → U { (∗ ∣ /) U }

কোঁকড়া বন্ধনী মানে “শূন্য বা বেশি বার”, যা কোডে একটি while. এভাবে লিখলে বাঁ-সংযোগও (8 − 4 − 2 = 2) ঠিক থাকে, কারণ loop বাঁ থেকে জমা করে। প্রথম ব্লকটি হাতে লেখা scanner: অঙ্কের জন্য maximal munch, আর ইচ্ছা করে শুধু ASCII অঙ্ক।

def tokens(s):                               # hand-written scanner, maximal munch
    out, i = [], 0
    while i < len(s):
        c, j = s[i], i + 1
        if c in "0123456789":                # ASCII digits only, on purpose
            while j < len(s) and s[j] in "0123456789": j += 1
            out.append(("NUM", int(s[i:j]), i))
        elif c in "+-*/()": out.append((c, c, i))
        elif c != " ": raise SyntaxError(f"col {i + 1}: unexpected {c!r}")
        i = j
    return out + [("$", None, len(s))]
print(" ".join(f"{k}:{v}" if k == "NUM" else k for k, v, _ in tokens("12*(3+45) - 6")))
print("'৫'.isdigit():", "৫".isdigit(), "| int('৫') =", int("৫"))
try: tokens("7 + ৫")
except SyntaxError as e: print("tokens('7 + ৫') ->", e)

প্রথম লাইনে token-এর ধারা: “12”, “45” এক একটি NUM, কারণ scanner অঙ্ক যতক্ষণ আসে ততক্ষণ পড়ে; ফাঁকা ঘর বাদ, শেষে $. দ্বিতীয় লাইনটি কেন str.isdigit ব্যবহার করা হয়নি তার উত্তর: Python-এ '৫'.isdigit() সত্য আর int('৫') হলো 5. নিয়মটি “শুধু ASCII” রাখায় তৃতীয় লাইনে বাংলা অঙ্ক কলাম ৫-এ স্পষ্ট error পেয়েছে। কোনটি চান, সেটি নকশার সিদ্ধান্ত; নীরবে ঘটতে দেওয়া চলবে না।

এবার parser. প্রতিটি variable-এর জন্য একটি function: expr, term, unary. দুই স্তরের loop একই ছাঁচের, তাই একটি সাধারণ loop. সংখ্যার মান Fraction, যাতে 7/2 ঠিক 7/2 থাকে। গভীরতার একটি সীমাও আছে, কারণ input অবিশ্বস্ত।

from fractions import Fraction
class Parser:            # E -> T {(+|-) T} ; T -> U {(*|/) U} ; U -> - U | NUM | ( E )
    def __init__(p, text, max_depth=100): p.t, p.k, p.d, p.max = tokens(text), 0, 0, max_depth
    def peek(p): return p.t[p.k][0]
    def eat(p, kind):
        tok = p.t[p.k]; p.k += 1
        if tok[0] != kind: raise SyntaxError(f"col {tok[2] + 1}: expected {kind!r}, got {tok[0]!r}")
        return tok
    def loop(p, ops, sub, f):                # one precedence level, left associative
        v = sub()
        while p.peek() in ops: op = p.eat(p.peek())[0]; v = f(op, v, sub())
        return v
    def expr(p): return p.loop("+-", p.term, lambda o, a, b: a + b if o == "+" else a - b)
    def term(p): return p.loop("*/", p.unary, lambda o, a, b: a * b if o == "*" else a / b)
    def unary(p):
        p.d += 1
        if p.d > p.max: raise SyntaxError(f"nesting deeper than {p.max}")
        if p.peek() == "-": p.eat("-"); v = -p.unary()
        elif p.peek() == "NUM": v = Fraction(p.eat("NUM")[1])
        else: p.eat("("); v = p.expr(); p.eat(")")
        p.d -= 1; return v
def parse(text): p = Parser(text); v = p.expr(); p.eat("$"); return v
print("2*(3+4)-5 =", parse("2*(3+4)-5"), "| 8-4-2 =", parse("8-4-2"), "| 2*-3 =", parse("2*-3"), "| 7/2 =", parse("7/2"))

চারটি ফলই প্রত্যাশিত: 2*(3+4)-5 = 9, বাঁ-সংযোগে 8-4-2 = 2, একক বিয়োগ 2*-3 = -6, আর ভাগ 7/2 ভগ্নাংশ হিসেবে। প্রতিটি token একবারই পড়া হয়, কোনো function পেছনে ফেরে না, তাই সময় token-সংখ্যায় রৈখিক; ডাকের গভীরতা বন্ধনী আর একক বিয়োগের গভীরতার সমান।

ধাপ ১token
2 * ( 3 + 4 ) - 5 $
^
ধাপ ২প্রথম operand
expr → term → unary
unary: NUM 2
term sees *
ধাপ ৩বন্ধনী
term: eat *
unary: eat (  depth 1
  → expr (inner)
ধাপ ৪ভেতরের expr
3, sees +, eat +
term → 4
inner value 7, sees )
ধাপ ৫গুণ শেষ
eat )  depth 0
term: 2 * 7 = 14
sees - : not * or /
ধাপ ৬বিয়োগ
expr: eat -
term → 5
14 - 5 = 9, sees $
ধাপ ৭শেষ
parse: eat $
result 9
tokens read: 10, once each
  1. Token. Scanner ৯টি token আর শেষে $ দিয়েছে। Parser বাঁ থেকে একটি একটি দেখবে, একবারে শুধু পরেরটি (lookahead ১)।
  2. প্রথম operand. expr ডাকে term, সে ডাকে unary, যে NUM 2 খায়। ফিরে এসে term পরের token * দেখে: তার নিজের স্তরের operator.
  3. বন্ধনী। * খাওয়ার পর ডান operand-এর জন্য আবার unary, যে ( দেখে গভীরতা ১ করে আর নতুন একটি expr ডাকে।
  4. ভেতরের expr. 3 পড়ে, + দেখে যোগের loop চালায়, 4 পড়ে মান 7. পরের token ) কোনো operator নয়, তাই ভেতরের expr থামে।
  5. গুণ শেষ। unary ) খেয়ে গভীরতা ০ করে আর 7 ফেরত দেয়; term হিসাব করে 2 · 7 = 14. পরের - গুণ-ভাগ নয়, তাই term ফেরে।
  6. বিয়োগ। বাইরের expr - দেখে, নতুন term থেকে 5 পায়, হিসাব 14 − 5 = 9. এরপর $.
  7. শেষ। parse নিশ্চিত হয় যে পুরো input খাওয়া হয়েছে ($); নইলে “(1+2))”-এর মতো বাড়তি অংশ নীরবে বাদ পড়ত। মোট ১০টি token, প্রতিটি একবার।
import random
random.seed(85)
def gen(d):                                  # random expression text, depth <= d
    r = random.random()
    if d == 0 or r < 0.3: return str(random.randint(0, 20))
    if r < 0.4: return "-" + gen(d - 1)
    if r < 0.55: return "(" + gen(d - 1) + ")"
    return gen(d - 1) + random.choice(" + - * / ".split()) + gen(d - 1)
ok = same = zero = 0
for _ in range(3000):
    s = gen(5)
    try: mine = parse(s)
    except ZeroDivisionError: zero += 1; continue
    ref = eval(s)            # reference: Python's own parser, on our own generated text
    ok += 1; same += abs(float(mine) - ref) <= 1e-9 * max(1, abs(ref))
print(f"random expressions: {ok} compared, {same} agree, {zero} divide by zero")
for bad in ["2*(3+4", "2**3", "7 -", "12 + x", "(1+2))", "(" * 150 + "1" + ")" * 150]:
    try: parse(bad); print(bad, "-> accepted?!")
    except SyntaxError as e: print(f"{bad[:12]!r:15} -> {e}")

Seed 85 দিয়ে বানানো ৩০০০টি এলোমেলো expression-এর 84টিতে শূন্য দিয়ে ভাগ, বাকি 2916টির প্রতিটিতে আমাদের মান Python-এর নিজের parser-এর মানের সমান (এখানে eval শুধু নিজের বানানো string-এ, তুলনার জন্য)। তারপর ছয়টি ভাঙা input: অসমাপ্ত বন্ধনীতে কলাম ৭-এ expected ')', 2**3-এ কলাম ৩, অচেনা অক্ষর x-এ কলাম ৬, বাড়তি )-এ কলাম ৬, আর ১৫০ স্তরের বন্ধনীতে nesting deeper than 100. লক্ষ করুন 7 --এর বার্তা “expected '('” একটু বিভ্রান্তিকর; ভালো উত্তরে বলুন “expected number or '('”, যা ৪.৩-এর বিষয়।

৪.১(সহজ) কেউ grammar-এর নিয়ম E → E + T হুবহু কোডে লিখলেন: def expr(): v = expr(); eat('+'); .... কী ঘটবে, আর কেন CFG-তে নিয়মটি নির্দোষ?

expr কোনো token না খেয়েই নিজেকে ডাকে, তাই অসীম recursion, আর Python-এ RecursionError. CFG-তে নিয়মটি কোনো সমস্যা নয়: derivation শুধু একটি বৈধ ক্রম বলে, কীভাবে খোঁজা হবে বলে না; LR parser (পর্ব ৩৯) বাঁ-recursion পছন্দই করে। Top-down parser-এর জন্য left recursion দূর করতে হয়: A → Aα ∣ β থেকে A → βA′, A′ → αA′ ∣ ε, যা কোডে একটি while. সাধারণ ভুল: ডান-recursion E → T + E লিখে recursion এড়ানো, যাতে 8 − 4 − 2 ভুল করে 8 − (4 − 2) = 6 হয়।

৪.২(মাঝারি) এবার ঘাত ^ যোগ করতে হবে, যা সবচেয়ে শক্ত আর ডান-সংযোগী (2^3^2 = 2^9 = 512). নতুন স্তর যোগ করবেন, নাকি অন্য কৌশল? দশটি precedence-স্তর হলে?

ছোট ভাষায় একটি নতুন স্তর যথেষ্ট: U → − U ∣ W, W → A [ ^ U ], A → NUM ∣ ( E ). ^-এর ডান দিকে আবার U ডাকায় ডান-সংযোগ আসে (loop নয়, recursion), আর −2^2 হয় −(2^2), গণিতের প্রচলিত অর্থে। দশ স্তরে দশটি প্রায় একই function হয়, তখন Pratt parser (precedence climbing) ভালো: প্রতিটি operator-এর একজোড়া binding power (l, r), আর একটি function expr(min). পর্ব ৪২-এর টেবিলে + − (10, 11), ∗ / (20, 21), ^ (31, 30): l < r মানে বাঁ-সংযোগ, l > r মানে ডান-সংযোগ। সেই পর্বের চেকারে সঠিক টেবিলে ২২২২২টি expression-এর একটিতেও গাছ আলাদা হয়নি, আর ^-এর সংখ্যা উল্টে (30, 31) দিলে ২২৩২টিতে আলাদা, যেমন 2^2^2. একটি অঙ্কের ভুলে associativity উল্টে যায়, তাই এমন টেবিল সবসময় brute force-এ যাচাই করুন।

৪.৩(মাঝারি) Parser-এ input আসবে ব্যবহারকারীর কাছ থেকে। ভালো error message কেমন হবে, আর ((((…1…)))) ধরনের লক্ষ স্তরের input-এ কী সমস্যা?

ভালো বার্তায় তিনটি জিনিস: কোথায় (কলাম, দরকার হলে লাইন), কী পাওয়া গেল, আর কী প্রত্যাশিত ছিল। “প্রত্যাশিত” সেটটি আসলে LL(1)-এর FIRST সেট (পর্ব ৩৮): unary-এর শুরুতে FIRST = {−, NUM, (}, তাই বার্তা হওয়া উচিত “expected '-', number or '('”. গভীর input-এ recursive descent-এর ডাকের stack input-এর গভীরতার সমান বাড়ে, আর Python-এর recursion সীমা বা আসল stack ফুরিয়ে যেতে পারে: একজন ব্যবহারকারী এক লাইনে service থামিয়ে দিতে পারেন। প্রতিকার: গভীরতার স্পষ্ট সীমা (উপরের কোডের মতো), অথবা explicit stack-সহ parser, যা আসলে পর্ব ৩৪-এর PDA. প্রথম error-এ থামবেন, নাকি panic mode-এ এগিয়ে আরও error জমাবেন, তাও বলে দিন।

৪.৪(কঠিন) “আপনার parser কি সব সময় রৈখিক সময়ে চলে? Backtracking parser কেন exponential হতে পারে, আর কোন শর্তে backtracking লাগে না?”

এই grammar LL(1): প্রতিটি সিদ্ধান্ত একটি lookahead token থেকে নেওয়া যায় (কোন নিয়ম, loop চলবে কি না), তাই কোনো সিদ্ধান্ত বদলাতে হয় না আর সময় O(n). শর্তটি পর্ব ৩৮-এর LL(1) শর্ত: একই variable-এর বিকল্পগুলোর FIRST সেট আলাদা, আর ε-বিকল্প থাকলে FOLLOW-এর সঙ্গেও আলাদা। Grammar এমন না হলে একটি সরল backtracking parser প্রতিটি বিকল্প চেষ্টা করে ব্যর্থ হলে ফেরে, আর ২.১-এর regex-এর মতো একই অংশের অনেক ভাগ চেষ্টা করে exponential হতে পারে। প্রতিকার: left factoring, memoization (packrat parsing, যা PEG-এ রৈখিক সময় দেয়, বেশি মেমরির দামে), অথবা যেকোনো CFG-এর জন্য Earley বা GLR (পর্ব ৪১), যার সবচেয়ে খারাপ সময় n3. প্রমাণ হিসেবে পর্ব ৩৮-এর run উল্লেখ করতে পারেন: হাতে লেখা recursive descent আর Lark-এর Earley parser ৪০০০টি query-তে একটিতেও দ্বিমত করেনি।

৫ · “এটা কি NP-hard?” — ছদ্মবেশ চেনা আর reduction-এর খসড়া

বাস্তবে কেউ বলেন না “এটি 3-COLOR”. বলেন “তিনটি ডেলিভারি slot-এ অর্ডার ভাগ করুন, যাতে একই রাইডারের দুটি কাজ এক slot-এ না পড়ে”. নিচের জোড়াগুলো মুখস্থ রাখার মতো: বাঁ দিকেরটি P-তে, ডান দিকেরটি NP-complete, আর দেখতে প্রায় এক।

P-তে (দ্রুত algorithm জানা)NP-complete (decision রূপ)পার্থক্য এক কথায়
দুই শিফট: 2-COLOR (BFS)তিন slot: 3-COLORদুই রঙে প্রতিটি পছন্দ পাশেরটিকে বাধ্য করে
প্রতি শর্তে দুটি literal: 2SATতিনটি literal: 3SAT2SAT-এ implication graph-এর SCC
প্রতিটি রাস্তা একবার: Euler pathপ্রতিটি জেলা একবার: HAMPATHEuler-এ শুধু degree গোনা
রাইডার আর অর্ডার জোড়া: bipartite matchingতিন দলের জোড়া (3-dimensional matching)দুই দলে augmenting path কাজ করে
দুই জেলার সবচেয়ে ছোট পথসব জেলা ঘুরে ছোট রুট: TSPTSP-তে কোনগুলো ঘোরা হলো মনে রাখতে হয়
ছোট সংখ্যায় SUBSET-SUM (DP)বড় সংখ্যায় SUBSET-SUMpseudo-polynomial (ভাগ ৭)
৫.১(সহজ) একজন প্রার্থী বললেন: “আমি বাজারঘরের slot-বণ্টন সমস্যাকে SAT-এ রূপান্তর করেছি, তাই এটি NP-hard.” ভুলটি কোথায়?

দিক উল্টো। X ≤p SAT মানে “X, SAT-এর চেয়ে কঠিন নয়”: এতে X-এর একটি সমাধানের পথ মেলে (SAT solver দিয়ে), কঠিনতার প্রমাণ নয়। 2-COLOR-কেও SAT-এ রূপান্তর করা যায়, অথচ সেটি P-তে। NP-hard দেখাতে উল্টো দিক লাগে: একটি জানা NP-complete A থেকে A ≤p X. মনে রাখার বাক্য (পর্ব ৫৯): “A ≤p B আর A NP-hard হলে B NP-hard; A ≤p B আর B ∈ P হলে A ∈ P”. ইন্টারভিউতে দুটি দিকেরই নাম দিন: কঠিনতা প্রমাণে SAT ≤p X, সমাধানে X ≤p SAT; পর্ব ৭৩ দ্বিতীয়টি নিয়ে।

৫.২(মাঝারি) বাজারঘর ঈদের “প্রোমো বান্ডল” বানাবে: n টি পণ্যের কিছু জোড়া একসঙ্গে দেওয়া যায় না (একই সরবরাহকারী বা স্টকের সংঘাত)। প্রশ্ন: “k টি পণ্য বাছা যায় কি, যাদের কোনো দুটির মধ্যে সংঘাত নেই?” এটি NP-complete দেখান, ইন্টারভিউর খসড়ার আকারে।
BUNDLE = { ⟨G, k⟩ : graph G (product = vertex, conflict = edge) has k pairwise
                    non-adjacent vertices }
1. in NP  : certificate = the k products ; check all pairs in O(k²)
2. hard   : INDEPENDENT-SET ≤p BUNDLE with f(⟨G, k⟩) = ⟨G, k⟩  (same question)
            (or CLIQUE ≤p BUNDLE with f(⟨G, k⟩) = ⟨complement of G, k⟩)
3. ⇔      : S is a clique in G ⇔ S is independent in the complement
4. bonus  : S independent ⇔ V \ S is a vertex cover, so BUNDLE(G, k) ⇔ VC(G, n − k)
checker   : all 1024 graphs on 5 vertices × k = 1..5 -> 5120 pairs, 0 disagreements

খসড়ায় চারটি বাক্যই যথেষ্ট, কিন্তু প্রতিটি লাগে: NP-তে আছে (certificate আর polynomial যাচাই), reduction-এর দিক (জানা সমস্যা থেকে নতুনে), f polynomial সময়ে হিসাবযোগ্য (complement নিতে O(n2)), আর দুই দিকের ⇔. Brute force কোনো প্রমাণ নয়, কিন্তু ভুল দিক বা ভুল k (যেমন n − k-এর জায়গায় k) এক মুহূর্তে ধরে।

from itertools import combinations
V = range(5); E_ALL = list(combinations(V, 2))      # all 10 possible edges on 5 vertices
def independent(E, S): return all(not (u in S and v in S) for u, v in E)
def clique(E, S): return all((u, v) in E for u, v in combinations(sorted(S), 2))
def cover(E, S): return all(u in S or v in S for u, v in E)
def best(E, test, k): return any(test(E, set(S)) for S in combinations(V, k))
checked = agree_c = agree_v = 0
for mask in range(1 << len(E_ALL)):                 # every graph on 5 labelled vertices
    E = {e for i, e in enumerate(E_ALL) if mask >> i & 1}
    comp = set(E_ALL) - E                           # f(G, k) = (complement of G, k)
    for k in range(1, 6):
        checked += 1
        is_ = best(E, independent, k)               # "bundle of k non-conflicting products"
        agree_c += is_ == best(comp, clique, k)     # IS  <=>  CLIQUE in the complement
        agree_v += is_ == best(E, cover, 5 - k)     # IS of size k <=> VC of size n - k
print(f"(graph, k) pairs: {checked}")
print(f"IS(G,k) == CLIQUE(complement,k): {agree_c}   IS(G,k) == VC(G,5-k): {agree_v}")

৫টি vertex-এর সম্ভাব্য ১০টি edge-এর প্রতিটি উপসেট একটি graph, তাই 210 = 1024টি graph, আর k = 1 থেকে 5: মোট 5120টি (graph, k) জোড়া। তিনটি প্রশ্নের উত্তর সবগুলোতে মিলেছে: G-তে k আকারের independent set ⇔ complement-এ k আকারের clique ⇔ G-তে n − k আকারের vertex cover. ছোট ক্ষেত্রে এমন ⇔ যাচাই reduction লেখার আগে আর পরে দুবারই কাজে লাগে।

৫.৩(মাঝারি) রাইডারদের দুই শিফটে ভাগ করতে হবে, যাতে “একসঙ্গে কাজ করা যায় না” এমন জোড়া এক শিফটে না পড়ে। পরের সপ্তাহে শিফট হলো তিনটি। দুটি প্রশ্নের জটিলতা কী, আর ইন্টারভিউতে কী কোড লিখবেন?

দুই শিফট মানে graph-টি bipartite কি না: BFS বা DFS দিয়ে রঙ করুন, একটি edge-এর দুই প্রান্তে একই রঙ পেলে উত্তর “না”, আর সেই বিজোড় cycle-টিই প্রমাণ; সময় O(V + E). তিন শিফট মানে 3-COLOR, যা NP-complete (পর্ব ৬১), তাই কোনো polynomial algorithm জানা নেই, আর P ≠ NP হলে (খোলা প্রশ্ন, যদিও বেশিরভাগ গবেষক তাই মনে করেন) থাকবেও না। ইন্টারভিউতে তিন শিফটের জন্য: ছোট দলে backtracking (প্রতিটি রাইডারকে একটি রঙ, সংঘাত হলেই পিছু হটা), বড় দলে SAT encoding বা heuristic (ভাগ ৬)। এক রঙ থেকে দুই রঙে কাজ সহজ, তিনে কঠিন: এই লাফটি বললেই প্রশ্নকর্তা বোঝেন যে আপনি দেখেছেন।

৫.৪(কঠিন) “বাজারঘরের ভ্যান ৬৪টি জেলা ঘুরে আসবে, সবচেয়ে ছোট রুটের কোড লিখুন, যেন সবসময় সেরা উত্তর দেয় আর দ্রুত চলে।” কী বলবেন?

প্রথমে সৎ কথাটি: “সবসময় সেরা” আর “সবসময় দ্রুত (polynomial)” একসঙ্গে দিতে পারলে P = NP প্রমাণ হতো, কারণ TSP-এর decision রূপ NP-complete. তারপর বিকল্পগুলো। Exact: Held–Karp DP সময় প্রায় n2 · 2n, n = 64-এ অবাস্তব; বাস্তবের exact solver (branch and bound, ILP) অনেক instance-এ দ্রুত, কিন্তু নিশ্চয়তা নেই। Approximation: দূরত্ব ত্রিভুজ-অসমতা মানলে (metric TSP) MST-ভিত্তিক algorithm সর্বোচ্চ দ্বিগুণ, Christofides 1.5 গুণ (সাধারণ, অ-metric TSP-তে কোনো ধ্রুবক ratio সম্ভব নয়, যদি না P = NP; পর্ব ৭১)। Heuristic: nearest neighbour দিয়ে শুরু, তারপর 2-opt-এর মতো local search, সময়ের সীমা দিয়ে। শেষে জিজ্ঞেস করুন: “সেরা” কতটা জরুরি? দৈনিক রুটে ভালো একটি উত্তর এক সেকেন্ডে প্রায়ই সেরা উত্তরের চেয়ে বেশি কাজের।

৬ · Exact, approximation, heuristic, SAT না ILP — বেছে নেওয়ার যুক্তি

পরিস্থিতিপছন্দনিশ্চয়তা
n ≤ প্রায় ২০সব উপসেট বা bitmask DP, 2n · poly(n)সেরা উত্তর
n প্রায় ৪০, যোগফলের প্রশ্নmeet in the middle, প্রায় 2n/2সেরা উত্তর
উত্তরের আকার k ছোটFPT, যেমন vertex cover 2k · nসেরা উত্তর
সংখ্যাগুলো ছোটpseudo-polynomial DPসেরা উত্তর
যদি-তাহলে আর “সব আলাদা” ধরনের শর্তSAT solverসমাধান বা UNSAT-এর প্রমাণ, সময় অনিশ্চিত
খরচ, ধারণক্ষমতা, linear শর্তILP (integer programming)সেরা উত্তর আর নিম্নসীমা, সময় অনিশ্চিত
দ্রুত উত্তর চাই, মানের সীমা জানা দরকারapproximation algorithmপ্রমাণিত ratio
দ্রুত, ভালো উত্তর হলেই চলেheuristic, local searchকোনো নিশ্চয়তা নেই
৬.১(মাঝারি) Vertex cover-এর দুটি দ্রুত পদ্ধতি: (ক) একটি maximal matching-এর প্রতিটি edge-এর দুই প্রান্ত নেওয়া; (খ) প্রতিবার সবচেয়ে বেশি edge-ওয়ালা vertex নেওয়া। কোনটি “approximation algorithm”, কোনটি heuristic? এলোমেলো graph-এ কোনটি ভালো দেখায়?

(ক) একটি 2-approximation, আর প্রমাণ দুই লাইনের: matching-এর edge-গুলো কোনো vertex ভাগ করে না, তাই যেকোনো cover-কে প্রতিটির অন্তত এক প্রান্ত নিতে হয়: OPT ≥ |M|. আমরা নিই 2|M| ≤ 2 · OPT. আর matching maximal বলে প্রতিটি edge ঢাকা পড়ে। (খ) একটি heuristic: এলোমেলো graph-এ প্রায়ই খুব ভালো, কিন্তু খারাপভাবে বানানো কিছু graph-এ এর ratio n বাড়ার সঙ্গে বাড়তে থাকে বলে জানা (log n-এর ক্রমে), তাই কোনো ধ্রুবক নিশ্চয়তা নেই। নিচের চেকার দুটির সত্যিকারের ছবি দেখায়।

import random
from itertools import combinations
random.seed(7)
def exact(n, E):                                  # brute force: smallest vertex cover
    for k in range(n + 1):
        for S in combinations(range(n), k):
            if all(u in S or v in S for u, v in E): return k
def matching_cover(E):                            # 2-approximation: both ends of a maximal matching
    C = set()
    for u, v in E:
        if u not in C and v not in C: C |= {u, v}
    return len(C)
def greedy_degree(n, E):                          # heuristic: take the busiest vertex first
    E, C = set(E), set()
    while E:
        deg = {}
        for u, v in E: deg[u] = deg.get(u, 0) + 1; deg[v] = deg.get(v, 0) + 1
        x = max(sorted(deg), key=deg.get); C.add(x); E = {e for e in E if x not in e}
    return len(C)
r_m, r_g = [], []
for _ in range(300):
    n = 10; E = [e for e in combinations(range(n), 2) if random.random() < 0.3]
    random.shuffle(E); opt = exact(n, E)
    if opt == 0: continue
    r_m.append(matching_cover(E) / opt); r_g.append(greedy_degree(n, E) / opt)
print(f"graphs: {len(r_m)} (n = 10, edge chance 0.3)")
print(f"matching 2-approx : worst ratio {max(r_m):.2f}, mean {sum(r_m) / len(r_m):.3f}")
print(f"max-degree greedy : worst ratio {max(r_g):.2f}, mean {sum(r_g) / len(r_g):.3f}")

Seed 7-এর ৩০০টি এলোমেলো graph-এ (১০টি vertex, প্রতিটি edge ৩০% সম্ভাবনায়) brute force-এ সেরা cover বের করে দুই পদ্ধতির অনুপাত। Matching-পদ্ধতির সবচেয়ে খারাপ অনুপাত ঠিক 2.00, গড় 1.581: নিশ্চয়তার সীমা ছুঁয়েছে, পেরোয়নি। Greedy-র সবচেয়ে খারাপ 1.25, গড় 1.022: এখানে অনেক ভালো। ইন্টারভিউর শিক্ষা এটিই: গড়ে ভালো আর নিশ্চিতভাবে ভালো আলাদা জিনিস। বাস্তবে দুটি একসঙ্গে চালিয়ে ছোটটি নেওয়া যায়, তাতে নিশ্চয়তাও থাকে।

৬.২(মাঝারি) তিনজন রাইডার, আটটি অর্ডার; প্রতিটি অর্ডার ঠিক একজনকে, প্রত্যেক রাইডারের মোট সময় ৬০ মিনিটের মধ্যে, আর মোট যাত্রার সময় সবচেয়ে কম। SAT, না ILP? Greedy কেন যথেষ্ট নয়?

শর্তগুলো linear (সময়ের যোগফল ≤ 60) আর লক্ষ্য একটি linear খরচ, তাই ILP স্বাভাবিক পছন্দ; SAT-এ সংখ্যার যোগফল encode করা যায়, কিন্তু সেটি ভারী। পর্ব ৭৩-এর সত্যিকারের run (PuLP 3.3.2 আর CBC 2.10.3) এই প্রশ্নেরই: প্রতিটি অর্ডারকে সবচেয়ে সস্তা রাইডারকে দেওয়া greedy-তে মোট ১০৯ মিনিট, কিন্তু একজনের ভার ৬৫, অর্থাৎ শর্ত ভাঙে; LP relaxation ১১০.৫২ (নিম্নসীমা, কিছু চলক ভগ্নাংশে); ILP-এর সেরা উত্তর ১১৬, আর 38 = 6561টি বণ্টনের brute force-ও ১১৬. ইন্টারভিউর তিনটি বাক্য: greedy শর্ত মানে না; LP একটি নিম্নসীমা দেয়, যা দিয়ে যেকোনো উত্তরের মান মাপা যায়; ILP সেরা উত্তর দেয়, কিন্তু সাধারণভাবে NP-hard বলে সময়ের নিশ্চয়তা নেই।

৬.৩(সহজ) “আমাদের heuristic গত মাসের সব ডেটায় সেরা উত্তরের ২% কাছে ছিল, তাই এটি সমস্যাটি সমাধান করে।” কী বলবেন?

দাবিটি অভিজ্ঞতার, প্রমাণের নয়, আর দুটোই মূল্যবান। ভালো উত্তর তিনটি সতর্কতা যোগ করে: (১) “সেরা উত্তর” কীভাবে জানা গেল? ছোট instance-এ exact solver বা একটি LP নিম্নসীমা দিয়ে মাপুন, নইলে ২% সংখ্যাটির ভিত্তি নেই। (২) ডেটা বদলালে (ঈদের চাপ, নতুন জেলা) heuristic খারাপ হতে পারে; দুষ্টভাবে বানানো বা চরম instance-এ পরীক্ষা করুন। (৩) সময় আর মানের সীমা পর্যবেক্ষণে রাখুন, আর একটি fallback (approximation বা সময়-সীমিত exact) রাখুন। ৬.১-এর ফল এখানে উদাহরণ: greedy-র গড় ভালো, তবু নিশ্চয়তা matching-এর।

৭ · Complexity-র যুক্তি — pseudo-polynomial DP আর input-এর encoding

ঝালিয়ে নিন: পর্ব ০৫ · encoding, পর্ব ৫৭ · class P, পর্ব ৬১ · strong আর weak NP-completeness; DP-র কৌশল DSA কোর্সের পর্ব ৫৩-এ।

৭.১(মাঝারি) “SUBSET-SUM-এর O(n · t) DP তো আছে। তাহলে SUBSET-SUM NP-complete হয় কীভাবে? আপনি কি P = NP প্রমাণ করে ফেললেন?”

না। Complexity মাপা হয় input-এর দৈর্ঘ্যে, অর্থাৎ bit-সংখ্যায়। t লিখতে লাগে প্রায় log2 t bit, তাই n · t আসলে n · 2(t-এর bit সংখ্যা): input-এর দৈর্ঘ্যে exponential. এমন algorithm-কে বলে pseudo-polynomial: সংখ্যাগুলো unary-তে লিখলে (unary encoding) polynomial, binary-তে নয়। এজন্য SUBSET-SUM “weakly” NP-complete; অন্যদিকে 3-COLOR বা bin packing strongly NP-complete, যেখানে সংখ্যা ছোট রাখলেও কঠিনতা যায় না। ব্যবহারিক বাক্য: “ওজন কেজিতে পূর্ণসংখ্যা আর সীমা কয়েকশো কেজি হলে DP চমৎকার; টাকা পয়সা পর্যন্ত আর সীমা কোটি হলে নয়।”

import random
random.seed(3)
def subset_sum(nums, t):          # bitset DP: bit s of reach is 1 <=> some subset sums to s
    reach = 1
    for x in nums: reach |= reach << x
    return reach >> t & 1
print(" b  input bits   DP cells n*(t+1)  answer")
for b in (8, 12, 16, 20, 32, 64):                    # 10 numbers of b bits each
    nums = [random.randrange(1, 2 ** b) for _ in range(10)]
    t = sum(random.sample(nums, 5))                  # a target that is reachable
    bits = sum(x.bit_length() for x in nums) + t.bit_length()
    ans = subset_sum(nums, t) if b <= 20 else "not run"
    print(f"{b:2}  {bits:10}  {10 * (t + 1):17.3g}  {ans}")
N = 1_000_003                                         # trial division: about sqrt(N) steps
print("digits of N:", len(str(N)), "| divisions up to sqrt(N):", int(N ** 0.5) - 1)

প্রতিটি সারিতে ১০টি b-bit সংখ্যা। Input-এর মোট bit (input bits) b-এর সঙ্গে রৈখিকভাবে বাড়ে: 84, 127, 165, 219, তারপর 343, 704. কিন্তু DP টেবিলের ঘর n · (t + 1) বাড়ে 2b-এর হারে: 5.71e+03 থেকে 3.79e+07, আর b = 64-এ 6.37e+20, যা কোনো কম্পিউটারে চলবে না, যদিও input মাত্র ৭০৪ bit. Bitset-কৌশলে (reach |= reach << x) প্রতিটি সংখ্যার জন্য একটি shift আর একটি OR, যা contest-এ DP-কে অনেক গুণ দ্রুত করে, কিন্তু 2b-এর বৃদ্ধি বদলায় না। শেষ লাইন ৭.২-এর জন্য: ৭ অঙ্কের N-এ trial division প্রায় ৯৯৯টি ভাগ।

৭.২(মাঝারি) “N মৌলিক কি না, 2 থেকে √N পর্যন্ত ভাগ করে দেখি। এটি O(√N), তাই polynomial.” ঠিক কি?

N-এর মানে sublinear, কিন্তু input-এর দৈর্ঘ্য d = N-এর অঙ্ক বা bit সংখ্যা। √N ≈ 10d/2, যা d-তে exponential: ৭ অঙ্কে প্রায় হাজার ভাগ, ৪০ অঙ্কে প্রায় 1020. মৌলিকতা পরীক্ষা তবুও P-তে আছে: AKS algorithm (২০০২) deterministic polynomial সময়ে, আর বাস্তবে Miller–Rabin-এর মতো randomized পরীক্ষা ব্যবহার হয়, যার ভুলের সম্ভাবনা পুনরাবৃত্তিতে যত খুশি কমানো যায় (পর্ব ৬৯)। Factoring (গুণনীয়ক বের করা) আলাদা প্রশ্ন: তার কোনো polynomial classical algorithm জানা নেই, আর সেটি NP-complete কি না তাও জানা নেই।

৭.৩(কঠিন) Contest-এর সমস্যা: n ≤ 40 টি সংখ্যা, প্রতিটি 1012 পর্যন্ত; কোনো উপসেটের যোগফল ঠিক T কি না। কোন পদ্ধতি, কেন অন্যগুলো নয়?

সংখ্যা বড়, তাই O(n · T) DP বাদ (T প্রায় 4 · 1013 পর্যন্ত)। সব উপসেট 240 ≈ 1.1 · 1012, এটিও বাদ। Meet in the middle: সংখ্যাগুলো দুই ভাগে ২০টি করে, প্রতিটি ভাগের 220 ≈ ১০ লক্ষ যোগফল বানিয়ে একটি ভাগ সাজান, আর অন্য ভাগের প্রতিটি s-এর জন্য T − s খুঁজুন (binary search বা hash). সময় প্রায় 220 · 20. তত্ত্বের দিক: এটি এখনো exponential, শুধু ঘাত অর্ধেক; NP-completeness বদলায়নি। ইন্টারভিউতে সীমাগুলো পড়েই পদ্ধতি বাছাই দেখান: “n ছোট কিন্তু সংখ্যা বড়, তাই উপসেটের দিকে কাজ করব, মানের দিকে নয়।”

৮ · Halting-ধাঁচের trick প্রশ্ন — timeout, static analysis আর “সব bug ধরা” tool

৮.১(সহজ) “বাজারঘরের অনলাইন judge-এ জমা দেওয়া কোড চালানোর আগে একটি function লিখুন, যা বলে দেবে কোডটি অসীম loop-এ পড়বে কি না।” কী উত্তর দেবেন?

সাধারণভাবে এমন function অসম্ভব: এটি ঠিক halting problem, যা পর্ব ৫১-এ diagonalization দিয়ে undecidable প্রমাণিত। এর মানে এমন কোনো algorithm নেই যা সব কোডে থামে আর সব কোডে ঠিক উত্তর দেয়। তারপর বাস্তব সমাধান বলুন: প্রতিটি run-এ সময় আর মেমরির সীমা (judge আসলে এটিই করে), আর সীমা পেরোলে “time limit exceeded”, যা “অসীম loop” নয়, শুধু “বাজেটে শেষ হয়নি”. সাধারণ কিছু loop (যেমন while True: যাতে কোনো break নেই) static analysis-এ ধরা যায়, কিন্তু সেটি অর্ধেক উত্তর, কারণ কিছু কোড ধরা পড়বে না।

৮.২(মাঝারি) “তাহলে এই program থামবে কি না বলুন: while x != 0: x = (x*x + 1) % m, x আর m দেওয়া।” এটি কি halting problem-এর মতোই অসম্ভব? আর while n != 1: n = n/2 if n even else 3n + 1?

প্রথমটি decidable, কারণ x-এর মান মাত্র m টি: pigeonhole-এ m ধাপের মধ্যে হয় x = 0 (থামে), নয় কোনো মান আবার আসে, আর deterministic বলে তখন থেকে চিরকাল একই চক্র। অর্থাৎ সসীম স্মৃতির program একটি সসীম যন্ত্র, আর তার জন্য halting সহজ (চক্র খোঁজা, যেমন একটি set বা Floyd-এর পদ্ধতি)। দ্বিতীয়টি Collatz-এর প্রশ্ন: n সীমাহীন, আর “সব n-এ থামে” দাবিটি Collatz conjecture, যা আজও খোলা। অনেক বড় পর্যন্ত কম্পিউটারে যাচাই হয়েছে, কিন্তু প্রমাণ নেই। দুটির পার্থক্যই প্রশ্নের মূল: undecidability আসে সীমাহীন স্মৃতি থেকে।

def halts_finite(x0, m):              # program: while x != 0: x = (x*x + 1) % m
    seen, x, steps = set(), x0, 0     # only m possible states -> repeat or stop within m steps
    while x != 0:
        if x in seen: return f"LOOPS FOREVER (state {x} repeats after {steps} steps)"
        seen.add(x); x = (x * x + 1) % m; steps += 1
    return f"HALTS after {steps} steps"
for m, x0 in ((10, 1), (13, 2), (1000, 2)):
    print(f"m = {m:4}, x0 = {x0}:", halts_finite(x0, m))
def collatz_steps(n, cap):            # unbounded integers: we can only run with a cap
    k = 0
    while n != 1 and k < cap:
        n = n // 2 if n % 2 == 0 else 3 * n + 1; k += 1
    return k if n == 1 else None
s = {n: collatz_steps(n, 10_000) for n in range(1, 100_000)}
print("n < 100000 that did not reach 1 within the cap:", [n for n in s if s[n] is None])
print("most steps:", max(s.values()), "at n =", max(s, key=s.get))

m = 10-এ x0 = 1 থেকে ৫ ধাপে থামে, m = 13-এ x0 = 2 থেকে ২ ধাপে (2 → 5 → 26 mod 13 = 0). m = 1000-এ x0 = 2 থেকে ৮ ধাপ পরে state 26 আবার আসে, তাই চিরকাল চলবে, আর এটি প্রমাণ, অনুমান নয়। আসলে m = 1000-এ কোনো শুরু থেকেই থামে না, কারণ x2 + 1 কখনো 8 দিয়ে বিভাজ্য নয়। Collatz অংশে ১ লক্ষের কম প্রতিটি n ১০,০০০ ধাপের মধ্যে 1-এ পৌঁছেছে (তালিকা []), সবচেয়ে বেশি 350 ধাপ n = 77031-এ। এটি একটি নির্দিষ্ট সীমা পর্যন্ত পর্যবেক্ষণ, প্রমাণ নয়।

৮.৩(মাঝারি) “এমন একটি linter বানান যা সব null-dereference ধরে আর কখনো ভুল সতর্কতা দেয় না।” প্রতিক্রিয়া কী?

“কোনো input-এ program null-dereference করে কি না” program-এর আচরণের প্রশ্ন, তাই Rice-এর theorem-এর আওতায়: যে tool সব program-এ থামে, সে একসঙ্গে sound (কিছু মিস করে না) আর complete (কোনো ভুল সতর্কতা নেই) হতে পারে না (পর্ব ৫৫-এর উপপাদ্য ২.২, HALTTM ≤m CRASH). তাই প্রশ্ন হলো কোন আপস: type checker সাধারণত sound দিকে ঝোঁকে আর কিছু ভুল সতর্কতা দেয়; bug-খোঁজা tool ভুল সতর্কতা কমাতে কিছু bug মিস করে। সেই পর্বের mypy run-এ দুটিই দেখা গেছে: একটি ভুল সতর্কতা, একটি মিস। ভালো উত্তর শেষে প্রস্তাব দেয়: ভাষার নিয়ম কঠোর করা (nullable type আলাদা), যাতে প্রশ্নটি syntactic হয়ে decidable হয়ে যায়।

৮.৪(মাঝারি) তিনটি “সমান কি না” প্রশ্ন: (ক) দুটি regex একই language বর্ণনা করে কি? (খ) দুটি CFG? (গ) দুটি Python function সব input-এ একই ফল দেয় কি? কোনটি decidable?
(a) decidable  : regex -> NFA -> DFA -> minimise, compare (lesson 20) ;
                 can be exponential in the regex size, but always terminates
(b) undecidable: EQ for CFGs (lessons 37, 54) ; testing on strings only finds differences
(c) undecidable: semantic property of programs (Rice, lesson 53) ;
                 tests, property-based testing and bounded checks give evidence only

প্রশ্নকর্তা প্রায়ই (ক)-তে “না” আশা করেন না; উত্তরটি বলে দেয় আপনি জানেন regular language-এর জগৎ কতটা ভালো আচরণ করে। ২.২-এর brute force তাই একটি সহজ উপায়, কিন্তু চাইলে সম্পূর্ণ প্রমাণও সম্ভব: minimal DFA দুটি একই কি না, renaming বাদে।

৮.৫(কঠিন) “যথেষ্ট বড় timeout দিলেই তো halting ধরা যায়। ধরুন T = 1000 ধাপ, বা যন্ত্রের আকার অনুযায়ী T(n).” এই যুক্তির ফাঁক দেখান।

T ধাপের বিচারক আসলে অন্য প্রশ্নের decider: “M কি T ধাপের মধ্যে থামে?” এটি decidable, কিন্তু halting নয়। প্রতিটি নির্দিষ্ট T-এর একটি প্রতিপক্ষ আছে: T + 1 ধাপে থামা যন্ত্র। পর্ব ৫৫-এর run-এ ৪-state Busy Beaver চ্যাম্পিয়ন ১০৭ ধাপে থামে, অথচ T = 100-এর বিচারক তাকে “LOOPS” বলে। যন্ত্রের আকার অনুযায়ী T(n) নিলেও বাঁচা যায় না: T computable হলে কোনো n-এ T(n) < S(n) হতেই হবে (S হলো Busy Beaver-এর ধাপ-function, যা কোনো computable function-এর চেয়ে দ্রুত বাড়ে), নইলে বিচারকটি halting-এর decider হতো। ইন্টারভিউর এক বাক্যে: “Timeout একটি বাজেট, রায় নয়।”

৯ · Contest-এ automaton — KMP, Aho–Corasick আর DFA-র ওপর DP

Contest-এ “দৈর্ঘ্য n-এর কয়টি string-এ কোনো নিষিদ্ধ শব্দ নেই” বা “N পর্যন্ত কয়টি সংখ্যা কোনো অঙ্ক-নিয়ম মানে” ধরনের প্রশ্নের একটিই রেসিপি: নিয়মটিকে একটি DFA বানান, তারপর DP-র অবস্থা = (কত অক্ষর বসানো হলো, DFA-র state). DFA-তে যত state, DP-র প্রতিটি স্তরে তত ঘর। বাজারঘরের রিভিউ-ফিল্টারের নিষিদ্ধ শব্দ খোঁজা আর এই গোনা একই যন্ত্রের দুই ব্যবহার।

৯.১(মাঝারি) Σ = {a, b, c}. দৈর্ঘ্য n-এর কয়টি string-এ “aba” বা “cc” substring হিসেবে নেই? n = 1 থেকে 5-এর মান আর বড় n-এর (mod 109 + 7) পদ্ধতি দিন।
automaton state = longest suffix of the text that is a prefix of some pattern
states: ε, a, c, ab  (alive) ; aba, cc (dead = a pattern was seen)
        a    b    c
  ε     a    ε    c
  a     a    ab   c
  c     a    ε    dead(cc)
  ab    dead ε    c
counts n = 1..5 : 3, 8, 21, 54, 140      (brute force agrees up to n = 8)
large n : 4×4 transition-count matrix M ; answer = sum of row ε of M^n
          -> O(4³ · log n) with fast exponentiation

এটি একটি Aho–Corasick automaton-এর সম্পূর্ণ রূপ (প্রতিটি state থেকে প্রতিটি অক্ষরের তীর বানানো, failure link আগেই হিসাব করা); একটি মাত্র pattern হলে এটিই পর্ব ২৩-এর string matching automaton. একটি সূক্ষ্ম জায়গা: “ab” থেকে a পড়লে “aba”, যার নিজের মধ্যে pattern শেষ হয়েছে। Pattern অন্য pattern-এর ভেতরে শেষ হলে (যেমন “bcc”-এর ভেতরে “cc”) সেটি ধরতে Aho–Corasick-এর output link লাগে; নিচের কোড প্রতিটি state-এর শেষে কোনো pattern আছে কি না সরাসরি দেখে একই কাজ করে।

ধাপ ১n = 0
ε:1  a:0  c:0  ab:0
total 1 (empty string)
ধাপ ২n = 1
ε:1  a:1  c:1  ab:0
total 3
ধাপ ৩n = 2
ε:2  a:3  c:2  ab:1
total 8  (cc dropped)
ধাপ ৪n = 3
ε:5  a:7  c:6  ab:3
total 21
ধাপ ৫n = 4
ε:14 a:18 c:15 ab:7
total 54
  1. শুরু। ফাঁকা string একটি, state ε-তে। প্রতিটি পরের সারি আগের সারির প্রতিটি ঘর থেকে তিনটি অক্ষরের তীর ধরে যোগ করে বানানো।
  2. n = 1. ε থেকে a → a, b → ε, c → c: তিনটি ঘরে ১ করে, মোট ৩.
  3. n = 2. ε-তে আসে ε·b, a·b নয় (সেটি ab), c·b: মোট ২; a-তে আসে তিন state থেকে a: ৩; c-তে ε·c আর a·c: ২ (c·c মানে “cc”, বাদ); ab-তে a·b: ১. মোট ৮ = 9 − 1.
  4. n = 3. একই নিয়মে ε:5, a:7, c:6, ab:3, মোট ২১. বাদ পড়েছে “aba” আর “cc” থাকা ছয়টি string: 27 − 21 = 6.
  5. n = 4. ε:14, a:18, c:15, ab:7, মোট ৫৪; চেকারের brute force-ও ৫৪. প্রতিটি স্তরে কাজ ৪ × ৩, তাই n স্তরে O(n), আর matrix-এর ঘাত দিয়ে O(log n).
from itertools import product
def build(pats, sigma):               # Aho–Corasick-style DFA: state = longest suffix that
    pref = {p[:i] for p in pats for i in range(len(p) + 1)}   # is a prefix of some pattern
    bad = {q for q in pref if any(q.endswith(p) for p in pats)}
    def go(q, c):
        s = q + c
        while s not in pref: s = s[1:]
        return s
    return bad, {(q, c): go(q, c) for q in pref for c in sigma}
def count(pats, sigma, n, mod=None):  # DP over DFA states: strings avoiding every pattern
    bad, d = build(pats, sigma)
    cur = {"": 1}
    for _ in range(n):
        nxt = {}
        for q, v in cur.items():
            for c in sigma:
                r = d[(q, c)]
                if r not in bad: nxt[r] = nxt.get(r, 0) + v
        cur = {q: v % mod for q, v in nxt.items()} if mod else nxt
    return sum(cur.values()) % mod if mod else sum(cur.values())
P, S = ["aba", "cc"], "abc"
bad, d = build(P, S)
print("states:", sorted({q for q, _ in d}, key=lambda q: (len(q), q)), "| dead:", sorted(bad))
for n in range(1, 9):
    brute = sum(not any(p in "".join(w) for p in P) for w in product(S, repeat=n))
    print(f"n = {n}: DP {count(P, S, n):5}  brute force {brute:5}")
print("n = 1000 (mod 1e9+7):", count(P, S, 1000, 10**9 + 7))

প্রথম লাইনে automaton-এর ছয়টি state, যার দুটি dead (aba, cc). তারপর n = 1 থেকে 8 পর্যন্ত DP আর সব 3n string-এর brute force: 3, 8, 21, 54, 140, 363, 941, 2439, প্রতিটিতে হুবহু মিল। শেষ লাইনে n = 1000-এ উত্তর mod 109 + 7 = 712012506, এক মুহূর্তে; brute force-এ 31000টি string লাগত। build-এর সরল রূপটি state প্রতি কয়েকটি string-তুলনা করে; বড় pattern-সেটে আসল Aho–Corasick-এর failure link একই টেবিল রৈখিক সময়ে বানায়।

৯.২(মাঝারি) 0 থেকে N-এর মধ্যে কয়টি সংখ্যা ৩ দিয়ে বিভাজ্য আর দশমিক লেখায় “13” নেই? N = 1018 পর্যন্ত। কোন দুটি DFA-র product এখানে লুকিয়ে আছে?

দুটি DFA: অঙ্কের যোগফল mod 3 (তিন state, কারণ 10 ≡ 1 mod 3, তাই সংখ্যা mod 3 = অঙ্কের যোগফল mod 3) আর “শেষ অঙ্ক 1 কি না”-র দুই state, যেখানে 1-এর পর 3 মানে dead. তাদের product construction-এ ছয়টি state (পর্ব ০৮)। Digit DP এর সঙ্গে একটি বাড়তি bit যোগ করে: “এ পর্যন্ত বসানো অঙ্কগুলো N-এর prefix-এর সমান কি না” (tight), কারণ tight হলে পরের অঙ্ক N-এর অঙ্ক ছাড়াতে পারে না। অবস্থা (অবস্থান, mod 3, শেষটি 1, tight): ১৯ অবস্থান × ৩ × ২ × ২, প্রতিটি থেকে বড়জোর ১০টি অঙ্ক। শুরুর শূন্যগুলো “13” তৈরি করে না, তাই আলাদা সামলাতে হয়নি; অন্য নিয়মে (যেমন “শূন্য নেই”) সেটি লাগবে।

from functools import lru_cache
def count_upto(N):        # x in [0, N]: divisible by 3 and decimal form has no "13"
    D = str(N)
    @lru_cache(maxsize=None)
    def go(i, r, last1, tight):        # DFA state = (sum mod 3, last digit was 1)
        if i == len(D): return 1 if r == 0 else 0
        total = 0
        for c in range((int(D[i]) if tight else 9) + 1):
            if last1 and c == 3: continue              # would create "13": dead state
            total += go(i + 1, (r + c) % 3, c == 1, tight and c == int(D[i]))
        return total
    return go(0, 0, False, True)
brute = lambda N: sum(1 for x in range(N + 1) if x % 3 == 0 and "13" not in str(x))
for N in (13, 140, 1000, 31337):
    print(f"N = {N:6}: digit DP {count_upto(N):6}  brute force {brute(N):6}")
print("N = 10^18:", count_upto(10**18))

চারটি ছোট N-এ digit DP আর সব সংখ্যা গোনা brute force একই: N = 13-এ 5 (0, 3, 6, 9, 12), 140-এ 44, 1000-এ 328, 31337-এ 9798. তারপর N = 1018-এ 280518294073568635, মুহূর্তে। এত বড় N-এ brute force সম্ভব নয়, তাই ছোট N-এ মিলিয়ে নেওয়াই আস্থার ভিত্তি; contest-এ জমা দেওয়ার আগে ঠিক এই অভ্যাসটি অনেক ভুল ধরে।

৯.৩(সহজ) “ABABAC” pattern-এর KMP failure function (π) বের করুন, আর বলুন কেন KMP-এর মোট সময় O(n + m), যদিও ভেতরে একটি while loop আছে।
q      1  2  3  4  5  6
P_q    A  AB ABA ABAB ABABA ABABAC
π[q]   0  0  1  2  3  0          (lesson 23, 7 comparisons in total)

π[q] হলো প্রথম q অক্ষরের সবচেয়ে লম্বা proper border-এর দৈর্ঘ্য (যা prefix-ও, suffix-ও)। q = 6-এ C যোগ হলে border-এর শিকল ধরে পেছায় (3 → 1 → 0), কোনোটি মেলে না। সময়ের যুক্তি amortized: মিলে যাওয়া অংশের দৈর্ঘ্য k প্রতি অক্ষরে বড়জোর ১ বাড়ে, আর while-এর প্রতিটি ঘুরে অন্তত ১ কমে; k কখনো ঋণাত্মক নয়, তাই মোট কমা মোট বাড়ার চেয়ে বেশি হতে পারে না: text-এ n, pattern বানাতে m. KMP আসলে পর্ব ২৩-এর DFA-র সংকুচিত রূপ; Σ ছোট হলে পুরো DFA-টেবিল বানানোও চলে।

১০ · ব্যাখ্যা করার প্রশ্ন, শেষ সপ্তাহের প্রস্তুতি আর কোর্সের সমাপ্তি

অনেক ইন্টারভিউতে একটি অংশ থাকে, যেখানে কোড নয়, ব্যাখ্যা চাওয়া হয়: তত্ত্ব না জানা সহকর্মী বা পণ্যের দায়িত্বে থাকা মানুষকে আপনি একটি সিদ্ধান্ত কীভাবে বোঝাবেন। ভালো উত্তর ছোট, একটি উপমা দেয়, সংখ্যা দেয়, আর শেষে একটি কাজের প্রস্তাব।

১০.১(মাঝারি) “গতকাল কুপন-যাচাইয়ের একটি regex সার্ভার আটকে দিয়েছিল। পণ্যের দায়িত্বে থাকা সহকর্মীকে তিন-চার বাক্যে বুঝিয়ে বলুন কী হয়েছিল আর কী করবেন।”

আদর্শ উত্তর: “আমাদের কুপনের নিয়মটি এমনভাবে লেখা ছিল যে একটি লম্বা, প্রায়-ঠিক কুপনকে প্রোগ্রাম অসংখ্য উপায়ে টুকরো করে দেখছিল, ঠিক যেমন একটি তালার সব সংখ্যা একে একে ঘোরানো। প্রতি দুটি বাড়তি অক্ষরে কাজ চার গুণ হয়, তাই ৩০ অক্ষরের একটি কুপনেই কয়েক সেকেন্ড লাগে। আমরা নিয়মটি এমনভাবে আবার লিখেছি যে প্রতিটি কুপন একভাবেই টুকরো হয়, আর পুরোনো নিয়মের সঙ্গে প্রায় দশ হাজার নমুনায় মিলিয়ে দেখেছি যে কোনো বৈধ কুপন বাদ পড়ছে না। সঙ্গে কুপনের দৈর্ঘ্য ৩২-এ সীমিত করছি আর একটি স্থায়ী পরীক্ষা যোগ করছি, যাতে ভুলটি ফিরে না আসে।” লক্ষ করুন: কোনো পরিভাষা নেই, কারণ আছে, প্রমাণ আছে, আর পরের কাজ আছে।

১০.২(মাঝারি) একজন সহকর্মী বিরক্ত: “আমাদের static analyzer এত ভুল সতর্কতা দেয় কেন? ভালো tool হলে তো শুধু আসল bug দেখাত।” উত্তর দিন, Rice-এর নাম না নিয়েও।

“কোনো tool-ই সব program পড়ে নিখুঁতভাবে বলতে পারে না, চালালে কী ঘটবে; এটি গণিতে প্রমাণিত সীমা, কোনো tool-এর দুর্বলতা নয়। তাই প্রতিটি tool একটি দিক বেছে নেয়: হয় কিছু bug মিস করবে, নয় কিছু ভুল সতর্কতা দেবে। আমাদের tool দ্বিতীয়টি বেছেছে, যাতে কোনো সত্যিকারের null-ভুল ফসকে না যায়। ভুল সতর্কতা কমাতে কোডে type-এর তথ্য আরও স্পষ্ট লিখতে পারি, আর সত্যিই নিরাপদ জায়গাগুলো কারণ লিখে চিহ্নিত করতে পারি।” প্রশ্নকর্তা চাইলে তখন sound বনাম complete আর পর্ব ৫৫-এর প্রমাণের কথা তুলুন।

১০.৩(সহজ) “এমন একটি ঘটনা বলুন যখন তত্ত্বের জ্ঞান আপনার কাজে লেগেছে।” আপনার অভিজ্ঞতা কম হলে কী বলবেন?

সত্যি ঘটনা বলুন, বানানো নয়; ছোট হলেও চলে। কাঠামো: পরিস্থিতি (কী সমস্যা), আপনার কাজ (কোন মডেল চিনলেন), ফল (সংখ্যায়), আর শিক্ষা। অভিজ্ঞতা কম হলে নিজের অনুশীলনের প্রকল্প যথেষ্ট: “একটি ছোট calculator বানানোর সময় বুঝলাম grammar-এ left recursion থাকলে recursive descent আটকে যায়; loop-এ বদলে দিয়ে এলোমেলো তিন হাজার expression-এ ফল মিলিয়েছি।” এই পাতার যেকোনো চেকার এমন একটি গল্পের বীজ, যদি আপনি নিজে সেটি বদলে, ভেঙে আর আবার ঠিক করে দেখেন।

ইন্টারভিউ বা contest-এর আগের সাত দিন

দিনকাজকোথায়
১ভাগ ১–২: মডেল চেনা, একটি দুর্বল regex নিজে লিখে ভাঙা আর ঠিক করাপর্ব ১৩, ১৭, ২১
২ভাগ ৩: একটি নিজের flow-এর state machine আর BFS-চেকারপর্ব ২০, ২৪
৩ভাগ ৪: কাগজে না দেখে tokenizer আর parser, ঘড়ি ধরে ৩০ মিনিটপর্ব ২২, ৩৮, ৪২
৪ভাগ ৫–৬: দশটি সমস্যার নাম শুনে “P, NP-complete, না অজানা” বলা; দুটি reduction খাতায়পর্ব ৫৯, ৬১, ৭৩
৫ভাগ ৭–৮: encoding আর undecidability-র ফাঁদ জোরে ব্যাখ্যাপর্ব ০৫, ৫১, ৫৫
৬ভাগ ৯: দুটি automaton-DP নিজে লিখে brute force-এ মেলানোপর্ব ০৮, ২৩
৭ভাগ ১০-এর ব্যাখ্যা জোরে বলা; নতুন বিষয় নয়, বিশ্রামএই পাতা
অভিনন্দন

আপনি গণনার তত্ত্ব কোর্সের ৮৫টি পর্ব পেরিয়ে এসেছেন: string আর language থেকে finite automaton আর regex, context-free grammar, pushdown automaton আর parsing, Turing machine, computability আর undecidability, P আর NP থেকে PSPACE, randomized, circuit, interactive আর quantum complexity, আর model checking ও program analysis-এর প্রয়োগ। সবচেয়ে বড় অর্জন একটি প্রশ্ন করার অভ্যাস: “এই কাজে কতটুকু স্মৃতি লাগে, কত সময়, আর আদৌ কি সম্ভব?” সেই প্রশ্নের উত্তরেই regex নিরাপদ হয়, parser সরল হয়, আর অসম্ভব প্রতিশ্রুতি এড়ানো যায়।

এরপর কী করবেন

এই পাতা কোনো চাকরি বা contest-এর ফলের নিশ্চয়তা দেয় না। আপনার হাতে যা আছে, তা হলো মডেল চেনা, শর্তসহ দাবি করা আর ছোট ক্ষেত্রে যাচাই করার অভ্যাস, আর না-জানা জায়গায় সৎভাবে “এটি খোলা প্রশ্ন” বা “এখানে আমি নিশ্চিত নই” বলতে পারা।

আরও গভীরে: ৯.১-এর মতো গোনার উত্তর সবসময় একটি linear recurrence মানে, কারণ সেটি একটি সসীম matrix-এর ঘাত; তাই যেকোনো regular language-এর “দৈর্ঘ্য n-এর শব্দ-সংখ্যা”-র generating function একটি rational function. Unambiguous grammar-এর context-free language-এ generating function algebraic হয় (Chomsky আর Schützenberger, ১৯৬৩ বলে পরিচিত), আর এই ফল উল্টো দিকে খাটিয়ে কিছু language inherently ambiguous প্রমাণ করা হয়েছে বলে জানা। Regex engine-এর দিকে, কোন NFA-তে পথের সংখ্যা exponential হারে বাড়ে তার একটি নির্দিষ্ট গঠনগত শর্ত আছে (Weber আর Seidl, ১৯৯১ বলে পরিচিত), যা ReDoS-এর static checker-গুলোর তাত্ত্বিক ভিত্তি।

পরীক্ষা ও ইন্টারভিউতে: “Regex দিয়ে HTML বা বন্ধনী পার্স করা যায়?” — formal অর্থে না, ভাষাটি non-regular; parser বা stack লাগে। “NP-hard আর NP-complete-এর পার্থক্য?” — NP-complete মানে NP-hard আর নিজেও NP-তে; halting problem NP-hard কিন্তু NP-তে নেই। “Timeout দিয়ে halting ধরা যায়?” — না, timeout শুধু “বাজেটে শেষ হলো কি না” বলে। “O(n · W) knapsack কি polynomial?” — না, pseudo-polynomial; W-এর bit-দৈর্ঘ্যে exponential. “Recursive descent-এ left recursion কেন সমস্যা?” — token না খেয়েই নিজেকে ডাকে; loop বা A′-রূপে বদলান।

AI-এর যুগে — নকল ইন্টারভিউ আর AI-এর উত্তর যাচাই

AI সহকারী ইন্টারভিউ-প্রস্তুতির ভালো সঙ্গী, যদি আপনি তাকে প্রশ্নকর্তা বানান আর তার উত্তরকে সন্দেহের চোখে দেখেন। এই বিষয়ে তার চেনা ভুলগুলো: “regex দিয়ে বন্ধনী মেলান” ধরনের অনুরোধে আত্মবিশ্বাসী ভুল pattern; ReDoS-এর “সংশোধন”, যা language বদলে দেয় বা দুর্বলতা রেখে দেয়; reduction উল্টো দিকে (“SAT-এ রূপান্তর করেছি, তাই NP-hard”); pseudo-polynomial DP-কে polynomial বলা; “যথেষ্ট বড় timeout-এ halting ধরা যায়” ধরনের দাবি; P বনাম NP-কে মীমাংসিত বলা; আর না-থাকা উপপাদ্য বা বইয়ের পাতার উল্লেখ। এর বেশিরভাগ এই পাতার মতো ছোট brute-force চেকারে মুহূর্তে ধরা পড়ে।

নকল ইন্টারভিউর একটি কাঠামো; কোনো আসল প্রতিষ্ঠানের প্রশ্ন বা ব্যক্তিগত তথ্য দেবেন না:

তুমি একজন কড়া কিন্তু ভদ্র software engineering ইন্টারভিউয়ার, যার ঝোঁক গণনার তত্ত্বের দিকে (regex, state machine, parsing, complexity). আমার স্তর: [শুরু/মাঝারি/উন্নত]। ১. আমাকে একটি প্রশ্ন দাও, input-এর আকার আর শর্তসহ। শুধু প্রশ্ন, উত্তর নয়। ২. আমি জোরে ভাবব। আমি না চাইলে সংকেত দিও না; চাইলে একবারে একটি ছোট সংকেত। ৩. আমি কোনো জটিলতা বললে জিজ্ঞেস করো: "কোন input-দৈর্ঘ্যে মাপছ?" আর reduction বললে: "কোন দিকে?" ৪. আমার কোড বা pattern ভুল হলে সবচেয়ে ছোট counterexample দাও, যা আমি Python-এ মেলাতে পারি। ৫. শেষে চারটি দিকে ১ থেকে ৪ নম্বর দাও: প্রশ্ন বোঝা, মডেল চেনা, সমাধান ও জটিলতা, যাচাই ও ব্যাখ্যা। ৬. খোলা প্রশ্ন (যেমন P বনাম NP, Collatz) মীমাংসিত বলবে না; কোনো তথ্যে নিশ্চিত না হলে "নিশ্চিত নই" লেখো, কোনো বই বা প্রবন্ধ বানাবে না।

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

নিজেকে যাচাই করুন

প্রতিটি প্রশ্নে আগে খাতায় ভাবুন, তারপর উত্তর বাছুন। সব তথ্য প্রশ্নের ভেতরেই আছে।

ক্রমএকটি নতুন সমস্যা X NP-complete দেখানোর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. X-এর decision রূপ লেখা (একটি সীমা k-সহ)
  2. X ∈ NP: certificate আর polynomial সময়ের যাচাই
  3. একটি জানা NP-complete সমস্যা A বাছা
  4. Polynomial সময়ের f বানানো, যা A-এর instance-কে X-এর instance-এ নেয়
  5. দুই দিক প্রমাণ: w ∈ A ⇔ f(w) ∈ X

(সহজ) একটি backtracking regex engine ^(a+)+$-কে 10টি a আর শেষে একটি b-এর input-এ চালায়। শেষে মোট কয়বার $ পরীক্ষা হয়?

  • 10
  • 55
  • 1023
  • 1024

(মাঝারি) একজন প্রার্থী তাঁর নতুন সমস্যা X-কে polynomial সময়ে SAT-এ রূপান্তর করেছেন (X ≤p SAT). এ থেকে নিশ্চিতভাবে কী বলা যায়?

  • X NP-hard
  • X ∈ NP
  • X ∈ P
  • X undecidable

(মাঝারি) Σ = {a, b, c}. দৈর্ঘ্য ৩-এর কয়টি string-এ “aba” বা “cc” substring হিসেবে নেই?

  • 21
  • 22
  • 24
  • 19

(মাঝারি) SUBSET-SUM-এর DP-র সময় O(n · t). সংখ্যাগুলো binary-তে লেখা আর t প্রায় 240. কোন বর্ণনাটি ঠিক?

  • Polynomial, কারণ n আর t-এর গুণফল
  • ভুল উত্তর দেয়, কারণ সমস্যাটি NP-complete
  • Polynomial, কারণ সংখ্যাগুলো unary-তে
  • Pseudo-polynomial: t-এর মানে polynomial, bit-দৈর্ঘ্যে exponential

(কঠিন) OTP-র নিয়ম: SENT-এ ভুল কোডে w বাড়ে, w = 2 অবস্থায় আরেকটি ভুলে LOCKED; মেয়াদ ফুরালে EXPIRED; EXPIRED থেকে resend (বড়জোর দুবার) আবার SENT-এ নেয় আর w = 0 করে দেয়। একজন আক্রমণকারী LOCKED হওয়ার আগে পর্যন্ত মোট সর্বোচ্চ কয়টি ভুল অনুমান করতে পারেন?

  • 3
  • 6
  • 7
  • 9

(মাঝারি) Pratt parser-এ প্রতিটি infix operator-এর (বাঁ, ডান) binding power. যোগ (10, 11), গুণ (20, 21). ঘাত ^ সবচেয়ে শক্ত আর ডান-সংযোগী (2^3^2 = 512). ^-এর জন্য কোন জোড়া ঠিক?

  • (30, 31)
  • (31, 30)
  • (15, 14)
  • (5, 5)

(সহজ) একটি program-এ একটিমাত্র চলক x, মান সবসময় 0 থেকে 999-এর মধ্যে, আর প্রতিটি ধাপে নতুন x শুধু পুরোনো x-এর ওপর নির্ভর করে। “এটি থামে কি না” প্রশ্নটি সম্পর্কে কোনটি ঠিক?

  • Decidable: বড়জোর ১০০০ ধাপ চালালেই উত্তর মেলে
  • Undecidable, কারণ এটি halting problem
  • শুধু timeout দিয়েই বলা যায়, প্রমাণ সম্ভব নয়
  • Rice-এর theorem অনুযায়ী undecidable

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব শব্দ এখানে একসাথে:

মনে রাখুন

  1. মডেল আগে, কোড পরে: সসীম স্মৃতি, stack, না সীমাহীন অনুসন্ধান; P, NP-hard, না undecidable. প্রশ্নের চেহারা দেখে এই দুটি সিঁড়িতে জায়গা ঠিক করুন।
  2. Regex: একই অংশ একাধিক উপায়ে মেলা মানে বিপদ; দ্ব্যর্থহীন pattern, রৈখিক engine, দৈর্ঘ্যের সীমা, আর brute-force সমতা যাচাই।
  3. State machine আর parser: table-এ নিয়ম, BFS-এ প্রমাণ; grammar থেকে function, left recursion থেকে loop, আর অবিশ্বস্ত input-এ গভীরতার সীমা।
  4. দিক আর মাপ: কঠিনতা প্রমাণে A ≤p X, সমাধানে X ≤p SAT; জটিলতা মাপুন bit-দৈর্ঘ্যে, তাই O(n · t) pseudo-polynomial.
  5. Timeout বাজেট, রায় নয়: সসীম স্মৃতিতে halting decidable, সীমাহীনে নয়; আর প্রতিটি গোনার উত্তর ছোট ক্ষেত্রে brute force দিয়ে মেলান।

পথের শেষ: এটিই গণনার তত্ত্ব কোর্সের শেষ পর্ব; এর পরে আর কোনো পর্ব নেই। ৮৫টি পর্ব পেরিয়ে আসার জন্য অভিনন্দন। যেকোনো মডিউল আবার ঝালিয়ে নিতে কোর্স হোম বা পর্ব ০১-এর মানচিত্রে ফিরে যান, আর পাশের সম্পূর্ণ কোর্স হিসেবে DSA, ডিসক্রিট ম্যাথমেটিক্স বা Cybersecurity শুরু করতে পারেন। ইন্টারভিউ আর contest-এর জন্য শুভকামনা।

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান