Data Structures

Block-Based Deque

Difficulty

Asked at Citadel Securities

Theory: Data Structures You Implement, Not Import

Read the problem, hints and solution here. The editor needs a bigger screen: open this page on a laptop to write and run your code.

Available in C++ and Python. You are solving it in Python. Switch to C++

This problem is only available to subscribers.

Language:

C++23 Python 3.12

run_block_deque

from typing import Any


class BlockDeque:
    """..."""

    BLOCK = 8

    def __init__(self) -> None:
        # ...
        self.blocks = []
        self.first = 0
        self.count = 0

    def push_back(self, value: int) -> None:
        # ...
        pass

    def push_front(self, value: int) -> None:
        # ...
        # ...
        pass

    def block_at(self, index: int) -> tuple[list[int | None], int]:
        """..."""
        # ...
        return (None, 0)

    def get(self, index: int) -> int:
        # ...
        return None

    def set(self, index: int, value: int) -> None:
        # ...
        pass

    def front(self) -> int:
        return self.get(0)

    def back(self) -> int:
        return self.get(self.count - 1)

    def size(self) -> int:
        return self.count

    def block_count(self) -> int:
        return len(self.blocks)


# ...
# ...
# ...
# ...
def run_block_deque(ops: list[tuple[Any, ...]]) -> list[int | bool | None]:
    d = BlockDeque()
    out = []
    held = (None, 0)
    for op in ops:
        name = op[0]
        if name == "push_back":
            d.push_back(op[1])
            out.append(None)
        elif name == "push_front":
            d.push_front(op[1])
            out.append(None)
        elif name == "get":
            out.append(d.get(op[1]))
        elif name == "set":
            d.set(op[1], op[2])
            out.append(None)
        elif name == "front":
            out.append(d.front())
        elif name == "back":
            out.append(d.back())
        elif name == "size":
            out.append(d.size())
        elif name == "block_count":
            out.append(d.block_count())
        elif name == "hold":
            held = d.block_at(op[1])
            out.append(None)
        elif name == "held":
            block, offset = held
            out.append(None if block is None else block[offset])
        elif name == "held_is":
            block, offset = d.block_at(op[1])
            out.append(block is held[0] and offset == held[1])
    return out

Unlock to runUpgrade

Unlock the problem to run it against the tests.

Next in STL From ScratchSmall-Buffer VectorData Structures

Block-Based Deque

xxxxxxxx

xxxxxxxxxxx