Solve array and tree algorithm challenges
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Solve the following three algorithmic tasks:
1) Unique triplet sum: Given an integer array nums and an integer target (default
0), return all unique triplets [a, b, c] such that a + b + c = target with no duplicate triplets. Explain an O(n^
2) approach using sorting and two pointers, and detail how you handle duplicates and edge cases.
2) K most common values: Given an integer array nums and an integer k, return the k values with highest frequency. If two values share the same frequency, order them by value descending in the output. Implement an O(n log k) solution using a min-heap of size k (e.g., Python’s heapq) and explain how you produce final descending order.
3) Equalize root-to-leaf path sums with minimal increments: You are given a complete binary tree represented as an array costs where costs[i] is the nonnegative cost at node i. In one operation you may increment any node’s cost by 1. Compute the minimum total increments required so that every root-to-leaf path has the same sum. Provide an algorithm and analyze its time and space complexity.
Quick Answer: This question evaluates algorithmic problem-solving skills across array, heap, and tree data structures, testing competencies in duplicate handling, frequency aggregation, and balancing root-to-leaf path sums within the Coding & Algorithms domain.
Unique Triplet Sum (3Sum)
Given an integer array `nums` and an integer `target` (default `0`), return all unique triplets `[a, b, c]` such that `a + b + c == target`, with no duplicate triplets in the output.
Sort the array, then for each index `i` run a two-pointer scan over the remaining suffix to find pairs summing to `target - nums[i]`. Skip equal neighbouring values at the fixed index and after recording a hit to avoid duplicate triplets. This yields an O(n^2) time, O(1) extra-space (ignoring output) solution.
The order of triplets in the returned list follows the sorted-array scan (non-decreasing by first element, then second).
Constraints
- 0 <= len(nums) <= 3000
- -10^5 <= nums[i] <= 10^5
- target defaults to 0 if not provided
- Each triplet in the output must be unique (no duplicate [a, b, c] sets)
Examples
Input: ([-1, 0, 1, 2, -1, -4], 0)
Expected Output: [[-1, -1, 2], [-1, 0, 1]]
Explanation: Two distinct triplets sum to 0; the duplicate -1 is handled so [-1,0,1] appears once.
Input: ([0, 0, 0, 0], 0)
Expected Output: [[0, 0, 0]]
Explanation: All zeros yield a single unique triplet despite four zeros.
Hints
- Sort the array first so equal values are adjacent — this makes both duplicate-skipping and the two-pointer scan possible.
- Fix the first element with an outer loop, then use a left/right two-pointer scan on the remaining suffix to find the other two values.
- After fixing index i, skip it when nums[i] == nums[i-1]; after recording a hit, advance past equal lo/hi values to avoid duplicate triplets.
K Most Common Values
Given an integer array `nums` and an integer `k`, return the `k` values with the highest frequency. When two values share the same frequency, the one with the **larger value** comes first. The final result is ordered by frequency descending, then by value descending.
Use a min-heap of size `k` keyed by `(frequency, value)`: push each distinct value's `(count, value)` pair and pop whenever the heap exceeds `k`. Because the smallest `(freq, value)` is evicted, the heap retains the k highest-frequency values, breaking frequency ties in favour of the larger value. Finally sort the surviving k entries by `(freq, value)` descending to produce the output. This is O(n log k) time.
Constraints
- 0 <= len(nums) <= 10^5
- -10^9 <= nums[i] <= 10^9
- 0 <= k <= number of distinct values in nums
- Frequency ties are broken by value descending; final output is sorted by frequency descending, then value descending
Examples
Input: ([1, 1, 1, 2, 2, 3], 2)
Expected Output: [1, 2]
Explanation: 1 (freq 3) then 2 (freq 2) are the two most common.
Input: ([1], 1)
Expected Output: [1]
Explanation: Single element.
Hints
- Count frequencies first with a hash map / Counter.
- Keying the size-k min-heap by the tuple (frequency, value) lets a single pop evict the worst candidate AND break frequency ties toward the smaller value.
- A min-heap pops smallest-first, so to get descending output you sort the surviving k entries by (freq, value) in reverse at the end.
Equalize Root-to-Leaf Path Sums with Minimal Increments
You are given a complete (perfect) binary tree stored as a heap array `costs`, where `costs[i]` is the nonnegative cost at node `i`, node `i`'s children are at indices `2*i + 1` and `2*i + 2`. In one operation you may increment any single node's cost by 1. Return the **minimum total number of increments** so that every root-to-leaf path has the same sum.
Process the tree bottom-up. For each internal node, its two child subtrees must have equal post-equalization path sums, so you raise the cheaper child's required sum up to the more expensive one; the gap `(max - left) + (max - right)` is added to the running total. The node's own required path sum becomes `costs[i] + max(left, right)`. Leaves contribute their own cost as their path sum. This greedy bottom-up pass is optimal because increments are never wasted — you only ever lift the lighter side to match the heavier, which is forced.
Constraints
- 0 <= len(costs); the tree is a complete (perfect) binary tree, so len(costs) is typically 2^h - 1
- 0 <= costs[i] <= 10^4
- Only increments (cost + 1) are allowed; you may never decrease a cost
- Goal: all root-to-leaf path sums become equal with the fewest total increments
Examples
Input: ([0, 0, 0, 0, 0, 0, 0],)
Expected Output: 0
Explanation: All zeros, all paths already sum to 0.
Input: ([0, 0, 0, 0, 0, 1, 1],)
Expected Output: 1
Explanation: Right subtree's leaves are both 1 (already equal); root must lift its left child path (0) to match the right child path (1), costing 1.
Hints
- Think bottom-up: a node's two subtrees must end up with equal path sums before you can reason about the node above it.
- At each internal node the only optimal move is to raise the lighter child subtree's path sum up to the heavier one — the gap (max - left) + (max - right) is the increments charged at that node.
- Carry up costs[i] + max(left_child_sum, right_child_sum) as the node's own equalized path sum, and accumulate all the gaps as you ascend.