Morgan Stanley OA 2022 - Count Products in Quantity Range

Problem Description

A product manufacturing company labels all its products and manages production through an online hierarchy on their website. Each product is represented as a node in the hierarchy, where the node’s value denotes the quantity of the manufactured product. The oldest product is set as the root of this hierarchy, and related products are connected by relational edges.

The company’s manufacturing team wants to analyze the number of products that fall within a given range X (inclusive), represented by the interval ([low, high]), where low denotes the minimum quantity and high denotes the maximum quantity. The team will use this data to fulfill orders.

Write an algorithm that outputs a list of product quantities that fall within the specified range.

Input Format

• The first line contains two integers:
  • N — the number of relational edges in the hierarchy.
  • A constant value (always 2).
• The next N lines contain two space-separated integers, representing the quantities of two products connected by a relational edge in the hierarchy. The first value in the first line is the quantity of the oldest product.
• The next line contains an integer M — the number of products.
• The next line contains M space-separated integers representing the quantities of the manufactured products.
• The next line contains an integer low — the lower bound of the product quantity range.
• The last line contains an integer high — the upper bound of the product quantity range.

Output Format

• Print the unique product quantities that fall within the range ([low, high]) (inclusive), sorted in ascending order.
• If no product quantities fall within the range, print -1.

Constraints

• 1 <= N, M <= 10^5
• 0 <= Product Quantity <= 10^9
• 0 <= low <= high <= 10^9

Sample Input

4 2
0 1
1 2
1 3
1 4
5
14 3 19 4 10
4
18

Sample Output

4 10 14

Explanation

The hierarchy is as follows:

             0(14)
               /   \
          (3)1    2(19)
          /   \
     (4)3     4(10)

The range for analysis is ([low, high]:[4, 18]).
The quantities of the manufactured products available in the hierarchy are: 14, 3, 19, 4, 10.
The quantities that lie within the given range are: 4, 10, 14.