Time/Space Tradeoffs - Java

1. Which strategy provides the best time/space tradeoff for this workload?
   Answer: Compute only the $5$ requested values when needed and avoid retaining them afterward. When evaluating caching and memoization strategies, always match the solution to the actual workload — consider how many values are needed, how often each is reused, and how long the program runs. Here, the program receives exactly $5$ keys, uses each once, then terminates. Since no value is ever requested twice, there is zero reuse to exploit. The expensive value(k) computation must happen exactly $5$ times no matter what strategy you choose — that cost is unavoidable. The only question is whether you incur additional unnecessary computation or memory overhead. Computing each value on demand and discarding it (option B) pays exactly that minimum cost: $5$ computations, negligible memory, no wasted work. Option A is wasteful in both dimensions of the tradeoff: it precomputes all $1{,}000$ values, spending $995$ computations you never need, and allocates an array you barely use. Option C is a softer version of the same mistake — precomputing $500$ values still wastes up to $495$ computations with no benefit since each key is used only once. Option D (memoization) sounds sophisticated, but memoization only helps when the same key is requested multiple times during execution. With exactly $5$ distinct keys each used once, a memoization map adds HashMap overhead while providing zero cache hits — it's the right tool for the wrong job. The key study tip: caching pays off only when there is repeated access to the same data. When each item is accessed exactly once, any form of precomputation or retention is pure overhead. Always ask "how many times will this value actually be reused?" before choosing a caching strategy.
2. Which statement best describes materializing all transformed values in a second array?
   Answer: It uses $O(n^2)$ additional space but avoids repeating the expensive transformation on later reads. Whenever you see a question about storing computed results in a data structure, think about the classic space-time tradeoff: you spend memory to save computation time (or vice versa). "Materializing" values simply means computing them once and storing them for future use. Here, you have an $n \times n$ array, so materializing every transformed value into a second array requires storing exactly $n^2$ elements — that's $O(n^2)$ additional space. The payoff is that each of those 20 subsequent reads simply fetches the stored result instead of re-running the expensive transformation. This makes A correct: it accurately captures both the space cost and the time benefit. B is wrong because it confuses a streaming or sliding-window strategy (where you process one row at a time and discard the rest) with full materialization. Storing the entire second array at once is definitively $O(n^2)$, not $O(n)$. C is wrong in two ways. First, $O(1)$ space would mean storing almost nothing, which contradicts filling a second array. Second, the word "deterministic" here is a red herring — yes, determinism means the same input always yields the same output, but that's precisely why caching is valid, not why you can skip storage. Determinism justifies reuse; it doesn't eliminate the need to store anything. D gets the logic completely backwards. Reading a stored value 20 times costs nothing extra in transformation work — the whole point of materializing is that the transformation runs once, not 20 times. As a study tip: when a question mentions an expensive operation paired with repeated access, immediately think "cache/materialize = pay space, save time."
3. Which change best uses additional space to improve the dominant operation?
   Answer: Maintain a HashMap from email to record and update both structures when customers are added. When a program performs millions of lookups but only rare insertions, you should immediately ask: what data structure gives O(1) average lookup while keeping my existing structure intact? This is the classic time-space tradeoff — spend a little extra memory to dramatically cut runtime. A HashMap keyed by email address delivers exactly that. Searching by email becomes an $O(1)$ average operation instead of $O(n)$ linear scanning, and the original list stays untouched for ordered reporting. When a new customer is added (rarely), you update both structures — a trivial cost given the insert rate. This makes D the correct answer: it targets the dominant operation (search), uses extra space wisely, and preserves existing functionality. A is wrong because discarding the original records and storing only hash codes destroys the data you need — you'd have nothing meaningful to reconstruct records from, and you'd lose the ordered list entirely. B caches only the last result, so it helps only if the same email is queried back-to-back. With millions of diverse searches, this cache hits almost never and provides no real improvement. C is the worst option: sorting before every search turns a problem you could solve in $O(1)$ into one that costs $O(n \log n)$ per query — far worse than the original linear scan. Strategy tip: On data-structure questions, always match the structure to the dominant operation. If you're searching by a unique key millions of times, a HashMap is almost always the right tool — and maintaining parallel structures for different access patterns is a standard, real-world design.
4. Which approach correctly explains the relevant time/space tradeoff?
   Answer: Buffer all numbers, compute the final mean, and then scan the buffer to select the closest number. When a problem requires you to compare each data point against a value that isn't known until all data has been seen — like an arithmetic mean — you must ask yourself: "Can I compute the comparison criterion before I've finished reading the data?" If not, you either need to store the data or accept an approximation. Here, the exact mean $\bar{x} = \frac{1}{n}\sum_{i=1}^n x_i$ is only finalized after the last number arrives. To find which number is closest to that mean, you need to revisit every value and compute $|x_i - \bar{x}|$. Since the stream is non-resettable, you cannot re-read it. The only correct solution is B: buffer all $n$ numbers in memory, compute the final mean once streaming ends, then scan the buffer to find the closest value. This trades space — $O(n)$ memory — for the ability to perform a necessary second pass. A is tempting but wrong. A running mean updates correctly, but the closest number to the final mean cannot be determined mid-stream — earlier values might end up closer than anything seen so far, and you've already discarded them. C is a flawed greedy assumption. A value below the current running mean could be very close to the final mean if later large values pull the mean downward. You cannot safely discard anything. D conflates "last compared" with "closest." The final number examined has no special claim to being nearest the mean. Study tip: Whenever a selection criterion depends on a global property (like the mean) computed from the full dataset, treat any single-pass, constant-space approach with suspicion — it likely sacrifices correctness for efficiency.
5. Compared with computing every result without caching, what is the most likely effect of this cache after the first cycle?
   Answer: It adds memory overhead but provides essentially no hits because results are evicted before reuse. When you see a caching question, the key insight is to compare the cache size against the working set size — how many distinct keys cycle through before a key repeats. Here, 200 distinct keys cycle in fixed order, but the LRU cache holds only 100 entries. Think through what happens: after the cache fills with keys K1–K100, the next request K101 evicts K1. By the time K1 repeats (200 requests later), it has long since been evicted. In fact, every key gets pushed out before its turn comes around again. The cache never delivers a single hit after the warm-up period — you pay the memory cost of maintaining 100 cached results while gaining nothing in computation savings. That makes B correct: the cache adds overhead but produces essentially zero hits. A is wrong because it assumes results stay cached until their key repeats. That would require a cache large enough to hold all 200 keys. With only 100 slots and 200 rotating keys, no result survives long enough to be reused. C is wrong on two counts: LRU evicts the least recently used entry, not the least frequently used, and in a strict round-robin pattern every key has identical frequency. There's no "most frequent" subset for LRU to favor, so neither computation nor memory is saved. D is wrong because holding half the keys doesn't mean half the requests hit. A hit only occurs if the specific key being requested right now is cached — and as shown above, that never happens in this cycling pattern. Study tip: Always compare cache capacity to working set size. If the working set exceeds cache capacity in a sequential or round-robin pattern, assume a near-zero hit rate regardless of cache algorithm.
6. Which statement most accurately compares the two strategies?
   Answer: Strategy Y uses $O(V^2)$ stored distance space but can answer each later query in $O(1)$ time. When comparing query strategies on graphs, you need to think about the space-time tradeoff: preprocessing costs memory but speeds up future queries, while on-demand computation saves space but pays time per query. Strategy Y runs BFS from every one of the $V$ vertices, storing the shortest distance from each source to every destination. That produces a $V \times V$ distance table, which is $O(V^2)$ space. Once that table is built, any query is just a single array lookup — $O(1)$ time. This is exactly what A describes, making it the correct answer. B is tempting but wrong. "Always less total time" is an overstatement. If you only need to answer a handful of queries, Strategy X (one BFS per query at $O(V + E)$ each) may be far cheaper than preprocessing all $V$ sources. Strategy Y only wins on total time when the number of queries is large enough to justify the upfront cost. C is factually incorrect. BFS absolutely uses extra space — it requires a queue and a visited array, both of which are $O(V)$. Strategy X isn't "space-free"; it just doesn't persist data between queries. D confuses equal-weight edges with instant lookup. Equal weights mean BFS correctly finds shortest paths (no need for Dijkstra), but BFS still runs in $O(V + E)$ per query. Equal weights do not make the answer retrievable in $O(1)$. Study tip: On tradeoff questions, always ask yourself: how many queries are expected? That determines whether preprocessing is worth the cost.
7. Which conclusion is best supported for this workload?
   Answer: The hash set should use less memory because storage scales with the number of active IDs, not the full range. When comparing data structures, memory analysis requires you to think about two separate dimensions: the range of possible values and the count of actual values stored. These can diverge dramatically, and that gap is the key to this question. A bit vector covering IDs from $0$ to $999{,}999{,}999$ must allocate one bit per possible ID, regardless of how many are active. That's $10^9$ bits, or roughly $125$ MB — just to represent the full range. A HashSet<Integer>, by contrast, only allocates memory proportional to what it actually stores. With $1{,}000$ active IDs, even accounting for boxed Integer objects (roughly 16 bytes each) plus hash table overhead, you're looking at well under $100$ KB. The hash set wins decisively because its storage scales with active count, not the value range — making D correct. A is tempting but misidentifies the winner. Yes, each possible ID costs only one bit in the vector, but you pay that cost for all $10^9$ possible IDs, not just the $1{,}000$ active ones. The per-element cost is low; the total cost is enormous. B correctly identifies that boxed Integer objects carry overhead, but draws the wrong conclusion. That overhead is real yet modest at $1{,}000$ entries — nowhere near the $125$ MB the bit vector requires. C confuses time complexity with space complexity. Both structures support $O(1)$ lookups, but that says nothing about memory usage. As a study tip: whenever a question involves a sparse dataset over a large range, immediately ask yourself whether the structure scales with range or with active count — that distinction usually decides the answer.
8. Assuming both methods use ordinary fixed-width numeric values, which comparison is correct?
   Answer: Both take $O(n)$ time, but Method Y uses $O(1)$ extra space instead of $O(n)$. When analyzing algorithm complexity, always evaluate time and space separately — they can differ dramatically even when two methods solve the same problem. Method X (memoized recursion) visits each subproblem $F(0)$ through $F(n)$ exactly once, giving $O(n)$ time. However, it stores every computed result in a memo table, which requires $O(n)$ extra space. Method Y (iterative) also computes each value once in a single loop — still $O(n)$ time — but discards old results immediately, keeping only the two most recent values. That's a fixed amount of memory regardless of $n$, which is $O(1)$ extra space. This makes A correct: equal time complexity, but a meaningful space advantage for Method Y. B is wrong because memoization doesn't reduce time complexity to $O(\log n)$ — it ensures each subproblem is solved once, not that the number of subproblems shrinks logarithmically. You still need to compute all $n+1$ values. C is wrong because having two dependencies doesn't multiply the cost. Method Y computes each new value with a single addition step, regardless of how many predecessors it has. The loop runs $n$ times: that's $O(n)$, not $O(n^2)$. D is wrong because it incorrectly assumes both methods need $O(n)$ space. Method Y proves that's unnecessary — you only need the previous two values at any moment. Study tip: When comparing algorithms, always ask separately — how many steps? and how much memory? — because optimizing one doesn't automatically optimize the other.
9. Which approach most directly trades additional space for faster expected running time?
   Answer: Insert elements into a HashSet, using proportional space and expected $O(n)$ time. When a question asks about trading space for speed, you should immediately think about hash-based data structures — they're the classic tool for achieving faster lookup by accepting extra memory overhead. Here's the core idea: a HashSet stores elements in a hash table, so checking whether an element already exists takes expected $O(1)$ time. As you iterate through the array once and attempt to insert each element, if add() returns false, a duplicate exists. You touch each element exactly once, giving you expected $O(n)$ total time — while using $O(n)$ extra space for the set. This is precisely the space-for-time tradeoff the question describes, making C the correct answer. The distractors each represent different tradeoffs. A uses essentially no extra space (constant), but the nested-loop comparison of every pair costs $O(n^2)$ time — the opposite of trading space for speed. B gets closer: copying the array uses $O(n)$ space and sorting brings the time down to $O(n \log n)$, which is better than $O(n^2)$ but still worse than the expected $O(n)$ of the hash approach. It also requires the extra copy step to avoid modifying the original array. D sounds attractive — $O(n)$ time and constant space — but scanning adjacent elements only catches duplicates in a pre-sorted array. On an unsorted array, it simply doesn't work. As a study tip, remember this pattern: **sorting → $O(n \log n)$, hashing → expected $O(n)$**. Whenever a question mentions "expected time" and "proportional extra space," that's a strong signal that hashing is the intended answer.
10. Which algorithm best satisfies both requirements?
    Answer: Heap sort, because it has worst-case time $O(n\log n)$ and constant auxiliary array space. When a question gives you two constraints simultaneously — time complexity and space complexity — your job is to find the algorithm that satisfies both, not just one. Here, you need $O(n \log n)$ worst-case time and $O(1)$ auxiliary space (no extra array proportional to input size). Heap sort is the only classical algorithm that delivers both. It builds a max-heap in-place in $O(n)$ time, then repeatedly extracts the maximum, maintaining $O(n \log n)$ worst-case time overall. Critically, it rearranges elements within the original array, requiring only $O(1)$ extra space. That makes C the correct answer. A is tempting because merge sort genuinely achieves $O(n \log n)$ worst-case — but it requires an $O(n)$ auxiliary array to merge the two halves. The question explicitly forbids this, so merge sort fails the space requirement. B is a classic trap. Java's built-in sort uses quicksort for primitives, and quicksort is in-place in practice. However, its worst-case time degrades to $O(n^2)$, which directly violates the time requirement stated in the problem. The question says worst-case $O(n \log n)$ is mandatory. D falls apart immediately: counting sort is not comparison-based and requires auxiliary storage proportional to the value range, not the input size. That violates the space constraint, and it isn't even $O(n \log n)$ — it's $O(n + k)$. Study tip: Memorize the "big three" comparison sorts — merge sort ($O(n \log n)$ time, $O(n)$ space), quicksort ($O(n \log n)$ average, $O(n^2)$ worst), and heap sort ($O(n \log n)$ worst, $O(1)$ space). Exam questions often test whether you know the tradeoffs between all three simultaneously.

Start this quiz