Google Software Engineer Entry Level (L3) Interview Preparation Guide

A partial hotfix, restoring some functionality but not all, needs careful handling so the working state isn't accidentally lost and the remaining gap is clearly tracked, not silently forgotten.

Approach

1. Preserve the working state explicitly: commit the partial fix on its own clearly-labeled branch/commit rather than mixing it with further in-progress changes, so it can be safely deployed or rolled back to independently.
2. Document exactly what's fixed and what isn't, in the commit message and in a tracked follow-up item, including which specific scenarios remain broken, so the gap doesn't get discovered again from scratch by whoever picks it up next.
3. Capture logs/diagnostics before finalizing the partial fix, since once deployed, the remaining broken scenarios may become harder to reproduce (the environment has changed).
4. Decide deploy versus rollback based on net impact: does the partial fix genuinely reduce customer impact for a real majority of cases, or does it introduce a confusing half-fixed state that's harder to reason about than either the original bug or a full rollback? If unsure, a clean rollback while completing the fix properly is usually safer than shipping a partial state that stakeholders might mistake for "done."

Writing the follow-up plan

State precisely what remains broken, why the partial fix doesn't cover it yet, and a concrete next step with an owner, rather than a vague "will investigate further" that has no forcing function to actually get finished.

Trade-offs and pitfalls

The main risk of shipping a partial fix is stakeholders treating "mostly fixed" as "fixed," closing out attention on the issue before the remaining gap is actually addressed; being explicit and specific about what's still broken in every status update is what prevents that.

To solve this we use digit DP: iterate digits from most-significant to least, tracking (pos, sum_mod_k, tight, leading_zero). DP returns count of valid numbers from pos to end given current sum modulo k. Leading zeros must not contribute to sum (but zero itself counts: if whole number is 0, sum 0 mod k). Tight limits digit choice to N's digit at pos.

Approach:

1. Convert N to digit array.
2. dfs(pos, sum_mod, tight, leading_zero) returns count.
3. If pos == len(digits): return 1 if sum_mod == 0 and not (leading_zero==True and treat zero valid) — we count zero as valid so return 1 when sum_mod==0.
4. For each digit d from 0 to (tight? digits[pos] : 9):
   • next_leading_zero = leading_zero and d==0
   • next_sum = sum_mod if next_leading_zero else (sum_mod + d) % k
   • next_tight = tight and (d == digits[pos])
   • accumulate dfs(pos+1, next_sum, next_tight, next_leading_zero)
5. Memoize on (pos, sum_mod, tight, leading_zero) but tight and leading_zero are small (2 each). Use -1 cache when tight==False to allow reuse; when tight==True, can't reuse across different prefixes so include tight in key.

Python implementation:

def count_up_to(N, k):
    digits = list(map(int, str(N)))
    n = len(digits)
    from functools import lru_cache

    @lru_cache(None)
    def dfs(pos, sum_mod, tight, leading_zero):
        if pos == n:
            return 1 if sum_mod % k == 0 else 0  # zero is counted because leading_zero may be True but sum_mod==0
        limit = digits[pos] if tight else 9
        res = 0
        for d in range(0, limit + 1):
            ntight = tight and (d == limit)
            nleading = leading_zero and (d == 0)
            nsum = sum_mod if nleading else (sum_mod + d) % k
            res += dfs(pos + 1, nsum, ntight, nleading)
        return res

    return dfs(0, 0, True, True)

Key points:

• State: pos (0..digits-1), sum_mod (0..k-1), tight (0/1), leading_zero (0/1).
• Transition adds digit d; if still leading zeros, digit doesn't affect sum.
• Base: at end, count if sum_mod==0.
• Memoization: cache key size ~ digits * k * 2 * 2.

Complexity:

• Time: O(digits * k * 10) ~ O(digits * k) since inner loop 10 constant.
• Space: O(digits * k * 4) for memo.

Edge cases:

• N=0 handled: returns 1 when k divides 0.
• Large k relative to digits: still works; complexity scales with k.

Direct answer

Make two passes over the array without ever dividing. In the first pass, fill the output with the running PREFIX product (the product of everything to the left of each index). In the second pass, walk from the right and multiply each entry by a running SUFFIX product (the product of everything to the right of each index). After both passes, output[i] holds the product of every element except nums[i].

Structured elaboration

Approach

def product_except_self(nums):
    n = len(nums)
    output = [1] * n

    prefix = 1
    for i in range(n):
        output[i] = prefix
        prefix *= nums[i]

    suffix = 1
    for i in range(n - 1, -1, -1):
        output[i] *= suffix
        suffix *= nums[i]

    return output


def naive_division(nums):
    """The disallowed shortcut, shown only to make its zero-element failure
    concrete rather than asserted: multiply everything once, then divide by
    each element in turn."""
    total = 1
    for x in nums:
        total *= x
    out = []
    for x in nums:
        if x == 0:
            out.append(None)  # division by the zero element is undefined
        else:
            out.append(total // x)
    return out

This is O(n) time (two linear passes) and O(1) extra space, not counting the output array itself, exactly as the question specifies, since only two running scalar accumulators (prefix and suffix) are kept alongside the output.

Why prefix and suffix products work, and why no division is needed

Every position i's answer is exactly (product of nums[0..i-1]) * (product of nums[i+1..n-1]), the product of everything strictly to the left, times the product of everything strictly to the right. The first pass computes and stores the left-hand factor for every index in one sweep (writing it into output[i] before nums[i] itself is folded into the running prefix). The second pass computes the right-hand factor the same way while sweeping backward, multiplying it directly into the value already stored. Because the two factors are built and combined without ever needing nums[i] itself in the final expression, this naturally avoids the "divide the total product by nums[i]" approach, which is both explicitly disallowed here and would break outright on any zero in the input (division by zero, or worse, silently wrong results if a naive implementation tries to special-case just one zero).

Leave-one-out features (the question's explicit ask)

The prefix/suffix accumulation pattern used here is the general technique behind computing a "leave-one-out" aggregate for every position without recomputing the whole aggregate from scratch each time. The most common leave-one-out feature in practice is a SUM (for example, "total spend across a group, excluding this member"), computed the same way with running prefix and suffix sums instead of products; the product version shown here applies the identical idea whenever the aggregate you need excluded is a product rather than a sum, for example computing a joint likelihood or a normalization factor across a set of independent factors while excluding one factor at a time.

Worked example

Executed with python3 s84.py (both functions defined above):

product_except_self([1, 2, 3, 4]) = [24, 12, 8, 6]
manual check: [24, 12, 8, 6]

Manually: excluding index 0 leaves 2*3*4=24; excluding index 1 leaves 1*3*4=12; excluding index 2 leaves 1*2*4=8; excluding index 3 leaves 1*2*3=6. All four match the function's output exactly.

product_except_self([1, 2, 0, 4]) = [0, 0, 8, 0]
naive division-based version on the same input = [0, 0, None, 0]  <- breaks on the zero element

With a zero present, every output except the one at the zero's own index is 0 (since every other output's product still includes the zero), while the output AT the zero's index is the product of everything else (1*2*4=8). A division-based approach (compute the total product, then divide by nums[i]) fails outright here: dividing by the zero element itself is undefined, shown above returning None rather than the correct value 8.

Trade-offs and pitfalls

• The division-based shortcut (multiply everything, then divide by nums[i] for each output) is both explicitly disallowed by the question and fundamentally broken the moment any element is zero; the executed comparison above makes this concrete rather than asserted.
• The two-pass prefix/suffix technique generalizes directly to any associative combining operation (sum, product, min, max, and so on) wherever a "leave-one-out" aggregate is needed without an inverse operation (subtraction for sum, division for product) available or safe to use.
• If the array can be very large and the values themselves can be large integers, the running prefix and suffix products can grow to very large magnitudes; in a fixed-width integer language (unlike Python's arbitrary-precision integers), this needs an explicit overflow check or a different numeric representation, which is worth naming even though Python itself does not hit this limit.

Approach: do binary search over the value domain [min_val, max_val]. For a candidate mid, count how many array elements are <= mid in O(n). If count >= k, the kth smallest is <= mid, so move high = mid; else low = mid + 1. Stop when low == high.

Code (Python):

def kth_smallest_by_value(nums, k):
    if not 1 <= k <= len(nums):
        raise ValueError("k out of range")
    lo, hi = min(nums), max(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        # count elements <= mid in O(n)
        cnt = 0
        for x in nums:
            if x <= mid:
                cnt += 1
        if cnt >= k:
            hi = mid
        else:
            lo = mid + 1
    return lo

Key points:

• Counting is a single pass O(n) scan, constant extra space.
• When values are integers this returns the correct value; with floats you need epsilon or rank-aware checks.
• If duplicates exist, logic still holds because cnt tracks rank threshold.

Complexity:

• Time: O(n * log(R)) where R = (max_val - min_val + 1) for integers (or log(range/precision) for floats).
• Space: O(1).

When preferable to Quickselect:

• When you want guaranteed worst-case bounds (deterministic runtime depending on value range) rather than Quickselect's average O(n) but worst-case O(n^2).
• When value range is small relative to n (log R small) — e.g., integers in limited domain.
• When you cannot modify the array (this is non-destructive) or when data is streaming/external and you can only make sequential passes.
• When stability with many duplicates matters: value-binary-search handles ties cleanly.

Trade-offs:

• If value range is huge (like 64-bit random ints), log R may be large and Quickselect (average O(n)) is faster.
• For repeated queries, build summaries (counting sort, order-stat tree) may be better.

Direct answer. A code smell is a surface signal, not a bug in itself, that usually points to a deeper structural problem: the code works today but will resist the next change. It's a heuristic for WHERE to look, not proof that something is wrong.

Five smells common under deadline pressure

1. Long method -- a function that keeps growing because it's easier to add one more if than to stop and restructure. Remediation: extract by responsibility (see S5) as soon as a function needs a comment to separate its 'sections.'
2. Duplicated code -- the same logic copy-pasted with small tweaks because extracting a shared abstraction felt slower under a deadline. Remediation: extract the shared part once there are two clear copies (the classic 'rule of three' guards against over-extracting on the first duplicate).
3. God object/class -- one class or module that ends up owning unrelated responsibilities because it was the easiest place to bolt on 'just one more thing.' Remediation: split along 'reason to change' (SRP), migrating callers incrementally rather than in one big rewrite.
4. Shotgun surgery -- a single conceptual change (e.g., adding a new payment method) requires touching a dozen files because the concept isn't encapsulated anywhere. Remediation: consolidate the scattered logic behind one seam (a class, interface, or module) so future changes touch one place.
5. Primitive obsession -- passing raw strings/ints around for things that are really domain concepts (an email, a currency amount, a user ID), losing the validation and meaning a real type would carry. Remediation: introduce small value types/wrappers so invalid states become unrepresentable rather than merely 'usually correct.'

Why deadline pressure specifically produces these

Under pressure, the fastest LOCAL change is almost always to keep extending what's already there (one more branch, one more copy-paste, one more method on the class you already have open) rather than to pause and restructure. Each individual shortcut is locally rational; the smell accumulates because nobody's shortcut budget includes 'time to undo the last five shortcuts.'

Trade-offs and pitfalls

• Smells are a starting point for investigation, not an automatic verdict -- a long method that's a single linear sequence of well-named steps with no branching can be more readable than five tiny indirections that force you to jump around a file.
• Don't chase every smell with equal urgency; prioritize by where the churn and bug density actually are (see the complexity-metrics survivor for how to find that objectively) rather than refactoring whatever offends you first.
• Naming a smell is only useful if it's followed by a concrete remediation plan; 'this is a god object' without a proposed split is just a complaint.

Situation: An intermittent CI test failure that never reproduces locally can come from flakiness, infra instability, race conditions, or timing/timeout sensitivity. Here's a systematic debugging plan to identify and fix the root cause.

1. Triage & pattern analysis

• Collect CI failure history: frequency, time-of-day, node/agent IDs, commit hashes, PR vs master, test shard.
• Capture failing job artifacts (logs, test output, screenshots, core dumps, coverage).
• Note whether failures correlate with load spikes, high CPU/memory, or network issues.

2. Telemetry to enable/collect

• Test-level: full stdout/stderr, stack traces, assertion locations, test durations, timestamps with millisecond precision.
• Infra: agent CPU, memory, disk I/O, network latency, process counts, container cgroup metrics.
• Tracing/profiling: distributed traces (span timings), thread dumps, GC logs, perf or pprof snapshots for native code.
• Environment: exact binary, dependency versions, environment vars, JVM/Node flags.
• Persist a reproducible VM/container image of the failing CI node if possible.

3. Reproduce locally under load

• Re-run test in same OS/container image (use the CI image locally or in Docker).
• Mimic CI resources: limit CPU and memory, run with similar concurrency, use stress tools (stress-ng), network throttling (tc/netem).
• Run tests in loop and parallel to increase chance of exposing race/timing.
• Use CI-scale test runner (same test shard/scheduler).
• Increase log verbosity and enable timestamps.

4. Narrow down cause

• Flaky test (test code): add deterministic seeds, assert pre/post conditions, isolate external dependencies by mocking, add extra logging around setup/teardown.
• Infrastructure instability: look for correlated infra metrics (OOM, disk full, flaky network). Re-run on different agents and compare.
• Race condition: run under race detectors/sanitizers (ThreadSanitizer, Go race, Java concurrency tools), enable heavy instrumentation (LockProfilers), capture thread dumps at failure.
• Timing-sensitive: replace real timers with controllable clocks (fake clocks), reduce test timeouts locally, introduce artificial delays to see sensitivity.

5. Isolation strategy (binary search)

• Bisect commits to see when flakiness began.
• Minimize test: remove unrelated assertions, split test into smaller units to identify the failing section.
• Reproduce single-case under single-threaded mode to check concurrency dependency.
• Swap real dependencies with deterministic fakes to see if external systems cause nondeterminism.

6. Fix approaches

• For race: add proper synchronization, atomic operations, or redesign to avoid shared mutable state in tests.
• For timing: increase conservative timeouts, use condition-based waits (poll with timeout) instead of fixed sleeps, use fake clocks.
• For infra: add retries with exponential backoff for known transient failures, pin CI workers or improve resource isolation, or tweak resource requests/limits.
• For flaky test logic: rewrite to be deterministic, ensure clean setup/teardown, avoid shared state between tests, and add idempotency.

7. Validation & prevention

• Re-run tens/hundreds of attempts in CI and locally under stress to verify fix.
• Add telemetry and assertion checks to ensure invariant holds going forward.
• Add test-level flakiness gating (failing only after N consecutive failures) and alerting for infra anomalies.
• Add post-merge monitoring and a blame-minimizing bisect process for future regressions.

Example quick commands:

• Run with limited CPUs: docker run --cpus="0.5" ...
• Network jitter: tc qdisc add dev eth0 root netem delay 100ms 20ms
• Java thread dumps: jstack -l <pid> > dump.txt
• Go race: go test -race ./...

This plan identifies, reproduces, and isolates the root cause through telemetry, controlled experiments, and targeted fixes, then validates the fix under load before rolling back into CI.

Situation: In a one-on-one I overhear allegations that could become a harassment claim involving team members.

Immediate actions I take (safety, evidence preservation, HR/legal involvement, fairness):

1. Ensure immediate safety and support

• Separate parties if needed; offer private support to the person who raised the allegation.
• Clarify they’re heard, provide emergency resources (EAP, security) and explain next steps without pressuring them.

2. Preserve evidence without investigating

• Ask the reporter to preserve any messages, screenshots, or recordings.
• Immediately notify IT/Security (on a need-to-know basis) to preserve relevant logs, chat history, emails, build/deploy logs, and take forensic snapshots if required; request a legal hold on related data.
• Avoid accessing or sharing alleged evidence beyond required parties to prevent contamination.

3. Involve HR and Legal promptly

• Escalate to HR and Legal within the timeframe mandated by policy; provide a factual, limited written summary of what I heard and when.
• Recuse myself from fact-finding to avoid bias; request HR-led investigation and an impartial investigator.

4. Protect confidentiality and prevent retaliation

• Limit disclosure to HR, Legal, and necessary leadership; document who is informed.
• Put interim measures in place (temporary reassignments, remote work, adjusted reporting lines) consistent with fairness and minimal disruption.
• Communicate zero-retaliation policy and monitor team dynamics.

5. Ensure a fair, documented process

• Let HR handle interviews; offer technical assistance for evidence collection (timestamps, audit trails) when asked.
• Keep clear, dated records of my actions and communications.
• Follow up with HR on outcomes and ensure any remediation or team communications are coordinated by HR/Legal.

Why: These steps prioritize safety, maintain evidentiary integrity, respect confidentiality and due process, and reduce legal risk while supporting victims and preserving team trust.

Approach: do a reverse preorder traversal (visit right, then left, then node) and maintain a previous node pointer. For each visited node, set node.right = prev and node.left = null, then update prev = node. This produces the preorder-linked-list in-place. Recursion depth equals tree height => O(h) space.

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    private TreeNode prev = null; // previously processed node in reverse preorder

    public void flatten(TreeNode root) {
        // reverse preorder: right -> left -> node
        if (root == null) return;
        flatten(root.right);
        flatten(root.left);

        // invariants maintained here:
        // 1) 'prev' points to the head of the already-flattened list for the subtree
        // 2) all nodes in that list have left == null and use right as next pointer
        root.right = prev; // link current node to previously processed list
        root.left = null;  // ensure left is null as required
        prev = root;       // now current node becomes head of flattened list
    }
}

Key invariants:

• After processing a node, the subtree rooted at that node is flattened into a list following preorder, with left pointers null and right pointers as next.
• 'prev' always references the head of the flattened list for nodes already visited (which are those that appear after the current node in preorder).

Complexity:

• Time: O(n) — each node visited once.
• Space: O(h) — recursion stack where h is tree height.

Edge cases:

• Empty tree (root == null).
• Single-node tree.
• Skewed trees (height = n) result in O(n) stack depth; iterative alternatives (Morris-style) can achieve O(1) extra space if required.

Approach: use two pointers with a dummy head. Advance the fast pointer n+1 steps from dummy so the gap between fast and slow is n nodes; then move both until fast reaches end. Slow will be just before the node to remove — splice it out. This is one pass (single traversal), O(1) extra space.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    """
    Remove the nth node from end in one pass using dummy node.
    Returns the possibly new head.
    """
    dummy = ListNode(0, head)
    slow = dummy
    fast = dummy

    # Move fast n+1 steps ahead so slow ends at predecessor of target
    for _ in range(n + 1):
        fast = fast.next

    # Move both until fast hits the end
    while fast:
        slow = slow.next
        fast = fast.next

    # slow.next is the node to remove; unlink it
    to_remove = slow.next
    slow.next = to_remove.next
    # Optional: help GC
    to_remove.next = None

    return dummy.next

Key points:

• dummy handles removal of head uniformly.
• We advance fast n+1 to maintain gap; when fast is None, slow is at predecessor.
  Time complexity: O(L). Space complexity: O(1).

Edge cases:

• Removing the head (n == length) — handled by dummy.
• n equals 1 (remove last node).
• Single-node list (result may be None).
• Assume n is valid (1 ≤ n ≤ length).

Direct answer

An array gives $O(1)$ index-based random access and is cache-friendly, because its elements sit in one contiguous block of memory that the CPU can pull into cache together. A singly linked list gives $O(1)$ insertion or deletion once you already hold a reference to the splice point, at the cost of $O(n)$ traversal to reach any given position and extra per-node memory overhead. For a workload that is mostly random reads, pick an array (or dynamic array); for a workload that is mostly insertions and deletions in the middle where you already hold the relevant node reference, a linked list wins.

Structured elaboration

The contiguous-versus-non-contiguous memory allocation framing is exactly this same dimension stated differently: contiguous storage is what gives arrays both their cache locality and their index arithmetic; non-contiguous, per-node allocation is what gives linked lists their cheap local splicing at the cost of locality. In a garbage-collected (GC) language, this also affects collector pressure: many small linked-list node objects mean more individual objects for the garbage collector to track and scan, compared to one contiguous array allocation holding the same data.

Worked example

Consider inserting a new element in the middle of a ten-item collection, repeatedly, as items are typed into an editable list. With an array, each insertion must shift every element after the insertion point one slot over, an $O(n)$ cost per insertion regardless of whether you know exactly where to insert. With a singly linked list, if the editing position is tracked by an existing reference to the node just before it (as a cursor would be in a text-editing context), each insertion is a pure $O(1)$ relink; but if you only know the position as an index and must first walk from the head to reach it, the linked list gains nothing over the array for that access, since both now cost $O(n)$ overall. This is why the deciding factor is not "array versus linked list" in the abstract, but whether the workload naturally hands you a reference to the splice point or only an index.

Trade-offs & pitfalls

Assuming "$O(1)$ insertion" for a linked list means fast in absolute terms is a common mistake: reaching the splice point is usually the dominant cost unless a reference to it is already in hand from a prior traversal or an auxiliary index. Ignoring the per-element memory overhead ratio is another: a linked list of single integers can use several times the memory of the equivalent array, because the pointer overhead per node is fixed regardless of how small the stored value is. Modern hybrid structures such as a deque (double-ended queue) or a rope address parts of this trade-off by chunking data into contiguous blocks rather than choosing purely one extreme or the other.