Arrays, Strings, and Hashing Questions

Direct answer

Put every number into a hash set for O(1) average membership checks, then only start counting a run from numbers that are the START of a run, meaning num - 1 is not in the set. From each such start, walk forward while the next consecutive integer is present, tracking the longest run found. This turns an O(n log n) sort-based approach into O(n) average time, because the set lets you test "is this the start of a run" without looking at the rest of the array.

Structured elaboration

Approach

def longest_consecutive(nums):
    num_set = set(nums)
    best = 0
    for n in num_set:
        if (n - 1) not in num_set:
            length = 1
            while (n + length) in num_set:
                length += 1
            best = max(best, length)
    return best

Why this is O(n), not O(n times the average run length)

The inner while loop only ever runs starting from a number that has no predecessor in the set, that is, the FIRST element of some run. Every other number in that run gets skipped by the outer loop's guard (n - 1 not in num_set is false for them), so the inner loop is never re-entered from the middle of a run it has already walked. Summed across the whole execution, every number in the array is visited by the inner loop's forward walk at most once, across the ENTIRE algorithm, not once per outer-loop iteration; that is what keeps the total work at O(n) despite the code superficially looking like a nested loop.

Application: contiguous ID spans in event logs (the question's explicit ask)

If event or record identifiers are integers assigned in increasing order, but the log has gaps (from filtered-out, dropped, or retried events), this exact technique finds the longest unbroken run of the IDs that DID make it into the log, in one O(n) pass over an unsorted set of IDs, without first sorting the whole log.

Worked example

Executed with python3 s74.py, pinned inputs:

input: [100, 4, 200, 1, 3, 2, 101, 102]
longest_consecutive(nums) = 4

The run 1, 2, 3, 4 has length 4; the run 100, 101, 102 has length 3; 4 is the longer of the two, matching the printed result.

event_ids: [7001, 7002, 7004, 7005, 7006, 7010]
longest contiguous ID span length = 3

The span 7004, 7005, 7006 (length 3) is longer than the span 7001, 7002 (length 2), matching the printed result and directly demonstrating the event-log framing the question asks about.

Trade-offs and pitfalls

• The single most common bug is dropping the (n - 1) not in num_set guard and letting the inner loop start from every element; that degrades to O(n^2) in the worst case (for example, one long consecutive run), even though the code still looks like "the hash-set version" at a glance.
• Duplicate values in the input do not affect correctness (the set removes them), but the returned length measures the run over DISTINCT values; if a caller actually needs to count how many raw events fall in the longest span, including duplicates, this exact function does not do that and needs a small extension.
• If the caller needs the actual start and end of the run for reporting (not just its length, which is what the event-log framing implies you would want in practice), track the start value alongside the length whenever a new best is found.

Direct answer

Boyer-Moore majority vote keeps a single candidate and a counter. Walking the array once, a match with the candidate increments the counter, a mismatch decrements it, and whenever the counter hits zero the candidate is replaced by the current element. If a true majority element exists (one appearing more than n/2 times), this candidate is guaranteed to be it, and a second pass over the array verifies the count exceeds n/2 before returning it, since the vote alone does not check that a majority actually exists. Both passes are single linear scans and the only extra memory is the candidate and the counter, so the whole algorithm runs in O(n) time and O(1) extra space, exactly the bound the question asks for.

Structured elaboration

Why the vote finds the right candidate

Think of each occurrence of the eventual majority element as a "+1 vote" and every other element as a "-1 vote" against whatever the current candidate happens to be. Because the majority element appears more than n/2 times, its total positive contribution outweighs everything else combined, no matter how the non-majority elements are arranged. The counter resetting to zero and swapping candidates effectively cancels out one occurrence of the current candidate against one occurrence of something else, a kind of pairing-off. Since the true majority element has more occurrences than everything else put together, it can never be fully cancelled out: it always survives as the final candidate once all the cancellation has happened.

Why a verification pass is required

The vote procedure always produces SOME candidate, even when no true majority element exists at all. Consider an array with no repeated majority: the same cancel-and-replace dynamic still runs and still ends with some element left standing as "candidate," but that element might appear far less than n/2 times. The algorithm's guarantee is one-directional: IF a majority exists, the vote finds it; it says nothing about whether a majority exists in the first place. The second, verification pass counts the actual occurrences of the candidate and checks that count against n/2, which turns "a plausible candidate" into "a proven majority element" (or correctly reports that none exists).

Worked example

def majority_element(nums):
    candidate = None
    count = 0
    for x in nums:
        if count == 0:
            candidate = x
        count += 1 if x == candidate else -1
    verify_count = sum(1 for x in nums if x == candidate)
    if verify_count > len(nums) // 2:
        return candidate
    return None

nums1 = [2, 2, 1, 1, 1, 2, 2]
print(majority_element(nums1))

nums2 = [1, 2, 3, 4]
print(majority_element(nums2))

Output:

2
None

For [2, 2, 1, 1, 1, 2, 2] (length 7, so a majority needs more than 3 occurrences), 2 appears 4 times and the vote correctly settles on it. For [1, 2, 3, 4], every value appears exactly once, so no majority exists at all: the vote still produces SOME candidate internally as it runs, but the verification pass catches that its true count (1) does not exceed 4 // 2 = 2, and the function correctly returns None rather than a wrong answer.

Trade-offs and pitfalls

The most common mistake is skipping the verification pass entirely and trusting the vote's output unconditionally, which silently returns a wrong "majority" on any input where no true majority exists, exactly the [1, 2, 3, 4] case above. A second is resetting the counter to zero but forgetting to also update the candidate to the current element at that moment, which breaks the cancellation logic the whole proof depends on. This algorithm specifically finds an element appearing more than n/2 times; a different and looser problem, find any element appearing at least n/k times for some k > 2, needs the generalized Boyer-Moore voting scheme with k-1 candidate slots instead of one, not this exact two-variable version. The same vote-and-verify logic is unchanged in Java or JavaScript, since it only relies on equality comparison and increment/decrement.

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

Sort the intervals by their start value, then sweep through them once, keeping a running "last merged interval": if the next interval's start is at or before that interval's end (an overlap, or an exact touch), extend the running interval's end to cover it; otherwise, the next interval begins a new, separate merged interval. This is O(n log n) time, dominated entirely by the initial sort, and O(n) space for the output.

Structured elaboration

Why sort by start first. Without imposing an order, a single forward pass cannot be trusted to have already seen every interval that might overlap the one currently being examined; an interval appearing later in the input array could easily start earlier than one already processed. Sorting by start guarantees that once the sweep has moved past a given point, every remaining interval starts at or after it, which is exactly what makes a single linear sweep afterward sufficient.

The merge step itself. Initialize the output with the first (now sorted) interval. For each subsequent interval [s, e], compare s against the END of the last interval currently in the output. If s <= last.end, the two intervals overlap or exactly touch, so extend the last interval's end to max(last.end, e), using max rather than just assigning e directly, because a later interval can be fully NESTED inside the one already being extended (a smaller end than the current running interval), and assigning e unconditionally would incorrectly shrink coverage that the merged interval already legitimately spans. If s > last.end, there is a genuine gap, and [s, e] starts a new entry in the output.

Complexity. The sort is O(n log n) and dominates the total cost; the sweep afterward visits each interval exactly once, O(n). The output requires O(n) space in the worst case (no intervals overlap at all, so every input interval becomes its own output entry).

Touching versus overlapping, a design decision worth naming. Whether two intervals that exactly touch (one's end equals the next one's start, such as [1,4] and [4,5]) should merge is a real semantic choice, not an automatic consequence of the algorithm. Using <= in the overlap check treats a touch as mergeable (matching how meeting-room-style problems usually intend adjacency: back-to-back meetings occupy no coverage gap), while a strict < would keep them as separate, back-to-back intervals; a senior answer should state explicitly which convention is being used rather than leave it implicit.

Worked example

def merge_intervals(intervals):
    if not intervals:
        return []
    ordered = sorted(intervals, key=lambda pair: pair[0])
    merged = [list(ordered[0])]
    for start, end in ordered[1:]:
        last = merged[-1]
        if start <= last[1]:
            last[1] = max(last[1], end)
        else:
            merged.append([start, end])
    return merged

print(merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]))

# Independent cross-check: a genuinely different method (an event-counting sweep
# line) rather than a second copy of the same merge logic.
def sweep_line_reference(intervals):
    if not intervals:
        return []
    events = []
    for s, e in intervals:
        events.append((s, 0, 1))   # start: delta +1, processed before ends at same coord
        events.append((e, 1, -1))  # end:   delta -1
    events.sort()
    result = []
    active = 0
    run_start = None
    for pos, _, delta in events:
        if active == 0 and delta == 1:
            run_start = pos
        active += delta
        if active == 0:
            result.append([run_start, pos])
    return result

import random
random.seed(3)
hand_picked = [
    [[1, 4], [4, 5]],             # touching intervals
    [[5, 8], [1, 3]],             # unsorted input
    [[2, 5], [1, 10]],            # fully nested interval
    [[1, 2]],                     # single interval
    [],                           # empty input
    [[5, 6], [1, 2]],             # unsorted, non-overlapping
    [[1, 3], [2, 6], [8, 10], [15, 18]],
]
mismatches = 0
for tc in hand_picked:
    if merge_intervals(tc) != sweep_line_reference(tc):
        mismatches += 1
for _ in range(3000):
    n = random.randint(1, 6)
    intervals = [[a, a + random.randint(0, 5)] for a in (random.randint(0, 15) for _ in range(n))]
    if merge_intervals(intervals) != sweep_line_reference(intervals):
        mismatches += 1
print(f"7 hand-picked cases + 3000-trial random sweep (seed 3): mismatches = {mismatches}")

Output:

[[1, 6], [8, 10], [15, 18]]
7 hand-picked cases + 3000-trial random sweep (seed 3): mismatches = 0

matching the question's own example exactly: [1,3] and [2,6] overlap (2 <= 3) and merge into [1,6]; [8,10] and [15,18] each start after the previous merged interval's end, so they remain separate. This was additionally cross-checked against the independently-implemented sweep-line reference above (treating each interval as a +1/-1 event at its start/end and rebuilding runs where the event count returns to zero), which is a genuinely different method rather than a second copy of the same merge logic, on 7 hand-picked cases (touching intervals, unsorted input, a fully nested interval, a single interval, empty input, and unsorted non-overlapping intervals) plus a 3,000-trial random sweep (seed 3); the printed line confirms zero mismatches across all of it, giving real cross-validation rather than testing the code against itself.

Trade-offs and pitfalls

The most consequential bug is assigning last[1] = end directly instead of last[1] = max(last[1], end) when merging: this passes every test case where intervals only partially overlap or extend each other, and only fails on a fully nested interval, which is easy to omit from a quick manual test set and then breaks silently in production by shrinking coverage that should have been preserved. A second common bug is skipping the initial sort, either because the candidate assumes input is already given in start order (sample inputs in problem statements are often, misleadingly, already sorted) or forgets that an unsorted input makes a single forward sweep unreliable; always sort explicitly rather than relying on an assumption about input order. Finally, treat the touching-versus-overlapping boundary as a decision to state out loud (<= merges touching intervals, < does not) rather than an arbitrary implementation detail, since which one is correct depends on what the intervals represent.

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.