Katkat
Back

Solve common search/parse/graph frequency tasks

PayPalSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to perform a binary search on a rotated sorted array and subsequently count occurrences of elements to identify the top-k most frequent items.

Part 1: Rotated Sorted Array Search

You are given a sorted array of integers that has been rotated at some unknown pivot index. For example, [0, 1, 2, 4, 5, 6, 7] might become [4, 5, 6, 7, 0, 1, 2]. Write a function search(nums: List[int], target: int) -> int that returns the index of the target if it exists in nums, or -1 if it does not. You must implement this with O(log n) time complexity.

Part 2: Frequency Analysis

Given the same input array nums, write a function top_k_elements(nums: List[int], k: int) -> List[int] that returns the k most frequent elements in the array. If there is a tie, return the elements in any order.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 1 <= k <= number of unique elements

Examples

# Part 1
search([4, 5, 6, 7, 0, 1, 2], 0) # Output: 4

# Part 2
top_k_elements([1, 1, 1, 2, 2, 3], 2) # Output: [1, 2]

Edge Cases

  • Array with a single element.
  • Array that is not rotated (pivot at index 0).
  • All elements are the same.

Hints

Hint 1

For the rotated array, observe that at any mid-point, at least one half of the array must be sorted.

Hint 2

For frequency analysis, consider using a hash map to count occurrences followed by a heap or bucket sort approach for efficiency.

Hint 3

Ensure your search function handles duplicates if the problem constraints were expanded to include them, though they are not present here.

Follow-up questions

  • How would your approach for the rotated array change if the array contained many duplicate values?
  • Can you solve the top-k frequency problem in O(n) time complexity?
  • How would you modify the system if the input array were too large to fit into memory and arrived as a streaming data source?