Solve linked-list and top-K algorithm tasks
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### Question
Given a singly linked list, return the k-th node counted from the end.
Given an integer array, return the top k most frequent numbers.
Given a list of points on the 2-D plane, return the k points closest to the origin (0,
0).
Given a string where adjacent identical characters "collide" and disappear repeatedly (e.g., "abbba" → "aa" → ""), output the final string after all collisions are resolved.
https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/ https://leetcode.com/problems/top-k-frequent-elements/description/ https://leetcode.com/problems/k-closest-points-to-origin/description/ https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/description/
Quick Answer: This question evaluates competency in fundamental data structures and algorithmic techniques, including linked list manipulation, frequency counting and top‑K retrieval, closest-point geometric queries, and stack-based string processing for repeated deletions.
Kth Node From the End of a Linked List
Given a singly linked list (provided here as a list of node values in order) and an integer k, return the value of the k-th node counted from the END of the list (k = 1 is the last node). Return null if k is out of range (k < 1 or k > length).
Classic two-pointer / runner technique: advance a fast pointer k steps ahead, then move both fast and slow until fast reaches the end; slow lands on the k-th node from the end. Here the list is modeled as an array of values so the function takes (values, k).
Example: values = [1, 2, 3, 4, 5], k = 2 -> 4 (the 2nd node from the end).
Constraints
- 1 <= number of nodes <= 10^4
- Node values fit in a 32-bit signed integer
- 1 <= k, but k may exceed the list length (return null in that case)
Examples
Input: ([1, 2, 3, 4, 5], 2)
Expected Output: 4
Explanation: 2nd node from the end of [1,2,3,4,5] is 4.
Input: ([1], 1)
Expected Output: 1
Explanation: Single node; the last node is the node itself.
Hints
- Think of two pointers: move a fast pointer k steps ahead first.
- Then advance fast and slow together until fast falls off the end; slow is now at the k-th node from the end.
- Equivalently, the k-th node from the end is at 0-based index n - k from the front.
Top K Frequent Elements
Given an integer array nums and an integer k, return the k most frequent elements. To make the output deterministic, return them ordered by frequency descending; break ties by the numeric value ascending.
Count frequencies with a hash map, then select the top k. A bucket sort by frequency, or a heap, achieves better-than-O(n log n) selection, but any correct ordering that respects the tie-break rule above is accepted by these tests.
Example: nums = [1, 1, 1, 2, 2, 3], k = 2 -> [1, 2] (1 appears 3x, 2 appears 2x).
Constraints
- 1 <= nums.length <= 10^5
- Values fit in a 32-bit signed integer
- 1 <= k <= number of distinct values in nums
- Tie-break: equal frequencies ordered by value ascending
Examples
Input: ([1, 1, 1, 2, 2, 3], 2)
Expected Output: [1, 2]
Explanation: 1 appears 3x, 2 appears 2x — the two most frequent.
Input: ([1], 1)
Expected Output: [1]
Explanation: Only one distinct value.
Hints
- Count occurrences with a hash map first.
- You don't need to fully sort: a min-heap of size k, or bucket sort indexed by frequency, gives the top k efficiently.
- For deterministic output, break frequency ties by the smaller value.
K Closest Points to the Origin
Given a list of points on the 2-D plane (each point is [x, y]) and an integer k, return the k points closest to the origin (0, 0), measured by Euclidean distance. Compare using squared distance x*x + y*y to avoid floating point. To make the output deterministic, order the returned points by squared distance ascending, then by x ascending, then by y ascending.
A max-heap of size k, or a quickselect partition, finds the k closest in better than full-sort time, but any correct selection respecting the tie-break order above is accepted.
Example: points = [[1, 3], [-2, 2]], k = 1 -> [[-2, 2]] (distance^2 8 < 10).
Constraints
- 1 <= points.length <= 10^4
- Coordinates fit in a 32-bit signed integer
- 1 <= k <= points.length
- Use squared distance to compare; tie-break by x then y ascending
Examples
Input: ([[1, 3], [-2, 2]], 1)
Expected Output: [[-2, 2]]
Explanation: dist^2 of [-2,2] is 8, less than [1,3]'s 10.
Input: ([[3, 3], [5, -1], [-2, 4]], 2)
Expected Output: [[3, 3], [-2, 4]]
Explanation: dist^2: [3,3]=18, [-2,4]=20, [5,-1]=26 — closest two.
Hints
- Compare by squared distance x*x + y*y — no need for sqrt.
- A max-heap of size k keeps the k smallest distances seen so far.
- Quickselect partitions around the k-th smallest distance in O(n) average time.
Collapse Adjacent Identical Characters Until Stable
Given a string s, repeatedly remove every maximal run of two or more adjacent identical characters. Removing a run can bring new characters next to each other, which may form new runs; keep collapsing until no run of length >= 2 remains. Return the final string (which may be empty).
Example: "abbba" -> the run "bbb" disappears -> "aa" -> the run "aa" disappears -> "" (empty string).
A single left-to-right pass with a stack of (character, run-length) handles the cascading correctly: each time the top of the stack reaches a run, drop it and let the characters on either side become adjacent.
Constraints
- 0 <= s.length <= 10^5
- s consists of lowercase (and/or uppercase) letters
- A run of length >= 2 is removed entirely, not pairwise
- Removal cascades: collapsing may create new runs that must also be removed
Examples
Input: ('abbba',)
Expected Output: ''
Explanation: 'bbb' removed -> 'aa' -> 'aa' removed -> ''.
Input: ('abba',)
Expected Output: ''
Explanation: 'bb' removed -> 'aa' -> removed -> ''.
Hints
- Maintain a stack of (character, count) pairs as you scan left to right.
- When the incoming character matches the stack top, increment its count; when a count reaches the run threshold, remove that entry.
- After removing an entry, the new top and the next incoming character may match — that is the cascade, and the stack handles it automatically.