MCQ Questions

Q1: One million sorted integers — array vs doubly linked list lookup

We want to store one million "interesting" 64-bit unsigned integers, inserted in sorted order, and query whether a random 64-bit value is interesting. Each element probe takes 5 ns. Average-case lookup time?

• (A) 100 ns array / 2.5M ns linked list
• (B) 100 ns array / 5M ns linked list
• (C) 2.5M ns array / 2.5M ns linked list
• (D) 2.5M ns array / 5M ns linked list
• (E) 2.5M ns array / 100 ns linked list
• (F) 5M ns array / 100 ns linked list

Answer: A. Random-access array supports binary search in log2(10⁶) ≈ 20 probes → ≈ 100 ns. Linked list has no random access, so binary search degrades; average half-list scan is 5·10⁵ probes → ≈ 2.5M ns.

Q2: Alphabetic comparator bug

The instructor's comparator increments letter_index before reading characters, skipping index 0; for inputs ["aaa", "ccc"] it ends up comparing position 1 vs 1 ('a' vs 'c'), returns False, and the sort tries to swap — but the same buggy compare reverses on the swapped order too, leading to undefined behavior or an infinite loop in some sort frameworks.

• (A) ["ccc", "aaa"]
• (B) ["ccc", "ccc"]
• (C) ["aaa", "aaa"]
• (D) ["aaa", "ccc"]
• (E) Program will crash, throw an error, or exhibit undefined behavior.

Answer: E. The off-by-one (letter_index += 1 before reading) and the "return True even on equal" tail mean the comparator is not a strict weak ordering — most standard sorts will exhibit undefined behavior.

Q3: Extract a Field (bit ops on byte 6)

Records pack data-routing, pri, flag, r and destination-id into bytes 4-7. The flag field occupies bits 6..4 of byte 6 (3-bit field). Which expression extracts flag?

• (A) (record[2] & 0xF0) >> 4
• (B) (record[6] | 0xF) >> 4
• (C) (record[2] >> 4) & 0x7
• (D) (record[2] & 0x7) << 1
• (E) (record[6] & 0x70) >> 4

Answer: E. Mask 0x70 = 0111_0000 keeps exactly bits 6..4 of record[6], then shift right by 4 to align.

Q4: Stack size trace

list = [3, 3, 4, 2, 5, 4]
for element in list:
 if element is odd: push element
 else: old = pop; if old > element: push element

What is the maximum stack size?

• (A) 1
• (B) 2
• (C) 3
• (D) 4
• (E) 5

Answer: B (2). Trace: push 3 (size 1) → push 3 (size 2) → pop, 3<4, no push (size 1) → pop, 3>2, push 2 (size 1) → push 5 (size 2) → pop, 5>4, push 4 (size 1). Peak = 2.

Q5: Singly linked list operations dependent on length

Singly linked list with head pointer F and tail pointer L. Which operations take time proportional to list length?

• (A) Split the list into two equal-length lists
• (B) Add an element after the last element
• (C) Add an element before the last element
• (D) Add an element after the first element
• (E) Interchange first and last elements

Answer: A, C, E. Splitting requires walking to the midpoint (O(n)); inserting before tail needs the second-to-last node, which requires a full scan (O(n)); interchanging first and last requires the second-to-last node to relink (O(n)). Appending after L and inserting after F are both O(1) since we have those pointers directly.

Q6: Loop invariant of p = (k-1)!

p = 1; k = 1;
while (k < n) { p = p * k; k = k + 1; }

Which is a loop invariant (true at every loop-head and at exit)?

• (A) p = n^k
• (B) p = (k - 1)!
• (C) p = k!
• (D) p = (n-1)!
• (E) p = 2^(k-1)

Answer: B. Initially k = 1, p = 1 = 0! = (k-1)!. After each iteration k becomes k+1 and p is multiplied by the old k, preserving p = (k_new - 1)!.

Q7: Random number guessing in [1, 200]

Mary plays yes/no 20-questions on a number from 1 to 200, adversary always tells the truth. Worst-case optimal number of questions?

• (A) 199
• (B) 99
• (C) 32
• (D) 16
• (E) 8

Answer: E (8). Binary search the range: ceil(log2(200)) = 8.

Q8: BNF grammar derivations

Given the grammar (word starts with a letter, then optional pairlet of pairs of letters OR pairdg of pairs of digits), which strings can be derived?

• (A) pairlet — derivable: p + airlet (6 letters = 3 pairs). Yes.
• (B) pairlets — 8 letters: p + 7 letters. 7 is odd, can't form pairlet. No.
• (C) 70words — starts with a digit. word must start with a letter. No.
• (D) w70 — w + 2 digits = letter + pairdg. Yes.
• (E) words70 — w + ords (4 letters, 2 pairs) but then 70 (2 digits) follows. The grammar allows letter pairlet OR letter pairdg, NOT mixed. ords70 is not a valid suffix. No.

Answer: A, D. (Some OA versions also accept E if the grammar is interpreted with concatenation; the conservative answer is A, D.)

Q9: Stack initialization

Push: i := i + 1; S[i] := x
Pop: x := S[i]; i := i - 1

Stack array S[1..N]. Which initializes i correctly?

• (A) i := N
• (B) i := N - 1
• (C) i := N + 1
• (D) i := 0
• (E) i := 1

Answer: D. Push increments i before writing, so the first push lands at S[1]. That requires i = 0 initially.

Q10: Concurrency with atomic statements

Task 0: Task 1:
 x = 1 y = 1
 a = x + y b = x - y

Each statement is atomic. x = y = 0 initially. Which must hold?

• (A) (a == 2) ⇒ (b == 0)
• (B) (a == 1) ⇒ (b == 0)
• (C) (b == -1) ⇒ (a == 2)
• (D) (b == 0) ⇒ (a == 2)
• (E) None of the above

Answer: B, C.

• B: a == 1 means Task 0 saw x + y = 1. Since Task 0 just wrote x = 1, that requires y = 0 at the read, so Task 1 had not yet executed y = 1. Task 1 will then later read x = 1, y = 1, giving b = 0.
• C: b == -1 means Task 1 read x = 0, y = 1, so it executed both statements before Task 0's x = 1. Task 0 then reads x = 1, y = 1, so a = 2.
• A is false: a == 2 is consistent with Task 1 running y = 1 before Task 0's read and x = 1 after; b could equal -1.
• D is false: b == 0 is consistent with a == 1 from rule B above.

Q11: Adjacent pixels gray-level pairs

A 10-level (0..9) gray pixel pair (p, q) is legal if |p - q| ≤ 2. How many of the 100 ordered pairs are legal?

• (A) 10
• (B) 20
• (C) 34
• (D) 44
• (E) 90

Answer: D (44). For each p, the count of legal q values within ±2 is:

• p = 0 or 9: 3 choices
• p = 1 or 8: 4 choices
• p = 2..7 (six values): 5 choices each Total = 2·3 + 2·4 + 6·5 = 6 + 8 + 30 = 44.

Q12: Binary tree of height 6 — failure success probability

A full binary search tree of height 6 has 2⁷ - 1 = 127 nodes. Exactly one node fails (and all its descendants become unreachable); you randomly pick a target node. Probability that the failed node is not on the root→target path?

The probability of failure equals the average depth of a target node divided by 127. Sum of depths in a full tree of height 6 is Σ_{d=0}^{6} d · 2^d = 502. Expected probability of failure given uniform target = (1/127) · (502/127) ≈ 0.0312. Success ≈ 96.9%.

• (A) 90-100% — correct
• (B) 80-89.99%
• (C) 70-79.99%
• (D) 60-69.99%
• (E) 50-59.99%
• (F) less than 50%

Answer: A. ≈ 96.9% success.

Q13: Concurrent container thread safety

The concurrent_container shown uses one mutex around get, set, resize, but never destroy. Issues present?

• (A) Deadlock possible — No (single mutex).
• (B) Resource leak — No (destroy frees data).
• (C) Doesn't prevent multiple threads from accessing data — No (every method takes the lock).
• (D) Memory corruption — Yes: malloc(size) should be malloc(size * sizeof(int)); the buffer is size bytes but stores size ints.
• (E) Unaligned memory access — possible consequence of (D) on some platforms.
• (F) Doesn't handle invalid input — Yes: get returns -INT_MAX on out-of-range but only after entering the critical section and leaks the lock on the early return (no release before returning).
• (G) Integer overflow not protected — Yes: int N and size * sizeof(int) can overflow.
• (H) Correct and thread-safe — No.

Answer: D, F, G.

Q14: Timestamp-sorted container design

Insertion-only container of up to 10⁹ 32-bit-timestamped objects; iterate in sorted order occasionally; single-threaded. Acceptable worst-case designs?

• (A) Array, append + quicksort before iterate — quicksort is O(n log n) per iterate, append O(1). Acceptable.
• (B) Array, append + in-place merge sort after each insertion — O(n log n) per insert → totally O(n² log n). Not acceptable.
• (C) Array, keep sorted by inserting at correct position — O(n) per insert → O(n²) total. Not acceptable at 10⁹.
• (D) Balanced tree by timestamp — O(log n) per insert + O(n) iterate. Acceptable.
• (E) Linked list + merge sort before iterate — O(n log n) per iterate, O(1) insert. Acceptable.
• (F) Hashmap keyed by timestamp — iteration is not sorted unless re-sorted. Acceptable if you also sort on iterate (O(n log n) per iterate).
• (G) Preallocate array indexed by timestamp value (32-bit range = 4·10⁹ slots) — memory blowout for 10⁹ objects in 4·10⁹ slots is feasible (~16 GB), but worst-case iterate is O(2³²). Not acceptable.

Answer: A, D, E (F is borderline-acceptable).

Q15: Memory page record minimum bytes

Fields:

• Page status: 3 states → 2 bits.
• Page index: range [0, 364847] → log2(364848) = 19 bits.
• Access mode: 6 modes → 3 bits.
• Process ID: range [0, 37337] → log2(37338) = 16 bits.

Total = 2 + 19 + 3 + 16 = 40 bits = 5 bytes. With the "direct field access API as simple as possible" (byte-aligned fields, no bit-packing), each field rounds up to whole bytes: 1 + 3 + 1 + 2 = 7 bytes.

Answer: 7 bytes (under the byte-aligned interpretation; 5 bytes under bit-packed).

Q16: 7-drive RAID 0 fill-up time (Codility memory/throughput math)

Workload: 200000 writes/s; distribution 512B 20% / 1024B 30% / 4096B 40% / 16384B 10%. Average write size = 0.2·512 + 0.3·1024 + 0.4·4096 + 0.1·16384 = 102.4 + 307.2 + 1638.4 + 1638.4 = 3686.4 bytes. Aggregate write rate = 200000 · 3686.4 = 7.37 · 10⁸ bytes/s.

Total capacity = 7 · 513 GiB = 3591 GiB = 3855.5 · 10⁹ bytes. Target 86% = 3.315 · 10¹² bytes.

Time = 3.315e12 / 7.37e8 ≈ 4500 s ≈ 75 minutes.

Answer: ≈ 75 minutes.

Q17: DFS print order

dfs(node, target) prints node->value, marks visited = true, then recurses into right_child, parent, left_child (in that order, skipping visited or NULL nodes). Trace through the tree from dfs(node_11, target = 12).

Without the OCR'd diagram being fully legible, the print sequence depends on the exact tree shape. Typical Pure Storage answer pattern: nodes are visited in the order 11 → 5 (right child) → ... → 12, with the print list ending at 12.

{/* OCR-fragment: tree diagram for Q17 was unreadable; needs human review for the exact print order. */}

Answer: depends on the exact tree; typical correct answer prints all ancestors then siblings before reaching 12.

Q18: Alice's two-tier memory (LRU vs random)

Type A: 10 GB, 1 ms per read. Type Z: 1 TB, 100 ms per read. All 2048 objects stored in Z (size 512 MB each), copies of up to 20 objects fit in A (10 GB / 512 MB = 20).

• Naive random fill, 10 random reads: P(hit) = 20/2048 ≈ 0.00977. Avg time per object = 0.00977·1 + 0.99023·100 ≈ 99.033 ms. For 10 reads = 990.33 ms.
• Naive random + workload (50% recent / 50% random): recent reads hit Z (since A is random and stale), random reads hit A with prob 20/2048. Avg = 0.5·100 + 0.5·(0.00977·1 + 0.99023·100) ≈ 0.5·100 + 0.5·99.033 ≈ 99.517 ms.
• LRU strategy, best case (every recent re-read is in A): recent reads cost 1 ms, random reads cost ≈ 100 ms (cold miss). Avg = 0.5·1 + 0.5·100 = 50.5 ms.
• LRU worst case (random reads evict useful recent entries): essentially same as naive ≈ 99 ms.

Answers:

• Naive random, 10 reads → ≈ 990.330 ms total.
• Naive random with workload → ≈ 99.517 ms average.
• LRU best case → ≈ 50.500 ms.
• LRU worst case → ≈ 99.517 ms.

{/* OCR-fragment: original numbers in the OA may differ slightly (1024 vs 2048 objects, 10 GB vs 100 GB) due to redacted screenshots; verify on the platform. */}