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 hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Meta.

What role is this question designed for?

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

Compute tree right view and target-sum subarrays

Quick Overview

This two-part question evaluates skills in tree traversal and visible-node extraction for the binary-tree right-side view task and in array cumulative-sum reasoning for counting contiguous subarrays with a target sum, assessing data-structure manipulation and algorithmic problem-solving competency.

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are given two separate programming tasks. --- ## Task 1: Right-side view of a binary tree You are given the root of a binary tree. Imagine standing on the **right side** of the tree and looking at it. You can see exactly one node at each depth level: the rightmost node at that level. Write a function that returns a list (or array) of the values of the nodes that would be visible from the right side, ordered from **top to bottom**. ### Example Consider this binary tree: ``` 10 / \ 5 20 / \ \ 3 7 30 ``` From the right side, you see nodes with values: `[10, 20, 30]`. ### Input/Output - Input: `root` node of a binary tree where each node has: - `val`: integer - `left`: left child pointer (or null) - `right`: right child pointer (or null) - Output: An array (or list) of integers representing the visible node values from top to bottom. ### Constraints - Number of nodes `n` can be up to about `10^4`. - Node values can be any 32-bit signed integers. - The tree does not have to be balanced. --- ## Task 2: Count subarrays with a given sum You are given an integer array `nums` and an integer `k`. Return the **total number of contiguous subarrays** whose elements sum exactly to `k`. ### Example - Input: `nums = [1, 2, 3]`, `k = 3` Valid subarrays are: - `[1, 2]` (sum = 3) - `[3]` (sum = 3) So the answer is `2`. ### Input/Output - Input: - An integer array `nums` of length `n`. - An integer `k`. - Output: A single integer representing the number of contiguous subarrays whose sum equals `k`. ### Constraints - `1 <= n <= 10^5` (you should aim for an algorithm that is close to O(n)). - Elements of `nums` can be negative, zero, or positive (32-bit signed integers). - `k` is a 32-bit signed integer. You may implement both functions in any language of your choice.

Quick Answer: This two-part question evaluates skills in tree traversal and visible-node extraction for the binary-tree right-side view task and in array cumulative-sum reasoning for counting contiguous subarrays with a target sum, assessing data-structure manipulation and algorithmic problem-solving competency.

Part 1: Right-Side View of a Binary Tree

You are given a binary tree encoded as a level-order list. Each element is either an integer node value or None for a missing child. Return the values of the nodes visible when looking at the tree from the right side. At each depth, only the rightmost existing node should be included. For example, the level-order list [10, 5, 20, 3, 7, None, 30] represents a tree whose right-side view is [10, 20, 30].

Constraints

0 <= number of list entries <= 10^4
Node values are 32-bit signed integers
The input list is a valid level-order encoding of a binary tree
The tree may be empty and does not need to be balanced

Examples

Input: [10, 5, 20, 3, 7, None, 30]

Expected Output: [10, 20, 30]

Explanation: The rightmost node at each depth is 10, then 20, then 30.

Input: [1, 2, 3, None, 5, None, 4]

Expected Output: [1, 3, 4]

Explanation: At level 2, node 3 hides node 2 from the right. At level 3, node 4 is the rightmost visible node.

Hints

A breadth-first traversal lets you process the tree level by level; the last node you visit in each level is the visible one.
An alternative is depth-first search that visits right children before left children and records the first node seen at each depth.

Part 2: Count Subarrays With a Given Sum

Given an integer array `nums` and an integer `k`, return the total number of contiguous subarrays whose sum is exactly `k`. A subarray must contain consecutive elements. Because the array can include negative numbers, zero, and positive numbers, you should aim for an algorithm close to O(n).

Constraints

0 <= n <= 10^5
Each element of nums is a 32-bit signed integer
k is a 32-bit signed integer
An O(n) or near-O(n) solution is expected

Examples

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

Expected Output: 2

Explanation: The valid subarrays are [1, 2] and [3].

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

Expected Output: 2

Explanation: The subarrays [1, 1] at indices (0,1) and (1,2) both sum to 2.

Hints

Track a running prefix sum as you scan the array.
If `current_sum - k` has appeared before, then each previous occurrence marks a subarray ending at the current index with sum `k`.

Quick Overview