Topic
143 posts tagged “Computer Science”.
The Lycoris Team · · 5 min read Kadane's algorithm finds the maximum-sum contiguous subarray in one O(n) pass. How it works, why it's correct, code, edge cases, and common variations.
Chisato · · 5 min read A gossip protocol spreads information through a cluster by having each node periodically share state with a few random peers. How it works and its trade-offs.
The Lycoris Team · · 6 min read Copy-on-write shares data until someone modifies it, then copies only what changed. How CoW powers fork(), snapshots, containers, and immutable data.
The Lycoris Team · · 5 min read TCP congestion control decides how fast a sender transmits without overloading the network. Slow start, AIMD, CUBIC, and BBR explained.
Chisato · · 4 min read Byzantine fault tolerance lets a distributed system keep working correctly even when some nodes fail arbitrarily or actively lie, not just crash cleanly.
The Lycoris Team · · 4 min read A mutex lets exactly one thread hold a lock at a time; a semaphore allows a fixed number of concurrent holders. Here's what that difference means in practice.
The Lycoris Team · · 4 min read A rope is a binary tree of string chunks that makes inserting, deleting, and slicing huge strings fast, which is why text editors use it over plain arrays.
The Lycoris Team · · 4 min read A semaphore is a counter that limits how many threads can access a resource at once. How they work, semaphores vs mutexes, and common pitfalls.
Chisato · · 5 min read Raft and Paxos both let a distributed cluster agree on a value despite failures — Raft trades some flexibility for a design built to be understood.
Chisato · · 4 min read HBM stacks DRAM dies vertically and connects them through a wide interface, trading capacity per chip for far higher bandwidth than standard DRAM.
The Lycoris Team · · 4 min read A roaring bitmap is a compressed bitmap format that splits data into chunks and picks the best internal representation for each — fast and space-efficient.
Chisato · · 4 min read Thermal interface material fills microscopic gaps between a chip and its heatsink so heat can actually transfer to the cooler.
Chisato · · 4 min read Dennard scaling held that shrinking transistors kept power density constant, letting clock speeds rise for free. Its breakdown reshaped chip design.
Chisato · · 4 min read Clock speed measures cycles per second; IPC measures work done per cycle. Real CPU performance is the product of both, not either one alone.
The Lycoris Team · · 4 min read Memoization caches results top-down via recursion; tabulation builds a table bottom-up with loops. Same technique, opposite direction, different tradeoffs.
The Lycoris Team · · 4 min read Cardinality is how many distinct values a column has. Low-cardinality columns make poor index candidates because the database still scans most of the table.
The Lycoris Team · · 4 min read Manacher's algorithm finds the longest palindromic substring in linear time by reusing symmetry from palindromes already found, avoiding redundant checks.
Chisato · · 5 min read A world model is an AI system's internal simulation of how its environment changes, letting it predict outcomes before acting.
The Lycoris Team · · 5 min read The dining philosophers problem is a classic model of deadlock and starvation: five philosophers, five forks, and a resource-sharing rule that can lock up.
The Lycoris Team · · 4 min read The Z-algorithm builds a Z-array in linear time to find every occurrence of a pattern in a text — a fast alternative to naive string search.
Chisato · · 4 min read UMA gives every CPU core equal-latency memory access; NUMA gives each core faster access to its local memory bank. How the two architectures differ.
The Lycoris Team · · 4 min read An abstract syntax tree represents source code's grammatical structure as nodes a compiler, linter, or formatter can walk and transform programmatically.
Chisato · · 5 min read Overclocking runs a CPU, GPU, or memory beyond its rated clock speed for more performance, trading power, heat, and stability margin to get it.
The Lycoris Team · · 5 min read Floating-point numbers can't represent most decimals exactly in binary — that's why 0.1 + 0.2 gives 0.30000000000000004, and what IEEE 754 actually stores.
Takina · · 4 min read Most regex engines backtrack through an NFA; a few compile to a DFA instead. The difference explains why some patterns hang forever and others never do.
The Lycoris Team · · 5 min read Binary search finds a value in a sorted array in O(log n) time by repeatedly halving the search space. How it works, why it needs sorted input, and common pitfalls.
The Lycoris Team · · 4 min read Breadth-first search explores a graph level by level using a queue; depth-first search follows one path as far as it goes using a stack. When to use each.
Chisato · · 5 min read Clock gating and power gating both cut chip energy use by disabling idle circuit blocks, but one stops the clock while the other cuts power entirely.
The Lycoris Team · · 4 min read Read-your-writes consistency guarantees a client sees its own writes immediately, even when other clients might not yet. How it's implemented.
The Lycoris Team · · 4 min read A splay tree is a self-adjusting binary search tree that rotates recently accessed nodes to the root, giving fast amortized access to hot data.
The Lycoris Team · · 5 min read Two-phase commit locks resources until every node agrees to a transaction; the saga pattern trades that guarantee for availability using compensating steps.
The Lycoris Team · · 5 min read Functional programming builds programs from pure functions and immutable data; OOP bundles state and behavior into objects. Key differences explained.
The Lycoris Team · · 4 min read The halting problem proves no algorithm can determine, for every program and input, whether that program eventually stops. Why this limit is unavoidable.
The Lycoris Team · · 5 min read The traveling salesman problem asks for the shortest route visiting every city once — a classic NP-hard problem with major real-world stakes.
Chisato · · 5 min read Three ways machine learning models learn: from labeled examples, from patterns in unlabeled data, or from trial-and-error reward signals.
Chisato · · 4 min read SerDes converts parallel data to a serial stream for transmission and back, letting chips move data over fewer, faster wires with less overhead.
The Lycoris Team · · 4 min read Bloom filters and cuckoo filters both test set membership in constant space, but only one supports deletion. How they work and when to pick each.
The Lycoris Team · · 4 min read B-trees update data in place for fast, predictable reads; LSM-trees batch writes sequentially for higher write throughput. How databases pick.
The Lycoris Team · · 5 min read Just-in-time (JIT) compilation translates code to native machine instructions while a program runs, trading startup time for peak execution speed.
The Lycoris Team · · 4 min read A Turing machine is a simple abstract model of computation — a tape, a head, and a set of rules — that defines what it means for something to be computable.
Chisato · · 4 min read False sharing happens when threads on different cores write to unrelated variables that share one cache line, silently wrecking performance.
The Lycoris Team · · 4 min read Reservoir sampling picks a uniform random sample from a stream of unknown length using constant memory, without knowing the size in advance.
Chisato · · 4 min read PACELC extends CAP theorem by adding a tradeoff that applies even when there's no partition: latency versus consistency. Here's how it works.
Chisato · · 4 min read Overfitting memorizes training data and fails on new inputs; underfitting fails to learn the pattern at all. How to spot each and what fixes each one.
The Lycoris Team · · 4 min read Radix sort and counting sort can beat comparison sorts by never comparing elements at all — sorting integers in linear time under the right conditions.
Chisato · · 4 min read Instruction pipelining overlaps a CPU's fetch, decode, and execute stages so multiple instructions are in flight at once. How it works.
Chisato · · 4 min read DRAM stores each bit as a charge in a capacitor that needs constant refreshing; SRAM stores each bit in a transistor circuit that holds its state.
The Lycoris Team · · 4 min read A suffix array sorts every suffix of a string into one compact index, enabling binary-search pattern matching without a full suffix tree.
The Lycoris Team · · 4 min read A hash index gives O(1) equality lookups but no range scans; a B-tree supports both. Here's how the two database index types actually differ.
The Lycoris Team · · 5 min read A monotonic stack keeps elements in strictly increasing or decreasing order, solving next-greater-element and range problems in linear time.
Chisato · · 4 min read HBM stacks DRAM vertically next to the chip for extreme bandwidth per watt; GDDR spreads fast chips around the board. How the two approaches differ.
The Lycoris Team · · 4 min read Bellman-Ford handles negative edge weights and detects negative cycles; Dijkstra is faster but can't. When to use each shortest-path algorithm.
The Lycoris Team · · 4 min read Floyd-Warshall finds shortest paths between every pair of nodes in a weighted graph using dynamic programming — how the recurrence works and when to use it.
Chisato · · 4 min read ACID guarantees strict consistency after every transaction; BASE trades that for availability and scale. How each model works and when to pick one.
The Lycoris Team · · 4 min read The master theorem gives a direct formula for the time complexity of divide-and-conquer recurrences, skipping recursion-tree analysis by hand.
The Lycoris Team · · 4 min read The Rabin-Karp algorithm finds substrings by hashing, sliding a window in O(1) time per step instead of rehashing from scratch. Here's how it works.
The Lycoris Team · · 5 min read Prim's and Kruskal's both build a minimum spanning tree but grow it differently — one from a single node, the other by sorted edges. Here's how each works.
The Lycoris Team · · 5 min read Divide and conquer solves problems by splitting them into smaller subproblems, solving each recursively, and combining the results.
Chisato · · 4 min read Memory-mapped I/O maps device registers into the CPU's address space, letting hardware be read and written with ordinary load and store instructions.
Chisato · · 5 min read Cache associativity determines where a memory block can be placed in a CPU cache. How direct-mapped, fully associative, and set-associative caches compare.
The Lycoris Team · · 4 min read TCP guarantees ordered, reliable delivery via a handshake; UDP sends packets with no such guarantee but far less overhead. Where each one fits.
The Lycoris Team · · 4 min read Tail call optimization reuses a function's stack frame for its final call instead of pushing a new one, turning some recursion into constant stack space.
Chisato · · 4 min read DDR5 raises transfer rates, splits each module into two independent sub-channels, and moves voltage regulation onto the module itself. Here's what that buys you.
Chisato · · 4 min read Von Neumann shares one memory for code and data; Harvard architecture splits them. How the two computer architectures differ, and where each is used.
The Lycoris Team · · 4 min read Amdahl's Law says a program's speedup from parallelizing is capped by the fraction that must stay sequential — no matter how many cores you add.
Chisato · · 5 min read Memory channel configuration multiplies bandwidth between RAM and the CPU. How single-, dual-, and quad-channel setups differ, and why slot order matters.
The Lycoris Team · · 4 min read HyperLogLog is a probabilistic algorithm that estimates the number of distinct items in a huge dataset using only a few kilobytes of memory.
The Lycoris Team · · 4 min read A Count-Min Sketch is a probabilistic data structure that estimates item frequencies in a stream using fixed memory, trading exactness for space.
Chisato · · 4 min read The northbridge and southbridge were the two chips that routed data between a CPU, memory, and peripherals before modern SoCs absorbed their jobs.
The Lycoris Team · · 4 min read The producer-consumer problem is a classic concurrency pattern: coordinating producers and consumers around a shared, bounded buffer safely.
Chisato · · 4 min read Virtual memory gives every process its own private address space, mapped to physical RAM by the OS and CPU — enabling isolation, swapping, and overcommit.
The Lycoris Team · · 4 min read Regular expressions are matched by finite automata or backtracking engines. How regex engines parse patterns, and why some patterns run slowly.
The Lycoris Team · · 4 min read P is problems solvable quickly; NP is problems whose solutions are quickly checkable. Whether P equals NP is one of computing's open questions.
The Lycoris Team · · 5 min read Little's Law relates the number of requests in a system, their arrival rate, and how long each one takes — a simple formula for sizing capacity.
The Lycoris Team · · 5 min read LRU evicts whatever hasn't been used in the longest time; LFU evicts whatever has been used the fewest times. How each policy behaves and when to pick it.
Chisato · · 5 min read Simultaneous multithreading lets one physical CPU core run two instruction streams at once, filling idle execution units to raise throughput.
Chisato · · 4 min read A TLB is a small CPU cache that stores recent virtual-to-physical address translations, avoiding a slow page-table walk on every memory access.
The Lycoris Team · · 4 min read The Knuth-Morris-Pratt algorithm finds a pattern inside a text in linear time by never re-examining characters it has already matched.
Chisato · · 5 min read Cache coherence keeps each CPU core's private cache consistent with the others. The MESI protocol is the classic mechanism that makes it work.
The Lycoris Team · · 5 min read A ring buffer is a fixed-size array that wraps its read and write pointers around, giving O(1) enqueue and dequeue without ever resizing.
The Lycoris Team · · 5 min read A Fenwick tree, or binary indexed tree, answers prefix-sum queries and point updates in O(log n) with far less memory than a segment tree.
Chisato · · 5 min read Memory interleaving spreads consecutive addresses across multiple memory banks so the system can access them in parallel instead of one at a time.
The Lycoris Team · · 4 min read Dependency injection passes an object's dependencies in from outside rather than letting it construct them, making code easier to test and swap.
Chisato · · 5 min read Endianness decides whether a multi-byte number's most or least significant byte is stored first in memory. Why it matters and how to spot it.
Chisato · · 4 min read Speculative execution lets a CPU guess ahead and run instructions before it knows they're needed, buying speed at the cost of the timing side channels behind Spectre and Meltdown.
The Lycoris Team · · 4 min read A monad is a wrapper type with rules for chaining operations that might fail, be async, or carry extra context — like Promise or Optional, generalized.
The Lycoris Team · · 5 min read Raft is a consensus algorithm that lets a cluster of servers agree on a shared state even when some nodes fail. How leader election and log replication work.
The Lycoris Team · · 4 min read Bit manipulation uses operators like AND, OR, XOR, and shifts to work directly on binary representations — the basics behind flags, masks, and fast math.
The Lycoris Team · · 4 min read Amortized analysis measures the average cost of an operation over a sequence of calls, not its worst case. How dynamic array resizing gets O(1) amortized inserts.
Chisato · · 4 min read SIMD lets a CPU apply one instruction to multiple data points at once. How vectorization works, why compilers auto-vectorize loops, and its limits.
Chisato · · 4 min read DMA lets peripherals move data to and from memory without the CPU copying every byte, freeing the processor to do other work during transfers.
The Lycoris Team · · 4 min read When two keys hash to the same slot, a hash table needs a collision strategy. Chaining and open addressing solve it differently — here's the tradeoff.
Chisato · · 4 min read Branch prediction guesses which way an if-statement will go before the CPU knows, and out-of-order execution reorders instructions to keep pipelines full.
The Lycoris Team · · 5 min read A segment tree answers range queries — sum, min, max — over an array in logarithmic time, and supports updates without rebuilding the whole structure.
Chisato · · 4 min read Thermal throttling automatically reduces a chip's clock speed when it gets too hot, trading performance for safety. How it works and how to spot it.
The Lycoris Team · · 4 min read MVCC lets readers and writers work on a database concurrently without blocking each other, by keeping multiple versions of each row instead of locking it.
Chisato · · 4 min read A buffer overflow happens when a program writes past the end of a fixed-size memory buffer, corrupting adjacent data. How it works and how modern systems defend against it.
The Lycoris Team · · 4 min read Backtracking solves problems by building candidate solutions incrementally and abandoning any path that can't lead to a valid answer. How it works, with examples.
The Lycoris Team · · 4 min read The saga pattern coordinates a multi-step transaction across services using local commits and compensating actions instead of a distributed lock.
Chisato · · 4 min read TDP is the amount of heat a cooling system must dissipate for a chip, not a hard limit on its power draw. Why TDP and actual power draw often diverge.
The Lycoris Team · · 5 min read Union-find tracks a collection of disjoint sets and answers 'are these two items connected?' in near-constant time. How it works and where it's used.
Chisato · · 4 min read UEFI is the firmware that initializes hardware and boots the OS on modern computers, replacing BIOS with faster boot times, larger disk support, and Secure Boot.
The Lycoris Team · · 4 min read Topological sort orders the nodes of a directed acyclic graph so every dependency comes before what depends on it. How it works and where it's used.
The Lycoris Team · · 5 min read Two pointers walk a sorted array or string from both ends (or in tandem) to solve problems in one linear pass instead of nested loops.
The Lycoris Team · · 4 min read An LSM tree batches writes in memory and flushes them as sorted files on disk, trading read complexity for the fast, sequential writes many databases rely on.
The Lycoris Team · · 5 min read Two-phase commit coordinates a transaction across multiple databases with a prepare phase and a commit phase, trading availability for strong consistency.
The Lycoris Team · · 4 min read The sliding window technique tracks a moving subrange of an array or string, turning many O(n²) brute-force problems into a single O(n) linear pass.
The Lycoris Team · · 6 min read Dijkstra's algorithm finds shortest paths by exploring uniformly outward; A* reaches the same answer faster by using a heuristic to aim at the goal.
Chisato · · 4 min read A CRDT is a data structure that merges concurrent edits from multiple replicas automatically, without coordination or conflicts, using math instead of locks.
Chisato · · 4 min read NUMA gives each CPU its own local memory bank, so access speed depends on which processor is asking. How NUMA nodes and remote access latency work.
The Lycoris Team · · 4 min read A Merkle tree hashes data in pairs up to a single root hash, letting huge datasets be verified for integrity without downloading all of them.
Chisato · · 4 min read PCIe (PCI Express) is the high-speed serial bus connecting GPUs, SSDs, and network cards to a CPU. How lanes, generations, and bandwidth work.
The Lycoris Team · · 4 min read A skip list is a layered linked list with shortcut pointers giving O(log n) search, insert, and delete — a simpler alternative to balanced trees.
Chisato · · 4 min read SSDs store data in flash memory chips with no moving parts; HDDs use spinning magnetic platters. How that difference plays out in speed, cost, and durability.
The Lycoris Team · · 5 min read Greedy algorithms commit to the locally best choice at each step; dynamic programming weighs every subproblem. When each one actually works.
Chisato · · 4 min read Bandwidth measures how much data memory moves per second; latency measures how long one access takes. Why chips need both, not just one.
Chisato · · 4 min read Eventual consistency guarantees that replicas converge over time, not instantly. How it differs from strong consistency and when it's acceptable.
The Lycoris Team · · 4 min read Red-black and AVL trees both keep binary search trees balanced, but trade off rebalancing cost against lookup speed differently. How each works.
The Lycoris Team · · 4 min read A quantum computer uses qubits in superposition and entanglement to explore many possible states at once, rather than one bit value at a time.
Chisato · · 4 min read ECC memory detects and corrects single-bit errors in RAM automatically, using extra parity bits — critical for servers where silent corruption is costly.
Chisato · · 4 min read DDR and GDDR are both DRAM, but optimized for opposite goals: DDR minimizes latency for CPUs, GDDR maximizes bandwidth for GPUs. Here's how they diverge.
The Lycoris Team · · 4 min read A finite state machine models a system as a fixed set of states and the transitions between them. How FSMs work and where they show up in real software.
The Lycoris Team · · 4 min read An LRU cache evicts the least recently used item first when it runs out of room, keeping the most useful data in memory. Here's how it's built.
The Lycoris Team · · 4 min read Recursion solves a problem by calling itself on smaller inputs; iteration solves it with a loop. Same results, different trade-offs in memory and clarity.
The Lycoris Team · · 4 min read A B-tree is a self-balancing tree that keeps data sorted with logarithmic search, insert, and delete time — the structure behind most database indexes.
The Lycoris Team · · 5 min read Quicksort and mergesort are the two classic O(n log n) sorting algorithms — how they differ in memory use, stability, and worst-case behavior.
The Lycoris Team · · 4 min read Consistent hashing maps keys and nodes onto the same ring so adding or removing a server only reshuffles a small fraction of keys, not all of them.
The Lycoris Team · · 5 min read Graphs model networks of connected nodes; BFS and DFS are the two core ways to traverse them. How each works, and which to reach for.
The Lycoris Team · · 4 min read Stacks remove the most recent item first (LIFO); queues remove the oldest first (FIFO). How each works, their operations, and where they show up.
The Lycoris Team · · 4 min read A trie stores strings by sharing common prefixes across tree branches, making prefix lookups and autocomplete fast. How it compares to hash tables and BSTs.
Chisato · · 4 min read SRAM is fast, expensive, six-transistor memory used for CPU caches; DRAM is slower, cheaper, one-transistor memory used for main system memory.
The Lycoris Team · · 4 min read A heap is a tree-based structure that keeps the smallest or largest element at the root, enabling priority queues and heap sort in logarithmic time.
Chisato · · 5 min read L1, L2, and L3 CPU caches sit between the processor and main memory, trading capacity for speed at each level. How the hierarchy actually works.
The Lycoris Team · · 5 min read A Bloom filter is a compact data structure that tests whether an item might be in a set, using far less memory than storing the set itself.
The Lycoris Team · · 4 min read Memoization caches a function's return value by its input, skipping recomputation on repeat calls. How it works and when it actually helps.
The Lycoris Team · · 4 min read A linked list stores elements as nodes linked by pointers rather than contiguous memory, trading fast random access for cheap insertion and removal.
The Lycoris Team · · 4 min read Dynamic programming solves complex problems by breaking them into overlapping subproblems and caching results, avoiding redundant recomputation.
Chisato · · 4 min read CAP theorem says a distributed system can't guarantee consistency, availability, and partition tolerance all at once. What the trade-off means in practice.
Chisato · · 4 min read A race condition occurs when a program's correctness depends on the unpredictable timing of concurrent operations. Why they happen and how to prevent them.
Chisato · · 4 min read Moore's Law is the observation that transistor density on a chip roughly doubles every couple of years. Why it drove decades of gains, and why it's slowing.
The Lycoris Team · · 4 min read A binary search tree keeps every left descendant smaller and every right descendant larger than its parent. How lookups, inserts, and balance work.
The Lycoris Team · · 4 min read A hash table maps keys to array slots with a hash function for near O(1) lookups. How hashing, collisions, and resizing actually work under the hood.
The Lycoris Team · · 5 min read Big O notation describes how an algorithm's time or memory grows as input grows. The common classes, what they mean, and how to reason about them.
