Arrays, Strings, and Hashing Questions

Direct answer

A straightforward recursive flatten walks the nested structure, recursing into every sub-list and appending every non-list element directly to the result. It is correct and easy to read, but its recursion depth equals the input's NESTING depth, not its total element count, so an extremely deeply nested input (thousands of levels of [[[...]]]) can exceed the language's recursion limit and crash with a stack overflow, even though the total amount of data is tiny. An iterative version using an explicit stack does the identical traversal without ever growing the call stack, and handles arbitrary nesting depth safely.

Structured elaboration

The recursive approach

For each item in the input list: if it is itself a list, recursively flatten it and extend the result with what comes back; otherwise, append it directly. This mirrors the problem's own recursive structure (a nested list is either an element or a list of nested lists) almost exactly, which is why it reads so naturally, but that same one-to-one mirroring is exactly what ties its stack depth to the input's nesting depth.

Why recursion depth is the real concern here

Python's default recursion limit, retrievable via sys.getrecursionlimit(), is 1000. This limit exists to protect the underlying interpreter stack from being exhausted, which would crash the process outright rather than raising a catchable Python exception; the recursion limit is what turns that hard crash into a catchable RecursionError instead. A list nested 1500 levels deep, [[[...[1]...]]], has only a single element, but flattening it recursively requires 1500 nested calls, comfortably past the default limit, so the recursive version raises RecursionError on an input that is trivially small in terms of total data.

The iterative alternative with an explicit stack

Replace the call stack with an explicit Python list acting as a stack, where each stack entry is an ITERATOR over one level of nesting rather than a raw list. Repeatedly pull the next item from the iterator at the top of the stack: if it is a list, push an iterator over IT onto the stack and continue; if it is a plain element, append it to the result; if the top iterator is exhausted, pop it off and continue with whatever is now on top. This performs the exact same traversal as the recursive version, but the "depth" it tracks lives on the heap (as entries in the stack list), bounded only by available memory, not by the interpreter's fixed recursion limit.

Worked example

import sys

def flatten(nested):
    result = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

def flatten_iterative(nested):
    result = []
    stack = [iter(nested)]
    while stack:
        top = stack[-1]
        try:
            item = next(top)
        except StopIteration:
            stack.pop()
            continue
        if isinstance(item, list):
            stack.append(iter(item))
        else:
            result.append(item)
    return result

example = [1, [2, [3, 4], 5], 6]
print(flatten(example))
print(flatten_iterative(example))

depth = sys.getrecursionlimit() + 500
deeply_nested = 1
for _ in range(depth):
    deeply_nested = [deeply_nested]

try:
    flatten(deeply_nested)
    print("recursive: no error")
except RecursionError:
    print("recursive: RecursionError")

print("iterative:", flatten_iterative(deeply_nested))

Output:

[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
recursive: RecursionError
iterative: [1]

Both implementations agree exactly on the question's own example, [1, [2, [3, 4], 5], 6] -> [1, 2, 3, 4, 5, 6]. The recursion-depth concern is demonstrated directly, not just asserted: building a list nested 500 levels past the default recursion limit and flattening it recursively does raise RecursionError (confirmed against Python's default limit of 1000), while the iterative version flattens the exact same deeply nested input to [1] without any error.

Trade-offs and pitfalls

Raising sys.setrecursionlimit() to a larger number is a tempting quick fix, but it does not remove the underlying risk, it only moves the crash point further out, and pushing it too far can crash the whole PROCESS with a C-level stack overflow instead of a catchable Python exception, since the interpreter's own limit exists specifically to stay within the real stack memory available. The iterative version is the more ROBUST general answer for this reason: it trades a small amount of code complexity, managing an explicit stack of iterators rather than relying on the language's call stack, for a traversal that cannot fail on input shape alone, only on genuinely running out of memory. Also worth naming: neither version currently guards against a value that is directly self-referential (a list containing itself), which would recurse or loop forever regardless of which approach is used; that is a distinct edge case from nesting depth and would need explicit cycle detection if the input could ever be adversarial or attacker-controlled rather than merely deeply nested.

Direct answer

Read the input in fixed-size chunks (not the whole stream at once), strip any whitespace or newlines from each chunk, and only decode the largest prefix of accumulated characters that is a multiple of 4 (one base64 "quantum"). Carry the leftover 0-3 characters forward to be combined with the next chunk. This bounds memory use to the chunk size regardless of how large the input stream is, and correctly reproduces the standard library's own base64.b64decode output on the full data.

Structured elaboration

Why a naive whole-input decode does not work here: base64.b64decode (and equivalents in other languages) requires the entire encoded string in memory first. The question explicitly asks for constant extra memory proportional to block size, so the decode has to happen incrementally as bytes arrive.

The three things that make streaming base64 harder than streaming raw bytes:

1. Base64 decodes in fixed-size groups of 4 encoded characters to 3 raw bytes. You cannot decode a partial group, so any chunk boundary that splits a group of 4 has to be handled by holding the incomplete tail back and prepending it to the next chunk.
2. Whitespace and newlines are not part of the base64 alphabet but commonly appear in real-world encoded data (classic MIME-style line wrapping at 76 characters, for example). These must be filtered out per chunk, not just once at the start, since they can appear anywhere.
3. Padding (=) only ever appears at the very end of the full encoded string, so it naturally falls out of the last "leftover" group processed, no special-casing is needed beyond decoding whatever is left when the stream ends.

Algorithm:

• Maintain a small leftover byte buffer (0 to 3 bytes) carried between reads.
• On each read of block_size bytes: strip whitespace, prepend leftover, decode the largest prefix that is a multiple of 4, write the decoded bytes to the output stream, and save the remainder as the new leftover.
• After the input is exhausted, decode any final leftover (a well-formed base64 stream always leaves a multiple-of-4 remainder including padding at the true end).

Worked example

import base64

def streaming_b64_decode(in_stream, out_stream, block_size=4096):
    assert block_size % 4 == 0, "block_size must be a multiple of 4"
    leftover = b""
    while True:
        raw = in_stream.read(block_size)
        if not raw:
            break
        if isinstance(raw, str):
            raw = raw.encode("ascii")
        cleaned = bytes(c for c in raw if c not in b" \t\r\n")
        chunk = leftover + cleaned
        usable_len = (len(chunk) // 4) * 4
        usable, leftover = chunk[:usable_len], chunk[usable_len:]
        if usable:
            out_stream.write(base64.b64decode(usable))
    if leftover:
        out_stream.write(base64.b64decode(leftover))

# Pinned verification: random payloads of varying sizes, MIME-style 76-char line
# wrapping injected to exercise whitespace handling, decoded with an artificially
# small block_size=8 to force many chunk boundaries, compared byte-for-byte
# against base64.b64decode() run on the whole un-streamed input.
import io, random
random.seed(1234)

def make_test_payload(n_bytes):
    return bytes(random.randrange(0, 256) for _ in range(n_bytes))

for n in [0, 1, 2, 3, 4, 100, 1000, 12345]:
    payload = make_test_payload(n)
    encoded = base64.b64encode(payload)
    wrapped = b"\n".join(encoded[i:i+76] for i in range(0, len(encoded), 76))
    in_buf, out_buf = io.BytesIO(wrapped), io.BytesIO()
    streaming_b64_decode(in_buf, out_buf, block_size=8)
    decoded = out_buf.getvalue()
    reference = base64.b64decode(encoded)
    print(f"n_bytes={n:6d} encoded_len={len(wrapped):6d} matches_reference={decoded == reference == payload}")

Output:

n_bytes=     0 encoded_len=     0 matches_reference=True
n_bytes=     1 encoded_len=     4 matches_reference=True
n_bytes=     2 encoded_len=     4 matches_reference=True
n_bytes=     3 encoded_len=     4 matches_reference=True
n_bytes=     4 encoded_len=     8 matches_reference=True
n_bytes=   100 encoded_len=   137 matches_reference=True
n_bytes=  1000 encoded_len=  1353 matches_reference=True
n_bytes= 12345 encoded_len= 16676 matches_reference=True

Every case, including the empty input and inputs whose length is not a multiple of 3 (which is exactly what produces = padding), matched the standard library's non-streaming decoder exactly.

Trade-offs & pitfalls

• block_size must be a multiple of 4. If it is not, the "largest usable multiple of 4" logic still works correctly (it is computed dynamically from the accumulated chunk, not assumed from block_size directly), but choosing a multiple of 4 up front avoids an unnecessary one-off adjustment and keeps the memory bound exactly predictable.
• The leftover buffer is the entire reason this works, and it is easy to get wrong by resetting it every read instead of carrying it forward. That specific bug silently corrupts output only when a chunk boundary happens to fall mid-group, which makes it easy to miss with small test inputs that fit in a single chunk.
• Memory is bounded by chunk size, not stream size, which is the whole point for very large files, but this means you cannot validate the base64 alphabet or overall structure ahead of time the way an in-memory decode implicitly does; invalid characters are only caught when base64.b64decode raises on the chunk containing them, so error messages will reference a chunk-relative position, not a position in the original stream, unless you track a running byte offset yourself.
• This does not parallelize trivially. Because state (the leftover bytes) carries across chunks, you cannot decode arbitrary byte ranges independently the way you could with a format that has self-describing block boundaries; splitting work across threads requires aligning split points to 4-character boundaries first.

Direct answer

When the items themselves (like token dictionaries) aren't hashable, derive a hashable canonical key from each item's content, use that key in a seen-set for O(1) membership checks, and keep appending original items to the output in scan order exactly as with the hashable case. For datasets too large to hold in memory at once, the only state that needs to persist across chunks is that seen-set of keys, which lets the same logic run incrementally over a stream without ever materializing the whole dataset.

Building a canonical key for an unhashable item

A dict is unhashable because it's mutable, but its content can be turned into something hashable: json.dumps(obj, sort_keys=True) serializes a dict to a string with keys in a fixed order, so two dicts with identical content but different insertion order ({"text": "the", "pos": "DET"} vs {"pos": "DET", "text": "the"}) produce the identical key string and are correctly treated as duplicates. This assumes the values are themselves JSON-serializable (nested dicts/lists work, since sort_keys recurses; a value like a raw NumPy array or a custom object would need its own serialization rule first).

import json

def canonical_key(obj):
    return json.dumps(obj, sort_keys=True)

def dedupe_preserve_order(items):
    seen = set()
    result = []
    for item in items:
        key = canonical_key(item)
        if key not in seen:
            seen.add(key)
            result.append(item)
    return result

Adapting for extremely large datasets processed in chunks or streaming

The dedup logic doesn't change; what changes is that the input arrives as an iterable of chunks rather than one in-memory list, and the function becomes a generator so it never needs to hold more than the current chunk plus the running seen set in memory at once:

def dedupe_preserve_order_streaming(chunks):
    seen = set()
    for chunk in chunks:
        for item in chunk:
            key = canonical_key(item)
            if key not in seen:
                seen.add(key)
                yield item

Worked example

tokens = [
    {"text": "the", "pos": "DET"},
    {"pos": "DET", "text": "the"},   # same content, different key order -> duplicate
    {"text": "cat", "pos": "NOUN"},
    {"text": "the", "pos": "DET"},   # exact duplicate
    {"text": "sat", "pos": "VERB"},
]
print(dedupe_preserve_order(tokens))

chunk_a = [{"text": "the", "pos": "DET"}, {"text": "cat", "pos": "NOUN"}]
chunk_b = [{"pos": "DET", "text": "the"}, {"text": "sat", "pos": "VERB"}]
chunk_c = [{"text": "sat", "pos": "VERB"}, {"text": "mat", "pos": "NOUN"}]
print(list(dedupe_preserve_order_streaming([chunk_a, chunk_b, chunk_c])))

Output (verified by execution):

[{'text': 'the', 'pos': 'DET'}, {'text': 'cat', 'pos': 'NOUN'}, {'text': 'sat', 'pos': 'VERB'}]
[{'text': 'the', 'pos': 'DET'}, {'text': 'cat', 'pos': 'NOUN'}, {'text': 'sat', 'pos': 'VERB'}, {'text': 'mat', 'pos': 'NOUN'}]

The key-order-independence is confirmed directly: {"text": "the", "pos": "DET"} and {"pos": "DET", "text": "the"} are the same content in different insertion order, and both are correctly collapsed into a single kept occurrence, the first one, with the original dict shape preserved in the output (not the canonical JSON string). The streaming version, run across three separate chunks, produces exactly the same sequence as running the whole-input version on the concatenation of all three chunks, confirming that splitting the input into chunks doesn't change the result as long as the seen set is the one piece of state carried across chunk boundaries.

Trade-offs and pitfalls

• The seen set itself still grows with the number of distinct items, which is the real scaling limit. Chunking solves "the raw dataset doesn't fit in memory," but if the number of distinct keys is itself enormous (billions of unique tokens), the seen-set can become the new bottleneck. At that point the standard move is to accept approximate membership testing (a probabilistic structure that trades a small, bounded false-positive rate for sublinear memory), which is a different data structure than the exact-membership techniques covered here and belongs to the hash-table-internals side of the boundary between basic hashing techniques and hash-table design; naming it here as the next escalation point rather than implementing it is the honest answer once genuinely billions-scale.
• json.dumps(sort_keys=True) is not free: it's O(size of the item) per item, and for very large or deeply nested items this serialization cost can dominate; a cheaper but riskier alternative is hashing a canonical tuple representation directly (e.g., tuple(sorted(obj.items())) recursively) to avoid string formatting overhead, at the cost of more code to handle nested structures correctly.
• Streaming changes what "preserve order" can mean: within a single chunk, order is preserved as before; across chunks, the output order is chunk-arrival order, which is the only sensible definition once the whole dataset is never resident in memory simultaneously to be reordered globally.
• Common wrong turn: converting each dict to a frozenset(obj.items()) for hashing. This looks reasonable but silently breaks on nested unhashable values (a dict value inside the item) and, more subtly, changes semantics for numeric-vs-string key confusion in a way that a sorted JSON string does not, since JSON serialization is explicit about type.

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

An array gives O(1) random access because an index maps directly to a memory address via arithmetic, but inserting or deleting anywhere except the very end requires shifting every following element, an O(n) operation. A singly linked list gives O(1) insert or delete once you already hold a reference to the relevant node, but finding that node in the first place (including "the middle") costs O(n), since there is no arithmetic shortcut, only following pointers one at a time.

Structured elaboration

• The "O(1) insert" caveat, worth stating explicitly. A linked-list insert or delete is only O(1) when you ALREADY have a reference to the right node, typically because you're iterating and acting as you go. If you're only given a numeric position (say, "insert at index 500,000"), you still have to walk there first, which costs O(n); claiming a flat "O(1) insert" without that condition is the single most common oversimplification of this comparison.
• Concrete scenario favoring the array. A lookup table mapping millions of user IDs to profile records, queried by index or key extremely frequently: O(1) random access is the whole point, and the data is rarely inserted into at arbitrary positions.
• Concrete scenario favoring the linked list. An eviction-order list for a cache, where an arbitrary, already-known node is frequently removed from the middle and a new node re-inserted at the front; both operations are O(1) once you hold the node reference, with no shifting cost regardless of list size.

Worked example

Consider inserting one new element at the FRONT of a collection holding 1,000,000 items. On an array, every one of the 1,000,000 existing elements must shift one position to make room, an O(n) cost that scales with however large the array has grown. On a singly linked list, the operation is exactly two pointer writes (the new node's next pointer, and the head pointer), regardless of whether the list holds 10 elements or 10,000,000: the cost does not grow with list size at all. This is the concrete shape of the O(n)-versus-O(1) difference in the table above, not just an abstract notation.

Trade-offs & pitfalls

• Memory overhead and cache locality. Each linked-list node carries at least one extra pointer (8 bytes on a 64-bit system) beyond its payload, and nodes are not stored contiguously in memory. For an iteration-heavy workload, an array is often noticeably faster IN PRACTICE despite both being asymptotically O(n), because sequential array access is cache-friendly while pointer-chasing a linked list typically is not; this is a constant-factor, hardware-driven effect, not a difference in asymptotic complexity.
• The most common oversimplification is stating "linked-list insert/delete is O(1)" without the caveat that this assumes the relevant node reference is already in hand; always confirm whether the scenario gives you the node or just a position.
• Singly linked lists only walk forward. Anything that needs "delete the node before this one" or other backward movement needs either a doubly linked list, or tracking a trailing pointer while iterating forward.
• Don't confuse this with dynamic-array append. A dynamic array (Python's list, Java's ArrayList) amortizes appending at the END to O(1) via geometric growth, which is a different operation from inserting at an ARBITRARY position; conflating the two is a common mistake when reasoning about array costs.