PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

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.

  • Medium
  • Meta
  • Coding & Algorithms
  • Software Engineer

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.

Input: ([7, 8, 9], 3)

Expected Output: 7

Explanation: 3rd from the end equals the 1st from the front.

Input: ([10, 20, 30, 40], 1)

Expected Output: 40

Explanation: 1st from the end is the tail.

Input: ([5, 6], 3)

Expected Output: None

Explanation: k=3 exceeds the length 2, so it is out of range.

Input: ([], 1)

Expected Output: None

Explanation: Empty list has no nodes.

Input: ([-1, -2, -3], 2)

Expected Output: -2

Explanation: Negative values are handled; 2nd from end is -2.

Hints

  1. Think of two pointers: move a fast pointer k steps ahead first.
  2. Then advance fast and slow together until fast falls off the end; slow is now at the k-th node from the end.
  3. 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.

Input: ([4, 4, 5, 5, 6], 2)

Expected Output: [4, 5]

Explanation: 4 and 5 each appear 2x; tie broken by smaller value first.

Input: ([7, 7, 7], 1)

Expected Output: [7]

Explanation: Single distinct value repeated.

Input: ([3, 1, 2], 3)

Expected Output: [1, 2, 3]

Explanation: All frequencies equal (1); ordered by value ascending.

Input: ([-1, -1, -2, -2, -2, 0], 2)

Expected Output: [-2, -1]

Explanation: -2 appears 3x, -1 appears 2x.

Input: ([5, 5, 5, 5], 1)

Expected Output: [5]

Explanation: All occurrences are the same value.

Hints

  1. Count occurrences with a hash map first.
  2. You don't need to fully sort: a min-heap of size k, or bucket sort indexed by frequency, gives the top k efficiently.
  3. 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.

Input: ([[0, 0]], 1)

Expected Output: [[0, 0]]

Explanation: Point at the origin has distance 0.

Input: ([[1, 1], [1, -1], [-1, 1]], 3)

Expected Output: [[-1, 1], [1, -1], [1, 1]]

Explanation: All dist^2 = 2; tie broken by x then y ascending.

Input: ([[2, 2], [2, 2]], 1)

Expected Output: [[2, 2]]

Explanation: Duplicate points; one closest point returned.

Input: ([[10, 0], [1, 1], [0, 5]], 2)

Expected Output: [[1, 1], [0, 5]]

Explanation: dist^2: [1,1]=2, [0,5]=25, [10,0]=100 — closest two.

Hints

  1. Compare by squared distance x*x + y*y — no need for sqrt.
  2. A max-heap of size k keeps the k smallest distances seen so far.
  3. 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 -> ''.

Input: ('abc',)

Expected Output: 'abc'

Explanation: No adjacent duplicates, nothing collapses.

Input: ('aabccba',)

Expected Output: 'a'

Explanation: 'aa' and 'cc' go -> 'bba' -> 'bb' goes -> 'a'.

Input: ('',)

Expected Output: ''

Explanation: Empty input stays empty.

Input: ('aaa',)

Expected Output: ''

Explanation: A single run of 3 disappears entirely.

Input: ('a',)

Expected Output: 'a'

Explanation: A lone character has no run to collapse.

Input: ('abcddcba',)

Expected Output: ''

Explanation: 'dd' -> 'abccba' -> 'cc' -> 'abba' -> 'bb' -> 'aa' -> ''.

Input: ('aabbaa',)

Expected Output: ''

Explanation: Each pair collapses and cascades down to empty.

Hints

  1. Maintain a stack of (character, count) pairs as you scan left to right.
  2. When the incoming character matches the stack top, increment its count; when a count reaches the run threshold, remove that entry.
  3. After removing an entry, the new top and the next incoming character may match — that is the cascade, and the stack handles it automatically.
Last updated: Jun 25, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Find Shortest Unique Prefixes - Meta (medium)
  • Compute Exclusive Execution Times - Meta (medium)
  • Solve Tree Columns And Maze Variants - Meta (medium)
  • Solve Tree Diameter and Palindromic Counts - Meta (medium)
  • Simulate Monster Team Battles - Meta (hard)