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 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.

Solve Tree Diameter and Palindromic Counts

Q: Solve Tree Diameter and Palindromic Counts

This two-problem prompt evaluates proficiency in tree algorithms and recursion for computing longest paths in binary trees, along with string processing and palindromic substring enumeration that involve pattern recognition and algorithmic optimization.

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You will be given two independent coding problems. For each problem, explain your approach clearly and analyze both time and space complexity. ### Problem 1: Longest Path in a Binary Tree Given the root of a binary tree, return the length of the longest path between any two nodes in the tree. The path may or may not pass through the root. The length of a path is measured by the number of edges on that path. **Input:** The root node of a binary tree. **Output:** An integer representing the maximum number of edges between any two nodes. **Example:** ```text Input tree: 1 / \ 2 3 / \ 4 5 Output: 3 Explanation: The longest path is 4 -> 2 -> 1 -> 3 or 5 -> 2 -> 1 -> 3. ``` **Constraints:** - The number of nodes is between 0 and 10^4. - Node values are irrelevant to the answer. ### Problem 2: Count Palindromic Substrings Given a string `s`, count how many substrings of `s` are palindromes. A substring is a contiguous sequence of characters. Single-character substrings count as palindromes. **Input:** A string `s`. **Output:** An integer representing the number of palindromic substrings. **Example:** ```text Input: "aaa" Output: 6 Explanation: The palindromic substrings are "a", "a", "a", "aa", "aa", and "aaa". ``` **Constraints:** - `1 <= s.length <= 1000` - `s` consists of lowercase English letters.

Quick Answer: This two-problem prompt evaluates proficiency in tree algorithms and recursion for computing longest paths in binary trees, along with string processing and palindromic substring enumeration that involve pattern recognition and algorithmic optimization.

Part 1: Tree Diameter in a Binary Tree

You are given a binary tree encoded as a list named children. For each node i, children[i] = [left_child, right_child], where each child is either the index of another node or -1 if that child does not exist. If the tree is non-empty, node 0 is the root. Return the length of the longest path between any two nodes in the tree. The path may or may not pass through the root, and its length is measured in number of edges.

Constraints

0 <= number of nodes <= 10^4
If the tree is non-empty, node 0 is the root
Each child entry is either -1 or a valid node index
The input describes a valid binary tree

Examples

Input: [[1, 2], [3, 4], [-1, -1], [-1, -1], [-1, -1]]

Expected Output: 3

Explanation: The longest path is from node 3 to node 2 through node 1 and node 0, or from node 4 to node 2. That path has 3 edges.

Input: []

Expected Output: 0

Explanation: An empty tree has no edges, so its diameter is 0.

Input: [[-1, -1]]

Expected Output: 0

Explanation: A single-node tree has no path between two different nodes, so the diameter is 0.

Input: [[1, -1], [2, -1], [3, -1], [-1, -1]]

Expected Output: 3

Explanation: This is a chain of 4 nodes, so the longest path uses all 3 edges.

Input: [[1, 2], [3, -1], [-1, 4], [-1, -1], [-1, -1]]

Expected Output: 4

Explanation: The longest path is node 3 -> node 1 -> node 0 -> node 2 -> node 4, which contains 4 edges.

Hints

For each node, compute the height of its left and right subtrees.
The longest path through a node is left_height + right_height.

Part 2: Count Palindromic Substrings

Given a string s, count how many of its substrings are palindromes. A substring is a contiguous part of the string. Every single character counts as a palindromic substring.

Constraints

1 <= len(s) <= 1000
s consists only of lowercase English letters

Examples

Input: 'aaa'

Expected Output: 6

Explanation: The palindromic substrings are 'a', 'a', 'a', 'aa', 'aa', and 'aaa'.

Input: 'abc'

Expected Output: 3

Explanation: Only the three single-character substrings are palindromes.

Input: 'a'

Expected Output: 1

Explanation: A single character is always a palindrome.

Input: 'abba'

Expected Output: 6

Explanation: The palindromic substrings are 'a', 'b', 'b', 'a', 'bb', and 'abba'.

Input: 'racecar'

Expected Output: 10

Explanation: There are 7 single characters plus 'cec', 'aceca', and 'racecar'.

Hints

Every palindrome can be expanded from its center.
Remember that palindromes can have either odd length or even length.

Quick Overview

This two-problem prompt evaluates proficiency in tree algorithms and recursion for computing longest paths in binary trees, along with string processing and palindromic substring enumeration that involve pattern recognition and algorithmic optimization.