Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

A plain stack already gives $O(1)$ push, pop, and top because those operations only ever touch the top element. The trick for $O(1)$ minimum retrieval is to keep a second, parallel stack that tracks what the minimum would be after each push: whenever you push a value onto the main stack, you also push the smaller of that value and the previous minimum onto the min-stack, so its top is always the correct current minimum, and popping both stacks together keeps them in sync without ever rescanning.

Approach

• Maintain two stacks of equal length at all times: stack holds the real values, min_stack holds, at each position, what the minimum was after that push.
• push(x): append x to stack. Append x to min_stack if min_stack is empty or x is less than or equal to its current top; otherwise append the current top again (repeating the still-current minimum).
• pop(): pop from both stacks together; the value from stack is returned, the value from min_stack is discarded.
• get_min(): return min_stack's top directly.

class MinStack:
    def __init__(self):
        self.stack: list[int] = []
        self.min_stack: list[int] = []

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)
        else:
            self.min_stack.append(self.min_stack[-1])

    def pop(self) -> int:
        if not self.stack:
            raise IndexError("pop from empty stack")
        self.min_stack.pop()
        return self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def get_min(self) -> int:
        return self.min_stack[-1]


if __name__ == "__main__":
    s = MinStack()
    s.push(5)
    s.push(3)
    s.push(7)
    print(s.get_min())  # 3
    s.pop()
    print(s.get_min())  # 3
    s.pop()
    print(s.get_min())  # 5
    print(s.top())       # 5

Running this prints 3, 3, 5, 5: after pushing 5, 3, 7 the minimum is 3; popping 7 (the top) leaves the minimum still 3; popping 3 next leaves only 5, so both the minimum and the top become 5.

Key points

• Using <= (not strict <) when deciding whether to push a new minimum is what makes duplicate minimum values work correctly: if two entries tie for the minimum and you only recorded the first, popping it would incorrectly raise the recorded minimum before the still-present duplicate is gone.
• An alternative "encoded delta" trick stores a single stack, keeping only a running minimum variable, and pushes a value relative to that minimum instead of the raw value, updating the running minimum on push/pop as needed. It roughly halves auxiliary storage but is more error-prone to implement correctly, especially in fixed-width-integer languages (C++, Java) where the encoded delta itself can overflow if the gap between the pushed value and the previous minimum is large.

Complexity

Time: $O(1)$ for every operation (push, pop, top, get_min). Space: $O(n)$ auxiliary for $n$ elements (two stacks, each up to size $n$; a larger constant factor than a single stack, but still linear).

Edge cases

• pop or top on an empty stack should raise or otherwise signal an error rather than reading past the end.
• Duplicate values at the current minimum: handled correctly only if the min-stack push condition uses <=, not <.
• A single-element stack: get_min() must equal top().

Direct answer

Both strategies handle two keys hashing to the same bucket, but they store the overflow differently. Separate chaining keeps a small list (or similar container) at each bucket, so a collision just means appending to that bucket's list; insert, lookup, and delete all cost $O(1)$ on average. Open addressing instead keeps every entry directly in the single backing array, and on a collision probes a deterministic sequence of other slots (linear probing tries the next slot each time; quadratic probing tries slots at increasing squared offsets) until it finds an empty one. This keeps memory compact and cache-friendly, but makes delete trickier: removing an entry by simply clearing its slot can break the probe chain for entries that were placed after it.

Structured elaboration

Insert, lookup, delete, side by side

Load factor and resizing

Load factor $\alpha = \dfrac{n}{m}$ (n entries, m slots) governs both strategies' health. Chaining degrades gracefully as $\alpha$ rises past 1, since the expected cost per lookup is $O(1 + \alpha)$: the average list length just grows linearly with $\alpha$. Open addressing degrades sharply as $\alpha$ approaches 1, since probe sequences get long and clusters grow, so implementations typically resize (allocate a bigger table, commonly doubling it, and rehash every entry) once $\alpha$ crosses a fixed threshold, often around 0.7 for open addressing, versus a looser threshold for chaining since it tolerates a higher load factor before performance visibly suffers.

Why quadratic probing exists

Linear probing (always try the next slot) causes primary clustering: once a run of occupied slots forms, it tends to grow, since anything hashing into that run has to probe past all of it. Quadratic probing spreads probe offsets out (offsets $0, 1, 4, 9, \ldots$ from the original hash) to reduce, though not eliminate, that clustering; the trade-off is that not every slot in the table is guaranteed reachable unless the table size and probing constants are chosen carefully.

Worked example

A table of size $m = 8$ with a resize threshold of $\alpha = 0.75$ triggers a resize once $n$ would exceed $0.75 \times 8 = 6$ entries, i.e., on the 7th insert. After doubling, the new table has $m = 16$ slots and the same threshold now allows up to $0.75 \times 16 = 12$ entries before the next resize. This is the same amortized (averaged over a sequence of operations) argument as a doubling dynamic array: the expensive full-table rehash happens rarely enough, relative to the cheap inserts between resizes, that insert stays $O(1)$ amortized even though a single insert that triggers a resize costs $O(n)$.

Trade-offs & pitfalls

• Chaining costs extra memory per entry for list-node overhead, but tolerates a high load factor and makes deletion simple; a poorly-distributed hash function can degrade one bucket to $O(k)$ for that bucket's $k$ entries (worst case $O(n)$ if everything collides), which some standard library implementations guard against by converting a sufficiently long chain into a balanced tree.
• Open addressing has excellent cache locality (everything contiguous in one array) and no per-entry pointer overhead, but needs a lower load factor to avoid probe-length blowup, and its deletions need tombstones, which themselves need periodic cleanup: enough accumulated tombstones can make a lookup scan nearly the whole table before it reaches a truly empty slot.
• The most common wrong turn on open addressing: deleting an entry by clearing its slot outright. That "empty" slot is exactly the signal that stops a probe search, so a lookup for a different key that was displaced past the deleted slot will wrongly conclude that key isn't present, even though it's still sitting further along the probe chain.

Direct answer

Push every opening bracket onto a stack. On a closing bracket, it must match whatever opener currently sits on top of the stack; if it does not, or the stack is already empty, the string is invalid. After the scan, the string is valid only if the stack is empty, meaning every opener found a partner. This runs in $O(n)$ time and $O(n)$ space.

Structured elaboration

A stack models "the most recently opened, still-unclosed bracket" exactly, because it is last-in-first-out (LIFO): whichever opener was pushed most recently is always the one that must be closed next, and that is precisely what sits on top. Checking a closer against the top of the stack is an $O(1)$ lookup through a small mapping () pairs with (, ] with [, } with {).

Counting bracket types separately (how many ( versus how many )) is not enough: a string can have perfectly equal counts of every bracket type and still be invalid because the nesting order is wrong, for example ([)]. Only a structure that remembers order, like a stack, can catch that.

Worked example

def is_valid_brackets(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack: list[str] = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
    return not stack


if __name__ == "__main__":
    tests = ["()[]{}", "(]", "([)]", "{[]}"]
    print([is_valid_brackets(t) for t in tests])

Running this prints [True, False, False, True]. Trace ([)]: push (, push [, then see ); the top of the stack is [, which does not pair with ), so the function returns False immediately, even though the overall bracket counts are balanced.

Complexity

Time: $O(n)$, one pass over the string doing $O(1)$ work per character.
Space: $O(n)$ worst case, since a string of all opening brackets pushes every character onto the stack before the scan ends.

Edge cases

• Empty string: the stack never receives a push, so it is empty at the end and the function correctly returns True.
• A lone unmatched opening bracket at the very end: the stack is non-empty when the scan finishes, so the final not stack check (not just the per-character comparisons) is what catches it.
• A closing bracket with nothing open: stack is empty when a closer arrives, so the code must check not stack before indexing stack[-1], or it raises instead of returning False cleanly.

Trade-offs & pitfalls

Using a single stack with a pairs mapping generalizes cleanly to any number of bracket types; writing a separate counter per bracket type cannot detect ordering violations no matter how many counters you add.

Direct answer

Size each field to the minimum number of bits its actual value range needs, then pack them into one machine word using explicit shifts and masks: here, a 6-bit sensor ID, 4 boolean flags, a 10-bit unsigned humidity, and a 12-bit signed temperature add up to exactly $6 + 4 + 10 + 12 = 32\ \text{bits} = 4\ \text{bytes}$, one 32-bit word. Giving each field its own natural type instead (int16_t temperature, uint16_t humidity, uint8_t flags, uint8_t sensor_id, since the 10-bit and 12-bit ranges don't fit in a byte) costs $2 + 2 + 1 + 1 = 6\ \text{bytes}$, so packing saves roughly a third of the memory per record, at the cost of a shift, a mask, and (for the signed field) a sign-extension on every access, plus explicit handling of endianness and alignment that a per-field layout would otherwise get almost for free from the compiler.

Structured elaboration

Approach

• Budget bits from value ranges, not from convenient type widths: sensor_id 0..63 needs 6 bits; 4 independent boolean flags need 4 bits; humidity 0..1023 (tenths of a percent) needs 10 bits; temperature -2048..2047 (tenths of a degree, two's complement) needs 12 bits.
• Fix a layout, most significant bit (MSB) to least significant bit (LSB): [ sensor_id(6) | flags(4) | humidity(10) | temperature(12) ], packed into a uint32_t.
• Use explicit shifts and masks, not C bitfields (struct { unsigned id:6; ... };). The C standard leaves bitfield bit order, padding, and even the underlying storage's byte order implementation-defined, so two compilers, or two build configurations of the same compiler, can legally lay the same bitfield struct out differently. That is fatal for a format one device writes and another reads, or a format that has to survive a firmware update on the same device.
• Decouple the wire format from host byte order. Pick one byte order for storage (big-endian here) and convert to and from it explicitly with byte-at-a-time helpers, so the packed record is portable between a little-endian microcontroller and a big-endian one, and safe to store in flash and reread after the code around it has been relinked at a different address.

#include <stdint.h>

#define SENSOR_ID_MASK 0x3Fu
#define FLAGS_MASK     0x0Fu
#define HUM_MASK       0x3FFu
#define TEMP_MASK      0xFFFu

typedef struct {
    int16_t  temperature;
    uint16_t humidity;
    uint8_t  flags;
    uint8_t  sensor_id;
} sensor_record_t;

static uint32_t pack_record(const sensor_record_t *r) {
    uint32_t temp = (uint32_t)((uint16_t)r->temperature) & TEMP_MASK;
    uint32_t hum  = (uint32_t)r->humidity & HUM_MASK;
    uint32_t flg  = (uint32_t)r->flags & FLAGS_MASK;
    uint32_t id   = (uint32_t)r->sensor_id & SENSOR_ID_MASK;
    return (id << 26) | (flg << 22) | (hum << 12) | temp;
}

static void unpack_record(uint32_t packed, sensor_record_t *out) {
    out->sensor_id = (uint8_t)((packed >> 26) & SENSOR_ID_MASK);
    out->flags     = (uint8_t)((packed >> 22) & FLAGS_MASK);
    out->humidity  = (uint16_t)((packed >> 12) & HUM_MASK);
    uint32_t t = packed & TEMP_MASK;
    if (t & (1u << 11)) t |= ~TEMP_MASK;   /* sign-extend the 12-bit field */
    out->temperature = (int16_t)t;
}

static void write_be32(uint8_t *buf, uint32_t v) {
    buf[0] = (uint8_t)(v >> 24); buf[1] = (uint8_t)(v >> 16);
    buf[2] = (uint8_t)(v >> 8);  buf[3] = (uint8_t)(v);
}

static uint32_t read_be32(const uint8_t *buf) {
    return ((uint32_t)buf[0] << 24) | ((uint32_t)buf[1] << 16) |
           ((uint32_t)buf[2] << 8)  | (uint32_t)buf[3];
}

#include <stdio.h>
int main(void) {
    sensor_record_t original = { .temperature = -137, .humidity = 612, .flags = 0b1010, .sensor_id = 41 };
    uint32_t packed = pack_record(&original);
    uint8_t wire[4];
    write_be32(wire, packed);
    printf("packed word: 0x%08X\n", packed);
    printf("wire bytes: %02X %02X %02X %02X\n", wire[0], wire[1], wire[2], wire[3]);

    sensor_record_t decoded;
    unpack_record(read_be32(wire), &decoded);
    printf("decoded: temperature=%d humidity=%u flags=%u sensor_id=%u\n",
           decoded.temperature, decoded.humidity, decoded.flags, decoded.sensor_id);
    printf("roundtrip match: %s\n",
           (decoded.temperature == original.temperature && decoded.humidity == original.humidity &&
            decoded.flags == original.flags && decoded.sensor_id == original.sensor_id) ? "yes" : "no");
    printf("sizeof(packed word) = %zu bytes\n", sizeof(packed));
    printf("sizeof(sensor_record_t one-field-per-byte-ish struct) = %zu bytes\n", sizeof(sensor_record_t));
    return 0;
}

Key points

• Each mask isolates exactly one field's bit width: & 0x3F (6 bits), & 0xF (4 bits), & 0x3FF (10 bits), & 0xFFF (12 bits).
• Reading a signed sub-word field needs manual sign extension: if the field's own sign bit is set (bit 11 of the 12-bit temperature), OR in the complement of that field's mask to fill the high bits with ones before casting to the wider signed type.
• The wire format and the in-memory format are deliberately separate: pack_record/unpack_record work on a host uint32_t, and write_be32/read_be32 convert that to and from a fixed big-endian byte sequence, so host byte order never leaks into what's actually stored.

Worked example

Packing { temperature: -137, humidity: 612, flags: 0b1010, sensor_id: 41 } and running it through pack_record then write_be32, then back through read_be32 and unpack_record, prints:

packed word: 0xA6A64F77
wire bytes: A6 A6 4F 77
decoded: temperature=-137 humidity=612 flags=10 sensor_id=41
roundtrip match: yes
sizeof(packed word) = 4 bytes
sizeof(sensor_record_t one-field-per-byte-ish struct) = 6 bytes

The decoded values match the originals exactly, including the negative temperature surviving the sign-extension step, and the measured struct sizes (4 bytes packed vs 6 bytes unpacked, no padding needed in the unpacked layout on this build) confirm the memory-savings claim above with real numbers rather than an assumed one.

Trade-offs & pitfalls

Complexity / cost trade-off

Memory: $\frac{6 - 4}{6} \approx 33\%$ smaller per record, which barely matters for one record but is the entire point once you're buffering thousands of records in RAM or writing millions to flash. CPU: every packed-field access costs a shift plus a mask (and, for the signed field, a conditional sign-extend) versus a single load for a per-byte layout; on a modern 32-bit microcontroller these are single-cycle arithmetic logic unit (ALU) operations and are negligible next to typical sensor sampling rates, though a very tight, very high-frequency interrupt handler is worth measuring rather than assuming.

Edge cases

• Endianness: casting a raw uint8_t buf[4] directly to a uint32_t * and dereferencing it bakes in host byte order; a record written on a little-endian device and read on a big-endian one would silently corrupt every field. The explicit byte-at-a-time read_be32/write_be32 pair avoids this entirely.
• Alignment: many 32-bit microcontrollers fault on an unaligned multi-byte load, for example reading a uint32_t from an address that isn't a multiple of 4. Because this design only ever touches the byte buffer one byte at a time (through read_be32/write_be32) and only forms a uint32_t value in a local variable, it stays safe even when the 4-byte buffer itself isn't naturally aligned in flash; a naive pointer cast to uint32_t * would not be.
• Sign-extension bugs: forgetting the sign-extend step turns any negative reading into a large positive number once the top bit of the 12-bit field is masked out and left there; testing at least one negative value, as this example does with -137, catches this immediately.
• Flag drift: since the 4 flag bits are distinguished only by position, name each one with an explicit constant (for example FLAG_CALIBRATED = 1 << 0) rather than magic numbers, or a later firmware revision that reorders them silently breaks every record written by the previous version.

Direct answer

Walk the list once, and at each node redirect its next reference back to the previous node before advancing, using three tracking references: previous, current, and a temporary save of current's original next. This is $O(n)$ time and $O(1)$ space. A recursive version expresses the identical rewiring, handling everything after the current node first and then flipping the one link back, but it pays for that with $O(n)$ call-stack space that the iterative version does not need.

Structured elaboration

The iterative three-pointer dance. Before overwriting curr.next, save it in a temporary variable, or the rest of the list is lost permanently. Then point curr.next back at prev, advance prev to curr, and advance curr to the saved temporary. Repeat until curr is empty.

The recursive version. The base case is an empty list or a single remaining node, which is already "reversed" as-is. Otherwise, recursively reverse everything after the head first; that recursive call returns the new head of the whole reversed list. Then head.next.next = head flips the one link connecting the old head back into the newly-reversed remainder, and head.next = None prevents the old head from accidentally pointing at itself in a two-node cycle.

What language a solution is written in does not change any of this. The reskin into Python, JavaScript, Swift, or Kotlin, or building the linked-list node class from scratch first, is the same pointer-rewiring skill underneath; only the syntax for holding and dereferencing a reference changes, not the three-step relinking logic itself.

Worked example

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


def reverse_iterative(head):
    prev = None
    curr = head
    while curr:
        next_tmp = curr.next  # save before overwriting
        curr.next = prev
        prev = curr
        curr = next_tmp
    return prev


def reverse_recursive(head):
    if head is None or head.next is None:
        return head
    new_head = reverse_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head


def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out


def build_list(vals):
    dummy = Node(0)
    tail = dummy
    for v in vals:
        tail.next = Node(v)
        tail = tail.next
    return dummy.next


if __name__ == "__main__":
    print(to_list(reverse_iterative(build_list([1, 2, 3, 4]))))
    print(to_list(reverse_recursive(build_list([1, 2, 3, 4]))))

Running this prints [4, 3, 2, 1] twice, once from each implementation.

Complexity

Time: $O(n)$ for both the iterative and recursive versions, since each one visits every node exactly once.
Space: $O(1)$ extra for the iterative version (three pointer variables regardless of list length); $O(n)$ for the recursive version, from the call stack, since the recursion descends one frame per node before any relinking happens.

Edge cases

• Empty list (head is None): both versions return None immediately without any relinking.
• Single-node list: both versions return that same node unchanged as the new head, since there is nothing to reverse.
• Very long list: the recursive version risks an actual stack overflow, since typical call-stack depth limits are far smaller than what a linked list can otherwise hold in memory.

Trade-offs & pitfalls

The recursive version risks an actual stack overflow on a very long list in production, not just an academic concern, since typical call-stack depth limits are far smaller than what a linked list or array can otherwise hold in memory. The single most common bug in the iterative version is forgetting to save curr.next before overwriting it, which permanently disconnects the rest of the list from anything still reachable.