Katkat
Back

Solve array merge and tree flattening problems

MetaSoftware Engineer · HR Screen
MediumSoftware EngineerHR ScreenCoding & Algorithms

Last updated

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Solve array merge and tree flattening problems states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

  1. Given two sorted arrays, merge them into a single sorted array. Provide both an in-place approach (when the first array has enough trailing capacity) and an approach using extra buffer. Analyze time and space complexity for each, and discuss stability.
  2. Given a binary tree, flatten it in-place to a singly linked list following preorder traversal such that each node's right pointer points to the next node and all left pointers are null. Describe the algorithm, prove correctness, and analyze time and space complexity.