Solve Triangle Rows and Top Frequencies
Company: Ericsson
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You have 1 hour to solve both coding problems.
### Problem 1: Build an Additive Number Triangle
Given an integer `numRows`, return the first `numRows` rows of a triangle of numbers with the following rules:
- Row indexing starts at `0`.
- The first and last value in every row are `1`.
- Each interior value is the sum of the two adjacent values directly above it: `triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j]`.
Return the triangle as a list of rows.
Example:
```text
Input: numRows = 5
Output: [[1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]]
```
### Problem 2: Return the K Most Frequent Values
Given an integer array `nums` and an integer `k`, return any `k` distinct values that appear most frequently in `nums`.
If multiple values have the same frequency, any valid set of `k` values is acceptable. The output may be returned in any order.
Example:
```text
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
```
Expected approach: count frequencies and use a size-`k` min-heap to keep the current `k` most frequent values.
Quick Answer: This question set evaluates understanding of combinatorial number patterns and frequency-based selection, specifically the ability to generate an additive number triangle and to identify the k most frequent elements, assessing skills in array/list manipulation, counting, and selection algorithms.
Part 1: Build an Additive Number Triangle
Given a non-negative integer `numRows`, build and return the first `numRows` rows of an additive number triangle.
Rules:
- Row indexing starts at `0`.
- The first and last value of every row are `1`.
- Each interior value is the sum of the two values directly above it from the previous row.
If `numRows` is `0`, return an empty list.
Constraints
- 0 <= numRows <= 30
- Row 0 is `[1]`
- Each row `i` contains exactly `i + 1` integers
Examples
Input: 0
Expected Output: []
Explanation: Edge case: zero rows means the triangle is empty.
Input: 1
Expected Output: [[1]]
Explanation: Only the first row is needed.
Hints
- Build the triangle one row at a time, starting from row 0.
- For each new row, set the first and last elements to 1, then fill the middle using the previous row.
Part 2: Return the K Most Frequent Values
Given an integer array `nums` and an integer `k`, return `k` distinct values that appear most frequently in `nums`.
If multiple values have the same frequency, any valid set of `k` values is acceptable. The result may be returned in any order.
A strong approach is to count frequencies first, then use a size-`k` min-heap to keep track of the current top `k` values.
Constraints
- 1 <= len(nums) <= 100000
- -10^9 <= nums[i] <= 10^9
- 1 <= k <= number of distinct values in nums
Examples
Input: ([1, 1, 1, 2, 2, 3], 2)
Expected Output: [1, 2]
Explanation: Value 1 appears 3 times and value 2 appears 2 times, so they are the top 2.
Input: ([5], 1)
Expected Output: [5]
Explanation: Edge case: with one element, that element is the most frequent.
Hints
- Use a hash map or `Counter` to compute how often each value appears.
- Keep a min-heap of size `k` so the least useful candidate can be removed when a better one appears.