Solve Tree Diameter and Palindromic Counts
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
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.