Nielsen - Intern + PPO | Oncampus Online Assessment

Two Coding Problems: Perfect Squares Matching a Pattern & Special Binary Tree Traversal

Topics: Binary Search, Number Theory, Recursion, Binary Search Trees, Tree Traversal, Sorting, Strings.

---

Problem 1: Find All Perfect Squares Matching a Pattern

Problem Statement

You are given a string pattern consisting of digits (0-9) and underscores (_). Each underscore represents a missing digit.

Find all positive perfect squares that match the given pattern.

A number matches the pattern if:

• Every digit in the pattern matches the corresponding digit in the number.
• Each underscore (_) can be replaced by any digit from 0 to 9.
• The resulting number has exactly the same number of digits as the pattern.
• The resulting number does not begin with 0.

Print all matching perfect squares in ascending order, with each number on a separate line.

Examples

Example 1

Input:

1_0_5

Output:

11025

Explanation:

11025 = 105 * 105, so it is a perfect square and matches the pattern 1_0_5.

Example 2

Input:

12_4_9

Output:

120409
127449

Explanation:

• 120409 = 347 * 347
• 127449 = 357 * 357

Both numbers match the pattern and are perfect squares. They are printed in ascending order.

Constraints

• 1 <= pattern.length <= 13
• pattern contains only digits (0-9) and underscores (_).
• The resulting number must have exactly the same number of digits as the pattern.
• The resulting number must not begin with 0.
• Zero is not considered a valid square.
• All matching square values fit in a signed 64-bit integer.

Function Signature

vector<long long> findMatchingSquares(string pattern);

---

Problem 2: Preorder Traversal of a Special Binary Tree

Problem Statement

You are given an array arr containing N integers. Construct a special binary tree using the following steps.

Step 1: Construct the Binary Search Tree

1. Sort the array in ascending order.
2. Select the middle element as the root:
   • If N is odd, choose the element at index (N - 1) / 2.
   • If N is even, choose the element at index (N / 2) - 1.
3. Recursively construct the left subtree using the elements to the left of the selected middle element.
4. Recursively construct the right subtree using the elements to the right of the selected middle element.
5. Repeat the same process for both subtrees until all elements have been used.

Step 2: Identify Special Elements

An integer x is called a special element if the sum of the number formed by removing its last digit and the product of that number and the last digit equals the original number.

Let:

• last = x % 10
• remaining = x / 10, using integer division.

The element is special if:

remaining + remaining * last + last == x

Replace every special element in the tree with 0.

Step 3: Return the Preorder Traversal

Perform a preorder traversal of the modified tree and return the resulting sequence.

Preorder traversal visits nodes in this order:

1. Root
2. Left subtree
3. Right subtree

Examples

Example 1

Input:

8
12 8 7 16 19 41 33 29

Output:

16 0 0 12 0 0 33 41

Explanation:

After sorting the array:

7 8 12 16 19 29 33 41

The constructed binary search tree is:

        16
       /  \
      8    29
     / \   / \
    7  12 19 33
                 \
                  41

The special elements are 7, 8, 19, and 29. Replace these elements with 0.

The preorder traversal of the modified tree is: 16 0 0 12 0 0 33 41

Example 2

Input:

4
1 51 23 49

Output:

23 0 0 51

Explanation:

After sorting the array: 1 23 49 51

The constructed binary search tree is:

      23
     /  \
    1    49
           \
            51

The special elements are 1 and 49. Replace these elements with 0.

The preorder traversal of the modified tree is: 23 0 0 51

Constraints

• 1 <= N <= 1000
• 1 <= arr[i] <= 1,000,000,000

Function Signature

vector<int> processData(int n, vector<int> arr);