Sonali Bank Assistant Database Administrator Exam 9 January 2026 — Question Solution | সোনালী ব্যাংক সহকারী ডাটাবেজ অ্যাডমিনিস্ট্রেটর নিয়োগ পরীক্ষা ২০২৬ — প্রশ্ন সমাধান

Dynamic programming (DP) is an algorithm-design technique that solves a problem by breaking it into smaller overlapping subproblems, solving each subproblem only once, storing its answer in a table (or memo), and building the final answer from the stored answers. It turns many exponential-time recursive solutions into polynomial-time (or pseudo-polynomial-time) ones.

Properties of dynamic programming

1. Optimal substructure: an optimal solution to the problem contains optimal solutions to its subproblems (Bellman's principle of optimality). Example: if the cheapest route Dhaka → Chattogram passes through Cumilla, its Dhaka → Cumilla part must itself be the cheapest Dhaka → Cumilla route.
2. Overlapping subproblems: a plain recursion would solve the same subproblem again and again. (Divide and conquer, by contrast, splits into independent subproblems, as in merge sort.)
3. Memory of results (memoization / tabulation): each subproblem's answer is saved and looked up later instead of being recomputed.
   • Top-down (memoization): write the recursion and cache each result the first time it is computed.
   • Bottom-up (tabulation): fill a table from the smallest subproblems upward.
4. A recurrence relation: the answer of a state is defined from smaller states, with base cases.
5. A manageable number of distinct states: the running time is (number of states) × (work per state), so DP is fast when the distinct states are few (for the coin example, A + 1 states with k checks each).

Example: minimum number of coins

Coins {1, 5, 7} (unlimited supply), amount 10. Let dp[a] = fewest coins that make amount a.

dp[0] = 0, dp[a] = 1 + min{ dp[a − c] : coin c ≤ a }

Overlapping subproblems in the plain recursion (part of the call tree):

graph TD
  A10["coins(10)"] -- "use 1" --> A9["coins(9)"]
  A10 -- "use 5" --> A5["coins(5)"]
  A10 -- "use 7" --> A3["coins(3)"]
  A9 -- "use 5" --> A4a["coins(4)"]
  A5 -- "use 1" --> A4b["coins(4)"]
  A9 -- "use 7" --> A2a["coins(2)"]
  A3 -- "use 1" --> A2b["coins(2)"]

coins(4) and coins(2) are each reached by two branches. The plain recursion makes 43 calls for amount 10 and 34 309 calls for amount 30, while the DP table fills only 30 entries (dp[1] to dp[30]) with at most 3 checks each.

Bottom-up table:

a	Candidates dp[a − c] + 1	dp[a]
0	–	0
1	dp[0]+1=1	1
2	dp[1]+1=2	2
3	dp[2]+1=3	3
4	dp[3]+1=4	4
5	dp[4]+1=5, dp[0]+1=1	1
6	dp[5]+1=2, dp[1]+1=2	2
7	dp[6]+1=3, dp[2]+1=3, dp[0]+1=1	1
8	dp[7]+1=2, dp[3]+1=4, dp[1]+1=2	2
9	dp[8]+1=3, dp[4]+1=5, dp[2]+1=3	3
10	dp[9]+1=4, dp[5]+1=2, dp[3]+1=4	2

Answer: 2 coins (5 + 5). The greedy rule "largest coin first" gives 7 + 1 + 1 + 1 = 4 coins, which is not optimal; DP checks every choice through the stored answers.

import math

def min_coins(coins, amount):
    dp = [0] + [math.inf] * amount         # dp[a] = fewest coins for amount a
    last = [0] * (amount + 1)              # last coin used, to rebuild the answer
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
                last[a] = c
    picked, a = [], amount
    while a > 0:                           # walk back through the table
        picked.append(last[a])
        a -= last[a]
    return dp[amount], picked

print(min_coins([1, 5, 7], 10))

Output: (2, [5, 5])

Complexity: O(k · A) time and O(A) space for k coin types and amount A, against exponential time for the plain recursion.

Basis	Divide and conquer	Greedy	Dynamic programming
Subproblems	Independent	One choice, no subproblem revisited	Overlapping
Stores results	No	No	Yes (table or memo)
Optimal answer	Yes, for its problems	Only when the greedy-choice property holds	Yes, when optimal substructure holds
Example	Merge sort	Activity selection	Knapsack 0/1, LCS, Floyd–Warshall

Other standard DP problems: 0/1 knapsack, longest common subsequence, matrix-chain multiplication, edit distance, Floyd–Warshall all-pairs shortest paths.

Exam tip: name the two key properties (optimal substructure, overlapping subproblems), then show a recurrence and a filled table for one example.

The rule set

Every rule is for traffic from source A to destination B and tests the destination port:

Order	Source	Destination	Port condition	Action (assumed)
Rule 1	A	B	port = 89	allow
Rule 2	A	B	port < 443 (0–442)	deny
Rule 3	A	B	port = 443	allow
(end)	any	any	anything else	implicit deny

The rules as stated give no action, so the usual layout of such a rule set is assumed: a narrow allow (Rule 1), a broad deny (Rule 2) and an allow for HTTPS (Rule 3). For the port-443 packet only Rule 3's action matters, because Rules 1 and 2 do not match it, as the trace shows.

The "first match" inspection procedure

1. The firewall reads the packet's header: source, destination, protocol and destination port.
2. It compares the packet with the rules from the top, one by one, in order.
3. A rule matches only if every field in it matches the packet.
4. At the first matching rule, the firewall applies that rule's action (allow or deny) and stops; later rules are never checked.
5. If no rule matches, the implicit default rule at the end (deny all) drops the packet.

Trace: packet A → B, destination port 443

Step	Rule	Test	Result
1	Rule 1	443 = 89?	No match → go to next rule
2	Rule 2	443 < 443?	No match: "less than 443" covers ports 0–442 only, so 443 is not inside it
3	Rule 3	443 = 443?	Match → apply Rule 3's action, stop

Verdict: the packet is decided by Rule 3, the first and only matching rule. Rule 3 is the allow rule for port 443, so the packet is ACCEPTED. The result is always Rule 3's own action: had Rule 3 been written as a deny rule, the same trace would end in REJECTED.

flowchart TD
    P["Packet A to B, port 443"] --> R1{"Rule 1: port = 89?"}
    R1 -- "No" --> R2{"Rule 2: port less than 443?"}
    R1 -- "Yes" --> X1["Apply Rule 1, stop"]
    R2 -- "No" --> R3{"Rule 3: port = 443?"}
    R2 -- "Yes" --> X2["Apply Rule 2, stop"]
    R3 -- "Yes" --> OK["Apply Rule 3: ACCEPT, stop"]
    R3 -- "No" --> D["Implicit default: DENY"]

Simulation of first-match processing

RULES = [  # (name, src, dst, test on destination port, action)
    ("Rule 1", "A", "B", lambda p: p == 89,  "ALLOW"),
    ("Rule 2", "A", "B", lambda p: p < 443,  "DENY"),
    ("Rule 3", "A", "B", lambda p: p == 443, "ALLOW"),
]

def inspect(src, dst, dport):
    for name, s, d, test, action in RULES:      # top to bottom
        hit = (s == src and d == dst and test(dport))
        print(f"  {name}: {'MATCH' if hit else 'no match'}")
        if hit:
            return f"{action} by {name}"          # first match wins: stop here
    return "DENY by the implicit default rule"

for port in (443, 89, 80, 8080):
    print(f"Packet A -> B, destination port {port}")
    print("  Result:", inspect("A", "B", port))

Output:

Packet A -> B, destination port 443
  Rule 1: no match
  Rule 2: no match
  Rule 3: MATCH
  Result: ALLOW by Rule 3
Packet A -> B, destination port 89
  Rule 1: MATCH
  Result: ALLOW by Rule 1
Packet A -> B, destination port 80
  Rule 1: no match
  Rule 2: MATCH
  Result: DENY by Rule 2
Packet A -> B, destination port 8080
  Rule 1: no match
  Rule 2: no match
  Rule 3: no match
  Result: DENY by the implicit default rule

Why the order matters

• With these actions, port 89 is inside Rule 2's range (0–442), yet it is allowed, because Rule 1 is checked first. If Rule 1 were placed after Rule 2, port 89 would be denied.
• If Rule 2 were written ≤ 443, the port-443 packet would match Rule 2 first and be rejected; Rule 3 would then be shadowed (it could never be reached).
• So firewall rules are written specific first, general later, with deny-all at the end.

If "from 443" means source port 443

These rules test the destination port of traffic going A → B. A packet coming from port 443 is normally the reply of an HTTPS server B to A, i.e. traffic in the B → A direction, which matches none of these rules. A stateful firewall accepts it because it belongs to the connection A opened to B:443 (it is found in the state table); a stateless filter needs a separate return rule, otherwise the default deny drops it.

Exam tip: in first-match processing, check each condition literally ("< 443" excludes 443), stop at the first hit, and remember the hidden "deny all" at the end.