Find k most frequent in linear time

Quick Overview

This question evaluates a candidate's ability to design and analyze efficient frequency-counting algorithms and related data structures, testing competencies in hashing, bucket-based grouping, heap usage, and time/space complexity reasoning.

Find k most frequent in linear time

Company: PayPal

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given an integer array nums and an integer k (1 ≤ k ≤ number of distinct values in nums), return any k values that appear most frequently. Implement an average-case O(n) time, O(n) space solution using a frequency map and bucket-based grouping; explain why it is linear. Then compare it with a heap-based O(n log k) approach: discuss when each is preferable, memory trade-offs, and how you would break ties. Clarify handling of negative numbers and very large value ranges. Provide code and analyze time and space complexity.

Overview: This question evaluates a candidate's ability to design and analyze efficient frequency-counting algorithms and related data structures, testing competencies in hashing, bucket-based grouping, heap usage, and time/space complexity reasoning.

PayPal logo
PayPal
Aug 13, 2025
mediumSoftware EngineerTechnical ScreenCoding & Algorithms
12
0

Given an integer array nums and an integer k (1 ≤ k ≤ number of distinct values in nums), return any k values that appear most frequently. Implement an average-case O(n) time, O(n) space solution using a frequency map and bucket-based grouping; explain why it is linear. Then compare it with a heap-based O(n log k) approach: discuss when each is preferable, memory trade-offs, and how you would break ties. Clarify handling of negative numbers and very large value ranges. Provide code and analyze time and space complexity.