Combined Bank, Assistant Programmer, 2026(2)

Combined Bank
Officer IT (Job ID-10226)
Post: Assistant programmer; Exam: 22-May-2026

1. Compare BFS & DFS with examples

Both BFS and DFS are graph traversal algorithms used to visit all nodes in a graph or tree. They differ in how they explore nodes and the order in which they visit them.1. BFS (Breadth-First Search)BFS explores a graph level by level. It starts from the root node, visits all its immediate neighbors first, then moves to the next level of neighbors. It uses a queue data structure to keep track of nodes.How it works:

Start at root: Visit the starting node.
Visit neighbors: Visit all adjacent nodes at the current depth.
Move to next level: Only after all nodes at the current level are visited, move to the next level.
Queue used: FIFO (First In First Out) order is followed.

Traversal order: A → B → C → D → EBFS visits A first, then all of A’s children (B, C), then all of their children (D, E).<Best used for: Finding the shortest path in an unweighted graph, searching nodes close to the root, and peer-to-peer networks.2. DFS (Depth-First Search)DFS explores a graph by going as deep as possible along each branch before backtracking. It starts from the root, follows one path to the end, then comes back to explore other paths. It uses a stack data structure (or recursion).<How it works:

Start at root: Visit the starting node.
Go deep: Pick one neighbor and explore it fully before moving to the next neighbor.
Backtrack: When a dead end is reached, go back to the previous node and explore other paths.
Stack used: LIFO (Last In First Out) order is followed.

Traversal order: A → B → D → E → CDFS visits A, then goes deep into B, then D, then back to B, then E, then back to A, then C.Best used for: Solving puzzles with one solution path, detecting cycles, topological sorting, and maze solving.Comparison Table:

Point	BFS	DFS
Full Form	Breadth-First Search	Depth-First Search
Exploration	Level by level (wide)	Deep as possible (deep)
Data Structure	Queue (FIFO)	Stack (LIFO) or Recursion
Memory Use	More, stores all nodes at current level	Less, stores only the current path
Shortest Path	Finds shortest path in unweighted graph	Does not guarantee shortest path
Backtracking	No backtracking needed	Backtracking is used
When to Use	Target is near the starting node	Target is deep in the graph

Example Scenario:Imagine searching for a friend in a social network:

BFS: Check yourself first, then all your direct friends, then their friends, layer by layer. Good if the person is likely a close connection.
DFS: Check yourself, then your first friend, then that friend’s first friend, going as deep as possible. Good if the person is far down one specific chain.

BFS (Breadth-First Search) vs DFS (Depth-First Search)BFS এবং DFS উভয়ই graph traversal algorithms যা graph বা tree-এর সব nodes visit করতে ব্যবহৃত হয়। এগুলো nodes explore করার পদ্ধতি এবং visit করার order-এর দিক থেকে আলাদা।<1. BFS (Breadth-First Search)BFS একটি graph level by level explore করে। এটি root node থেকে শুরু করে, প্রথমে সব immediate neighbors visit করে, তারপর next level-এর neighbors-এ যায়। এটি nodes track করতে queue data structure ব্যবহার করে।<How it works:

Start at root: Starting node visit করা হয়।
Visit neighbors: Current depth-এর সব adjacent nodes visit করা হয়।
Move to next level: Current level-এর সব nodes visit করার পর next level-এ যাওয়া হয়।
Queue used: FIFO (First In First Out) order follow করা হয়।

Traversal order: A → B → C → D → EBFS প্রথমে A visit করে, তারপর A-এর সব children (B, C), তারপর তাদের children (D, E)।<Best used for: Unweighted graph-এ shortest path খুঁজতে, root-এর কাছাকাছি nodes search করতে, এবং peer-to-peer networks-এ।<2. DFS (Depth-First Search)DFS একটি graph প্রতিটি branch যতটা সম্ভব deep যেতে explore করে, backtrack করার আগে। এটি root থেকে শুরু করে, একটা path-এর end পর্যন্ত যায়, তারপর অন্য paths explore করতে ফিরে আসে। এটি stack data structure (বা recursion) ব্যবহার করে।<How it works:

Start at root: Starting node visit করা হয়।
Go deep: একটা neighbor বেছে নিয়ে পরের neighbor-এ যাওয়ার আগে এটা fully explore করা হয়।
Backtrack: Dead end পৌঁছালে previous node-এ ফিরে আসা হয় এবং অন্য paths explore করা হয়।
Stack used: LIFO (Last In First Out) order follow করা হয়।

Traversal order: A → B → D → E → CDFS A visit করে, তারপর B-এর deep যায়, তারপর D, তারপর B-এ ফিরে E, তারপর A-এ ফিরে C।<Best used for: একটা solution path থাকা puzzles solve করতে, cycles detect করতে, topological sorting-এ, এবং maze solving-এ।<Comparison Table:

Point	BFS	DFS
Full Form	Breadth-First Search	Depth-First Search
Exploration	Level by level (wide)	Deep as possible (deep)
Data Structure	Queue (FIFO)	Stack (LIFO) বা Recursion
Memory Use	বেশি, current level-এর সব nodes store করে	কম, শুধু current path store করে
Shortest Path	Unweighted graph-এ shortest path খুঁজে	Shortest path guarantee করে না
Backtracking	Backtracking প্রয়োজন হয় না	Backtracking ব্যবহার করা হয়
When to Use	Target starting node-এর কাছাকাছি থাকলে	Target graph-এর deep-এ থাকলে

2. Explain the time complexity of merge sort. Best, average, Worst.

Time Complexity of Merge Sort

Merge Sort is a sorting algorithm that uses the divide and conquer approach. It splits the array into two halves, sorts each half recursively, and then merges them back together in sorted order. Because it always divides the array in half and performs a full merge, its time complexity remains the same in all cases.

How Merge Sort Works

Divide: Split the array into two equal halves until each sub-array has only one element.
Conquer: Sort each half by calling Merge Sort recursively.
Merge: Combine the sorted halves into a single sorted array.

Time Complexity Analysis

1. Best Case: O(n log n)
Even when the array is already sorted, Merge Sort still divides the array into halves and merges them all. It does not check if the array is already sorted, so the number of operations stays the same.

Example: Array [1, 2, 3, 4, 5] still goes through full splitting and merging.

2. Average Case: O(n log n)
For a randomly ordered array, Merge Sort consistently divides and merges. The work done at each level is proportional to n, and the number of levels is log n. So the total remains n log n.

Example: Array [5, 2, 8, 1, 9] is split, sorted, and merged in the same structured way.

3. Worst Case: O(n log n)
When the array is in reverse order, Merge Sort still performs the same number of divisions and comparisons during merging. Unlike Quick Sort, its performance does not degrade for bad input.

Example: Array [9, 8, 7, 6, 5] takes the same time as any other arrangement.

Why All Cases Are O(n log n)

Fixed division: The array is always split exactly in half, regardless of input order.
Full merge: Every element is compared and placed during the merge step.
Tree depth: The recursion tree always has log n levels for n elements.
Linear work per level: Each level processes all n elements during merging.

Space Complexity: O(n) extra space is needed for the temporary arrays during merging.

Time Complexity of Merge Sort
Merge Sort হলো একটি sorting algorithm যা divide and conquer approach ব্যবহার করে। এটি array-কে দুটি half-এ ভাগ করে, প্রতিটি half-কে recursively sort করে, এবং তারপর সেগুলোকে sorted order-এ merge করে ফেরত আনে। এটি সবসময় array-কে half-এ ভাগ করে এবং full merge perform করে, তাই সব case-এ time complexity same থাকে।<

Merge Sort কীভাবে কাজ করে

Divide: Array-কে দুটি equal half-এ ভাগ করা হয় যতক্ষণ না প্রতিটি sub-array-এ একটা element থাকে।
Conquer: প্রতিটি half-কে recursively Merge Sort call করে sort করা হয়।
Merge: Sorted halves-কে একটি single sorted array-এ combine করা হয়।

Time Complexity Analysis

1. Best Case: O(n log n)
Array already sorted থাকলেও Merge Sort এটিকে half-এ ভাগ করে এবং সব merge করে। এটি check করে না array already sorted কিনা, তাই operations-এর সংখ্যা same থাকে।

Example: Array [1, 2, 3, 4, 5] এতেও full splitting এবং merging হয়।

2. Average Case: O(n log n)
Randomly ordered array-এর জন্য Merge Sort consistently divide এবং merge করে। প্রতিটি level-এ কাজ n-এর সমানুপাতিক, এবং levels-এর সংখ্যা log n। তাই total n log n থাকে।

Example: Array [5, 2, 8, 1, 9] same structured way-এ split, sort এবং merge হয়।

3. Worst Case: O(n log n)
Array reverse order-এ থাকলেও Merge Sort same সংখ্যক divisions এবং merge-এর সময় same সংখ্যক comparisons perform করে। Quick Sort-এর মতো bad input-এ performance degrade হয় না।

Example: Array [9, 8, 7, 6, 5] অন্য যেকোনো arrangement-এর সমান সময় নেয়।

সব Case O(n log n) কেন

Fixed division: Array সবসময় exactly half-এ ভাগ হয়, input order যাই হোক না কেন।
Full merge: Merge step-এ প্রতিটি element compare এবং place করা হয়।
Tree depth: n elements-এর জন্য recursion tree-এ সবসময় log n levels থাকে।
Linear work per level: প্রতিটি level-এ merging-এর সময় সব n elements process করা হয়।

Space Complexity: Merging-এর সময় temporary arrays-এর জন্য O(n) extra space প্রয়োজন।

3. Suppose your dataset has missing values and noise. How would you preprocess it?

Data Preprocessing for Missing Values and Noise

Data preprocessing is the step of cleaning and transforming raw data before feeding it into a model. Missing values and noise are two common problems that can reduce accuracy and mislead results. Below are the methods to handle them.

1. Handling Missing Values

Missing values occur when some data points are not recorded or are lost. They must be handled carefully to avoid biased results.

Deletion: Remove rows or columns that have too many missing values. This is simple but only works when the missing data is small and random.
Mean/Median/Mode Imputation: Fill missing numeric values with the average (mean), middle value (median), or most common value (mode) of that column.
Forward/Backward Fill: Use the previous or next available value to fill the gap, useful in time-series data.
Predictive Imputation: Use machine learning models like KNN or regression to predict and fill the missing values based on other columns.
Constant Value Fill: Replace missing values with a fixed number like 0 or a label like “Unknown” for categorical data.

Example: In an age column, if 10% of entries are blank, you can fill them with the mean age of all other rows.

2. Handling Noise

Noise refers to random errors or unwanted variation in data that hides true patterns. It must be reduced to improve model performance.

Binning: Sort data into groups or bins and replace values with the bin average or median. This smooths out local fluctuations.
Regression: Fit a regression line to the data and use the predicted values to replace noisy points.
Outlier Detection: Identify extreme values using the Z-score or IQR method and remove or cap them.
Smoothing Filters: Use moving average or Gaussian filters to reduce random spikes in numerical data.
Clustering: Group similar data points together and remove points that do not belong to any major cluster.

Example: In a temperature dataset, a sudden reading of 500°C is clearly noise. Using the IQR method, this outlier can be detected and replaced with the median.

Data Preprocessing for Missing Values and Noise

Data preprocessing হলো raw data clean এবং transform করার step যা model-এ feed করার আগে করা হয়। Missing values এবং noise দুটি common problem যা accuracy কমায় এবং results mislead করতে পারে। নিচে এগুলো handle করার methods দেওয়া হয়েছে।

1. Handling Missing Values

Missing values ঘটে যখন কিছু data points record করা হয় না বা হারিয়ে যায়। Biased results এড়াতে এগুলো carefully handle করতে হবে।

Deletion: Rows বা columns remove করা যেগুলোতে অনেক missing values আছে। এটি simple কিন্তু শুধু small এবং random missing data-এর ক্ষেত্রে কাজ করে।
Mean/Median/Mode Imputation: Missing numeric values সেই column-এর average (mean), middle value (median) বা most common value (mode) দিয়ে fill করা।
Forward/Backward Fill: আগের বা পরের available value ব্যবহার করে gap fill করা, time-series data-এর জন্য useful।
Predictive Imputation: KNN বা regression এর মতো machine learning models ব্যবহার করে অন্য columns-এর উপর ভিত্তি করে missing values predict এবং fill করা।
Constant Value Fill: Missing values একটি fixed number যেমন 0 বা categorical data-এর জন্য “Unknown” label দিয়ে replace করা।

Example: একটি age column-এ যদি 10% entries blank থাকে, তাহলে অন্য rows-এর mean age দিয়ে সেগুলো fill করা যায়।

2. Handling Noise

Noise হলো data-এর random errors বা unwanted variation যা true patterns hide করে। Model performance উন্নত করতে এটি কমাতে হবে।

Binning: Data-কে groups বা bins-এ sort করে এবং bin average বা median দিয়ে values replace করা। এটি local fluctuations smooth করে।
Regression: Data-এর উপর regression line fit করে এবং noisy points-কে predicted values দিয়ে replace করা।
Outlier Detection: Z-score বা IQR method ব্যবহার করে extreme values identify করে remove বা cap করা।
Smoothing Filters: Numerical data-এর random spikes কমাতে moving average বা Gaussian filters ব্যবহার করা।
Clustering: Similar data points একসাথে group করে এবং এমন points remove করা যা কোনো major cluster-এর অংশ নয়।

Example: একটি temperature dataset-এ হঠাৎ 500°C reading noise হিসেবে স্পষ্ট। IQR method ব্যবহার করে এই outlier detect করা যায় এবং median দিয়ে replace করা যায়।

4. A voice signal is band-limited to 4 kHz. Each sample is quantized using 256 discrete levels. Find the resulting bit rate in a Pulse Code Modulation (PCM) system.

Given:

Bandwidth of voice signal = 4 kHz
Quantization levels = 256

Step 1: Find the Sampling Rate
According to the Nyquist theorem, the minimum sampling rate is twice the highest frequency.

Sampling Rate = 2 × Bandwidth
Sampling Rate = 2 × 4 kHz = 8 kHz = 8000 samples/second

Step 2: Find Bits Per Sample
Each sample is quantized into 256 levels. The number of bits needed is found using:

Levels = 2ⁿ
256 = 2ⁿ
n = log₂(256) = 8 bits per sample

Step 3: Calculate Bit Rate
Bit Rate = Sampling Rate × Bits Per Sample
Bit Rate = 8000 × 8 = 64,000 bits/second = 64 kbps

PCM Bit Rate Calculation

Given:

Voice signal-এর Bandwidth = 4 kHz
Quantization levels = 256

Step 1: Sampling Rate বের করা
Nyquist theorem অনুযায়ী, minimum sampling rate highest frequency-এর দ্বিগুণ।

Sampling Rate = 2 × Bandwidth
Sampling Rate = 2 × 4 kHz = 8 kHz = 8000 samples/second<

Step 2: Bits Per Sample বের করা
প্রতিটি sample 256 levels-এ quantize করা হয়। Bits-এর সংখ্যা নিচের সূত্র দিয়ে পাওয়া যায়:

Levels = 2ⁿ
256 = 2ⁿ
n = log₂(256) = 8 bits per sample<

Step 3: Bit Rate হিসাব
Bit Rate = Sampling Rate × Bits Per Sample
Bit Rate = 8000 × 8 = 64,000 bits/second = 64 kbps

5. Two separate threads are initialized with the exact same instance of CounterSubsystem and run concurrently to completion. State definitively whether the final value of transactionCounter is guaranteed to be exactly 2000. Name the specific multithreading hazard that occurs here and explain the low-level mechanical steps that cause this behavior.

class CounterSubsystem implements Runnable {
public int transactionCounter = 0;
@Override
public void run() {
for (int i = 0; i < 1000; i++) {
transactionCounter++;
}
}
}

Multithreading Analysis: CounterSubsystem

Is the final value guaranteed to be 2000?

No, the final value of transactionCounter is NOT guaranteed to be exactly 2000. The actual result could be any value between 1000 and 2000, but it will most likely be less than 2000.

Specific Multithreading Hazard

The hazard is a Race Condition, more specifically a Data Race or Read-Modify-Write Race Condition. It occurs because multiple threads access and modify the same shared variable without any synchronization mechanism.

Low-Level Mechanical Steps Causing the Behavior

The statement transactionCounter++ looks like a single operation in Java source code, but it is not atomic at the CPU or JVM bytecode level. It breaks down into three separate mechanical steps:

READ: Load the current value of transactionCounter from main memory into a thread-local CPU register or cache.
MODIFY: Increment the value inside the register by 1.
WRITE: Store the incremented value back from the register into main memory.

Because the two threads run concurrently with no locking, their six total steps (three per thread) can interleave in an unpredictable order decided by the operating system scheduler. This causes updates to be lost.
Concrete Example of a Lost Update:

Time Step	Thread 1	Thread 2	Memory Value
1	READ: sees 0		0
2		READ: sees 0	0
3	MODIFY: 0 + 1 = 1		0
4		MODIFY: 0 + 1 = 1	0
5	WRITE: stores 1		1
6		WRITE: stores 1	1

Both threads read 0, both computed 1, and both wrote 1. One full increment was lost. If this pattern repeats across the 1000 iterations, the final count will be significantly lower than 2000.

How to Fix It

synchronized keyword: Wrap the increment inside a synchronized block using a shared lock object.
AtomicInteger: Replace int with java.util.concurrent.atomic.AtomicInteger and use its incrementAndGet() method, which is atomic.
volatile: Using volatile alone is not enough here because it does not make the compound read-modify-write operation atomic.

Multithreading Analysis: CounterSubsystem

Final value 2000 হওয়া guaranteed কিনা?

No, transactionCounter-এর final value exactly 2000 হওয়া guaranteed নয়। Actual result 1000 থেকে 2000-এর মধ্যে যেকোনো value হতে পারে, কিন্তু এটি সম্ভবত 2000-এর কম হবে।

Specific Multithreading Hazard

Hazard হলো Race Condition, আরো specifically Data Race বা Read-Modify-Write Race Condition। এটি occurs করে কারণ multiple threads কোনো synchronization mechanism ছাড়াই একই shared variable access এবং modify করে।

Low-Level Mechanical Steps যা Behavior Cause করে

Statement transactionCounter++ Java source code-এ single operation দেখালেও CPU বা JVM bytecode level-এ এটি atomic নয়। এটি তিনটি separate mechanical steps-এ break down হয়:

READ: transactionCounter-এর current value main memory থেকে thread-local CPU register বা cache-এ load করা।
MODIFY: Register-এর value 1 বাড়ানো।
WRITE: Incremented value register থেকে main memory-তে store back করা।

দুটি thread কোনো locking ছাড়াই concurrently run করলে তাদের ছয়টি total steps (প্রতিটি thread-এ তিনটি) operating system scheduler দ্বারা unpredictable order-এ interleave হতে পারে। এতে updates lost হয়।

Lost Update-এর Concrete Example:

Time Step	Thread 1	Thread 2	Memory Value
1	READ: 0 দেখে		0
2		READ: 0 দেখে	0
3	MODIFY: 0 + 1 = 1		0
4		MODIFY: 0 + 1 = 1	0
5	WRITE: 1 store করে		1
6		WRITE: 1 store করে	1

দুটি thread 0 পড়ে, দুটি 1 compute করে, এবং দুটি 1 write করে। একটি full increment lost হয়ে যায়। এই pattern 1000 iterations জুড়ে repeat হলে final count 2000-এর চেয়ে significantly কম হবে।

Fix করার উপায়

synchronized keyword: Increment-কে shared lock object ব্যবহার করে synchronized block-এর মধ্যে wrap করা।
AtomicInteger: int-কে java.util.concurrent.atomic.AtomicInteger দিয়ে replace করে তার incrementAndGet() method ব্যবহার করা, যা atomic।
volatile: শুধু volatile ব্যবহার করা এখানে যথেষ্ট নয় কারণ এটি compound read-modify-write operation-কে atomic করে না।

6. In a B+ tree, each node can have a maximum of 4 child pointers (order m = 4). From height 0 to height 2 (where height 0 is the root), what is the maximum number of keys that can be stored across all nodes in the tree?

Given:
Order m = 4 (maximum 4 child pointers per node)
Height range: 0 (root) to 2 (leaves)

Key Property:
In a B+ tree, if a node has a maximum of m child pointers, it can hold a maximum of m − 1 keys. Here, each node can hold up to 3 keys.<

Step-by-Step Calculation:

Height 0 (Root):
1 node × 3 keys = 3 keys
This root has 4 children to maximize the tree.

Height 1 (Internal Nodes):
4 nodes × 3 keys = 12 keys
Each of the 4 children of the root is full and has 4 children of its own.

Height 2 (Leaf Nodes):
16 nodes × 3 keys = 48 keys
4 nodes at height 1 each have 4 children, giving 4 × 4 = 16 leaves.

Total Maximum Keys:
3 + 12 + 48 = 63 keys

Formula Verification:
Total keys = (m − 1) × (m⁰ + m¹ + m²)<
Total keys = 3 × (1 + 4 + 16) = 3 × 21 = 63

Given:
Order m = 4 (প্রতিটি node-এর সর্বোচ্চ 4 child pointers)
Height range: 0 (root) থেকে 2 (leaves) পর্যন্ত

Key Property:
B+ tree-এ একটি node-এর সর্বোচ্চ m child pointers থাকলে এতে সর্বোচ্চ m − 1 keys থাকতে পারে। এখানে প্রতিটি node সর্বোচ্চ 3 keys ধারণ করতে পারে।

Step-by-Step Calculation:

Height 0 (Root):
1 node × 3 keys = 3 keys
এই root maximum tree তৈরি করতে 4 children রাখে।

Height 1 (Internal Nodes):
4 nodes × 3 keys = 12 keys
Root-এর 4 children প্রতিটি full থাকে এবং প্রতিটির 4 children থাকে।<

Height 2 (Leaf Nodes):
16 nodes × 3 keys = 48 keys
Height 1-এর 4 nodes প্রতিটির 4 children থাকলে 4 × 4 = 16 leaves পাওয়া যায়।<

Total Maximum Keys:
3 + 12 + 48 = 63 keys
Formula Verification:
Total keys = (m − 1) × (m⁰ + m¹ + m²)<
Total keys = 3 × (1 + 4 + 16) = 3 × 21 = 63

7. #include <stdio.h>
int main() {
int ledger[5] = {10, 20, 30, 40, 50};
int *ptr1 = (int *)(&ledger + 1);
int *ptr2 = (int *)(ledger + 1);
// Note: Assuming the prompt meant to print using the variables defined above.
// If evaluating the exact expression printed in the prompt: *(ptr1 - 1) and *(ptr2 + 2)
printf("%d, %d", *(ptr1 - 1), *(ptr2 + 2));
return 0;
}

Code:

#include <stdio.h>
int main() {
int ledger[5] = {10, 20, 30, 40, 50};
int *ptr1 = (int *)(&ledger + 1);
int *ptr2 = (int *)(ledger + 1);
printf(“%d, %d”, *(ptr1 – 1), *(ptr2 + 2));
return 0;
}

Output:
50, 40

Step-by-Step Explanation
1. Array Layout in Memory

2. ptr1 = (int *)(&ledger + 1)

&ledger is a pointer to the entire array, type int (*)[5].
&ledger + 1 jumps forward by the size of the whole array (5 ints = 20 bytes). It lands just after the array ends.
ptr1 now points to the memory location right after ledger[4].

3. ptr2 = (int *)(ledger + 1)

ledger decays to a pointer to the first element, type int *.
ledger + 1 moves forward by 1 int (4 bytes) and points to ledger[1] which holds 20.
ptr2 points to the address of ledger[1].

4. *(ptr1 – 1)

ptr1 sits just past the end of the array.
ptr1 – 1 moves back by 1 int (4 bytes), landing on ledger[4].
Value = 50.

5. *(ptr2 + 2)

ptr2 points to ledger[1].
ptr2 + 2 moves forward by 2 ints (8 bytes), landing on ledger[3].
Value = 40.

8. A system utilizes a 32-bit logical address space and a page size of 2^{20} bytes. If each entry (block) in the Translation Lookaside Buffer (TLB) requires 6 bytes, calculate the total memory required for the TLB to map the entire logical address space

Given:

Logical address space = 32-bit
Page size = 2²⁰ bytes
TLB entry size = 6 bytes per entry

Step 1: Calculate Total Logical Address Space
A 32-bit address can reference 2³² unique bytes.

Total logical address space = 2³² bytes

Step 2: Calculate Number of Pages
Number of pages = Total address space ÷ Page size
Number of pages = 2³² ÷ 2²⁰ = 2^{(32 − 20)} = 2¹² = 4096 pages

Step 3: Calculate Total TLB Memory
Each page needs one TLB entry to map the entire logical address space.

Total TLB memory = Number of pages × Entry size
Total TLB memory = 4096 × 6 = 24576 bytes

In kilobytes: 24576 ÷ 1024 = 24 KB

TLB Memory Requirement Calculation

Given:Logical address space = 32-bit

Page size = 2²⁰ bytes
TLB entry size = 6 bytes প্রতি entry

Step 1: Total Logical Address Space হিসাব
32-bit address 2³² unique bytes reference করতে পারে।
Total logical address space = 2³² bytes

Step 2: Number of Pages হিসাব
Number of pages = Total address space ÷ Page size
Number of pages = 2³² ÷ 2²⁰ = 2^{(32 − 20)} = 2¹² = 4096 pages

Step 3: Total TLB Memory হিসাব
পুরো logical address space map করতে প্রতিটি page-এর জন্য একটি TLB entry প্রয়োজন।

Total TLB memory = Number of pages × Entry size
Total TLB memory = 4096 × 6 = 24576 bytes

Kilobytes-এ: 24576 ÷ 1024 = 24 KB<

9. Consider a concurrent transaction schedule involving two data items, X and Y:

Transaction 1 (T_1): Read(X), Write(X), Read(Y), Write(Y)
Transaction 2 (T_2): Read(Y), Write(Y), Read(X), Write(X)

Describe how the standard Two-Phase Locking (2PL) protocol treats these transactions if they execute concurrently, identifying the exact operational state (hazard) the system will enter. Contrast this outcome with how the Strict 2PL protocol alters the lock release timeline.

Two-Phase Locking (2PL) Analysis for Concurrent Transactions
Transaction Details:

T1: Read(X), Write(X), Read(Y), Write(Y)
T2: Read(Y), Write(Y), Read(X), Write(X)

Standard 2PL Execution

In standard 2PL, each transaction has a growing phase (only acquiring locks) and a shrinking phase (only releasing locks). Both transactions request exclusive locks because they intend to write.

Step-by-Step Interleaving:

Step	T1 Action	T2 Action	Lock Status
1	Lock-X(X) granted		T1 holds X
2	Read(X), Write(X)		T1 holds X
3		Lock-X(Y) granted	T1 holds X, T2 holds Y
4		Read(Y), Write(Y)	T1 holds X, T2 holds Y
5	Lock-X(Y) requested → WAITS		T1 waits for Y
6		Lock-X(X) requested → WAITS	T2 waits for X

Operational State Entered: DEADLOCK

The system enters a deadlock (circular wait). T1 holds the lock on X and waits for Y, while T2 holds the lock on Y and waits for X. Neither can proceed. The database must detect this (using a wait-for graph or timeout) and resolve it by aborting and rolling back one of the transactions.

Strict 2PL Protocol

Strict 2PL follows the same growing phase rules as standard 2PL, so it encounters the same deadlock for this schedule. However, it alters the lock release timeline significantly:

Standard 2PL: Once a transaction reaches its maximum lock point, it enters the shrinking phase and may release locks gradually. For example, T1 could release Lock(X) after Write(X) if it had already acquired Lock(Y), but since it is blocked, this never happens.
Strict 2PL: All locks are held until the transaction commits or aborts. No lock is released before the end. This means even if a transaction somehow completed its operations, it would keep all locks until the final commit point.

Contrast Table:

Aspect	Standard 2PL	Strict 2PL
Deadlock Risk	Yes, occurs in this schedule	Yes, same growing phase behavior
Lock Release	Can release after last use (shrinking phase)	Held strictly until commit/abort
Cascading Rollbacks	Possible	Prevented
Schedule Type	Recoverable, but not strict	Strict and recoverable

Key Takeaway: Strict 2PL does not eliminate the deadlock in this specific concurrent schedule, but it guarantees that no uncommitted data is ever exposed to other transactions by forcing all locks to remain until the transaction fully terminates.

Concurrent Transactions-এর জন্য Two-Phase Locking (2PL) Analysis

Transaction Details:

T1: Read(X), Write(X), Read(Y), Write(Y)
T2: Read(Y), Write(Y), Read(X), Write(X)

Standard 2PL Execution

Standard 2PL-এ প্রতিটি transaction-এর growing phase (শুধু lock acquire করা) এবং shrinking phase (শুধু lock release করা) থাকে। উভয় transaction write করবে বলে exclusive locks request করে।
Step-by-Step Interleaving:

Step	T1 Action	T2 Action	Lock Status
1	Lock-X(X) granted		T1 holds X
2	Read(X), Write(X)		T1 holds X
3		Lock-X(Y) granted	T1 holds X, T2 holds Y
4		Read(Y), Write(Y)	T1 holds X, T2 holds Y
5	Lock-X(Y) requested → WAITS		T1 waits for Y
6		Lock-X(X) requested → WAITS	T2 waits for X

Operational State: DEADLOCK

System deadlock (circular wait)-এ প্রবেশ করে। T1 X lock hold করে Y-এর জন্য waits করে, এবং T2 Y lock hold করে X-এর জন্য waits করে। কেউই এগোতে পারে না। Database এটি detect করতে হবে (wait-for graph বা timeout ব্যবহার করে) এবং একটি transaction abort এবং rollback করে resolve করতে হবে।

Strict 2PL Protocol
Strict 2PL standard 2PL-এর মতো same growing phase rules follow করে, তাই এটি same deadlock encounter করে। কিন্তু এটি lock release timeline significantly alter করে:

Standard 2PL: Transaction maximum lock point reach করলে shrinking phase-এ প্রবেশ করে এবং gradually locks release করতে পারে। উদাহরণস্বরূপ, T1 Lock(X) Write(X)-এর পর release করতে পারত যদি Lock(Y) already acquire করা থাকত, কিন্তু blocked হওয়ায় এটি কখনো হয় না।
Strict 2PL: সব locks transaction commit বা abort না হওয়া পর্যন্ত hold করা হয়। End-এর আগে কোনো lock release করা হয় না। এর মানে transaction যদি somehow operations complete করে, সব locks final commit point পর্যন্ত keep করবে।

Contrast Table:

Aspect	Standard 2PL	Strict 2PL
Deadlock Risk	Yes, এই schedule-এ occurs করে	Yes, same growing phase behavior
Lock Release	Last use-এর পর release করতে পারে (shrinking phase)	Commit/abort পর্যন্ত strictly held
Cascading Rollbacks	Possible	Prevented
Schedule Type	Recoverable, কিন্তু strict নয়	Strict এবং recoverable

Key Takeaway: Strict 2PL এই specific concurrent schedule-এর deadlock eliminate করে না, কিন্তু এটি guarantee দেয় যে transaction fully terminate না হওয়া পর্যন্ত uncommitted data অন্য transaction-এর কাছে expose হয় না, সব locks-কে end পর্যন্ত hold করে রেখে।

10. Compare between TCP and UDP, their connection, reliability, speed. One real life use case of UDP.

TCP vs UDP

TCP (Transmission Control Protocol) and UDP (User Datagram Protocol) are both transport layer protocols, but they serve different purposes based on the needs of the application.

1. Connection

TCP: Connection-oriented. It establishes a connection using a 3-way handshake (SYN, SYN-ACK, ACK) before data transfer begins. The connection is closed gracefully after communication ends.
UDP: Connectionless. It sends data directly without any handshake or setup phase. There is no formal connection established or terminated.

2. Reliability

TCP: Highly reliable. It guarantees delivery through acknowledgments, retransmissions, and sequence numbers. Lost packets are resent, and data arrives in the correct order.
UDP: Unreliable. It does not guarantee delivery, order, or duplicate protection. Packets may be lost, duplicated, or arrive out of order without any automatic correction.

3. Speed

TCP: Slower due to connection setup, acknowledgments, congestion control, and flow control mechanisms. The overhead ensures data integrity but adds delay.
UDP: Faster because it has minimal overhead. No handshake, no acknowledgment, and no retransmission means lower latency and quicker transmission.

Comparison Table:

Feature	TCP	UDP
Connection	Connection-oriented (3-way handshake)	Connectionless (no handshake)
Reliability	Guaranteed delivery with ACK	No delivery guarantee
Speed	Slower due to overhead	Faster, low latency
Ordering	Data arrives in sequence	No ordering guarantee
Error Checking	Yes, with recovery	Yes, but no recovery
Use Case	Web, email, file transfer	Streaming, gaming, DNS

Real-Life Use Case of UDP

Video Streaming (YouTube Live, Netflix, Twitch)

Video streaming platforms use UDP because speed and low latency matter more than perfect reliability. If a few video frames are lost during a live broadcast, it is better to skip them and keep the stream flowing smoothly rather than pause and retransmit. Users prefer a slightly imperfect but continuous video over a constantly buffering one. UDP allows the video to reach the viewer quickly without waiting for acknowledgments or retransmissions.

Other UDP Examples:

Online Gaming: Real-time player positions and actions must be sent instantly. A delayed packet is useless, so UDP is preferred.
DNS Queries: Domain name lookups are small, single-packet requests where the overhead of TCP is unnecessary.
Voice over IP (VoIP): Phone calls over the internet use UDP to avoid delays that would make conversations awkward.

TCP vs UDP

TCP (Transmission Control Protocol) এবং UDP (User Datagram Protocol) উভয়ই transport layer protocol, কিন্তু application-এর প্রয়োজন অনুযায়ী ভিন্ন উদ্দেশ্যে ব্যবহৃত হয়।

1. Connection

TCP: Connection-oriented। Data transfer শুরুর আগে 3-way handshake (SYN, SYN-ACK, ACK) ব্যবহার করে connection establish করে। Communication শেষে connection gracefully close করা হয়।
UDP: Connectionless। কোনো handshake বা setup phase ছাড়াই সরাসরি data পাঠায়। কোনো formal connection establish বা terminate করা হয় না।

2. Reliability

TCP: Highly reliable। Acknowledgments, retransmissions এবং sequence numbers-এর মাধ্যমে delivery guarantee করে। Lost packets resent হয় এবং data সঠিক order-এ পৌঁছায়।
UDP: Unreliable। Delivery, order বা duplicate protection guarantee করে না। Packets হারিয়ে যেতে পারে, duplicate হতে পারে বা out of order পৌঁছাতে পারে, কোনো automatic correction ছাড়াই।

3. Speed

TCP: Slower কারণ connection setup, acknowledgments, congestion control এবং flow control mechanisms-এর overhead থাকে। Data integrity নিশ্চিত করে কিন্তু delay add করে।
UDP: Faster কারণ এতে minimal overhead আছে। কোনো handshake, acknowledgment বা retransmission না থাকায় latency কম এবং transmission দ্রুত।

Comparison Table:

Feature	TCP	UDP
Connection	Connection-oriented (3-way handshake)	Connectionless (কোনো handshake নেই)
Reliability	ACK সহ guaranteed delivery	Delivery guarantee নেই
Speed	Overhead-এর কারণে slower	Fast, low latency
Ordering	Data sequence-এ পৌঁছায়	Ordering guarantee নেই
Error Checking	Yes, recovery-সহ	Yes, কিন্তু recovery নেই
Use Case	Web, email, file transfer	Streaming, gaming, DNS

UDP-এর Real-Life Use Case

Video Streaming (YouTube Live, Netflix, Twitch)

Video streaming platforms UDP ব্যবহার করে কারণ speed এবং low latency perfect reliability-এর চেয়ে বেশি important। Live broadcast-এর সময় কিছু video frames হারিয়ে গেলে skip করা এবং stream smoothly চালু রাখা ভালো, pause করে retransmit করার চেয়ে। Users slightly imperfect কিন্তু continuous video prefer করে constant buffering-এর চেয়ে। UDP acknowledgments বা retransmissions-এর জন্য অপেক্ষা না করে দ্রুত video viewer-এর কাছে পৌঁছাতে দেয়।

অন্যান্য UDP Examples:

Online Gaming: Real-time player positions এবং actions instantly পাঠাতে হবে। Delayed packet useless হয়, তাই UDP prefer করা হয়।
DNS Queries: Domain name lookups ছোট, single-packet requests যেখানে TCP-এর overhead unnecessary।
Voice over IP (VoIP): Internet-এর মাধ্যমে phone calls UDP ব্যবহার করে যাতে conversation awkward না হয়।

11. Assume a banking application wants to add fingerprint system for their App. Write one functional requirement and one security requirement.

Fingerprint System for Banking App

1. Functional Requirement

The app shall allow registered users to log in using their fingerprint as an alternative to the traditional username and password. The system must verify the fingerprint against the stored template and grant access to the user’s account dashboard within 2 seconds if the match is successful.

Example: A user opens the banking app, places their finger on the sensor, and the app unlocks directly to the home screen without typing a password.

2. Security Requirement

The app shall store all fingerprint biometric data in an encrypted format inside the device’s secure hardware (Trusted Execution Environment or Secure Enclave) and never transmit raw fingerprint images or templates to the bank’s server or any external database.

Example: Even if the bank’s main server is hacked, the attacker cannot steal any fingerprint data because the actual biometric information never leaves the user’s phone.

Fingerprint System for Banking App

1. Functional Requirement

App-টি registered users-কে traditional username এবং password-এর বিকল্প হিসেবে তাদের fingerprint ব্যবহার করে log in করতে দেবে। System stored template-এর সাথে fingerprint verify করবে এবং match successful হলে 2 seconds-এর মধ্যে user-এর account dashboard-এ access grant করবে।

Example: একজন user banking app open করলে, sensor-এ তাদের finger রাখলে, এবং app password type না করেই সরাসরি home screen unlock হয়ে যায়।

2. Security Requirement

App-টি সব fingerprint biometric data encrypted format-এ device-এর secure hardware (Trusted Execution Environment বা Secure Enclave)-এ store করবে এবং raw fingerprint images বা templates কখনো bank-এর server বা কোনো external database-তে transmit করবে না।

Example: Bank-এর main server hack হলেও attacker কোনো fingerprint data চুরি করতে পারবে না কারণ actual biometric information কখনো user-এর phone ছেড়ে যায় না।

Leave a Comment Cancel Reply

You must be logged in to post a comment.

Field Based Job Solution Topic Based QnS IT Job News / Circular

Combined Bank Officer IT (Job ID-10226) Post: Assistant programmer; Exam: 22-May-2026

Leave a Comment Cancel Reply

Combined Bank
Officer IT (Job ID-10226)
Post: Assistant programmer; Exam: 22-May-2026