Quick Overview

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.

Implement range-sum tree and sort merged lists

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

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.

Quick Answer: 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.

Range Sum of a Binary Tree

Given a binary tree whose nodes store integer values, and two integers `low` and `high` defining an inclusive range `[low, high]`, return the sum of all node values that fall within the range. The tree is provided as a level-order (breadth-first) array where `null` marks a missing child. For example, `[10, 5, 15, null, null, 13, 18]` represents a root `10` with children `5` and `15`, where `15` has children `13` and `18`. Return the integer sum of every node value `v` with `low <= v <= high`. If the tree is empty, return `0`. Note: this is a general binary tree (not necessarily a BST), so every node must be visited. If the tree were guaranteed to be a BST you could prune subtrees that lie entirely outside `[low, high]`, but here no ordering can be assumed.

Constraints

  • 0 <= number of nodes <= 10^4
  • -10^5 <= node value <= 10^5
  • -10^5 <= low <= high <= 10^5
  • The tree is a general binary tree, not necessarily a BST.
  • Use a 64-bit accumulator if node count and magnitudes can make the sum overflow 32-bit.

Examples

Input: ([10, 5, 15, 3, 7, None, 18], 7, 15)

Expected Output: 32

Explanation: Nodes are 10,5,15,3,7,18. Those in [7,15] are 10, 15, 7 -> 32.

Input: ([10, 5, 15, 3, 7, 13, 18, 1, None, 6], 6, 10)

Expected Output: 23

Explanation: Nodes in [6,10] are 10, 7, 6 -> 23.

Hints

  1. Because the tree is a general binary tree (not a BST), you cannot prune any subtree — you must inspect every node.
  2. A simple DFS or BFS that adds v whenever low <= v <= high works in O(n).
  3. If the input were a BST, you could skip the left subtree when a node's value < low, and the right subtree when value > high, turning each lookup into O(h) for the boundary walk.

Merge and Sort Two Unsorted Linked Lists

Given two singly linked lists of integers that are **not necessarily sorted**, merge them into a single singly linked list whose nodes appear in nondecreasing order. The existing nodes are reused (no new value nodes are allocated), so the result is exactly the multiset of all values from both lists, arranged in ascending order. Each linked list is provided as an array of its values in list order. Return the merged, sorted array of values. Follow-up: if both input lists were already sorted, you could merge them in linear `O(n + m)` time with a two-pointer splice (no comparison sort needed).

Constraints

  • 0 <= len(list1), len(list2) <= 10^4
  • -10^9 <= node value <= 10^9
  • Duplicate values are allowed and must all be preserved.
  • Either or both lists may be empty.
  • Inputs are NOT guaranteed to be sorted, so a single linear two-pointer merge is insufficient on its own.

Examples

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

Expected Output: [1, 2, 3, 4, 5, 6]

Explanation: All six values sorted ascending.

Input: ([], [])

Expected Output: []

Explanation: Both lists empty -> empty result.

Hints

  1. The lists are unsorted, so you must order all values — collect every value from both lists, then sort.
  2. Total order is the multiset union of both lists' values; duplicates stay.
  3. If the lists were already sorted, you would not sort — instead walk two pointers and splice the smaller current node each step for O(n + m).

Loading coding console...