NAPT flashcards

32 cards. Read the term and the definition here. The deck at the top of this page is optional.

Binary search complexity

On a sorted array of n elements, binary search runs in O(log n) time and makes at most floor(log2 n) + 1 comparisons in the worst case.

Hash table load factor

Load factor α equals the number of stored keys divided by the number of buckets. Open addressing requires α below one; average lookup remains O(1) while α stays small.

Stable sorting algorithm

A stable sort preserves the original relative order of elements that compare equal. Insertion sort, merge sort, and counting sort are stable; standard quicksort and heapsort are not.

Big-O upper bound

f(n) = O(g(n)) means there exist positive constants c and n0 such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n0, giving an asymptotic upper bound on growth.

Binary search tree in-order

An in-order traversal of a binary search tree visits the left subtree, then the node, then the right subtree, producing keys in ascending sorted order.

Amortized dynamic array append

Appending to a dynamic array is O(1) amortized because occasional O(n) resize-and-copy operations are spread across many cheap appends.

Stack versus queue

A stack is LIFO: push and pop occur at the top. A queue is FIFO: enqueue at the rear and dequeue from the front. Both support O(1) insertion and removal.

Dijkstra non-negative weights

Dijkstra's shortest-path algorithm requires all edge weights to be non-negative. With a binary heap, its running time is O((V+E) log V).

Single Responsibility Principle

A class should have only one reason to change, meaning it should serve exactly one actor or stakeholder concern in the system.

Open/Closed Principle

Software entities should be open for extension but closed for modification, so new behavior is added through new code rather than editing tested code.

Liskov Substitution Principle

Objects of a superclass should be replaceable by objects of a subclass without breaking correctness. Subtypes must honor the superclass contract, including preconditions and postconditions.

Interface Segregation Principle

Clients should not be forced to depend on methods they do not use. Splitting a large interface into smaller role-specific interfaces reduces unnecessary coupling.

Dependency Inversion Principle

High-level modules and low-level modules should both depend on abstractions, and abstractions should not depend on details; details depend on abstractions.

Layered architecture dependencies

In a strict layered architecture, each layer may call only the layer directly beneath it, preventing presentation code from reaching persistence directly and keeping layers replaceable.

Coupling versus cohesion

Coupling measures interdependence between modules; cohesion measures how closely related the responsibilities inside one module are. Good design targets low coupling and high cohesion.

Model-View-Controller pattern

MVC separates the data and business rules (model), the presentation (view), and input handling (controller), allowing each concern to change and be tested independently.

First normal form

First normal form requires every column value to be atomic and prohibits repeating groups or multivalued attributes within a single row.

Second normal form

Second normal form requires first normal form plus no partial dependency: each non-key attribute must depend on the entire composite primary key, not just part of it.

Third normal form

Third normal form requires second normal form and no transitive dependency: non-key attributes must not depend on other non-key attributes, only on candidate keys.

ACID transaction properties

Atomicity means all-or-nothing execution; Consistency means valid state transitions; Isolation means concurrent transactions do not interfere; Durability means committed changes survive failures.

INNER versus LEFT JOIN

An INNER JOIN returns only rows with matching keys in both tables. A LEFT JOIN returns every row from the left table plus matches, using NULLs where no match exists.

Foreign key referential integrity

A foreign key constrains a child column so each value must either match a value in the parent key or be NULL when the column is nullable, preserving referential integrity.

WHERE versus HAVING

WHERE filters individual rows before grouping and aggregation. HAVING filters groups after aggregation and may reference aggregate functions such as COUNT or SUM.

Composite index leftmost prefix

A composite index on columns (a, b, c) can serve queries that filter on a, or a and b, or a and b and c; it cannot serve a query filtering only on b or c.

Black-box testing

Black-box testing derives test cases from specifications and expected behavior without inspecting internal code, using techniques such as equivalence partitioning and boundary value analysis.

Boundary value analysis

Boundary value analysis selects test inputs at, just below, and just above each boundary of an input range, because defects cluster at the edges of valid domains.

Statement versus branch coverage

Statement coverage requires every executable statement to run at least once. Branch coverage additionally requires every decision outcome, true and false, to be exercised.

Cyclomatic complexity formula

Cyclomatic complexity V(G) = E − N + 2 for a connected control-flow graph, or P + 1 where P is the number of decision nodes; it equals the minimum number of independent paths.

Unit versus integration testing

Unit tests isolate the smallest testable component, such as a function or class. Integration tests verify that multiple components interact correctly through their interfaces.

Regression testing purpose

Regression testing re-runs an existing suite of tests after a code change to confirm that previously working functionality has not been broken by the modification.

Test oracle

A test oracle is the mechanism that decides whether an observed test result is correct, such as a specification, reference implementation, or expected-output file.

Mutation testing score

Mutation testing injects small code changes called mutants. A mutant is killed when a test fails on it, and the mutation score equals killed mutants divided by total mutants.