Solve Merge Lists and Vertical Traversal
Company: Meta
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Two coding tasks were mentioned for a 40-minute round:
1. **Merge multiple sorted linked lists**: You are given an array of `k` singly linked lists, where each list is sorted in nondecreasing order. Merge all of them into one sorted linked list and return the head of the merged list.
2. **Vertical traversal of a binary tree**: You are given the root of a binary tree. Group nodes by their vertical column index, from the leftmost column to the rightmost column. Within each column, output nodes from top to bottom. If two nodes share the same row and column, preserve their left-to-right order as seen in a standard breadth-first traversal.
Quick Answer: This question evaluates proficiency with merging sorted linked lists and performing vertical traversal of binary trees, focusing on algorithms, data structure manipulation, and complexity analysis within the Coding & Algorithms domain.