Data Structures and Algorithms

A Star Schema consists of a Fact table at the center (containing measures/key figures) surrounded by Dimension tables (containing descriptive attributes). This is the fundamental data warehouse pattern that optimizes query performance by denormalizing dimension data.

A Joiner transformation is used in Informatica when you need to join data from heterogeneous sources, such as combining data from a relational database table and a flat file, which cannot be joined using a Source Qualifier.

Active transformations change the number of rows passing through them. The Sorter transformation is active because it changes the row order. In contrast, Expression transformations are passive (same number of input and output rows), and Lookup transformations can be active or passive depending on whether they're connected or unconnected.

Sorting is a resource-intensive operation in data processing (such as Ab Initio). It is costly in terms of temporary disk space and CPU time because it requires comparing and reorganizing all records.

B-tree indexes are ideal for unique columns, reverse key indexes are designed to avoid contention in Oracle Parallel Server (RAC) environments, and bitmap indexes are highly efficient for columns with low cardinality.

PL I permits arrays with up to 15 dimensions and elements can be any data type not just numeric. Array subscripts start at 1 by default, not 0, and arrays are memory structures not directly tied to DB2.

Statement A correctly distinguishes subscript (array occurrence number) from index (byte displacement). Statement B is true - index manipulation requires PERFORM VARYING, SEARCH, or SET statements. Statement C is true - SEARCH/SEARCH ALL require an indexed table. Since A, B, C are all true, 'None of the above' (D) is the correct false statement.

The question asks for classes that store key/value pairs, replace old entries on duplicates, and offer constant-time performance. LinkedHashMap, HashMap, and Hashtable implement the Map interface (storing key/value pairs) and provide constant-time performance. LinkedHashSet, TreeSet, and HashSet are Set implementations, not Maps.

A FIFO queue requires efficient add-at-end and remove-from-front operations. LinkedList provides O(1) for both operations. ArrayList requires O(n) for front removal. LinkedHashMap/LinkedHashSet/TreeMap don't provide queue semantics. Vector has same issues as ArrayList. Option D (LinkedList) is optimal.

With infinite memory, Counting sort achieves O(n + k) time complexity where k is the range of values. Since we have infinite memory and are sorting natural numbers, Counting sort is optimal. Comparison sorts like Merge sort and Heap sort are O(n log n), while Bubble sort is O(n^2).

Merge sort consistently performs at O(n log n) time complexity across all cases - best, average, and worst. This is because it always divides the array in half (log n levels) and merges n elements at each level. The n log n complexity is its fundamental characteristic.

Finding the maximum number in an unsorted list requires examining every single element at least once, resulting in a linear time complexity of n.

Accessing an element by index in an array takes O(1) time because arrays use direct memory addressing. In a linked list, finding an element at a specific index requires traversing from the head node, which takes O(n) time in the worst case. The ratio of array access time to linked list access time is therefore 1:n.

NP stands for Nondeterministic Polynomial time in computational complexity theory. This class contains decision problems for which a proposed solution can be verified in polynomial time by a deterministic Turing machine, even though finding the solution might require exponential time.