Algorithmic Complexity & Code-Level Optimization Questions

Direct answer
Convert cycles to joules directly (cycles times joules-per-cycle), convert the battery's mAh-and-voltage rating to joules (amp-hours times volts times 3600 seconds/hour), then divide. For this specific input, the compute burst consumes about $7.5\times10^{-5}\%$ of the battery, which is negligible in isolation. That is the real point of the exercise: a single billion-cycle burst almost never matters for battery life on its own, what matters is how often it repeats, plus everything else on the device (radio, screen) that usually dwarfs a single CPU burst.

Structured elaboration
Energy consumed by the computation:

$E_{compute} = N_{cycles} \times E_{cycle} = 10^9 \times 3\times10^{-11}\text{ J} = 0.03\text{ J}$

Energy available in the battery, converting amp-hours and volts to joules via $1\text{ Ah} = 3600\text{ C}$ and $E = Q \times V$:

$E_{battery} = 3.0\text{ Ah} \times 3.7\text{ V} \times 3600\ \tfrac{\text{s}}{\text{h}} = 39{,}960\text{ J} \;(\approx 11.1\text{ Wh})$

Fraction of battery consumed:

$\%\text{consumed} = \frac{E_{compute}}{E_{battery}} \times 100 = \frac{0.03}{39{,}960}\times100 \approx 7.51\times10^{-5}\%$

The step that makes the repeat-rate question answerable: how long does one burst take? Energy per cycle says nothing about time, so add the one missing quantity, the clock. At a 2.5 GHz core:

$t_{burst} = \frac{10^9\text{ cycles}}{2.5\times10^9\text{ cycles/s}} = 0.4\text{ s}$

That single number bounds everything that follows. One core can start this computation at most $1/0.4 = 2.5$ times per second, so any proposed repetition rate above 2.5 per second per core is not a heavier workload, it is an impossible one. It is worth checking a proposed duty cycle against this before computing its energy, because a rate that exceeds the core's throughput produces a perfectly correct-looking energy number for a scenario that cannot occur.

Assumptions made explicit: $3\times10^{-11}$ J/cycle is treated as an already-averaged, workload-representative figure, when in reality per-cycle energy varies a lot with the DVFS (dynamic voltage and frequency scaling) state, which core cluster (performance versus efficiency) is active, and instruction mix, so a single constant is a simplification, not a measurement of this exact workload. A quick sanity check on it: $3\times10^{-11}\text{ J/cycle} \times 2.5\times10^{9}\text{ cycles/s} = 0.075\text{ W}$ of sustained core power, which is an efficiency-core figure; a performance core under sustained load is around an order of magnitude higher, so if this work lands on the big cluster every percentage below scales up with it. The calculation also ignores DVFS transition overhead and other components drawing power during the burst (memory controller, caches), and treats 3.7 V as the battery's nominal average voltage rather than its true instantaneous voltage, which drifts as a Li-ion cell discharges.

Worked example
The arithmetic above is the worked example. To show why the headline number is deceptively small, extend it to a sustained workload, using the 0.4 s burst time to keep the scenario physically possible. A core doing nothing but this computation back to back runs $86{,}400 / 0.4 = 216{,}000$ bursts in 24 hours:

$E_{total} = 216{,}000 \times 0.03\text{ J} = 6{,}480\text{ J}$

$\%\text{consumed (one core saturated, 24 h)} = \frac{6{,}480}{39{,}960}\times100 \approx 16.2\%$

The same per-event cost at lower, more realistic duty cycles:

The exact same per-event energy cost is irrelevant as a one-shot number and material as a sustained workload: the repetition rate, not the per-event cost, is what actually decides whether this matters for battery life. It is also worth noticing that even the saturated-core row, a full day of one core doing nothing else, costs only about a sixth of the battery at the assumed per-cycle energy, which is the sanity check that the assumed $3\times10^{-11}$ J/cycle describes a small, efficient core rather than a peak-performance one.

Trade-offs & pitfalls
Reporting only the single-shot percentage (as the headline framing invites) massively understates real-world impact for anything that runs repeatedly, so an energy-optimization decision needs the duty cycle, not just the per-operation cost. Equally, a duty cycle quoted without checking it against the burst's wall-clock time can describe work the hardware cannot physically perform, which is the mirror-image error and just as easy to make. A workload can also look cheap in cycles yet still be expensive in energy if it forces a higher DVFS state (waking the performance cluster) or keeps the radio or GPS active longer than the compute itself takes, both of which this simple per-cycle model does not capture at all.

Direct answer

LRU (least recently used) evicts whichever entry was accessed longest ago; LFU (least frequently used) evicts whichever entry has been accessed the fewest times overall. Both support O(1) average-case get and put with the standard implementation, a hash map plus a doubly linked list for LRU, or a hash map plus frequency buckets for LFU, so the real difference for session objects is not raw speed, it is which access PATTERN each one handles well or badly.

Structured elaboration

• LRU complexity: O(1) average for get and put, using a hash map (key to node) plus a doubly linked list ordered by recency; on access, unlink and re-insert the node at the front, an O(1) pointer operation.
• LFU complexity: O(1) average using the classic hash-map-of-frequency-buckets design, a hash map from key to node, a hash map from frequency count to a doubly linked list of keys at that frequency, and tracking the current minimum frequency. Each access moves a node to the next frequency bucket, O(1), but with meaningfully more bookkeeping per access than LRU.
• How a full scan hurts each: a single sequential scan of many session objects that will never be touched again, such as a batch audit job iterating every session, is the classic LRU-killer: each scanned key becomes most-recently-used and evicts genuinely hot session data, tanking hit rate right after the scan. LFU is naturally immune to this specific failure mode, since a one-time scan gives every scanned key a frequency of only 1, which will not outrank sessions already at high frequency.
• How a traffic spike hurts each: LFU has the opposite weakness, it is slow to adapt to a session that suddenly becomes hot, for example one tied to a viral shared link, since it starts at frequency 1 and must earn enough accesses to outrank long-lived, previously-popular sessions before LFU protects it. LRU adapts instantly, since one access makes the session most-recently-used and safe from the next eviction regardless of history.
• A hybrid: a common production compromise tracks both recency and frequency, for example a two-tier cache where a first access goes into a small probationary LRU segment and only gets promoted to a larger protected segment after a second access within some time window, resisting a one-time scan (a single-access key never leaves probation, so it cannot evict protected data) while still adapting quickly to genuinely new hot keys (promoted after just their second access, not after accumulating a high absolute frequency).

Worked example

A cache with room for 10,000 session objects, sitting in front of a store that holds 1,000,000 sessions, and a nightly audit job that reads every one of those 1,000,000 sessions once. The size relationship is the whole point: the scan set is 100 times the cache's capacity. A scan that only re-read the 10,000 sessions already resident would evict nothing at all under LRU, it would just permute the recency order, and under LFU it would add 1 to every resident key and leave the ranking unchanged. The damage comes from the 990,000 keys that were never in the cache.
Under plain LRU, each of those audit reads is a miss, and a miss gets ADMITTED at the most-recently-used end. After the first 10,000 misses the cache has already evicted every genuinely hot session, and it spends the rest of the scan churning through rows that will never be read again. Real traffic then resumes against a cache whose hit rate is near zero and has to refill it from scratch, a measurable dip after every nightly audit.
Under plain LFU, each of those 990,000 newly admitted keys enters at frequency 1 while the genuinely hot sessions already sit at much higher counts, so the audit rows become eviction candidates almost as fast as they arrive and the hot set survives the scan intact. Note the asymmetry that makes this a trade rather than a free win: the same frequency-1 entry point is exactly what makes LFU slow to protect a brand-new session that is about to become hot.

Trade-offs and pitfalls

LFU's extra bookkeeping, frequency buckets and minimum-frequency tracking, is a real, if modest, implementation and memory cost over LRU's simpler linked-list design, and LFU needs an aging or decay mechanism in practice, otherwise a key that was extremely popular last month but is now cold can sit protected by its accumulated historical frequency long after it stopped mattering, a failure mode LRU does not have. Choosing purely on this trade-off without measuring the actual access pattern, how common full scans versus sudden spikes are in the real workload, is a common mistake; the hybrid approach exists precisely because most real workloads mix both failure modes.

Direct answer

Quickselect finds the kth largest element in average O(n) time by reusing quicksort's partitioning step, but only ever recursing into the ONE side of the partition that contains the answer, instead of both sides like quicksort does. Its PARTITIONING is O(1) extra space (a handful of index variables, all swaps done within the array), which is the property the question is asking about; whether the function as a whole is O(1) space then depends on one API decision, whether it sorts the caller's list in place or works on a copy, and that decision is made explicit below rather than left implied.

Structured elaboration

The core idea: pick a pivot, partition the array around it (everything less than the pivot ends up to its left, everything greater or equal ends up to its right, matching quicksort's Lomuto or Hoare partition scheme), and check where the pivot landed relative to the index you're looking for. If the pivot landed exactly at the target index, you're done. If the target index is to the left of the pivot's final position, recurse only into the left partition; if it's to the right, recurse only into the right partition. Because you discard the other half of the array entirely at each step instead of processing both halves, the expected total work follows the same geometric-series shrinking as quicksort's average case, giving expected time $T(n) = T(n/2) + O(n) = O(n)$ rather than quicksort's $O(n \log n)$, because there's no second recursive branch to sum in. The in-place partitioning (swapping elements within the same array, using only a few index variables) is what keeps the SEARCH's extra space at O(1): no auxiliary array is needed to partition, and writing the loop iteratively rather than recursively keeps the call stack at O(1) too, where a recursive quickselect would add O(log n) expected stack frames. Be precise about what that does and does not cover, because it is the easiest claim in this problem to overstate: the implementation below deliberately begins with arr = nums[:], a full O(n) copy, so that it does not scramble the caller's list. That copy makes the FUNCTION O(n) extra space even though the ALGORITHM is O(1). Truly O(1) total extra space requires permuting the caller's array in place and documenting that side effect, which is a one-line change (drop the copy and use nums directly) and is the right call when the caller owns a throwaway buffer; the copy is the right call when the caller's ordering is load-bearing. State which one you chose, do not claim both.

Worst case is still $O(n^2)$, exactly like quicksort, if the pivot choice is consistently bad (e.g., always picking the smallest or largest remaining element on an already-sorted or adversarially-ordered input with a naive pivot rule); choosing the pivot uniformly at random, as below, makes that worst case exponentially unlikely rather than eliminating it, which is the standard practical mitigation (a deterministic median-of-medians pivot selection guarantees worst-case O(n) instead, at a larger constant factor, and is rarely needed in interview-level implementations).

Behavior for invalid k and duplicates, stated explicitly: k is defined as 1-indexed from the largest (k=1 means the single largest element), and any k outside [1, len(nums)] is a usage error that should raise rather than silently return a wrong answer. Duplicate values are handled correctly by the partition scheme without special-casing: if the target value appears multiple times, the algorithm still converges on a single correct index in the sorted-order sense (the kth position when ties are broken arbitrarily among equal values), because partitioning only compares against the pivot's value, never against object identity.

Worked example

import random

def quickselect_kth_largest(nums, k):
    """Return the kth largest element (k=1 -> largest).

    Time: O(n) average, O(n^2) worst case.
    Space: O(1) for the selection itself; O(n) overall because of the defensive
    ``arr = nums[:]`` copy below, which leaves the caller's list unmodified.
    Drop the copy and partition ``nums`` directly for true O(1) extra space,
    at the cost of permuting the caller's list.
    """
    if not nums:
        raise ValueError("nums must be non-empty")
    if k < 1 or k > len(nums):
        raise ValueError(f"k={k} out of range for array of length {len(nums)}")

    target_index = len(nums) - k  # index of the kth largest in ascending sorted order
    arr = nums[:]  # O(n) copy: preserves the caller's list. Use `arr = nums` for O(1) space.
    lo, hi = 0, len(arr) - 1

    while lo < hi:
        pivot_index = random.randint(lo, hi)
        arr[pivot_index], arr[hi] = arr[hi], arr[pivot_index]
        pivot = arr[hi]
        store = lo
        for i in range(lo, hi):
            if arr[i] < pivot:
                arr[i], arr[store] = arr[store], arr[i]
                store += 1
        arr[store], arr[hi] = arr[hi], arr[store]

        if store == target_index:
            return arr[store]
        elif store < target_index:
            lo = store + 1
        else:
            hi = store - 1

    return arr[lo]


random.seed(42)
print(quickselect_kth_largest([3, 2, 1, 5, 6, 4], 2))              # 5
print(quickselect_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4))     # 4
print(quickselect_kth_largest([5, 5, 5, 5], 3))                    # 5, duplicates handled
try:
    quickselect_kth_largest([1, 2, 3], 5)
except ValueError as e:
    print("invalid k:", e)

Running this prints:

5
4
5
invalid k: k=5 out of range for array of length 3

each matched against sorted(nums, reverse=True)[k-1] as an independent check during development, confirming correctness on both distinct and duplicate-heavy inputs.

Trade-offs and pitfalls

Using a fixed pivot choice (always the first or last element) instead of a random one turns an already-sorted or reverse-sorted input into the O(n^2) worst case deterministically, which is exactly the input shape an adversary or a careless test generator is most likely to produce, so randomizing pivot selection is not a cosmetic detail. A second pitfall is the space claim itself: it is very easy to say "quickselect is O(1) extra space" and then ship a function that opens with a full copy of the input, which is O(n). Those are two different claims about two different things (the algorithm versus this function), and an interviewer will ask which one you meant. Mutating the caller's original list in place without documenting it is the mirror-image mistake, since quickselect's partitioning permanently reorders the array as a side effect; the version above copies first and says so, trading the O(1) space guarantee for a non-surprising API, and either choice is defensible as long as it is stated. Finally, quickselect only finds the kth element, it does not leave the array fully sorted, so if a caller actually needs a sorted prefix or suffix (not just one position), a full sort is the right tool despite quickselect's better asymptotic complexity for the single-element query.

Direct answer

In array-of-structures (AoS), each record (a struct with several fields) is stored contiguously, one after another, so an array of particles looks like [x0,y0,z0,vx0,vy0,vz0, x1,y1,z1,...]. In structure-of-arrays (SoA), each field gets its own contiguous array: all x-values together, all y-values together, and so on. For a tight loop touching millions of small structs per second, SoA usually wins on memory bandwidth, cache utilization, and vectorization, because most hot loops only touch one or two fields per pass, and SoA lets the CPU fetch exactly the data it needs.

Structured elaboration

• Memory bandwidth and cache utilization: a CPU cache line is typically 64 bytes. A Particle struct with 6 float32 fields (x, y, z, vx, vy, vz) is 24 bytes, so AoS packs about 2.7 structs per cache line. If a loop only needs x, every cache-line fetch also pulls in five unused fields per struct: roughly 4 useful bytes out of every 24 fetched (about 17% bandwidth efficiency). In SoA, a 64-byte cache line holds 16 contiguous x-values, all useful for an x-only loop: essentially 100% bandwidth efficiency.
• Vectorization (single instruction, multiple data, or SIMD): a 256-bit AVX2 register holds eight float32 values, but only if they are contiguous in memory. In SoA, x[0..7] are contiguous, so the compiler can issue one vector load-and-add over eight values at once. In AoS the eight x-values sit 24 bytes apart (a strided access), so the compiler must either emit a gather, or reassemble a vector with shuffle/permute instructions, or give up and go scalar.
• The precondition everyone forgets, and the one that decides whether any of the above happens at all: the compiler has to be ALLOWED to vectorize. Contiguity is necessary and not sufficient. If the loop is a floating-point REDUCTION (summing x over every particle), vectorizing it means adding the values in a different order, and IEEE 754 addition is not associative, so a conforming compiler must refuse by default no matter how perfect the layout is. You unlock it by granting reassociation explicitly (-ffast-math, -fassociative-math, #pragma omp simd reduction(+:s), or by hand-splitting the accumulator into several independent partial sums). A loop with no cross-iteration dependency (out[i] = a[i] * b[i]) has no such barrier and vectorizes on layout alone. Check which of the two you have before predicting a speedup.
• Why AoS is still sometimes the right choice: if the hot loop touches ALL fields of one record together (e.g. "advance this particle's position from its velocity" for one particle at a time, with no cross-particle vectorization), AoS keeps everything for that record in one or two cache lines and is simpler to reason about and to pass around as a single unit. SoA only wins when the loop is field-major (one field across many records), not record-major (all fields of one record).

Worked example

Summing the x-coordinates of 1,000,000 particles, each with 6 float32 fields. The bytes part of this is settled by arithmetic; the instruction part is settled by what the compiler actually emits, so it was compiled and read rather than assumed.

• Bytes fetched: AoS makes the loop touch all 24,000,000 bytes of the struct array even though only 4,000,000 bytes of it (the x values) are needed, because x is interleaved with the other five fields. SoA touches exactly 4,000,000 bytes, all useful. That is a 6x cut in bytes fetched, and it does not depend on any compiler decision.
• Instructions, IF the compiler is allowed to reassociate: 1,000,000 float adds become 1,000,000 / 8 = 125,000 vaddps instructions on 256-bit AVX2, an 8x cut in instruction count on top of the 6x cut in bytes.
• Instructions as actually emitted at plain -O2: neither layout vectorizes. MEASURED with clang at -O2 (default, IEEE-conforming): targeting x86-64 with -mavx2, the SoA sum compiles to a chain of vaddss (scalar single, one float per instruction) into a single accumulator, with no vaddps and no ymm register anywhere in the loop; on arm64 the same loop unrolls 16 wide but still emits sixteen scalar fadd s0, s0, sN into one serial chain. The AoS sum gets the same scalar treatment. Measured wall clock for 200 passes over the million elements, across four runs: AoS 128.7 to 129.7 ms against SoA 105.8 to 111.7 ms, a ratio between 1.15x and 1.22x. At -O2 the loop is bound by the latency of one serial floating-point add chain, not by memory bandwidth, so the layout barely shows up at all.
• The same code at -O2 -ffast-math, which grants the reassociation: SoA now compiles to vaddps on ymm registers (x86-64 AVX2) and fadd.4s (arm64 NEON), and the measured times become AoS 46.5 to 50.5 ms against SoA 8.1 to 8.5 ms, a ratio between 5.7x and 5.9x over the same four runs. That 5.8x, not the 48x you get from naively multiplying 6x by 8x, is what the layout is worth here, because the two effects are not independent: once the SoA loop is vectorized it becomes bandwidth-bound, and bandwidth is the thing the 6x already counted.
• One more thing the emitted code corrects: at -ffast-math the AoS loop does NOT fall back to scalar. On arm64 it also vectorizes to fadd.4s, and on x86-64 AVX2 it vectorizes with vmovups plus vblendps and vpermpd, reassembling each vector of eight x-values out of the interleaved layout with shuffles. AoS loses by 5.8x because it moves 6x the bytes and spends extra instructions un-interleaving them, not because vectorization was refused.

The takeaway to state in an interview: the bytes ratio is a property of the layout, the instruction ratio is a property of the layout AND the compiler flags, and the speedup is neither of them multiplied together. Quote the one you measured.

Trade-offs and pitfalls

SoA is harder to refactor when a "particle" needs to be created, deleted, or passed around as one unit, since you now update N parallel arrays instead of one struct, and it can hurt when the real access pattern is record-major, where chasing N separate arrays for one entity's fields can itself cost cache locality. A common middle ground is array-of-structures-of-arrays (AoSoA): group records into small batches (say 8 or 16), store each batch in SoA layout, and iterate batch by batch, getting good vectorization within a batch and good locality when a handful of fields for one entity are needed together.

Direct answer

At $\alpha = 0.05$ (the significance threshold: the largest probability of a false alarm,
concluding there is a real difference when there actually isn't one, that we're willing to
accept), this A/B sample does not show statistically significant evidence that Server B is
faster: the observed 2ms difference has a t-statistic of about 1.81 (a t-statistic measures
how many standard errors the observed gap sits away from zero; a value close to zero looks
like ordinary noise) on about 95 degrees of freedom (a parameter, driven here by the sample
sizes and variances, used to pick the right threshold for this test), below the roughly 1.99
critical value (the threshold the t-statistic would need to exceed, in either direction, to
count as significant at this alpha), and the 95% confidence interval for the difference (a
range that, if you repeated this experiment many times, would contain the true average
difference about 95% of the time) includes zero.

Structured elaboration

A t-test is a standard way to check whether the gap between two group averages is larger
than you would expect from ordinary sampling noise alone, given how much the underlying data
varies. Because the two samples here have different standard deviations (5ms versus 6ms), use
Welch's t-test rather than the pooled-variance (Student's) t-test, which assumes equal
variances. Welch's test does not require that assumption and is the safer default
whenever sample variances differ, which they do here.

Degrees of freedom use the Welch-Satterthwaite approximation (a correction that accounts for
the two groups having different variances) rather than the simple
$n_A + n_B - 2$:

The 95% confidence interval for the mean difference uses the same standard error and
the critical value from the $t$ distribution at that degrees of freedom:

Required sample size per group to detect a difference $\Delta$ with significance level
$\alpha$ and power $1-\beta$ (power is the probability the test correctly detects a real
difference of size $\Delta$, if one truly exists; 0.8 means an 80% chance of catching a
real effect instead of missing it), given an assumed pooled standard deviation $\sigma$:

Worked example

$SE$ above is the standard error: an estimate of how much the difference between the two
sample means would bounce around if this experiment were repeated many times.

With $df \approx 95$, the two-sided critical value at $\alpha = 0.05$ is
$t_{crit} \approx 1.985$, and since $|t| = 1.81 < 1.985$, we fail to reject the null
hypothesis (the default assumption of no real difference between the two servers' mean
latency, which we only abandon if the data gives strong enough evidence against it) that the
two servers have equal mean latency; this corresponds to a p-value of about 0.07 (the
probability of seeing a gap at least this large purely by chance if the null hypothesis were
actually true). The 95% confidence interval for the difference is:

The interval spans zero, consistent with "not significant": Server B might be faster,
slower, or the same, and 50 samples per server was not enough to tell apart from noise.

One choice drives that verdict and it should be stated rather than assumed, because the
question asks a DIRECTIONAL thing ("is Server B faster") while the test above is
two-sided. A two-sided test splits the 5% false-alarm budget across both tails, so it
asks "are these two different" and needs $|t| > 1.985$. A one-sided test spends the
whole 5% on the "B is faster" tail, needs only $t > 1.661$ at the same degrees of
freedom, and on these exact numbers returns a one-sided p of about 0.037 against the
two-sided 0.073: the same data, the same alpha, and the opposite conclusion. I report it
as not significant because the direction was not fixed before the data was seen, and
switching to the one-sided test after noticing which way the gap fell is how a nominal 5%
false-alarm rate quietly becomes 10%. The defensible practice is to pre-register the
direction (and the sample size) before collecting, and to default to two-sided when you
did not. This is worth surfacing rather than burying, because a reviewer who assumed a
one-sided test would read this same table as a win.

For the required sample size to reliably detect a 1ms difference at 80% power
($z_{\alpha/2} = 1.96$, the cutoff value from the standard normal distribution for a
two-sided test at $\alpha = 0.05$; $z_\beta = 0.84$, the cutoff value corresponding to 80%
power; both are looked up from a standard normal table or quantile function, not derived
here, pooled $\sigma \approx 5.5$ms):

Round up to 475 samples per server (roughly 9-10x the current sample of 50), which
explains directly why the current experiment came back inconclusive: it was
underpowered for a difference this small.

Trade-offs & pitfalls

Latency distributions are typically right-skewed, not normal, and real interest is
often in a tail percentile (p95/p99) rather than the mean. This t-test framework is the
right first tool for a mean comparison, but the identical sample-size and rigor logic
applies to a percentile comparison too, for example an experiment framed as "did a
change improve p95 latency by 10%": there, a parametric t-test on the mean is the wrong
tool, and a bootstrap or permutation test on the percentile difference is preferred (these
resample the data itself to estimate variability, rather than assuming it follows a
particular curve like the normal or t-distribution), since it makes no distributional
assumption and directly targets the metric of interest. Also watch for non-independence:
back-to-back latency samples from the same server under sustained load are often
autocorrelated (a slow request tends to follow another slow request), which violates the
i.i.d. assumption (independent and identically distributed: each sample drawn independently
from the same underlying distribution) behind both the t-test and the sample-size formula and
can make a result look more significant than it really is; spacing samples out or using a
block-bootstrap (a resampling method that keeps runs of consecutive samples together, so it
captures that correlation instead of assuming independence) corrects for this.