Solve linked list, top-K, and string reduction
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Solve the following algorithmic tasks:
1) Given a singly linked list, return the k-th node from the end (1-indexed). Describe one-pass and two-pass approaches, edge cases (k <= 0, k > n), and time/space complexity.
2) Given an array of integers, return the top k most frequent numbers. Explain how to handle ties, streaming data, and large ranges; compare min-heap, bucket sort, and quickselect approaches.
3) Given a list of 2D points, return the k points closest to a target point (default origin). Specify the distance metric, constraints, and the complexity of heap-based vs divide-and-conquer solutions.
4) Given a string, repeatedly remove any maximal group of adjacent equal characters until no more removals are possible, and output the final string (e.g., "abbba" -> "aa" -> ""). Provide an algorithm (e.g., stack) and analyze complexity and memory usage.
Quick Answer: This problem set evaluates algorithmic problem-solving across linked list indexing from the end, top-K frequency selection, k-nearest point retrieval, and iterative string reduction, emphasizing knowledge of data structures (singly linked lists, heaps/buckets, partitioning approaches, stacks), complexity analysis, edge-case handling, and scalability for streaming or large ranges. It is commonly asked to assess trade-offs between time and space complexity, correctness under boundary conditions, and appropriate algorithm/data-structure choice within the Coding & Algorithms domain, operating at both conceptual understanding and practical application levels.