HP JBT flashcards

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

Array random access

Arrays store elements contiguously, so address of index i equals base plus i times element size. Access is O(1), but inserting or deleting shifts elements, costing O(n).

Stack versus queue

A stack removes the most recently added item (LIFO) using push and pop. A queue removes the oldest item (FIFO) using enqueue at rear and dequeue at front.

Hash table load factor

Load factor is the number of stored entries divided by the number of buckets. As it grows, collisions increase and lookups degrade from O(1) toward O(n), so tables resize.

Binary search tree property

For every node, all keys in the left subtree are smaller and all keys in the right subtree are larger. In-order traversal therefore yields keys in sorted order.

Pass by value

The callee receives a copy of the argument, so changes inside the function do not affect the caller's variable. Pass by reference instead shares the original memory location.

Master theorem

For T(n) equals a times T(n/b) plus f(n), compare f(n) with n raised to log base b of a. The larger determines the complexity class, with an extra log factor when equal.

Quicksort worst case

Quicksort degrades to O(n squared) when the pivot is consistently the smallest or largest element, as with sorted input. Randomized or median-of-three pivots make this unlikely.

Dijkstra constraint

Dijkstra's shortest path algorithm assumes all edge weights are non-negative. With negative edges it can produce wrong results, so Bellman-Ford is used instead.

Dynamic programming conditions

Dynamic programming applies when a problem has overlapping subproblems and optimal substructure. Memoization caches top-down recursive results; tabulation fills a table bottom-up iteratively.

BFS shortest path

Breadth-first search explores vertices level by level, so the first time it reaches a vertex in an unweighted graph is via a shortest path. Its cost is O(V plus E).

Stable sorting

A stable sort preserves the relative order of records with equal keys. Merge sort and insertion sort are stable; quicksort and heapsort typically are not.

Deadlock four conditions

Deadlock requires mutual exclusion, hold and wait, no preemption, and circular wait at the same time. Breaking any single condition prevents deadlock from occurring.

Thread shared state

Threads within one process share code, global data, and open files, but each has its own stack, registers, and program counter. Shared data needs synchronization.

Translation lookaside buffer

The TLB caches recent virtual-to-physical page translations. A TLB hit avoids an extra memory read for the page table, greatly speeding address translation.

Thrashing

Thrashing happens when active processes need more memory than is available, causing constant page faults and near-zero CPU utilization. Reducing multiprogramming or adding memory helps.

Amdahl's law

Speedup equals one divided by the sum of the serial fraction plus the parallel fraction divided by the parallel speedup. Serial portions cap the maximum achievable gain.

Round robin scheduling

Each ready process runs for at most one time quantum, then moves to the back of the queue. Response time is bounded, but a very large quantum behaves like first-come first-served.

Third normal form

A relation is in 3NF when it is in 2NF and no non-key attribute depends transitively on the primary key. This removes redundancy caused by non-key to non-key dependencies.

ACID properties

Atomicity means all-or-nothing execution, consistency preserves constraints, isolation hides concurrent effects, and durability survives crashes. Together they define reliable transactions.

WHERE versus HAVING

WHERE filters individual rows before grouping, while HAVING filters groups after aggregation. Aggregate conditions such as COUNT greater than five belong in HAVING.

NULL in SQL

NULL represents an unknown value, so comparisons with equals return unknown rather than true. Use IS NULL or IS NOT NULL, and note that COUNT of a column skips NULLs.

Left outer join

A left outer join returns every row from the left table plus matching rows from the right. Unmatched left rows appear once with NULL values in right-side columns.

Composite index prefix rule

An index on columns a and b can serve queries filtering on a, or on a and b together, but generally not on b alone, because the leading column is required.

TCP three-way handshake

The client sends SYN, the server replies SYN-ACK, and the client sends ACK. This establishes sequence numbers and a reliable, ordered connection before data transfer begins.

TCP versus UDP

TCP is connection-oriented, ordered, and retransmits lost segments. UDP is connectionless with no delivery guarantee, favored for streaming, DNS, and low-latency traffic.

Private IPv4 ranges

Private addresses are 10.0.0.0/8, 172.16.0.0/12, and 192.168.0.0/16. They are not routable on the public internet and require NAT for external communication.

HTTP status classes

2xx indicates success, 3xx redirection, 4xx client error, and 5xx server error. Common examples include 200 OK, 404 Not Found, and 500 Internal Server Error.

Cyclomatic complexity

Cyclomatic complexity equals edges minus nodes plus twice the connected components, and equals decision points plus one. It gives the minimum number of independent paths to test.

Black-box versus white-box

Black-box testing derives cases from requirements without seeing code, using equivalence partitioning and boundary values. White-box testing uses code structure and measures statement or branch coverage.

Cohesion and coupling

Cohesion measures how closely related a module's internal responsibilities are and should be high. Coupling measures dependence between modules and should be low for maintainability.

Work rate formula

If A completes a job in x days and B in y days, working together takes xy divided by x plus y days, assuming their rates add without interference.

Combinations formula

The number of ways to choose r items from n without regard to order is n factorial divided by r factorial times n minus r factorial. Order matters for permutations instead.

Compound interest formula

Amount equals principal times one plus rate over one hundred, raised to the number of years. Compound interest exceeds simple interest whenever the term exceeds one year.

Subject-verb agreement trap

The verb agrees with the true subject, not with phrases between them. In 'the list of items is long', the singular subject 'list' takes 'is', not 'are'.

Misplaced modifier

An introductory modifying phrase must describe the subject that immediately follows it. Otherwise the sentence implies the wrong noun performs the action, creating a dangling modifier.

Reading comprehension main idea

The main idea is the central claim the whole passage supports, broader than any single detail. Correct answers avoid extremes and stay within the passage's stated scope.

Parallel structure

Items joined by 'and' or 'or', and elements in a comparison, must share grammatical form. 'Reading, writing, and to swim' fails because the third item is an infinitive.