HP JBT cheat sheet

Array indexing is O(1) random access; insertion or deletion at position i costs O(n-i) due to element shifting.

Stack is LIFO (push/pop at top, O(1)); Queue is FIFO (enqueue at rear, dequeue at front, O(1) with circular buffer).

Singly linked list: search O(n), insert/delete at known node O(1); it has no backward traversal and needs extra pointer memory per node.

Binary search tree average search is O(log n) but degrades to O(n) when keys are inserted in sorted order (skewed tree).

Hash table average lookup is O(1); worst case O(n) when many keys collide into the same bucket; load factor = entries / buckets.

A complete binary tree with n nodes has height floor(log2 n); a full binary tree with L leaves has 2L-1 total nodes.

Pass by value copies the argument; pass by reference passes the address, so callee modifications are visible to the caller.

Infix to postfix uses a stack of operators; postfix evaluation pushes operands and pops two for each operator, yielding O(n) time.

Static variables keep state between calls; local variables are recreated per call and live on the call stack frame.

Master theorem: T(n)=aT(n/b)+f(n); compare f(n) with n^(log_b a) to get Theta(n^(log_b a)), Theta(f(n)), or Theta(f(n) log n).

Sorting bounds: comparison sorts are Omega(n log n) in the worst case; counting/radix sort reach O(n+k) or O(d(n+k)) with integer keys.

Quicksort average O(n log n), worst O(n^2) on already-sorted input with a fixed pivot; median-of-three reduces this risk.

Merge sort is stable and always O(n log n) but needs O(n) auxiliary space; heapsort is in-place O(n log n) but not stable.

Dijkstra requires non-negative edge weights; Bellman-Ford handles negative weights in O(VE) and detects negative cycles.

BFS finds shortest paths in unweighted graphs in O(V+E); DFS produces pre/post order and detects cycles in directed graphs.

Greedy algorithms are correct only with the greedy-choice property and optimal substructure (e.g., activity selection, Huffman coding).

Dynamic programming applies when subproblems overlap; memoization is top-down, tabulation is bottom-up.

0/1 knapsack DP table is O(nW) time and space; fractional knapsack is solved greedily in O(n log n) by value/weight ratio.

Process states: new, ready, running, waiting, terminated; only one process per CPU core is running at a time.

Threads of one process share code, data, and open files but have separate stacks, registers, and program counters.

Deadlock requires mutual exclusion, hold-and-wait, no preemption, and circular wait simultaneously; removing any one prevents it.

Paging maps virtual to physical addresses via page tables; a TLB hit avoids the extra memory access of a page-table walk.

Thrashing occurs when the working set exceeds physical memory, so page faults dominate CPU time; increasing multiprogramming worsens it.

CPU scheduling: FCFS is non-preemptive; SJF gives minimum average waiting time; Round Robin bounds response time by the quantum.

Amdahl's law: speedup = 1 / ((1-p) + p/s), where p is the parallel fraction and s the parallel speedup.

Cache hierarchy: L1 fastest and smallest, then L2, L3, then RAM; locality (temporal and spatial) drives hit rates.

Little's law: L = lambda * W, average items in system equals arrival rate times average time in system.

Normal forms: 1NF atomic values; 2NF no partial dependency on part of a composite key; 3NF no transitive dependency; BCNF every determinant is a candidate key.

ACID: Atomicity, Consistency, Isolation, Durability; isolation levels trade consistency against concurrency (read uncommitted to serializable).

SQL clause evaluation order: FROM, WHERE, GROUP BY, HAVING, SELECT, ORDER BY, LIMIT; WHERE filters rows, HAVING filters groups.

INNER JOIN returns matching rows only; LEFT JOIN keeps all left rows with NULLs where no match exists.

COUNT(*) counts rows including NULLs; COUNT(column) skips NULLs; NULL comparisons need IS NULL, never = NULL.

A primary key is unique and NOT NULL; a foreign key references a candidate key and enforces referential integrity.

Indexes speed reads but slow writes; a composite index on (a,b) can serve queries on a, or a and b, but not b alone.

A transaction that reads uncommitted data is a dirty read; non-repeatable read means the same row changes between reads; phantom read means new rows appear.

OSI layers 1-7: Physical, Data Link, Network, Transport, Session, Presentation, Application; TCP/IP collapses these into 4 layers.

TCP is connection-oriented with a 3-way handshake (SYN, SYN-ACK, ACK) and guarantees ordered delivery; UDP is connectionless and unreliable.

Well-known ports: HTTP 80, HTTPS 443, FTP 21, SSH 22, SMTP 25, DNS 53, POP3 110, IMAP 143.

IPv4 is 32-bit; IPv6 is 128-bit; private ranges are 10.0.0.0/8, 172.16.0.0/12, 192.168.0.0/16.

Subnet hosts = 2^(32-prefix) - 2, subtracting network and broadcast addresses.

DNS resolves names to IPs hierarchically (root, TLD, authoritative); HTTP is stateless, cookies and sessions add state.

HTTP status classes: 2xx success, 3xx redirect, 4xx client error, 5xx server error; 404 not found, 500 internal error.

TLS provides confidentiality, integrity, and authentication using certificates; HTTPS is HTTP over TLS on port 443.

SDLC models: Waterfall is sequential; Agile is iterative; Spiral adds risk analysis; V-model pairs each development phase with a test level.

Test levels: unit (single component), integration (interfaces), system (whole product), acceptance (user requirements).

Black-box techniques: equivalence partitioning, boundary value analysis, decision tables; white-box uses statement and branch coverage.

Cyclomatic complexity V = E - N + 2P, equal to the number of independent paths and the minimum test cases for branch coverage.

Regression testing re-runs existing tests after a change; smoke testing checks basic build viability before deeper testing.

A defect found later costs more to fix; reviews and static analysis catch defects before execution.

Cohesion should be high within a module and coupling low between modules; both are design quality indicators.

Version control: commit snapshots, branch isolates work, merge combines histories, and conflicts occur on the same lines.

Speed-distance-time: distance = speed * time; convert km/h to m/s by multiplying by 5/18.

Simple interest = PRT/100; compound interest = P(1+R/100)^T - P.

Work: if A finishes in x days and B in y days, together they take xy/(x+y) days.

Profit percent = (SP - CP)/CP * 100; successive discounts of a% and b% equal a + b - ab/100 percent.

Average = sum / count; if every value increases by k, the average increases by k.

Permutations nPr = n!/(n-r)!; combinations nCr = n!/(r!(n-r)!); nCr = nC(n-r).

Probability = favorable outcomes / total outcomes; for independent events P(A and B) = P(A)*P(B).

Series: arithmetic nth term a+(n-1)d; geometric nth term a*r^(n-1); sum of first n naturals = n(n+1)/2.

Syllogism: valid conclusion must hold in every model satisfying the premises; 'some A are B' does not imply 'some B are A' fails only if no overlap exists.

Subject-verb agreement: singular subject takes singular verb; ignore intervening phrases such as 'along with' or 'as well as'.

Neither/nor and either/or take a verb agreeing with the nearer subject.

Misplaced modifier: a modifier must sit next to the word it describes, usually right after the opening phrase.

Active voice is preferred in technical writing; passive is acceptable when the actor is unknown or unimportant.

Parallelism: items in a list or comparison must share the same grammatical form (all nouns, all infinitives).

Reading comprehension: identify the main idea, then locate supporting detail by keyword; avoid options that overstate or introduce outside facts.

Inference questions require a conclusion necessarily supported by the passage, not merely plausible.

Vocabulary in context: choose the meaning that fits the sentence, not the most common dictionary sense.