Company: UKG mcq
Difficulty: medium
Identify which of the following statements is true, with regards to the heap data structure and its role in sorting. Heap sort functions in O(n log n) asymptotic complexity and a heap of n elements may be constructed in O(n) asymptotic complexity (i.e. linear time). Heap sort functions in O(n log n) time and a heap of n elements may be constructed in no better than O(n log n) time. Heap sort functions in O(n^2) time and a heap of n elements may be constructed in no better than O(n log n) time. None of the above are correct. Construct a string of length N using the first K letters of an alphabet. The cost to construct the string is the number of instances where pairs of characters match in position and order. For example, to construct a string from the first K = 2 letters of the English alphabet that is N = 4 characters long, two of the many possible results are 'abab' for a cost of 1 and 'abba' for a cost of 0. Construct the strings for the following test cases to minimize cost. Select