দ্রুত রিভিশনের জন্য সূত্র, সাধারণ ভুল আর ফ্ল্যাশ কার্ড, এক জায়গায়।
৯৮টি সূত্র ও নিয়ম
সি ও প্রোগ্রামিং
C বনাম C++ এ ক্যারেক্টার কনস্ট্যান্টের সাইজ ট্র্যাপ
Character Literal Size Trap: sizeof(char) vs sizeof('a') in C vs C++
সূত্র
In C: sizeof('a') == sizeof(int) (usually 4 bytes). In C++: sizeof('a') == sizeof(char) == 1 byte. Always: sizeof(char) == 1.
নিয়ম ও সহজ উপায়
C ভাষায় ক্যারেক্টার লিটারাল বা কনস্ট্যান্ট যেমন 'a' এর টাইপ মূলত int (ইন্টিজার প্রমোশন নীতি), তাই sizeof('a') দিলে ইন্টিজারের সাইজ (সাধারণত ৩২-বিট আর্কিটেকচারে ৪ বাইট) রিটার্ন করে। পক্ষান্তরে C++ এ 'a' এর টাইপ সরাসরি char, তাই sizeof('a') হবে ১ বাইট। তবে উভয় ভাষাতেই char ভেরিয়েবলের সাইজ char c = 'a'; sizeof(c) সর্বদা ১ বাইট।
সি ও প্রোগ্রামিং
অ্যারে সাবস্ক্রিপ্ট সমতা কৌশল: a[i] ও i[a] এর বিনিময়যোগ্যতা
C/C++ এ অ্যারের সাবস্ক্রিপ্ট ব্র্যাকেট [] মূলত পয়েন্টার অ্যারিথমেটিকের সিনট্যাকটিক সুগার। কম্পাইলার a[i] কে অভ্যন্তরীণভাবে *(a + i) তে রূপান্তর করে। যোগের বিনিময় নিয়ম (Commutative Law) অনুযায়ী *(a + i) এবং *(i + a) হুবহু একই মেমরি নির্দেশ করে। ফলে C কোডে i[a] লেখা সম্পূর্ণ বৈধ এবং তা a[i] এর মান প্রদান করে।
Pre-increment (++a) vs Post-increment (a++) in Expressions
সূত্র
++a: Increment value first, then use in expression. a++: Use current value in expression first, then increment.
নিয়ম ও সহজ উপায়
প্রি-ইনক্রিমেন্ট (++a): ভেরিয়েবলের মান তৎক্ষণাৎ ১ বৃদ্ধি পায় এবং এক্সপ্রেশনে বর্ধিত নতুন মানটি কার্যকর হয়। পোস্ট-ইনক্রিমেন্ট (a++): এক্সপ্রেশনে আগে ভেরিয়েবলের বর্তমান মান ব্যবহৃত হয়, এরপর স্টেটমেন্ট অতিক্রম করার সময় মান ১ বৃদ্ধি পায়। ("Pre = আগে বাড়াও, Post = পরে বাড়াও")
ডাবল কোটেশনে থাকা স্ট্রিং লিটারালের শেষে কম্পাইলার স্বয়ংক্রিয়ভাবে একটি নাল ক্যারেক্টার '\0' যুক্ত করে। sizeof("text") কম্পাইল-টাইম অপারেটর যা মেমরিতে দখলকৃত মোট বাইট (নাল টার্মিনেটরসহ) গণনা করে। অন্যদিকে strlen("text") রান-টাইম লাইব্রেরি ফাংশন যা প্রথম '\0' পাওয়ার পূর্ব পর্যন্ত কেবলমাত্র দৃশ্যমান ক্যারেক্টারের সংখ্যা গুনে দেয়।
ptr = &var (address of var); *ptr = var (value of var). ptr2 = &ptr; *ptr2 = ptr (&var); **ptr2 = var (value of var).
নিয়ম ও সহজ উপায়
পয়েন্টার চেইনে প্রতিটি * (অ্যাস্টেরিস্ক) ডিরিফারেন্স অপারেশনে মেমরির একটি করে স্তর ভেদ করে মূল ভ্যালুর দিকে অগ্রসর হয়: ptr2 নিজে ধারণ করে পয়েন্টারের মেমরি অ্যাড্রেস, *ptr2 প্রকাশ করে মূল ভেরিয়েবলের অ্যাড্রেস, এবং **ptr2 সরাসরি মূল ভেরিয়েবলের মূল ভ্যালুকে প্রকাশ করে। কোনো ফাংশনে পয়েন্টারের মেমরি রেফারেন্স বদলাতে (যেমন dynamic memory allocation) ডাবল পয়েন্টার পাস করতে হয়।
সি ও প্রোগ্রামিং
বিটওয়াইজ শিফট: দ্রুত গুণন ও ভাগের শর্টকাট
Bitwise Shifts: Fast Multiplication and Division Rules
সূত্র
x << k == x * (2^k) and x >> k == floor(x / (2^k))
নিয়ম ও সহজ উপায়
ধনাত্মক পূর্ণসংখ্যার ক্ষেত্রে বামে k বিট শিফট (x << k) করা মানে সংখ্যাটিকে 2^k দ্বারা গুণ করা। ডানে k বিট শিফট (x >> k) করা মানে সংখ্যাটিকে 2^k দ্বারা পূর্ণসংখ্যায় ভাগ (Integer / Floor Division) করা। প্রসেসরের ALU-তে সাধারণ গুণ বা ভাগের চেয়ে বিটওয়াইজ শিফট অনেক দ্রুত কার্যকর হয়।
Bitwise Power of 2 Check: (n > 0) && ((n & (n - 1)) == 0)
সূত্র
isPowerOfTwo(n) = (n > 0) && ((n & (n - 1)) == 0)
নিয়ম ও সহজ উপায়
যেকোনো 2^k সংখ্যার বাইনারি উপস্থাপনায় ঠিক একটিমাত্র ১-বিট থাকে (যেমন 8 = 1000₂)। তার ঠিক পূর্ববর্তী সংখ্যা n - 1 এ ওই বিটটি ০ হয়ে তার ডানের সকল বিট ১ হয়ে যায় (যেমন 7 = 0111₂)। এদের মধ্যে বিটওয়াইজ AND করলে ফলাফল শূন্য (0) হয়। যদি (n & (n - 1)) == 0 হয় এবং n > 0 হয়, তবে সংখ্যাটি নিশ্চিতভাবে ২-এর ঘাত (Power of 2)।
ডেটা স্ট্রাকচার
বাইনারি ট্রি: লিফ নোড ও ডিগ্রি-২ নোডের সম্পর্ক (n0 = n2 + 1)
n0 = n2 + 1 (For ANY non-empty binary tree: Leaves = Nodes with 2 children + 1)
নিয়ম ও সহজ উপায়
যেকোনো নন-এম্পটি বাইনারি ট্রিতে (ট্রিটি ফুল, কমপ্লিট, স্ট্রিক্ট হোক বা সাধারণ যেকোনো বাইনারি ট্রি হোক) লিফ নোডের সংখ্যা (n₀) সর্বদা দুটি সন্তানযুক্ত ডিগ্রি-২ নোডের সংখ্যার (n₂) চেয়ে ঠিক ১ বেশি হবে: n₀ = n₂ + 1। ডিগ্রি-১ যুক্ত নোডের সংখ্যা যাই হোক না কেন, এই সম্পর্ক সর্বদা ধ্রুব থাকে।
ডেটা স্ট্রাকচার
h উচ্চতার বাইনারি ট্রিতে সর্বোচ্চ নোড সংখ্যা: 2^(h+1) - 1
Maximum Nodes in a Binary Tree of Height h: 2^(h+1) - 1
সূত্র
Max Nodes N = 2^(h+1) - 1 (Root at height 0) or 2^h - 1 (If root is at level 1)
নিয়ম ও সহজ উপায়
যদি রুট নোডের উচ্চতা বা লেভেল ০ ধরা হয়, তবে h উচ্চতার বাইনারি ট্রিতে সর্বোচ্চ নোড সংখ্যা N_max = 2^(h+1) - 1 (এটি একটি নিখুঁত ফুল বাইনারি ট্রি যেখানে প্রতিটি লেভেল i-তে 2^i টি নোড থাকে, সমষ্টি ∑ 2^i = 2^(h+1) - 1)। বিপরীতভাবে, N নোড বিশিষ্ট বাইনারি ট্রির সর্বনিম্ন উচ্চতা h_min = ⌈log₂(N + 1)⌉ - 1।
ডেটা স্ট্রাকচার
বাইনারি সার্চ ট্রির ইন-অর্ডার ট্রাভার্সাল সর্বদা সর্টেড থাকে
BST Inorder Traversal is Always Strictly Ascending (Sorted)
সূত্র
Inorder(BST) = Left -> Root -> Right ==> Strictly Ascending (Sorted) Order
নিয়ম ও সহজ উপায়
বাইনারি সার্চ ট্রিতে (BST) সংজ্ঞামতেই রুটের বাম সাবট্রির সকল উপাদান রুট থেকে ছোট (Left < Root) এবং ডান সাবট্রির সকল উপাদান রুট থেকে বড় (Root < Right)। ইন-অর্ডার ট্রাভার্সালের নিয়ম হলো Left -> Root -> Right। ফলে যেকোনো বৈধ BST-এর ইন-অর্ডার ট্রাভার্সাল করলে উপাদানগুলো সর্বদা ছোট থেকে বড় (Ascending Order) ক্রমে পাওয়া যায়।
ডেটা স্ট্রাকচার
n নোডের ট্রিতে এজের সংখ্যা সর্বদা n - 1 টি
Number of Edges in a Tree: Always n - 1
সূত্র
For any connected tree with n vertices: |E| = n - 1 (or |E| = V - 1)
নিয়ম ও সহজ উপায়
যেকোনো সাধারণ ট্রি, বাইনারি ট্রি বা গ্রাফের স্প্যানিং ট্রির ক্ষেত্রে যদি মোট ভার্টেক্স বা নোড সংখ্যা n হয়, তবে এজের সংখ্যা সর্বদা ঠিক n - 1 টি হবে। কারণ রুট ব্যতীত প্রতিটি নোডের ঠিক একটি প্যারেন্ট ইন-কামিং এজ থাকে। যদি ট্রিতে n - 1 এর চেয়ে ১টি এজও বেশি থাকে তবে সাইকেল সৃষ্টি হবে, আর কম থাকলে ট্রি ডিসকানেক্টেড হয়ে যাবে।
ডেটা স্ট্রাকচার
সার্কুলার কিউ পূর্ণ (Full) হওয়ার শর্ত: (rear + 1) % N == front
Circular Queue Full Condition: (rear + 1) % N == front
সূত্র
Full: (rear + 1) % N == front. Empty: front == rear (or front == -1). Usable capacity = N - 1.
নিয়ম ও সহজ উপায়
অ্যারে ভিত্তিক সার্কুলার কিউতে সাইজ N হলে ফুল (Full) এবং ফাঁকা (Empty) অবস্থার মধ্যে পার্থক্য করতে ১টি স্লট ইচ্ছাকৃতভাবে ফাঁকা রাখা হয়। ফলে সর্বোচ্চ N - 1 টি উপাদান রাখা যায়। নতুন উপাদান ইনসার্ট করতে rear = (rear + 1) % N হয়। তাই পরবর্তী অবস্থানটি যদি front-এর সমান হয়, অর্থাৎ (rear + 1) % N == front, তবে সার্কুলার কিউটি পূর্ণ।