Katkat
Back

Implement range-sum tree and sort merged lists

MetaSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

Implement range-sum tree and sort merged lists evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

  1. Given a binary tree whose nodes store integer values, and two integers low and high defining an inclusive range [low, high], write a function that returns the sum of all node values within the range. Implement the solution in C++, explain your approach, and analyze its time and space complexity. Discuss how your strategy would change if the input were guaranteed to be a binary search tree and why.
  2. Given two singly linked lists of integers (not necessarily sorted), merge them into a single singly linked list whose nodes are in nondecreasing order. Reuse the existing nodes (avoid allocating new value nodes except constant-overhead helpers). Implement the solution in C++, explain the algorithm, and analyze time and space complexity. If the input lists are already sorted, describe a linear-time alternative and its complexity.