Microsoft Software Engineer (Entry Level) Interview Preparation Guide

Direct answer
parseDate has to make an explicit policy decision before any test can be written: when a format is genuinely ambiguous (like "01/02/2020", which could be January 2nd or February 1st depending on locale), does the function guess using one convention, or refuse and force the caller to disambiguate? The edge cases below assume the safer senior default: reject genuine ambiguity rather than silently guessing, and only accept slash-dates where one component is unambiguously out of range for the other reading.

Structured elaboration
The edge-case categories map to distinct failure modes of a multi-format date parser:

Worked example

function parseDate(dateStr) {
 if (dateStr === null || dateStr === undefined) return null;
 if (typeof dateStr !== 'string' || dateStr.trim() === '') return null;
 const s = dateStr.trim();

 // ISO 8601 (date, or date+time with optional offset)
 const iso = /^(\d{4})-(\d{2})-(\d{2})(?:[T ](\d{2}):(\d{2})(?::(\d{2}))?(Z|[+-]\d{2}:?\d{2})?)?$/;
 const isoMatch = s.match(iso);
 if (isoMatch) {
 const [, y, mo, d, h = '00', mi = '00', se = '00', off] = isoMatch;
 const dt = new Date(`${y}-${mo}-${d}T${h}:${mi}:${se}${off ? off : 'Z'}`);
 if (isNaN(dt.getTime())) return null;
 // Reject calendar-invalid dates the Date constructor would otherwise silently roll forward.
 if (dt.getUTCFullYear() !== Number(y) || dt.getUTCMonth() + 1 !== Number(mo) || dt.getUTCDate() !== Number(d)) {
 return null;
 }
 return dt;
 }

 if (/^\d{10}$/.test(s)) return new Date(Number(s) * 1000); // epoch seconds
 if (/^\d{13}$/.test(s)) return new Date(Number(s)); // epoch milliseconds

 // Slash format MM/DD/YYYY only; ambiguous forms are rejected rather than guessed.
 const slash = /^(\d{1,2})\/(\d{1,2})\/(\d{4})$/;
 const slashMatch = s.match(slash);
 if (slashMatch) {
 const [, mm, dd, yyyy] = slashMatch.map(Number);
 if (mm < 1 || mm > 12) return null; // first component cannot be a month at all
 if (dd < 1 || dd > 31) return null;
 if (dd <= 12 && dd !== mm) return null; // genuinely ambiguous: MM/DD and DD/MM both plausible
 const dt = new Date(Date.UTC(yyyy, mm - 1, dd));
 if (dt.getUTCMonth() !== mm - 1 || dt.getUTCDate() !== dd) return null; // e.g. 02/30/2020
 return dt;
 }
 return null;
}

Three Jest tests, run for real (Jest 30, npx jest parseDate.test.js, all passed: "Test Suites: 1 passed, 1 total. Tests: 3 passed, 3 total."):

const { parseDate } = require('./parseDate');

test('leap-day ISO string parses to the correct UTC calendar date', () => {
 const d = parseDate('2020-02-29');
 expect(d).not.toBeNull();
 expect(d.getUTCFullYear()).toBe(2020);
 expect(d.getUTCMonth()).toBe(1); // 0-indexed: February
 expect(d.getUTCDate()).toBe(29);
});

test('non-leap-year Feb 29 is rejected, not silently rolled to March 1', () => {
 expect(parseDate('2019-02-29')).toBeNull();
});

test('null, empty string, and an unambiguous-invalid slash date all return null', () => {
 expect(parseDate(null)).toBeNull();
 expect(parseDate('')).toBeNull();
 expect(parseDate('13/40/2020')).toBeNull(); // month 13 has no valid reading in either convention
});

Key points: the parser tries formats in a fixed priority order (ISO, epoch, slash) and returns null on no match rather than falling through to JavaScript's permissive native Date parsing, which is intentionally never called on unrecognized strings. Complexity: O(1) per call relative to input length (a fixed small number of regex matches against a short string); there is no loop over the string's characters beyond what the regex engine does internally. Edge cases covered by the tests above: leap-day validity (year-dependent), non-leap-day rejection (proves the parser doesn't trust the native Date object's auto-rollover), and the null/empty/unambiguous-invalid family in one test to keep the suite proportionate to a medium-difficulty question.

Trade-offs and pitfalls
The biggest pitfall is delegating straight to new Date(dateStr): it accepts a wide, engine-dependent set of formats, silently rolls invalid calendar dates forward, and returns an Invalid Date object (which is a Date instance, so typeof checks don't catch it; only isNaN(dt.getTime()) does) instead of null or throwing. A second pitfall is guessing on ambiguous formats: picking US convention by default silently mis-parses every DD/MM date from a non-US caller, and the bug is invisible in code review because both dates "look valid." The safer senior answer explicitly narrows supported formats and fails loudly and predictably outside that set, and documents that narrowing as part of the function's contract rather than leaving callers to reverse-engineer it from behavior. A third pitfall, caught by running the original version of this exact code against its own stated design goal: the first draft's slash-format guard only rejected mm > 12 and silently accepted every other slash date as MM/DD, including genuinely ambiguous ones like "01/02/2020" (both Jan 2 and Feb 1 are valid dates), which directly contradicted the "reject genuine ambiguity" policy stated above. Verified: parseDate('01/02/2020') returned a Date object instead of null under that first version. The fix (shown in the code above) adds an explicit ambiguity check, dd <= 12 && dd !== mm, so a slash date is only accepted when the day component is unambiguously out of range as a month (e.g. 03/25/2020) or when both readings agree (e.g. 05/05/2020); re-run against the same three Jest tests, all three still pass, and parseDate('01/02/2020') now correctly returns null.

Approach: parse the JSON report, aggregate stats per (project, test_name), compute runs, passes, pass_rate, avg_duration, failure_rate, and impact = failure_rate * avg_duration * runs. Filter tests with runs > 5 and pass_rate between 40% and 95% (inclusive). Sort by impact descending and output top 10.

import json
from collections import defaultdict
from statistics import mean

# Example: report is a JSON array loaded from a file
def top_flaky_tests(report_json, top_n=10):
    # Aggregation: key -> list of (status, duration)
    agg = defaultdict(lambda: {"durations": [], "passes": 0, "runs": 0, "project": None})
    
    for rec in report_json:
        key = (rec["project"], rec["test_name"])
        entry = agg[key]
        entry["project"] = rec["project"]
        entry["runs"] += 1
        entry["durations"].append(rec.get("duration_seconds", 0) or 0)
        if rec.get("status") == "pass":
            entry["passes"] += 1

    candidates = []
    for (project, test_name), v in agg.items():
        runs = v["runs"]
        if runs <= 5:
            continue
        passes = v["passes"]
        pass_rate = passes / runs
        # pass rate between 40% and 95%
        if not (0.40 <= pass_rate <= 0.95):
            continue
        avg_duration = mean(v["durations"])
        failure_rate = 1 - pass_rate
        impact = failure_rate * avg_duration * runs
        candidates.append({
            "project": project,
            "test_name": test_name,
            "runs": runs,
            "pass_rate": pass_rate,
            "avg_duration": avg_duration,
            "failure_rate": failure_rate,
            "impact": impact
        })

    # sort by impact descending and return top N
    candidates.sort(key=lambda x: x["impact"], reverse=True)
    return candidates[:top_n]

# Usage:
# with open("ci_report.json") as f:
#     report = json.load(f)
# print(top_flaky_tests(report))

Assumptions:

• Input is a list of records (or JSON-lines) with keys shown.
• duration_seconds present or treated as 0 if missing.
• pass_rate bounds are inclusive (adjust if exclusive desired).
• Impact formula prioritizes frequent, long-running failures.

Complexity:

• Let n = number of records, m = unique tests.
• Aggregation: O(n) time, O(m) space.
• Sorting candidates: O(k log k) where k ≤ m (k is filtered tests). Overall O(n + k log k).

Direct answer
Open with the headline status (on track, at risk, or blocked), then give the reader exactly what changed since the last update, what you need from them if anything, and by when, in that order.

Structured elaboration

1. Headline status first, as an explicit word, not something the reader has to infer from the tone: "on track," "at risk," or "blocked." This lets a reader triage in two seconds whether they need to read further.
2. What changed, briefly: the one or two things that happened since the last update that the reader doesn't already know.
3. What you need, if anything, stated as a specific, actionable ask rather than a vague mention of a problem. If there's nothing needed, say so, so the reader isn't left wondering whether an ask is buried in the update.
4. By when. A specific date or milestone anchors the ask; "soon" is not a deadline.
5. Keep it to a few sentences. A status update that's long enough to require its own summary has failed at being a status update.

Worked example
"Status: at risk. The vendor integration is behind because their sandbox environment has been down for two days; no ETA from them yet. I need someone with an existing vendor contact to escalate on our side, since my usual contact hasn't responded since Monday. If we don't get sandbox access back by Thursday, this pushes our launch date by roughly a week."

Headline status stated explicitly, what changed (vendor outage) stated in one clause, a specific ask (escalate via a different contact) instead of a vague complaint, and a concrete deadline and consequence tied to it.

Trade-offs and pitfalls

• Burying "at risk" or "blocked" inside a paragraph of otherwise neutral-sounding detail is the single most common failure; a reader skimming quickly can miss it entirely if it's not the first word.
• Overusing "at risk" as a reflexive hedge, when things are actually fine, trains readers to stop trusting your status labels; reserve it for genuine risk.
• A status update isn't the place for a root-cause deep dive; that belongs in a linked doc or a follow-up conversation, not in the two sentences someone reads on their phone.

Intro (0:00–0:20): "Hi—I'll demonstrate reasoning about a space vs time trade-off using the 'top-k frequent elements' problem. Goal: given an array, return k most frequent elements. I'll contrast two approaches and show why you'd pick one over the other depending on constraints."

Problem & example (0:20–0:40):
Input: nums = [1,1,1,2,2,3], k = 2
Expected output: [1,2] (order doesn't matter)

Approach overview (0:40–1:10):

• Option A (low extra space): Use a min-heap of size k. Time O(n log k), Space O(k + unique).
• Option B (fast time): Use bucket sort (frequency buckets). Time O(n), Space O(n + unique).
  I'll pick based on n, number of unique values (u), memory limits, and k.

Quick audience-check 1 (1:10–1:15): "If u ≫ k but memory is constrained, which approach favors memory?" (Expected quick answer: heap.)

Pseudocode sketch (1:15–1:50):

# Build freq map
freq = Counter(nums)  # O(n)
# Option A: min-heap size k
heap = []
for val, f in freq.items():   # O(u)
    if len(heap) < k:
        heappush(heap, (f,val))
    else:
        if f > heap[0][0]:
            heapreplace(heap, (f,val))
# result = [val for (_,val) in heap]  # O(k)

Trade-off reasoning (1:50–2:25):

• If k is small and memory limited, heap uses only O(k) extra (good).
• If you need fastest possible time and can afford O(n) extra, bucket sort gives linear time by placing values into frequency-indexed lists.
• Also consider worst-case u ~ n: heap time becomes O(n log k) still good when k small; bucket uses O(n) space which may be unacceptable in embedded contexts.

Quick audience-check 2 (2:25–2:30): "If k is near u (k≈u), which approach is simpler/faster?" (Expected: bucket or simply sort by frequency — bucket or sort both OK; bucket gives O(n).)

Closing (2:30–3:00):
"Summary: pick heap when memory constrained or k small; pick bucket when you need optimal time and have memory. Always quantify n, u, k, and memory budget before choosing. Happy to dive deeper into bucket pseudocode or runtime measurements."

A CI-only, non-locally-reproducing GPU OOM under a hard 30-minute clock needs a plan built around commands that surface the actual memory numbers fast, not guesswork.

First 5 minutes: diff the environment with real commands

# On the CI runner (or in its logs), find the GPU type and total memory
nvidia-smi --query-gpu=name,memory.total,memory.used --format=csv
# Diff CI's job config against local: batch size, precision, GPU count
diff <(cat ci/config.yaml) <(cat local/config.yaml)

Check whether CI shares one GPU across multiple concurrent jobs (a common cost-saving CI setup): if two jobs are scheduled onto the same device, each effectively sees half the memory nvidia-smi reports as free.

Next 10 minutes: reproduce CI's exact conditions, not approximate ones

import torch
# Cap memory to match CI's actual per-job budget instead of using the full local GPU
torch.cuda.set_per_process_memory_fraction(0.5, device=0)
torch.cuda.empty_cache()

try:
    run_training_step(batch_size=CI_BATCH_SIZE)  # use CI's config value, not local's
except torch.cuda.OutOfMemoryError:
    print(torch.cuda.memory_summary(device=0, abbreviated=True))

torch.cuda.memory_summary() shows allocated vs. reserved memory and the largest free block, which distinguishes a hard ceiling breach (allocated is genuinely near the total) from fragmentation (reserved is high but no single free block is large enough for the next allocation).

Next 10 minutes: bisect whether it is a ceiling breach or fragmentation

If memory_summary() shows many small free blocks but no contiguous block large enough for the failing allocation, it is fragmentation building up across test cases in the same process; if allocated memory alone already approaches the device total, it is a real ceiling breach (too large a batch/model for the available memory, or tensors never released between test cases).

Last 5 minutes: cheapest safe mitigation to unblock CI

# ci/config.yaml - minimal change to restore a green CI while investigation continues
gpu_tests:
  batch_size: 16       # was 64; matches what CI's smaller/shared GPU can hold
  parallel_jobs: 1      # was 2; stop co-scheduling two GPU-heavy jobs on one device

# add between GPU-heavy test cases as a stopgap
import gc, torch
gc.collect()
torch.cuda.empty_cache()

File the deeper investigation (genuine leak, fragmentation, or under-provisioned CI resources) as a follow-up; the batch-size/serialization change is a mitigation, not the root-cause fix.

Complexity and edge cases

No algorithmic complexity change; the mitigation trades CI throughput (smaller batches, serialized GPU jobs) for a passing pipeline. Edge case: reducing batch size can quietly change what a test is actually validating (a model behavior test tuned for batch_size=64 may behave differently at 16); note this explicitly in the follow-up ticket so the mitigation does not silently become the permanent, untracked test configuration.

Situation: I discover our service is failing intermittently because an external team’s API returns errors and that team is in a different timezone.

First 30 minutes — step-by-step:

1. Quick verification (0–5 min)

• Reproduce the error once to confirm it’s external (curl/postman) and note timestamps, request IDs, status codes, and error bodies.
• Check recent deploys/rollbacks and internal metrics to rule out our changes.

2. Triage & evidence collection (5–12 min)

• Pull logs, error rates, traces, and affected endpoints/users. Screenshot or copy key error responses.
• Identify scope: % of requests failing, user impact, whether retries help.

3. Immediate mitigation attempt (12–18 min)

• If safe, enable circuit-breaker/shorter retries or route around the endpoint (fallback responses, cached data) to reduce user impact.
• Create a temporary ticket/incident in our tracker with tags and priority.

4. Communicate status (18–24 min)

• Post an incident update in the team Slack channel and to product/stakeholders: one-sentence summary, impact, what we’re doing now, ETA for next update.
• Include reproducible steps, sample logs, and link to the ticket/incident doc.

5. Escalate to the external team and follow-up plan (24–30 min)

• Open a concise message to the external team’s support/on-call channel or pager (include timestamps, request IDs, sample curl, correlation IDs), and mark it urgent. If out-of-hours, create a clear async handoff: what we need from them and when we’ll check back.
• Schedule follow-up checkpoints (e.g., 30/60 minutes) and assign owners internally to monitor and implement fixes.

Result / why this works:

• Confirms root cause quickly, reduces user impact with mitigations, creates a single source of truth for stakeholders, and provides the external team with actionable evidence so resolution can proceed even across timezones.

Direct answer

A binary search tree (BST), a tree where every node's left subtree holds smaller keys and its right subtree holds larger keys, supports search, insert, and delete by walking down from the root using key comparisons, giving O(log n) operations only when the tree stays roughly balanced. Deleting a node has three cases depending on how many children it has: a leaf (0 children) is simply removed, a node with exactly 1 child is replaced by that child, and a node with 2 children is replaced by its in-order successor's key (the smallest key in its right subtree), after which that successor is deleted from its original position, where it is now guaranteed to have at most one child.

Structured elaboration

Approach: BST search, insert, delete

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None


def bst_search(root, key):
    node = root
    while node is not None:
        if key == node.key:
            return node
        node = node.left if key < node.key else node.right
    return None


def bst_insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = bst_insert(root.left, key)
    elif key > root.key:
        root.right = bst_insert(root.right, key)
    return root


def _min_node(root):
    node = root
    while node.left is not None:
        node = node.left
    return node


def bst_delete(root, key):
    if root is None:
        return None
    if key < root.key:
        root.left = bst_delete(root.left, key)
    elif key > root.key:
        root.right = bst_delete(root.right, key)
    else:
        if root.left is None and root.right is None:
            return None                       # 0-child case
        if root.left is None:
            return root.right                 # 1-child case (right only)
        if root.right is None:
            return root.left                  # 1-child case (left only)
        # 2-child case: replace key with in-order successor, then delete it
        successor = _min_node(root.right)
        root.key = successor.key
        root.right = bst_delete(root.right, successor.key)
    return root

Approach: why a plain BST can degrade, and what AVL does differently

• A plain BST's height depends entirely on insertion order: inserting already-sorted keys (or reverse-sorted keys) builds a tree that is really a linked list in disguise, one child per node, giving O(n) search, insert, and delete instead of O(log n).
• An AVL tree (a self-balancing BST named for its inventors, Adelson-Velsky and Landis) prevents this by tracking a height at every node and, after every insert, walking back up and checking a balance factor (the height of the right subtree minus the height of the left subtree) at each ancestor. If the balance factor ever reaches +-2, a rotation restructures that subtree back to +-1; this happens on the way back up from the newly inserted node, so no ancestor is ever left unbalanced for more than the single insert that caused it.
• The specific rotation applied depends on where the imbalance shows up: a single rotation fixes a "straight-line" imbalance (left-left or right-right), and a double rotation (rotating the child first, then the node itself) fixes a "zig-zag" imbalance (left-right or right-left).
• A red-black tree solves the same degradation problem with a different, looser invariant, a coloring rule rather than a strict height-balance rule, trading a slightly taller worst-case tree for fewer rotations per insert.

def _h(node):
    return node.height if node else 0


def _update_height(node):
    node.height = 1 + max(_h(node.left), _h(node.right))


def _balance_factor(node):
    return _h(node.right) - _h(node.left)


def _rotate_left(x):
    y = x.right
    x.right = y.left
    y.left = x
    _update_height(x)
    _update_height(y)
    return y


def _rotate_right(y):
    x = y.left
    y.left = x.right
    x.right = y
    _update_height(y)
    _update_height(x)
    return x


def avl_insert(root, key):
    if root is None:
        node = Node(key)
        node.height = 1
        return node
    if key < root.key:
        root.left = avl_insert(root.left, key)
    elif key > root.key:
        root.right = avl_insert(root.right, key)
    else:
        return root

    _update_height(root)
    bf = _balance_factor(root)

    if bf > 1:  # right-heavy
        if _balance_factor(root.right) < 0:
            root.right = _rotate_right(root.right)  # RL case
        return _rotate_left(root)
    if bf < -1:  # left-heavy
        if _balance_factor(root.left) > 0:
            root.left = _rotate_left(root.left)      # LR case
        return _rotate_right(root)
    return root

Key points

• Search, insert, and delete on a BST are all O(height), so the entire performance story of a BST reduces to controlling its height.
• The delete case that needs the most care is the 2-child case: the node cannot simply be removed, a replacement key must be found that preserves the ordering invariant, and the in-order successor (or equivalently, the in-order predecessor) is the only choice that doesn't require restructuring more than one path.
• AVL's rebalancing only ever looks at the path from the inserted node back to the root, keeping a single insert's rebalancing cost proportional to the tree's height, not its size.

Worked example

Building a BST from [5, 3, 8, 2, 4, 7, 9] via repeated bst_insert, an in-order traversal prints [2, 3, 4, 5, 7, 8, 9], confirming the BST property. Deleting 2 (a leaf, the 0-child case) leaves [3, 4, 5, 7, 8, 9]. Deleting 3 next (now a 1-child case, since 3's only remaining child is 4) leaves [4, 5, 7, 8, 9]. Deleting 5, the root (a 2-child case), replaces its key with its in-order successor, 7, then removes the original 7 from the right subtree, leaving [4, 7, 8, 9].

To see the degradation: inserting [1, 2, 3, 4, 5, 6, 7] in sorted order into a plain BST via bst_insert produces a tree of height 7 (a straight chain, one child per node, for n = 7 nodes, the O(n) worst case). Running the same 7 keys through avl_insert instead produces a tree of height 3, and an in-order traversal still prints [1, 2, 3, 4, 5, 6, 7], confirming the rebalancing preserved the BST property while keeping the tree flat.

Trade-offs & pitfalls

Complexity

Plain BST: search, insert, and delete are all $O(h)$, where $h$ is the tree's height; $h$ ranges from $O(\log n)$ (balanced) to $O(n)$ (degenerate, such as sorted-order insertion).
AVL: search, insert, and delete are all $O(\log n)$ worst case, since the height-balance invariant guarantees $h = O(\log n)$ regardless of insertion order; each insert does $O(\log n)$ work walking back up, plus at most a constant number of rotations.
Space: $O(n)$ for the tree itself; $O(h)$ additional stack space for the recursive implementations shown here.

Edge cases

• Deleting a node with 2 children whose in-order successor is itself a leaf: the recursive bst_delete call on the successor correctly falls into the 0-child case.
• Deleting the root: handled the same as any other node, since the function returns the (possibly new) subtree root at every level.
• Inserting a duplicate key: the implementation shown ignores duplicates; a production version needs to decide up front whether duplicates are allowed and where they go if so.
• Empty tree: search and delete both return None safely; insert on an empty tree creates the first node.

A common bug in from-scratch delete implementations is fixing up the tree's shape but forgetting to also update any augmented metadata (heights, subtree sizes, color bits) on every node along the path back to the root; for AVL specifically, forgetting to update height before computing the balance factor at a node makes every rebalancing decision above it wrong. A second pitfall is choosing the in-order predecessor instead of the in-order successor for the 2-child case inconsistently across an implementation; either works, but mixing them without matching invariant logic can subtly break ordering.

Direct answer

Treat each value in the array as a pointer: from index i, "follow" nums[i] to land on index nums[i]. Because there are n+1 values all in the range [1, n], at least two different indices must point to the same value (pigeonhole), which means this functional graph has a cycle, and the duplicate value is exactly the entry point of that cycle. Floyd's tortoise-and-hare cycle detection finds that entry point in O(n) time and O(1) extra space, without modifying the array at all, which is exactly what the question asks for.

Approach (Floyd's cycle detection)

1. Start both slow and fast at nums[0], i.e. one step into the implicit linked structure (index 0 always has an outgoing "pointer," but nothing points back to it, so it can't be part of the cycle itself, only the tail leading into it).
2. Advance slow one step (slow = nums[slow]) and fast two steps (fast = nums[nums[fast]]) each iteration until they meet; a meeting point is guaranteed to exist since the structure has a cycle (standard tortoise-and-hare argument).
3. Reset a second pointer to index 0, then advance it and slow one step at a time together; the index where they meet is the cycle's entry point, which is the duplicate value.

Complexity

Time: O(n) (each phase does at most O(n) steps). Space: O(1) extra; nums itself is never modified.

Edge cases

• Exactly one duplicate value, appearing exactly twice: this is the assumed input shape and the algorithm handles it directly.
• The duplicate value equal to n itself (the largest allowed value): handled the same way, since indexing is 0-based but values start at 1, so nums[i] is always a valid index regardless of which value 1..n is duplicated.

def find_duplicate_floyd(nums):
    slow = nums[0]
    fast = nums[nums[0]]
    while slow != fast:
        slow = nums[slow]
        fast = nums[nums[fast]]
    slow2 = 0
    while slow2 != slow:
        slow2 = nums[slow2]
        slow = nums[slow]
    return slow


data = [1, 3, 4, 2, 2]
original = list(data)
print(find_duplicate_floyd(data), data == original)

Output:

2 True

The duplicate is correctly identified as 2, and data == original confirms the array was never mutated during the search.

Alternative technique: index-marking

A second valid approach exploits the same "values are indices" fact differently: walk the array once, and for each value, negate the entry at the index that value points to (abs(value) - 1). If you ever land on an index whose entry is already negative, that index (converted back to 1-based) is the duplicate, because it means two different positions "pointed" to it. This is also O(n) time and O(1) additional space, but unlike Floyd's approach, it works by temporarily mutating nums in place (each visited value's target slot gets negated), so if the caller needs nums to remain externally unmodified while the function runs (not just restored by the time it returns), Floyd's version is the safer default.

def find_duplicate_marking(nums):
    duplicate = None
    for x in nums:
        idx = abs(x) - 1
        if nums[idx] < 0:
            duplicate = idx + 1
            break
        nums[idx] = -nums[idx]
    for i in range(len(nums)):
        nums[i] = abs(nums[i])
    return duplicate


data2 = [1, 3, 4, 2, 2]
print(find_duplicate_marking(data2), data2)

Output:

2 [1, 3, 4, 2, 2]

Both techniques agree on the duplicate (2), and the marking approach restores the array to its original values by the time it returns, even though it mutated it during the scan.

Trade-offs and pitfalls

• "Does not modify the array" has two readings, and the question's phrasing ("without modifying the array") most naturally means Floyd's guarantee: never mutated, at any point, including during execution. The marking approach only satisfies a weaker version ("unmodified once the function returns"), which is a meaningful difference if another thread could read nums concurrently while this function runs, or if the function could throw partway through and leave the array in its negated state.
• A frequent proof gap: candidates often reach for cycle detection without first establishing why a cycle must exist here. The argument is exactly pigeonhole: n+1 values drawn from a range of only n possible values guarantees at least one repeat, and because every value is a valid index (never 0, since the range is [1, n] not [0, n-1]), the "value points to index" structure is well-defined for every position, forcing at least one node in the sequence to be revisited, i.e. a cycle.
• A common bug in the marking approach: forgetting the final restoration pass, which silently corrupts the caller's array (still functionally finds the right duplicate, but violates the "don't modify the array" requirement in a way that's easy to overlook if you only test the return value).

Direct answer

Plain Kahn's algorithm with a FIFO queue produces a valid topological order, but which one depends on insertion order among tied, simultaneously-available vertices. To force the lexicographically smallest valid order (smallest by node id, compared position by position), replace the queue with a min-heap: at every step, among all vertices currently free of unmet dependencies, always emit the smallest id. This is a small structural change with a real complexity cost: $O((V+E)\log V)$ instead of $O(V+E)$, because every insertion and extraction on the heap costs $O(\log V)$.

Structured elaboration

The algorithm is Kahn's algorithm verbatim except for one substitution: swap deque for heapq. Correctness for cycle detection is unchanged (a cycle still means some vertices never reach in-degree 0, so the output stays short); the only new property is that whenever more than one vertex is simultaneously eligible, the heap always yields the smallest one first, which is exactly the greedy rule that produces the lexicographically smallest sequence: committing to the smallest available choice at every position, given that any later choice is still available to be picked in a later position if it becomes newly eligible.

Why greedy-smallest-first is provably correct here (not just plausible). Suppose the true lexicographically smallest valid order picks vertex $x$ at some position, but $x$ is not the smallest currently-eligible vertex; call the smallest eligible one $y < x$. Since $y$ has no unmet dependency, nothing prevents placing $y$ at that position instead, and $y$'s own dependents only become eligible later regardless of whether $y$ is placed now or later, so swapping $y$ into that earlier position can only make the sequence lexicographically smaller or equal, never invalid. This is the standard exchange argument for greedy algorithms; it is why the heap substitution alone (no other logic change) is sufficient.

Worked example

import heapq
from typing import Dict, List, Optional

def topo_lex(graph: Dict[int, List[int]]) -> Optional[List[int]]:
    # Kahn's algorithm with a min-heap instead of a FIFO queue: among all
    # nodes currently available (indegree 0), always pop the smallest id.
    # Returns the lexicographically smallest valid topological order, or
    # None if the graph has a cycle.
    indegree = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            indegree[v] += 1

    heap = [u for u in graph if indegree[u] == 0]
    heapq.heapify(heap)
    order = []
    while heap:
        u = heapq.heappop(heap)
        order.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                heapq.heappush(heap, v)

    if len(order) != len(graph):
        return None
    return order

if __name__ == "__main__":
    dag = {5: [2, 0], 4: [0, 1], 2: [3], 3: [1], 0: [], 1: []}
    result = topo_lex(dict(dag))
    print("Lexicographically smallest order:", result)

    def is_valid_topo(order, graph):
        pos = {n: i for i, n in enumerate(order)}
        return all(pos[u] < pos[v] for u in graph for v in graph[u])
    print("Valid topological order:", is_valid_topo(result, dag))

    from itertools import permutations
    nodes = list(dag.keys())
    valid_orders = [list(p) for p in permutations(nodes) if is_valid_topo(list(p), dag)]
    brute_min = min(valid_orders)
    print("Brute-force minimum over all valid orders:", brute_min)
    print("Matches heap-based result:", brute_min == result)

    cyclic = {0: [1], 1: [2], 2: [0]}
    print("Cyclic graph result:", topo_lex(dict(cyclic)))

Output (actually executed with python3):

Lexicographically smallest order: [4, 5, 0, 2, 3, 1]
Valid topological order: True
Brute-force minimum over all valid orders: [4, 5, 0, 2, 3, 1]
Matches heap-based result: True
Cyclic graph result: None

The brute-force check enumerates every permutation of the six vertices, keeps only the ones that respect every edge, and takes the minimum by standard list (lexicographic) comparison. This is only feasible for the toy example ($6! = 720$ permutations) and exists purely to independently confirm the heap-based algorithm's exchange argument holds on a real case, not as a scalable approach in itself.

Complexity

Time $O((V+E)\log V)$: every vertex is pushed and popped from the heap once ($O(V \log V)$ total), and every edge triggers at most one additional push when its target's in-degree reaches zero ($O(E \log V)$ total). Space $O(V)$ for the heap and in-degree map, plus $O(V+E)$ for the adjacency list.

Edge cases

• All vertices tied at in-degree 0 (a totally disconnected graph): the heap degenerates to simply popping vertices in ascending id order, which is correct and matches the lexicographically-smallest definition trivially.
• A long single chain ($0\to1\to2\to\dots$): only one vertex is ever eligible at a time, so the heap never actually has a choice to make; the result is forced and identical to what plain Kahn's algorithm would produce.
• Cycle: identical detection to plain Kahn's algorithm, None when the output falls short of len(graph).
• Negative or non-integer ids: the heap comparison works for any totally ordered, hashable type, so this generalizes to string ids (alphabetical order) without changing the algorithm, only the type annotation.

Trade-offs and pitfalls

• Common mistake: assuming a plain, unmodified Kahn's algorithm with a FIFO queue already gives the lexicographically smallest order "because it processes in the order things become available." That is false in general: two vertices can become eligible in the same round, and FIFO preserves insertion order (which reflects the order their prerequisites happened to be processed in), not numeric order. Only replacing the queue's tie-breaking mechanism with an explicit min-heap (or a per-round sort) fixes this.
• Common mistake: sorting the entire vertex list once at the start and iterating in that fixed order while checking in-degree, instead of using a heap. This looks similar but is wrong: a vertex with a smaller id can become eligible several rounds after a vertex with a larger id, and a single static sort pass cannot re-examine a vertex once skipped in an earlier scan, or would need to re-scan the whole list every round, which is $O(V)$ per round instead of $O(\log V)$ per operation.
• This exact technique (a min-heap-based topological sort relying on the same exchange-argument correctness) shows up repeatedly in practice, confirming it is a stable, recognized approach rather than an unusual one-off construction; the min-heap substitution is the standard way this requirement is solved, not a workaround.
• The $O(\log V)$ factor genuinely matters at scale: for a graph with $V=10^6$ vertices, plain Kahn's algorithm and the lexicographic variant differ by roughly a factor of 20, which is worth naming explicitly if a system does not actually need reproducible ordering and is paying this cost for no functional benefit.

Direct answer
When a deadline, a client, or a business ask pushes toward something that conflicts with a principle a company has committed to, such as privacy, security, or data quality, the strongest answers show three things: you noticed the conflict explicitly rather than complying without registering it, you raised it through the right channel rather than either silently complying or unilaterally blocking the work, and you drove toward a resolution rather than just splitting the difference.

Structured elaboration

• Notice: name the specific moment you recognized the tension, and what concrete detail made you pause.
• Raise it: describe how you raised it, ideally backed by data or a concrete risk rather than an appeal to principle alone. A values-based objection lands far better when it is backed by the actual risk it protects against.
• Navigate: what you actually did in the interim, whether you proposed a compromise or a phased approach, who you looped in, and how you kept the relationship functional even while disagreeing.
• Outcome: what actually happened. An honest outcome, including "I was overruled and here is what I did next," is often more credible than a suspiciously clean win.

Worked example
A team was under pressure to ship a change quickly, and the fastest path meant skipping a validation step that existed specifically to catch a known class of data-quality problem. Rather than quietly skipping it or unilaterally blocking the release, the response was to time-box a reduced version of the validation, checking the highest-risk subset in the time available, and to flag explicitly and in writing what wasn't covered and what the residual risk was, so the decision to accept that risk was made deliberately by the right people rather than by default. The release shipped on time, and the flagged gap was closed within the following two days as agreed, rather than being silently forgotten.

Trade-offs and pitfalls
A story where you unilaterally blocked the work and were later vindicated can read as inflexible if it doesn't also show you understood the business pressure; the strongest answers show empathy for that pressure while still holding the line. A story where you quietly went along with the shortcut is not really an example of this competency at all; the action needs to show you actively surfaced the tension, not merely noticed it internally. Vague appeals to "our values" without a concrete risk attached tend to land weaker than a specific technical or business risk, clearly stated.