How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Implement range-sum tree and sort merged lists

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.

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.

Input: ([], 1, 100)

Expected Output: 0

Explanation: Empty tree sums to 0.

Input: ([5], 1, 10)

Expected Output: 5

Explanation: Single node 5 is within [1,10].

Input: ([5], 6, 10)

Expected Output: 0

Explanation: Single node 5 is outside [6,10].

Input: ([-10, -20, -5, -30, -15], -20, -5)

Expected Output: -50

Explanation: Nodes in [-20,-5] are -10,-20,-5,-15 (-30 excluded) -> -50.

Input: ([1, 1, 1, 1, 1], 1, 1)

Expected Output: 5

Explanation: All five duplicate values 1 are within [1,1].

Hints

Because the tree is a general binary tree (not a BST), you cannot prune any subtree — you must inspect every node.
A simple DFS or BFS that adds v whenever low <= v <= high works in O(n).
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.

Input: ([5], [])

Expected Output: [5]

Explanation: Second list empty; single value returned.

Input: ([], [7, 2])

Expected Output: [2, 7]

Explanation: First list empty; remaining values sorted.

Input: ([4, 4, 1], [4, 2])

Expected Output: [1, 2, 4, 4, 4]

Explanation: All three 4's are preserved (duplicates kept).

Input: ([-3, 0, 2], [-5, 1, 1])

Expected Output: [-5, -3, 0, 1, 1, 2]

Explanation: Negatives and duplicate 1's sorted ascending.

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

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

Explanation: Already-disjoint sorted ranges concatenate in order.

Hints

The lists are unsorted, so you must order all values — collect every value from both lists, then sort.
Total order is the multiset union of both lists' values; duplicates stay.
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).

Quick Overview