Exam prep

Why does building a list of characters and joining them at the end give O(N) performance for string construction?

• ALists store characters in a compressed format, so joining them requires less memory.
• BJoining a list of characters uses a built‑in cache that makes the operation constant time.
• CAppending to a list and joining avoids repeated copying of the whole string each time a character is added.
• DAppending characters to a string automatically expands its capacity in O(1) amortized time.

What are the three main actions performed when building a frequency map with a hash map?

• ADelete old entries, rehash the table, and iterate over the values.
• BSort the keys, merge duplicate entries, and compute the total frequency.
• CStore a new key, look up an existing key, and update or initialize its count.
• DCreate a linked list for collisions, traverse it, and remove zero‑count keys.

In the two‑pointer palindrome check, why are the pointers moved forward or backward before comparing characters?

• ATo skip over any characters that are not alphanumeric.
• BTo ensure the pointers always point to the middle of the string.
• CTo align the pointers with the nearest vowel for case‑insensitive comparison.
• DTo synchronize the pointers so they move at the same speed.

How does the sliding‑window technique update the sum when moving the window one position to the right?

• ADivide the previous sum by the element leaving the window and add the new element.
• BRe‑calculate the sum of all elements in the new window from scratch.
• CMultiply the previous sum by the ratio of the new element to the old element.
• DSubtract the element leaving the window and add the new element entering the window.

What property of a predicate function allows binary search to be applied to find the first true value?

• AThe function returns numeric scores that can be compared with a threshold.
• BThe function is monotonic: once it returns true, it stays true for all larger indices.
• CThe function is periodic, repeating true and false values at regular intervals.
• DThe function evaluates in constant time regardless of input size.

Why should nodes be marked as visited when they are enqueued in BFS rather than when they are dequeued?

• AIt allows the algorithm to skip levels with no outgoing edges.
• BIt guarantees that the queue will always contain an even number of nodes.
• CIt ensures that nodes are processed in alphabetical order.
• DIt prevents the same node from being added to the queue multiple times.

In the recursive DFS for maximum binary‑tree depth, what value is returned when the current node is null?

• A-1, to offset the depth counted for leaf nodes.
• BZero, indicating no additional depth beyond this point.
• CInfinity, because a null node represents an undefined path.
• DThe current depth counter passed as a parameter.

How can a max‑heap be simulated using Python’s default min‑heap implementation?

• ABy storing each value as a tuple with a Boolean flag indicating max‑heap mode.
• BBy overriding the comparison operators of the heap class to reverse ordering.
• CBy inserting the negative of each value, so the smallest negative corresponds to the largest original value.
• DBy periodically calling a function that rebuilds the heap in descending order.