Arrays, Strings, and Hashing Questions

Direct answer

Try IPv4 first: split on ., require exactly 4 parts, and each part must be all digits, at most 255, with no leading zero unless the part is exactly "0". If that fails, try IPv6: split on :, handle the :: zero-compression shorthand (which can appear at most once), require the expanded form to have exactly 8 groups, and each group must be 1 to 4 hexadecimal digits. Both formats have real edge-case density, which is exactly why this question is a good filter for carefulness rather than algorithmic cleverness.

Approach: IPv4

1. Split on .; reject unless there are exactly 4 parts.
2. Each part must be all-digit (test against /^[0-9]+$/), which also rejects a sign character or empty part.
3. Reject a leading zero unless the part is exactly "0" (i.e. "0" is valid, "00" and "01" are not).
4. Reject if the numeric value exceeds 255.

Approach: IPv6

1. :: can appear at most once; more than one is invalid (the shorthand would be ambiguous about how many zero groups it represents).
2. If :: is present, split the string into a "head" and "tail" around it, split each side on : (an empty side yields zero groups, not one empty-string group), and the total number of explicit groups on both sides together must be strictly less than 8 (the whole point of :: is to stand in for at least one omitted group).
3. If :: is absent, splitting on : must yield exactly 8 groups.
4. Every resulting group must be 1 to 4 hexadecimal digits.

Complexity

Both: O(L) where L is the length of the input string (each character is inspected a constant number of times across the split and per-group checks).

Edge cases

• IPv4 with a leading zero ("1.1.1.01"): rejected under the standard interview convention, discussed further below.
• IPv6 with the :: shorthand at the very start or end ("::1", "1::"), or standing alone for all-zero ("::"): all valid, and the head/tail split correctly produces zero groups on the empty side.
• A string that looks numeric but isn't a valid address in either format (e.g. too many or too few groups): correctly rejected by both checks, so the overall answer is "neither."

function isValidIPv4(s) {
  const parts = s.split(".");
  if (parts.length !== 4) return false;
  for (const p of parts) {
    if (!/^[0-9]+$/.test(p)) return false;
    if (p.length > 1 && p[0] === "0") return false;
    if (parseInt(p, 10) > 255) return false;
  }
  return true;
}

function isValidIPv6(s) {
  if ((s.match(/::/g) || []).length > 1) return false;
  let parts;
  if (s.includes("::")) {
    const [head, tail] = s.split("::");
    const headParts = head ? head.split(":") : [];
    const tailParts = tail ? tail.split(":") : [];
    if (headParts.length + tailParts.length >= 8) return false;
    parts = headParts.concat(tailParts);
  } else {
    parts = s.split(":");
    if (parts.length !== 8) return false;
  }
  for (const p of parts) {
    if (p.length < 1 || p.length > 4) return false;
    if (!/^[0-9a-fA-F]+$/.test(p)) return false;
  }
  return true;
}

const cases = ["172.16.254.1", "256.1.1.1", "1.1.1.1.1", "192.168.0.1",
  "2001:0db8:85a3:0000:0000:8a2e:0370:7334", "2001:db8::8a2e:370:7334", "::1", "::"];
for (const c of cases) {
  console.log(`${c} -> (${isValidIPv4(c)}, ${isValidIPv6(c)})`);
}

Output (executed, node s59_ip_validate.js):

172.16.254.1 -> (true, false)
256.1.1.1 -> (false, false)
1.1.1.1.1 -> (false, false)
192.168.0.1 -> (true, false)
2001:0db8:85a3:0000:0000:8a2e:0370:7334 -> (false, true)
2001:db8::8a2e:370:7334 -> (false, true)
::1 -> (false, true)
:: -> (false, true)

Each IPv4-shaped input is correctly recognized only as IPv4 ((true, false)), each IPv6-shaped input only as IPv6 ((false, true)), and the malformed 256.1.1.1 / 1.1.1.1.1 cases are correctly rejected as neither.

Trade-offs and pitfalls, grounded against a real parser

I checked this implementation's verdicts against Node's built-in net.isIP() (a mature, spec-driven parser shipped with the runtime this answer targets), as ground truth, over a wider test set that included two intentionally awkward cases. It surfaced one genuine, useful disagreement rather than confirming everything blindly:

const net = require("net");
console.log("1.1.1.01 -> mine:", isValidIPv4("1.1.1.01"), "net.isIP:", net.isIP("1.1.1.01"));
console.log("02001:0db8:85a3:0000:0000:8a2e:0370:7334 -> mine:", isValidIPv6("02001:0db8:85a3:0000:0000:8a2e:0370:7334"), "net.isIP:", net.isIP("02001:0db8:85a3:0000:0000:8a2e:0370:7334"));
console.log("::ffff:1.2.3.4 -> mine:", isValidIPv6("::ffff:1.2.3.4"), "net.isIP:", net.isIP("::ffff:1.2.3.4"));

Output (executed, node s59_parser_check.js):

1.1.1.01 -> mine: false net.isIP: 0
02001:0db8:85a3:0000:0000:8a2e:0370:7334 -> mine: false net.isIP: 0
::ffff:1.2.3.4 -> mine: false net.isIP: 6

• Leading zero and the oversized hex group: no disagreement here, and that itself is worth confirming rather than assuming. net.isIP("1.1.1.01") returns 0 (invalid), agreeing with this implementation's rejection; the same is true for the 5-hex-digit IPv6 group. Leading-zero rejection is a deliberate, security-motivated convention: leading zeros in IPv4 octets are genuinely ambiguous across tools (some historically parsed them as octal, so "010" meant 8, not 10), and that exact ambiguity was serious enough that Python's own standard-library ipaddress module was patched (CVE-2021-29921, fixed in Python 3.8.12 / 3.9.5 / 3.10.0a7) to reject any leading-zero octet outright rather than guess, precisely because parser disagreement on this point had been used to bypass IP-based access controls elsewhere. Node's net.isIP happens to already enforce the strict reading here, so this specific check doesn't surface a gap, but it would be a mistake to conclude every runtime's built-in parser is this strict; confirm it for whichever one you actually ship against.
• A real disagreement: "::ffff:1.2.3.4" (an IPv4-mapped IPv6 address, RFC 4291 section 2.5.5.2) is accepted by net.isIP as valid IPv6 (6), but this implementation rejects it (false). The reason is structural, not a bug in the sense of violating the question's own spec: the question defines IPv6 validity as "eight groups of 1-4 hex digits, allowing shorthand :: once," and "1.2.3.4" is neither a hex group nor handled by the ::-splitting logic, so it correctly falls out of scope for THIS definition. A production-grade validator that needs to accept the full real-world IPv6 address space would need an explicit extra branch recognizing a trailing dotted-quad segment. This is a good example of why "matches a mature real parser" and "matches the question's stated spec" are two different bars, and a candidate should be explicit about which one their implementation is targeting.
• A common bug in the IPv6 head/tail split: using head.split(":") unconditionally, without the head ? ... : [] guard, on an empty head (e.g. for "::1") produces [""] (one empty-string "group") instead of [] (zero groups), which then incorrectly fails the later 1-to-4-hex-digit check on that phantom empty group. This applies identically in JavaScript and in a straightforward Python port of the same logic.

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

Walk through long once with a single pointer, and advance a second pointer into short only when the current character of long matches the character short is currently waiting for. If the pointer into short reaches the end before long runs out, every character of short was found in order, so short is a subsequence of long.

Structured elaboration

Approach

def is_subsequence(short, long):
    i = 0
    if not short:
        return True
    for ch in long:
        if i < len(short) and ch == short[i]:
            i += 1
        if i == len(short):
            return True
    return i == len(short)

Only one pass over long is made, and the pointer into short never moves backward, so the total work is O(n) where n is the length of long, matching the question's explicit complexity requirement. No extra data structure is needed since matching only ever needs to compare the CURRENT position of short against the current character of long.

Application context (the question's explicit ask)

This same one-pass check is the building block behind approximate matching and fuzzy token mapping: for example, checking whether a user's typed abbreviation could plausibly expand to a longer canonical term ("gcm" as a subsequence of "google cloud monitoring"), or filtering a large candidate list down to the ones that could still match a partially typed query, before applying a more expensive scoring step only to that smaller candidate set.

Worked example

Executed with python3 s83.py, five pinned cases including two explicit edge cases (empty short, empty long):

is_subsequence('abc', 'ahbgdc')     = True  expected=True  match=True
is_subsequence('axc', 'ahbgdc')     = False expected=False match=True
is_subsequence('', 'anything')      = True  expected=True  match=True
is_subsequence('abc', '')           = False expected=False match=True
is_subsequence('ace', 'abcde')      = True  expected=True  match=True

'abc' is found in order inside 'ahbgdc' (a, then b, then c, each appearing later than the last), so it returns True. 'axc' fails because after matching 'a', no 'x' appears anywhere later in 'ahbgdc', so the pointer into short never reaches the end.

Trade-offs and pitfalls

• The empty-short-is-always-a-subsequence edge case (is_subsequence('', 'anything') returning True) is easy to get backwards if the loop logic is written slightly differently; the explicit if not short: return True guard above makes this an intentional decision rather than an accident of how the loop happens to terminate.
• If this check needs to run many times against the SAME long string with many different short candidates, a smarter structure (precomputing, for each position and character, the next occurrence of that character) avoids repeating the full O(n) scan per query, at the cost of O(n * alphabet size) preprocessing; that preprocessing trade is only worth it when the number of queries against the same long string is large.
• This only answers yes/no. If the caller also needs the actual matched positions in long (for example, to highlight which characters satisfied the match), track and return the index list as the pointer advances, rather than just the boolean.

Direct answer

With n elements, the best case is that the array holds exactly {1, 2, ..., n}, which makes the answer n + 1; otherwise the missing value lies somewhere in [1, n]. That collapses the search space enough to turn the array into its own presence table: place each value v (when 1 <= v <= n) at index v - 1 using swaps, then scan for the first index whose value doesn't match index + 1. That index (plus one) is the smallest missing positive integer, and the whole thing runs in O(n) time using O(1) extra space because no second array or hash set is ever allocated.

Structured elaboration

Why the search space collapses to [1, n+1]. Any value outside [1, n] (negative, zero, or greater than n) cannot possibly be the smallest missing positive integer for an n-element array, so it can be ignored or safely overwritten. This is what makes the array itself a viable substitute for a hash set: only n "slots" are needed to track presence of the n candidate values that matter.

The index-mapping (cyclic placement) pass. For each index i, while nums[i] is a valid candidate (1 <= nums[i] <= n) and it is not already sitting in its home slot (nums[nums[i] - 1] != nums[i]), swap nums[i] with nums[nums[i] - 1]. This pushes the value toward the index it "claims." A value equal to i + 1 is already home and the while loop stops immediately; a value outside [1, n] also stops the loop, since it can never claim a valid slot.

Why this stays O(n) despite the nested loop. Each swap places at least one element into its permanent correct home (once an element lands at its target index, the loop condition for that index becomes false and it never moves again). Since there are only n positions to permanently fill, the total number of swaps across the entire outer loop is bounded by n, so the nested while does not make this quadratic; it is a classic amortized-O(n) argument, the same one that justifies calling cyclic-sort-style placement linear.

The read-out pass. After placement, scan left to right for the first i where nums[i] != i + 1. That mismatch means value i + 1 never found a home, i.e. it was missing from the input, so the answer is i + 1. If no mismatch is found, every slot holds its expected value and the answer is n + 1.

Worked example

Trace on [3, 4, -1, 1] (n = 4), printing every swap exactly as executed:

start: [3, 4, -1, 1]
  swap nums[0] with nums[2] -> [-1, 4, 3, 1]
  swap nums[1] with nums[3] -> [-1, 1, 3, 4]
  swap nums[1] with nums[0] -> [1, -1, 3, 4]
after placement pass: [1, -1, 3, 4]
first mismatch at index 1: nums[1]=-1 != 2
answer = 2

Full runnable code (Python 3, no external dependencies) with pinned test cases:

def first_missing_positive(nums):
    """Return the smallest missing positive integer.
    O(n) time, O(1) extra space (beyond the input list, mutated in place).
    """
    n = len(nums)

    # Step 1: place each value v (1 <= v <= n) at index v-1 by swapping,
    # so that on a "perfect" array nums[i] == i+1 for all i.
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            target = nums[i] - 1
            nums[i], nums[target] = nums[target], nums[i]

    # Step 2: the first index i where nums[i] != i+1 reveals the answer.
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1


if __name__ == "__main__":
    tests = [
        ([3, 4, -1, 1], 2),
        ([1, 2, 0], 3),
        ([7, 8, 9, 11, 12], 1),
        ([1, 2, 3], 4),
        ([], 1),
        ([1], 2),
        ([2], 1),
    ]
    for arr, expected in tests:
        arr_copy = list(arr)
        result = first_missing_positive(arr_copy)
        print(f"input={arr!r:25} -> {result} (expected {expected})")

Output (actual run):

input=[3, 4, -1, 1]             -> 2 (expected 2)
input=[1, 2, 0]                 -> 3 (expected 3)
input=[7, 8, 9, 11, 12]         -> 1 (expected 1)
input=[1, 2, 3]                 -> 4 (expected 4)
input=[]                        -> 1 (expected 1)
input=[1]                       -> 2 (expected 2)
input=[2]                       -> 1 (expected 1)

Trade-offs and pitfalls

• The most common wrong turn is sorting first: it works, but costs O(n log n) time and fails the question's stated time bound. Naming it as a correct-but-non-optimal baseline before presenting the index-mapping trick shows the interviewer you understand why the O(n) approach is needed, not just that it exists.
• A hash set of seen values gets O(n) time but O(n) extra space, missing the O(1) space constraint. It is worth naming this trade-off explicitly rather than jumping straight to the in-place trick, since it demonstrates the same reasoning under a relaxed constraint.
• An easy implementation bug: omitting the "not already home" guard (nums[nums[i]-1] != nums[i]) causes an infinite loop whenever a value already equals its own target, which happens with duplicates like [1, 1], since the code would keep swapping a value with itself forever.
• The input array is mutated in place. If the array must be preserved, say so and either copy it first (paying O(n) space to keep O(n) time) or confirm in-place mutation is acceptable for the exercise.
• Duplicates and out-of-range values (negatives, zero, values greater than n) are both handled by the same guard condition, so no separate cleanup pass is required; stating this explicitly heads off the follow-up question before it's asked.

Direct answer

Make a single pass over the list and accumulate counts in a hash map (Python's collections.Counter, which is a dict subclass purpose-built for this): for each string, increment its entry by one. This is O(n) time, where n is the total number of strings processed, and O(u) extra space, where u is the number of unique strings, which for typical real-world data (repeated categorical values, tokens, log lines) is far smaller than n itself, keeping the approach both time- and memory-efficient at the "millions of items" scale the question asks about.

Structured elaboration

Why a hash map is the right tool here. Counting occurrences requires answering "have I seen this exact value before, and how many times" for each item, which is precisely the operation a hash map is built to do in O(1) average time per lookup/update. Building the count dict is therefore a single O(n) pass: for each string, look up its current count (defaulting to 0 if new) and increment it. Counter does exactly this internally and additionally provides convenience methods (most_common(), direct construction from an iterable) on top of a plain dict.

Time and space, stated precisely. Time is O(n) because every one of the n input strings is visited exactly once, and each hash map update is O(1) amortized. Space is O(u), the number of distinct strings, not O(n): a list with heavy repetition (say, a categorical column with only a handful of distinct values repeated millions of times) uses memory proportional to that handful of distinct values, not to the list's full length. This distinction between n (total items) and u (unique items) is the detail that actually matters for the "millions of items" framing in the question, since it is u, not n, that determines the dict's memory footprint.

Applying the same technique at a narrower grain: counting vowels in a string. The identical hash-based counting technique applies just as well one level down, to counting occurrences of specific characters within a single string rather than counting occurrences of whole strings within a list. A case-insensitive vowel count is the same idea: fold case first (so 'A' and 'a' count as the same vowel), then check each character against a fixed small set of vowels, incrementing a running total. Because the set of vowels is fixed and tiny (5 characters), this doesn't even need a full frequency dict. A simple counter check against a frozenset suffices, which is O(n) time (n = length of the single string) and O(1) extra space, since the vowel set's size never grows with input size.

Worked example

Full runnable code with pinned test cases, including the question's own example and the vowel-counting variant:

from collections import Counter


def string_frequencies(strings):
    """O(n) time (n = total strings), O(u) extra space (u = unique strings)."""
    return dict(Counter(strings))


def count_vowels(s, vowels=frozenset("aeiou")):
    """Same hash-based technique applied to characters of one string instead
    of elements of a list: case-insensitive vowel count, O(n) time, O(1)
    extra space (the vowel set has fixed size 5, independent of len(s))."""
    return sum(1 for ch in s.casefold() if ch in vowels)


if __name__ == "__main__":
    data = ['a', 'b', 'a', 'c', 'b', 'a']
    result = string_frequencies(data)
    print(f"string_frequencies({data!r}) = {result!r}")

    vowel_tests = [
        ("Hello World", 3),
        ("AEIOUaeiou", 10),
        ("xyz", 0),
        ("", 0),
        ("Interview", 4),
    ]
    for s, expected in vowel_tests:
        r = count_vowels(s)
        print(f"count_vowels({s!r}) = {r} (expected {expected})")

Output (actual run):

string_frequencies(['a', 'b', 'a', 'c', 'b', 'a']) = {'a': 3, 'b': 2, 'c': 1}
count_vowels('Hello World') = 3 (expected 3)
count_vowels('AEIOUaeiou') = 10 (expected 10)
count_vowels('xyz') = 0 (expected 0)
count_vowels('') = 0 (expected 0)
count_vowels('Interview') = 4 (expected 4)

The first line matches the question's own example exactly: ['a','b','a','c','b','a'] -> {'a': 3, 'b': 2, 'c': 1}. The count_vowels('Interview') case is worth naming explicitly: the capital I counts alongside the lowercase e, i, e, since .casefold() runs before the membership check, giving 4 total (I, e, i, e), matching a case-insensitive count rather than an ASCII-literal one.

Trade-offs and pitfalls

• Sorting the list first and counting runs of equal adjacent elements is a valid alternative, but costs O(n log n) time versus the hash map's O(n), and it also destroys the original ordering unless a copy is sorted separately; for "moderate lists (millions of items)" as the question specifies, the linear hash-map approach is the better default.
• Counter(strings) alone already returns a fully-functional mapping; wrapping it in dict(...) here is purely to return a plain, predictable type to a caller who may not want Counter-specific behavior (like its most_common() method or its handling of missing keys returning 0 instead of raising KeyError); either is a reasonable answer, and it's worth naming the trade-off rather than silently picking one.
• For truly massive inputs that don't fit in memory as a single Python list (as opposed to "millions of items," which a modern machine handles comfortably in RAM), the same technique still applies conceptually: replace strings with a generator/iterator and update a single running Counter one item (or one fixed-size chunk) at a time via .update(), instead of ever materializing the whole input as a list. Peak memory then holds only the current item or chunk plus the running counts, not the full input; the counting operation itself does not change, only how the input is fed into it.
• A frequency count over Unicode strings needs the same normalization awareness as any other string-identity comparison: two strings that look identical but differ in Unicode representation (composed versus decomposed accented characters) will be counted as different keys unless normalized first, which matters if the input list can contain non-ASCII text.
• For the vowel-counting variant specifically, .casefold() is the correct choice over .lower() for the same reason it matters in general caseless comparison: locale-independent, more aggressive folding handles edge cases like the German sharp s correctly, though for a fixed 5-character ASCII vowel set this distinction rarely changes the result in practice; naming .casefold() anyway signals the same caseless-comparison discipline that matters whenever a comparison needs to be genuinely Unicode-safe.