Quick Overview

Solve top-K and string rotation match evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Solve top-K and string rotation match

Company: TikTok

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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.

Quick Answer: Solve top-K and string rotation match evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

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

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

Expected Output: [12, 11, 5]

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

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

Expected 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

Input: ("abcde", "cdeab")

Expected Output: 2

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

Input: ("abcde", "abced")

Expected 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.

Loading coding console...