12 Core Computer Science Problems Solved: CPU, Paging, Normalization & Kubernetes Probes

Question 1: CPU Time Calculation

Problem: A program executes 800 million instructions with an average CPI of 3 at a clock frequency of 2 GHz. Find total clock cycles and CPU execution time.

Solution: Total cycles = 800 million × 3 = 2.4 billion cycles. 2 GHz = 2 billion cycles per second. Execution time = 2.4 billion ÷ 2 billion = 1.2 seconds.

Total cycles = 800M × 3 cycles/inst = 2.4B cycles
2 GHz = 2B cycles per second
Time = 2.4B ÷ 2B = 1.2 seconds

Key insight: First compute total work (cycles), then divide by cycles per second. Common errors: dividing 8 by 2 directly (ignoring CPI) or treating GHz as instruction throughput (confusing cycles with instructions).

Must confirm: Can state "instruction count × CPI = cycles" without hints and express final answer in seconds.

Question 2: Bus Bandwidth

Problem: Clock frequency 80 MHz, each bus cycle takes 4 clock cycles, each bus cycle transfers 64 bits. Compute bandwidth in decimal MB/s and explain why division by 4 is needed.

Solution: 160 MB/s.

80 MHz = 80M clock cycles per second
Each transfer takes 4 cycles: 80M ÷ 4 = 20M transfers/sec
64 bits ÷ 8 = 8 bytes/transfer
20M transfers/sec × 8 bytes/transfer = 160M bytes/sec
160M ÷ 1M = 160 MB/s

Dividing by 4 converts clock cycles to transfer count, not a unit conversion. One transfer consumes 4 clock cycles, so transfers per second are one quarter of clock cycles per second.

Must confirm: Do not treat 80M directly as transfer count; do not forget bit-to-byte division by 8.

Question 3: Paging Address Translation

Problem: Byte-addressed, page size 2 KiB, logical address 1810H. Page table: page 2 → frame 7, page 3 → frame 5, page 4 → frame 1. Find page number, offset, and physical address. Can the quotient be incremented by 1 because page numbers start at 0?

Solution: Logical page number 3, offset 10H, physical address 2810H. Cannot increment quotient.

2 KiB = 2048 B = 800H
1810H = 1×4096 + 8×256 + 1×16 = 6160
6160 ÷ 2048 = 3, remainder 16
Offset 16 = 10H
Page table: page 3 → frame 5
Physical address = 5 × 800H + 10H = 2810H

Logical page 3 starts at decimal 6144; address 6160 has offset 16 bytes from that page start. Although it is the 4th page sequentially, the page table key remains 3. Physical frame 5 differs from logical page 3; the page table must be consulted.

Must confirm: Distinguish page size 800H from address 1810H; only replace page number with frame number, leaving offset unchanged.

Question 4: Subnet Address Calculation

Problem: Interface address 192.168.20.173/27. Find mask, network address, broadcast address, and usable host count. Show last octet bitwise AND.

Solution: Mask 255.255.255.224, network 192.168.20.160, broadcast 192.168.20.191, 30 usable host addresses.

/27: first 27 bits network, last 5 bits host
Mask last octet: 11100000 = 224

173: 101 | 01101
224: 111 | 00000
AND: 101 | 00000 = 160

First three octets of mask are all 1s, unchanged. Host bits all 0 yields network address 160; host bits all 1 yields 10111111 = 191. Block size = 2^5 = 32 addresses; subtract network and broadcast for 30 usable (last octet 161–190).

Must confirm: /27 denotes network bits, not host bits; AND extracts network portion, not an arbitrary round number.

Question 5: Second Normal Form (2NF)

Problem: R(student_id, course_id, grade) satisfies 1NF, sole candidate key (student_id, course_id). Non-trivial FD: (student_id, course_id) → grade. No student_id → grade or course_id → grade. Can we conclude 2NF violation just because candidate key has two columns?

Answer: No. Under given FDs, the relation satisfies 2NF.

Only non-prime attribute is grade. Grade requires both student_id and course_id together; no non-prime attribute partially depends on the candidate key.

Know only student_id: cannot determine which course's grade
Know only course_id: cannot determine which student's grade
Both together: uniquely determine this grade

The given FDs could support higher normal forms, but the question only asks about 2NF. Do not mistake a composite candidate key for partial dependency; the combination itself is not the issue—whether a non-prime attribute depends on only part of the key is the key.

Must confirm: Identify the non-prime attribute being checked and the attributes it actually depends on.

Question 6: Third Normal Form (3NF)

Problem: Employee(emp_id, name, dept_id, dept_name), all single-valued; sole candidate key emp_id; FDs: emp_id → name, dept_id; dept_id → dept_name. One department can have many employees. Does this violate 3NF? Explain and provide a valid decomposition.

Answer: Violates 3NF.

dept_id → dept_name is a non-trivial FD. dept_id cannot determine emp_id (not a superkey); dept_name is not part of any candidate key (non-prime attribute). Both 3NF conditions fail.

Decompose into:

Employee(emp_id, name, dept_id)
Department(dept_id, dept_name)

Employee table retains department number; department name maintained in Department table. Full dependency path: emp_id → dept_id → dept_name; dept_name transitively depends on emp_id via dept_id.

Must confirm: Do not mechanically claim 3NF violation just because there are two arrows; explicitly verify that the middle determinant is not a superkey and the right side is a non-prime attribute.

Question 7: Lossless Join Decomposition

Problem: R(A,B,C) with only FD B → C, decomposed into R1(A,B) and R2(B,C). What is the common attribute? Is the decomposition lossless? Why is it not required that B also determines A?

Answer: Common attribute is B; decomposition is lossless.

R1 ∩ R2 = {B}
B → B (trivial, attribute determines itself)
Given B → C
Therefore B → BC, i.e., B determines all attributes of R2

Standard binary lossless join condition: common attribute determines all attributes of R1 OR common attribute determines all attributes of R2. Only one needs to hold.

Example: B = dept_id, C = dept_name, A = emp_id. Multiple employees can belong to same department; each employee record uses dept_id to match a unique dept_name, avoiding spurious combinations.

Must confirm: Previous question common attribute A determined left table; this question B determines right table—both are valid; do not memorize "A must determine left side".

Question 8: UML Class Diagram Notation

Problem: Specification states Order and OrderItem are in a composition relationship; WeChatPay class implements Payment interface. For each, specify line style, symbol, and which end the symbol appears on, and draw a simple diagram.

Answer: Composition: solid line + filled diamond, diamond at Order end. Implementation: dashed line + hollow triangle, triangle pointing to Payment interface.

[Order] ◆──────── [OrderItem]

[WeChatPay] - - -▷ [Payment]

Diamond marks the whole (composite) end; triangle marks the generalized/implemented end. Both composition and aggregation use a diamond, but aggregation is hollow; both inheritance and implementation use a hollow triangle, but inheritance uses solid line, implementation uses dashed line.

Must confirm: Check line style, shape, and position simultaneously, not just "there is an arrow".

Question 9: Three Types of Kubernetes Probes

Problem: Select probe type for each scenario: (A) long initialization at startup; (B) process running normally but temporarily should not receive requests, should not cause restart; (C) process hung, cannot self-recover, should restart after sustained failures.

Answer: A = Startup, B = Readiness, C = Liveness.

Startup probe: Protects startup processes needing initialization time. When configured, other probes wait until it succeeds; sustained failure can trigger restart.

Readiness probe: Determines if the pod can currently serve requests. Failure typically removes pod from Service endpoints; does not trigger restart by itself.

Liveness probe: Sustained failure triggers container restart; suitable for unrecoverable hangs.

Must confirm: "Process alive but not receiving traffic" vs "hung needing restart" are distinct needs. Do not treat all external dependency failures as liveness failures.

Question 10: Earned Value Calculation

Problem: At a given point: PV = 1.2M, EV = 0.9M, AC = 1.0M (in 10k RMB). Compute SV, CV, SPI, CPI, and interpret schedule and cost status. Can we claim savings just because AC < PV?

Solution: SV = -0.3M, CV = -0.1M, SPI = 0.75, CPI = 0.9; schedule behind, cost overrun for work performed.

SV = EV - PV = 0.9 - 1.2 = -0.3M
CV = EV - AC = 0.9 - 1.0 = -0.1M
SPI = EV / PV = 0.9 / 1.2 = 0.75
CPI = EV / AC = 0.9 / 1.0 = 0.9

Planned value of work to be done: 1.2M; actual earned value: 0.9M → schedule behind. Budget for work done: 0.9M; actual cost: 1.0M → cost overrun.

Cannot infer savings from AC < PV; must compare actual cost to earned value (work actually completed). SV is not a time difference; cannot say "behind by 30 days".

Must confirm: EV is not revenue; both indices use EV as numerator.

Question 11: Deadlock Prevention Analysis

Problem: Strategy A: all threads acquire locks in increasing order of lock ID. Strategy B: request all needed resources at once; if not all available, acquire none. Which necessary deadlock condition does each break?

Answer: A breaks circular wait; B breaks hold and wait.

Uniform increasing lock acquisition prevents wait cycles along lock IDs; does not forcibly preempt held locks nor eliminate mutual exclusion.

Request all resources atomically; if any unavailable, acquire none. Thread never holds some resources while waiting for others.

Must confirm: Four necessary conditions: mutual exclusion, hold and wait, no preemption, circular wait. Circular wait is indeed a necessary condition; previous Day 71 misstatement should not be memorized as fact.

Question 12: Reverse-Checking Common Misconceptions

Problem: Someone claims: "2 GHz frequency means 2 billion instructions executed per second; 32-bit address bus with byte addressing, must first compute 32 ÷ 8 to get address count." Identify the error in each statement.

Answer: First statement confuses cycles with instructions; second confuses address bit-width with data byte size.

2 GHz only means 2 billion clock cycles per second. Instruction throughput depends on average CPI. In the relevant model, instruction throughput = clock frequency ÷ average CPI, not a fixed 2 billion instructions/second.

32 address bits yield 2^32 distinct encodings. With byte addressing, each address corresponds to 1 byte, so address space = 2^32 bytes = 4 GiB. 32 ÷ 8 merely gives the byte size of a 32-bit datum, not the number of addresses.

Must confirm: First determine whether a number describes encoding width, data size, work quantity, or event count, then decide if division by 8 is appropriate.