Solve top-K and string rotation match

1. Given an unsorted array of integers and an integer k, return the k largest elements in descending order. Implement at least two approaches (e.g., a size-k min-heap and a quickselect-based method), discuss time/space complexities, and explain how you would handle duplicates and very large inputs (streaming or external memory).
2. Given two strings s and goal, you may repeatedly move the first character of s to the end of s. Determine whether s can be transformed into goal by any number of such operations. If yes, return the minimum number of moves needed; otherwise, return -1. Specify the algorithm, edge cases, and complexity.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Top-K Largest Elements (Descending)

Given an unsorted array of integers nums and an integer k, return the k largest elements in descending order.

If k is greater than the length of the array, return all elements sorted in descending order. If k <= 0 or the array is empty, return an empty list.

The canonical interview discussion asks for at least two approaches: a size-k min-heap (O(n log k) time, O(k) space — ideal for streaming / very large inputs since only k elements are held in memory) and a quickselect-based partition (O(n) average time, O(1) extra space). The reference below uses the min-heap approach because it generalizes to streaming and external-memory inputs. Duplicates are kept as-is (e.g. top-2 of [5,5,5] is [5,5]).

Constraints

• 0 <= len(nums) <= 10^6
• -10^9 <= nums[i] <= 10^9
• 0 <= k (k may exceed len(nums))
• Duplicates are allowed and preserved in the output
• Return value is sorted in strictly descending order of value

Examples

Example 1

Input: ([3, 1, 5, 12, 2, 11], 3)
Output: [12, 11, 5]

Explanation: The three largest values are 12, 11, 5, returned in descending order.

Example 2

Input: ([1, 2, 3, 4, 5], 2)
Output: [5, 4]

Explanation: Already-sorted input; top 2 are 5 and 4.

Hints

1. A full sort is O(n log n). Can you avoid sorting the entire array when k is small?
2. Maintain a min-heap of size k: the smallest of the k largest sits at the root, so a new element only matters if it beats the root.
3. For O(n) average time and O(1) extra space, use quickselect to partition the k-th largest into place, then sort just the top-k slice.
4. For very large or streaming inputs you cannot hold in memory, the size-k heap is the right tool — you only ever keep k elements.

String Rotation Match — Minimum Moves

Given two strings s and goal, you may repeatedly move the first character of s to the end of s. Determine whether s can be transformed into goal by any number of such operations.

If it is possible, return the minimum number of moves needed; otherwise return -1.

Moving the first character to the end is a left rotation. After i moves, s becomes s[i:] + s[:i]. So s can become goal iff goal is a rotation of s — which holds iff goal is a substring of s + s and the two strings have equal length. The minimum number of moves is the smallest starting index i < len(s) at which goal appears in s + s.

Edge cases: if lengths differ, return -1. If s == goal, the answer is 0. Empty strings match in 0 moves.

Constraints

• 0 <= len(s), len(goal) <= 10^5
• s and goal consist of lowercase (or arbitrary) characters
• If len(s) != len(goal) the answer is always -1
• Return 0 when s already equals goal
• Return the minimum (smallest) number of moves when multiple rotations match

Examples

Example 1

Input: ("abcde", "cdeab")
Output: 2

Explanation: After 2 left-rotations 'abcde' -> 'bcdea' -> 'cdeab' equals goal.

Example 2

Input: ("abcde", "abced")
Output: -1

Explanation: 'abced' is not a rotation of 'abcde', so no number of moves works.

Hints

1. Moving the first character to the end i times transforms s into s[i:] + s[:i] — a left rotation by i.
2. goal is reachable iff it is a rotation of s. A classic trick: goal is a rotation of s iff goal is a substring of s + s (when lengths are equal).
3. The minimum number of moves is the first index i (with i < len(s)) where goal begins inside s + s; use a left-to-right search so you find the smallest i.
4. Don't forget the guards: unequal lengths -> -1, identical strings -> 0, and empty strings -> 0.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

1. Given an unsorted array of integers and an integer k, return the k largest elements in descending order. Implement at least two approaches (e.g., a size-k min-heap and a quickselect-based method), discuss time/space complexities, and explain how you would handle duplicates and very large inputs (streaming or external memory). 2) Given two strings s and goal, you may repeatedly move the first character of s to the end of s. Determine whether s can be transformed into goal by any number of such operations. If yes, return the minimum number of moves needed; otherwise, return -1. Specify the algorithm, edge cases, and complexity.

Recommended Approach

For one-time top-K, use a size-K min-heap or quickselect plus sorting the selected K. For streaming windows, maintain counts in a hash map plus a heap with lazy deletion or bucketed frequency structures when updates must be near O(1). Define deterministic tie-breaking.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

One-time heap: O(n log k) time and O(k) space. Quickselect: expected O(n) plus O(k log k) to order output. Streaming complexity depends on window eviction and tie-breaking.

Edge Cases and Tests

k = 0, k > n, duplicate values, ties, negative values, stale heap entries, and deterministic output ordering.