Katkat
Back

Implement array parity and tree level views

MetaSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to handle two distinct sub-tasks: identifying array elements with unique parity and performing a level-order traversal of a binary tree.

Part 1: Array Parity

Given an array of integers, return a new array containing only those elements whose parity (even or odd) is unique within the entire input array. If an element is the only even number or the only odd number in the list, it should be included.

Example

Input: [1, 3, 5, 2, 7] Output: [2] (Because 2 is the only even number; 1, 3, 5, and 7 are all odd.)

Part 2: Tree Level View

Given the root of a binary tree, return a list of the values of the leftmost node at each level of the tree. A level is defined as a horizontal slice of the tree nodes at the same depth.

Example

Input: 1 /
2 3 /
4 5 Output: [1, 2, 4]

Function Signature

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def solve(nums, root):
    # Return a tuple: (list of unique parity items, list of leftmost tree values)
    pass

Constraints

  • Array length: 1 to 10^4.
  • Tree node count: 0 to 10^4.
  • Time complexity should be O(N) where N is the number of elements or nodes.

Hints

Hint 1

For the array parity part, first count the total number of even numbers and odd numbers in the input array.

Hint 2

For the tree traversal, consider using a Breadth-First Search (BFS) to track nodes level by level, ensuring you only collect the first node encountered at each depth.

Hint 3

Be sure to handle edge cases like an empty tree or an array containing only one parity type.

Follow-up questions

  • How would you modify the array parity solution if you needed to return the index of the unique parity elements instead of the values?
  • Can you implement the tree traversal using Depth-First Search (DFS) instead of BFS?
  • What is the space complexity of your tree traversal solution, and can it be optimized?